Arthur and Bert each writes down a positive integer on a piece of paper and then shows it to Charles. Charles then writes two numbers on a blackboard, visible to Arthur and Bert: one of them is the sum of Arthur's and Bert's numbers, and the other is a random number.
After this Charles asks Arthur if he knows Bert's number. If Arthur says he doesn't know, then he asks Bert if he knows Arthur's number. If Bert says he doesn't know, Charles continues with Arthur, then if necessary with Bert and so on... until he gets a positive answer.
When will Charles get a positive answer?
See my earlier posts for my logic.
Let the numbers on the blackboard be X and Y, where X < Y.
Then d = Y - X is greater than 0
A says no on round 1 if he is between 1 and X-1 (inclusive). He has one of X-1 numbers.
B says no on round 1 if he is between (1 + d) and X-1. He has one of X -1 - d numbers.
A says no on round 2 if he is between (1 + d) and (X -1 -d). He has one of X - 1- 2d numbers.
B says no on round 2 if he is between (1 + 2d) and (X - 1-d). He has one of X - 1- 3d. numbers.
...
A says no on round n if he is between (1 + (n-1)d) and (X - 1 -(n-1)d).
B says no on round 2 if he is between (1 + nd) and (X - 1- (n-1)d)
Every no reduces the range of the person who says no by d (compared to the range of the other party who last said no).
Since the range of the person who says no can never be less than 0, the
maximum number of no's is (X-1)/d, rounded up to the next whole
number.
For instance, if X = 13 and Y = 16, then d = 3 and the maximum number of no's is (13-1)/3 = 4.
If X = 14 and Y = 17, then d = 3 and the maximum number of no's is
(14-1)/3 = 4 1/3, which is 5 rounded up. We will only have
5 no's if A = 7. After B's second no, any observer can deduce
that B is between 7 and 10, but A still can't tell which is the random
number, and has to give a third no.
Edited on October 30, 2005, 6:54 pm
General Solution
