1. [55] Tom, Dick, and Harry play a game in which they each pick an integer between 1 and 2011. Tom picks a number first and informs Dick and Harry of his choice. Then Dick picks a different number and informs Harry of his choice. Finally, Harry picks a number different from both Tom's and Dick's. After all the picks are complete, an integer is randomly selected between 1 and 2011. The player whose number is closest wins 2 dollars, unless there is a tie, in which case each of the tied players wins 1 dollar. If Tom knows that Dick and Harry will each play optimally and select randomly among equally optimal choices, there are two numbers Tom can pick to maximize his expected profit; what are they?
Answer: 503,1509 Let $x$ denote the number Tom chooses. By the symmetry of the problem, picking $x$ and picking $2012-x$ yield the same expected profit. If Tom picks 1006, Dick sees that if he picks 1007, Harry's best play is to pick 1005 , and Dick will win with probability $\frac{1005}{2011}$, and clearly this is the best outcome he can achieve. So Dick will pick 1007 (or 1005) and Harry will pick 1005 (or 1007), and Tom will win with probability $\frac{1}{2011}$. Picking the number 2 will make the probability of winning at least $\frac{2}{2011}$ since Dick and Harry would both be foolish to pick 1, so picking 1006 is suboptimal. It is now clear that the answer to the problem is some pair $(x, 2012-x)$.
By the symmetry of the problem we can assume without loss of generality that $1 \leq x \leq 1005$. We will show that of these choices, $x=503$ maximizes Tom's expected profit. The trick is to examine the relationship between Tom's choice and Dick's choice. We claim that (a) if $x>503$, Dick's choice is $2013-x$ and (b) if $x503,2013-x$ is the smallest value of $y$ for which Harry always chooses a number less than $x$. This is obvious, for if $y\frac{2012-x-x}{2}=1006-x$ holds for all integers $x$ greater than 503, so, by symmetry, Harry chooses a number less than $x$ exactly half the time. The desired result actually follows immediately because the fact that Harry always chooses a number less than $x$ when $y=2013-x$ implies that there would be no point in Dick choosing a number greater than $2013-x$, so it suffices to compare Dick's expected profit when $y=2013-x$ with that of all smaller values of $y$, which is trivial.
Proof (b). This case is somewhat more difficult. First, it should be obvious that if $x2011-x$ and $y2009$, contradiction. We next claim that if $y \geq 1342+\left\lfloor\frac{x+1}{3}\right\rfloor$, then Harry chooses a number between $x$ and $y$. The proof follows from the inequality $\frac{1342+\left\lfloor\frac{x+1}{3}\right\rfloor-x}{2}>2011-\left(1342+\left\lfloor\frac{x+1}{3}\right\rfloor\right)$, which is equivalent to $3\left\lfloor\frac{x+1}{3}\right\rfloor>x-4$, which is obviously true. We also claim that if $y \leq 1340+\left\lfloor\frac{x+1}{3}\right\rfloor$ then Harry chooses a number greater than $y$. The proof follows from the inequality $\frac{1340+\left\lfloor\frac{x+1}{3}\right\rfloor-x}{2}x-1$, so, in fact, if $y=1341+\left\lfloor\frac{x+1}{3}\right\rfloor$, Harry still chooses a number between $x$ and $y$. In this case it is clear that such a choice of $y$ maximizes Dick's expected profit. It turns out that the same holds true even if $x \equiv 1(\bmod 3)$; the computations are only slightly more involved. We omit them here because they bear tangential relation to the main proof.
We may conclude that if $x>503$, the optimal choice for $x$ is 504 , and if $x<503$, the optimal choice for $x$ is 502. In the first case, $y=1509$, and, in the second case, $y=1508$. Since a choice of $x=503$ and $y=1509$ clearly outperforms both of these combinations when evaluated based on Tom's expected
profit, it suffices now to show that if Tom chooses 503, Dick chooses 1509. Since the computations are routine and almost identical to those shown above, the proof is left as an exercise to the reader.
Remark: For the more determined, intuition alone is sufficient to see the answer. Assuming Tom's number $x$ is less than 1006 , Dick will never pick a number $y$ that makes Harry's best move $y+1$, so Harry's best move will either be $x-1$ or anything in between $x$ and $y$. Clearly Tom does not want Harry to pick $x-1$, and the biggest number he can pick so that Harry will have to pick in between him and Dick is $\frac{1}{4}$ th of the way along the set of numbers, which in this case is 503 . In a rigorous solution, however, the calculations must be handled with grave care.
An interesting inquiry is, what is the optimal strategy with $n$ players?