Two people A and B and an umpire U play the following game. A chooses an arbitrary positive integer m, and B chooses an arbitrary positive integer n. Each gives his integer to U but not to the other player. U then writes two integers on a blackboard, one of which is m + n. U asks A if he knows n. If he does not, then U asks B if he knows m. If he does not, then U asks A if he knows n, and so on. Show that one player will be able to deduce the other's number after a finite number of questions.
Solution
We claim that: at question 2k-1, A knows the answer if T <= S - n/k; and at question 2k, B knows the answer if T ≥ S + n/k. We prove this by induction.
Take question 1. If T ≤ S - n = m, then A argues that if the true total is T, then n ≤ 0, which is impossible. So the true total must be S and A knows the answer.
Now take question 2. If T ≤ S + n, then B argues that if the true total is T, then at question 1, A would have been faced with m' = T - n, n' = n, S' = T and T' = S. Also T ≥ S + n translates to S' ≥ T' + n' or T' ≤ S' - n', so A would have known the answer. But he did not, so the true total must be S and B knows the answer. Thus the result is true for k = 1. Now suppose it is true for k.
So suppose we reach question 2k+1 and T ≤ S - n/(k+1). A argues that if the true total is T, then at the previous question B would have been faced with m' = m, n' = T - m, S' = T, T' = S. Also n = S - m = S - T + (T - m) = T' - S' + n', so T ≤ S - n/(k+1) translates into S' ≤ T' - (T' - S' + n')/(k+1) or (k+1) S' ≤ k T' + S' - n' or T' ≥ S' + n'/k. So (by induction) B would have known the answer. But he did not, so the true total must be S and A knows the answer.
Similarly, suppose we reach question 2k+2 and T ≥ S + n/(k+1). B argues that if the true total is T, then at the previous question B would have been faced with m' = T - n, n' = n, S' = T, T' = S. Also n = n' = S' - m', so T ≥ S + n/(k+1) translates into S' ≥ T' + n'/(k+1) or T' <= S' - n'/(k+1). So (by induction) A would have known the answer. But he did not, so the true total must be S and B knows the answer. Thus the result is true for k+1 and hence for all k.
Now if T = S, then A knows the answer on the first question. If T < S, then we must have T <= S - n/k for some positive integer k, and so A will know the answer after a finite number of questions. Similarly, if T > S, then we must have T ≥ S + n/k for some positive integer k, and so B will know the answer after a finite number of questions.
© John Scholes
jscholes@kalva.demon.co.uk
21 Dec 2002