Three assorted problems

By Hamoon Ekhtiari on Monday, April 29, 2002 - 10:34 pm:

1. The Seven Dwarfs are having breakfast, and Snow White has just poured them some milk. Before drinking, the dwarfs have a ritual. First, Dwarf #1 splits his milk equally among his brothers' mugs( leaving himself with nothing). Then Dwarf #2 does the same with his milk, etc. The process continues around the table, until Dwarf #7 has distributed his milk in this way. At the end, each dwarf has exactly the same amount of milk as he started with! If the total amount of milk was 42 ounces, how much milk did each dwarf have at the beginning? Is this the only possible distribution of milk, or does the problem admit multiple solutions? Explain.

2. A computer is programmed in the following way. First it prints out a random digit between 0 and 9 (with equal likelihood for each possible digit). Then it picks between the commands "break" and "continue", again randomly with equal probability. If it picks "continue", the process repeats; if it picks "break"; if it picks "break", the program terminates. What is the probability that the final output is a palindrome? (For example, if the program runs as "0, continue, 1, continue, 3, continue, 3, continue, 1, continue, 0, break", then the output is 013310. It reads the same forward and backward, and is thus a palindrome.)

3. Show that you cannot cover a circular disk with two circular disks of smaller diameter.

By Brad Rodgers on Tuesday, April 30, 2002 - 01:59 am:

These are interesting questions. Before the solutions, I have some hints to help someone who wants to try the problems on their own.

1) try assigning each amount of milk to start with the variable a₁ ,a₂ ,... for the first, second,... dwarf. See what you can deduce.

2) Consider the probability given r digits already

3) think about the amount of circumference needed to be covered

Here are the answers. If you want to try the problems on your own, avert your eyes!

1) 12,10,8,6,4,2,0 oz are the amounts for the first dwarf to pour to the last, respectively (you can check to see that this works fairly easily). I'm pretty sure this will be the only solution, as if you set up a table assuming the starting values to be a₁ ,a₂ ,..., and then go through each step representing the amount of milk in each dwarf's mug in the appropriate column, you'll find that each step is representable by a linear combination of a_n 's. Thus, as the amount in the last step is equal to the amount in the first step, the solution to problem is given by 6 simulteanous equations of six variables in the form

k_1,1 a₁ + k_1,2 a₂ + ... + k_1,6 a₆ = 0
k_2,1 a₁ + k_2,2 a₂ + ... + k_2,6 a₆ = 0
.
.
.
k_6,1 a₁ + k_6,2 a₂ + ... + k_6,6 a₆ = 0

Which is obviously uniquely soluble in terms of one of the a_n 's, say a₁ . And, as we're given the sum of all the a's is equal to 42, we can thus uniquely determine a₁ , and thus all a's.

2) I've never seen a problem like this before, and probability is my Achilles heel, but here is the solution I found.

\frac{1}{2} + \sum_{n = 1}^{\infty} \frac{1}{40^{n}} + \frac{1}{2} \sum_{n = 1}^{\infty} \frac{1}{40^{n}} = \frac{7}{13}

,

The first term accounting for single digit palindromes, the second for even palindromes, and the third for odd palindromes. The 1/2 coefficient is there because there is a 1/2 probability of that extra term being in there (not 10, as my previous post would have it!).

3) First note that such a construction would require at least one circle covering at least than 1/2 of the circumference. Suppose a circle, say circle S (small), covered 1/2 or more of another, larger circle's (circle B (big)) circumference. Then circle S must cover two diametrically opposite points on B. But this requires B to have a smaller diameter than S, which is a contradiction. Therefore a smaller circle can only cover less than 1/2 of a larger circle's circumference, and therefore two smaller circles must cover less than all of the larger circle's circumference. Therefore they cannot cover it all.

Brad