Thursday, January 11, 2007

Guess What? Topic: Probability/Sets. Level: AIME/Olympiad.

Problem: (2002 Putnam - B4) An integer $ n $, unknown to you, has been randomly chosen in the interval $ [1, 2002] $ with uniform probability. Your objective is to select $ n $ in an odd number of guesses. After each incorrect guess, you are informed whether $ n $ is higher or lower, and you must guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than $ 2/3 $.

Solution: We first prove that, in the interval $ [1, 3k] $, we can guess with a strategy that allows us to get the desired number in an even number of guesses with $ \frac{2}{3} $ probability. This is easy by induction.

Base case: $ [1,3] $. Pick $ 2 $. If $ n = 2 $, it's an odd number, but if $ n \neq 2 $, we can get it in the subsequent guess. So there is a $ \frac{2}{3} $ chance.

Induction step: Suppose it's true for the interval $ [1,3k] $. We want to show it is true for the interval $ [1,3k+3] $. Start by choosing $ 3k+2 $. If $ n = 3k+2 $, it's an odd number of guesses, but if $ n = 3k+3 $, it's even. Then guess $ 3k+1 $ (if we find that $ n < 3k+2 $) on the second guess. So if $ n = 3k+1, 3k+3 $, we can get it in an even number of guess. If we find that $ n < 3k+1 $, it's just choosing from the interval $ [1,3k] $ in an even number of guesses, so by the inductive hypothesis this is $ \frac{2}{3} $. Hence the probabability in the interval $ [1, 3k+3] $ is

$ P(n=3k+3)+P(n=3k+1)+P(n<3k+1) \cdot P(\text{even # of guesses}) = \frac{1}{3k+3}+\frac{1}{3k+3}+\frac{3k}{3k+3} \cdot \frac{2}{3} = \frac{2}{3} $

completing the induction.

So now we have the interval $ [1, 2002] $. Choose $ 2002 $. If $ n = 2002 $, we're done in an odd number of guesses. Otherwise, we want to guess $ n $ which is in $ [1,2001] = [1,3 \cdot 667] $ in an even number of guesses. By the lemma above, the probability of this is $ \frac{2}{3} $.

Therefore, the total probability is $ P(n = 2002)+P(n<2002) \cdot P(\text{even # of guesses}) = \frac{1}{2002}+\frac{2001}{2002} \cdot \frac{2}{3} = \frac{1335}{2002} > \frac{2}{3} $, as desired. QED.


Comment: This was a pretty neat problem. The way I figured out the solution was by an interesting recursion that find the best strategy for $ [1,m] $ based on optimizing the best strategies for $ [1,k] $ with $ k < m $ in trying to get an even and odd number of guesses. The pattern revealed the first lemma, which lead directly to the solution. It seems like some of the later problems on the test were a little easier than the earlier problems.


Practice Problem: (2002 Putnam - A3) Let $ n \ge 2 $ be an integer and $ T_n $ be the number of non-empty subsets $ S $ of $ \{1, 2, \ldots, n\} $ with the property that the average of the elements of $ S $ is an integer. Prove that $ T_n-n $ is always even.


  1. Clearly the subsets {1}, {2}, {3} ... {n} have this property. T_n - n then counts the subsets with more than one element with the property that the average of the elements of S is an integer.

    Given any such set {a, b, c, ...}, the set {n-a, n-b, n-c, ...} also has this property. This is a one-to-one correspondence EXCEPT when a set has the property that for every a in it, n-a is also in it.

    Counting these sets is easy; there are 2^{ floor(n/2)} of them, which is even for n \ge 2.

  2. Whoops, that last part doesn't work. Okay.

    For odd n, any such set has an even number of members (say, 2k) and its members sum up to nk, so the average can never be an integer.

    For even n, any set that doesn't contain n/2 falls prey to the same problem as above. A set that does contain n/2 has an odd number of members (say, 2k+1) which sum up to n(k + 1/2) = n/2(2k+1), so all such sets average to an integer. (By my previous counting argument, there are an even number of such sets.)

  3. YAY!!!
    totally understood that
    don't understand the comments above mine, but thats ok