Putnam 2002, Problem B-4

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:
Use the following strategy: guess \( 1, 3, 4, 6, 7, 9, \ldots \) until the target number \( n \) is revealed to be equal to or lower than one of these guesses. If \( n \equiv 1 \pmod{3} \), it will be guessed on an odd turn. If \( n \equiv 0 \pmod{3} \), it will be guessed on an even turn. If \( n \equiv 2 \pmod{3} \), then \( n + 1 \) will be guessed on an even turn, forcing a guess of \( n \) on the next turn. Thus the probability of success with this strategy is \( 1335/2002 > 2/3 \).  

Note: for any positive integer \( m \), this strategy wins when the number is being guessed from \( [1, m] \) with probability \( \frac{1}{m} \left\lfloor \frac{2m + 1}{3} \right\rfloor \). We can prove that this is best possible as follows. Let \( a_m \) denote \( m \) times the probability of winning when playing optimally. Also, let \( b_m \) denote \( m \) times the corresponding probability of winning if the objective is to select the number in an even number of guesses instead. (For definiteness, extend the definitions to incorporate \( a_0 = 0 \) and \( b_0 = 0 \).)  

We first claim that \( a_m = 1 + \max_{1 \leq k \leq m} \{ b_{k-1} + b_{m - k} \} \) and \( b_m = \max_{1 \leq k \leq m} \{ a_{k-1} + a_{m - k} \} \) for \( m \geq 1 \). To establish the first recursive identity, suppose that our first guess is some integer \( k \). We automatically win if \( n = k \), with probability \( 1/m \). If \( n < k \), with probability \( (k - 1)/m \), then we wish to guess an integer in \( [1, k - 1] \) in an even number of guesses; the probability of success when playing optimally is \( b_{k-1}/(k - 1) \), by assumption. Similarly, if \( n > k \), with probability \( (m - k)/m \), then the subsequent probability of winning is \( b_{m - k}/(m - k) \). In sum, the overall probability of winning if \( k \) is our first guess is \( (1 + b_{k-1} + b_{m - k})/m \). For optimal strategy, we choose \( k \) such that this quantity is maximized. (Note that this argument still holds if \( k = 1 \) or \( k = m \), by our definitions of \( a_0 \) and \( b_0 \).) The first recursion follows, and the second recursion is established similarly.  

We now prove by induction that \( a_m = \lfloor (2m + 1)/3 \rfloor \) and \( b_m = \lfloor 2m/3 \rfloor \) for \( m \geq 0 \). The inductive step relies on the inequality \( \lfloor x \rfloor + \lfloor y \rfloor \leq \lfloor x + y \rfloor \), with equality when one of \( x, y \) is an integer. Now suppose that \( a_i = \lfloor (2i + 1)/3 \rfloor \) and \( b_i = \lfloor 2i/3 \rfloor \) for \( i < m \). Then  
\[ 1 + b_{k-1} + b_{m - k} = 1 + \left\lfloor \frac{2(k - 1)}{3} \right\rfloor + \left\lfloor \frac{2(m - k)}{3} \right\rfloor \]  
\[ \leq \left\lfloor \frac{2m}{3} \right\rfloor \]  
and similarly \( a_{k-1} + a_{m - k} \leq \lfloor (2m + 1)/3 \rfloor \), with equality in both cases attained, e.g., when \( k = 1 \). The inductive formula for \( a_m \) and \( b_m \) follows.