Problem: (2002 Putnam – B4) An integer , unknown to you, has been randomly chosen in the interval with uniform probability. Your objective is to select in an odd number of guesses. After each incorrect guess, you are informed whether 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 .
Solution: We first prove that, in the interval , we can guess with a strategy that allows us to get the desired number in an even number of guesses with probability. This is easy by induction.
Base case: . Pick . If , it’s an odd number, but if , we can get it in the subsequent guess. So there is a chance.
Induction step: Suppose it’s true for the interval . We want to show it is true for the interval . Start by choosing . If , it’s an odd number of guesses, but if , it’s even. Then guess (if we find that ) on the second guess. So if , we can get it in an even number of guess. If we find that , it's just choosing from the interval in an even number of guesses, so by the inductive hypothesis this is . Hence the probabability in the interval is
completing the induction.
So now we have the interval . Choose . If , we're done in an odd number of guesses. Otherwise, we want to guess which is in in an even number of guesses. By the lemma above, the probability of this is .
Therefore, the total probability is , 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 based on optimizing the best strategies for with 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 be an integer and be the number of non-empty subsets of with the property that the average of the elements of is an integer. Prove that is always even.
Leave a Reply
You must be logged in to post a comment.