Discrete Mathematics 21-228: Summer II 2000
Extra Credit
Due Thursday, 8/10 by 1:00pm

You may discuss the problems in groups of at most 3 people, but each person must write her own homework. Please list the members of your group. You may not use any sources other than the notes and texts listed on the course page.

1.

Show that $S(n,k)$, the number of ways of partitioning a set of size $n$ into $k$ nonempty unlabeled parts is equal to

$$\frac{1}{k!}\sum_{i=0}^k {k \choose i}(-1)^i(k-i)^n.$$

$S(n,k)$ is sometimes called the Stirling number of the second kind.

[Hint: Look at the derivation for our non-recursive derangement formula]

2.

Let $\chi$, the chormatic number of the plane, be the minimum number of colors require to ensure no two points 1 unit apart in the plane get the same color. We showed in class that $\chi \geq 3$ since one cannot 2-color the vertices of a unit length equilateral triangle. Show that

$$4 \leq \chi \leq 7,$$

that is one cannot 3-color the plane, and that 7 colors are enough.

[Hint: One can show 9 colors suffice by tiling the plane with 9 squares of distinct colors arranged to form one large square, where each smaller square has diagonal length slightly less than 1 (one must also be careful in coloring the border of each sqaure).]

3.

In Massada, in ancient Greece, it was decided that there were too many prisoners and that many should be executed. One prisoner was given a sword and all 1000 prisoners were instructed to stand in a circle. The one with the sword was instructed to kill the man on his left and then pass the sword to the next man on the left, who would then do the same. The circle would continue to get smaller as this continued, and the last man left would be set free. Josephus, one of the prisoners, placed himself at the correct position in the lineup to be the one remaining man at the end of this elimination. At what position did he place himself on the circle? If the last two will be set free, where should Josephus direct his friend to stand?

[Hint: Try it for smaller numbers of prisoners first.]

4.

You're given $n$ processors, each of which is either good or bad. Your task is to find just one measly good processor. To aid you in your endeavor you may use any of the $n$ processors to test exactly one other processor. A good processor will correctly report the state of the processor it's testing. A bad processor will tell you whatever it must in order to deceive you. In fact it may not even give you the same answer if you use it to test a processor twice. You cannot use a processor to test itself. Devise a way to find one good processor using no more than $c\cdot n$ tests for some constant $c$.