# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

Guess What? Topic: Probability/Sets. Level: AIME/Olympiad. January 11th, 2007

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.

### 3 Responses to “Guess What? Topic: Probability/Sets. Level: AIME/Olympiad.”

1. t0rajir0u Says:

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. t0rajir0u Says:

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. Katia Says:

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