Adam, Bob, and Chuck, three perfectly intelligent logicians, are sitting facing each other with a hat on each of their heads so that each can see the others' hats but they cannot see their own. Each hat, they are told, has a (non-zero) positive integer on it, and the number on one hat is the sum of the numbers on the other two hats. The following conversation ensues:

Adam: I do not know the number on my hat.
Bob: I do not know the number on my hat.
Chuck: I do not know the number on my hat.
Adam: I do not know the number on my hat.
Bob: I do not know the number on my hat.
Chuck: I do not know the number on my hat.
Adam: I do not know the number on my hat.
Bob: I do not know the number on my hat.
Chuck: I do not know the number on my hat.
Adam: The number on my hat is 1691.

Adam was correct. What are the numbers on the other two hats?

Since I felt a bit guilty having posted a computer solution before, I thought I should rephrase my proof for all possible solutions a bit more math-like. I'll make a few observations and prove that there are multiple solutions.

With the logicians numbers being a, b, c, I will denote the round in which the game ends by r( a, b, c ). For our convenience, whenever it suits the understanding, I will also mark the winning player with an asterisk, e.g. r( a, b*, c ). Obviously r( a*, b, c ), r( a, b*, c), r( a, b, c*) always have remainders 1, 2, 0 respectively when divided by 3.

For the following bear in mind that every player has exactly two option in each round he plays: His number can be either the sum or the (positive) difference of the other two player's numbers, i.e. if a player sees the numbers x and y, he can only have number x+y or |x-y|.


The following statements are obviously true:

1. r(2n*, n,  n  ) = 1
   r( n, 2n*, n  ) = 2
   r( n,  n, 2n* ) = 3

The following statements need some work:

2. A)
   If
   r( a*,  b,   c )  = k      (i)
   then
   r( a, a+c*,  c )  = k+1    (ii)
   and
   r( a,   b, a+b* ) = k+2    (iii)
   and
   a = b + c                  (iv)

2. B)
   If
   r(    a, b*,  c )  = k      (i)
   then
   r(    a, b, a+b* ) = k+1    (ii)
   and
   r( b+c*, b,   c )  = k+2    (iii)
   and
   b = a + c                   (iv)

2. C)
   If
   r(   a,  b, c* )  = k       (i)
   then
   r( a+c*, b, c )   = k+1     (ii)
   and
   r( a, b+c*, c )   = k+2     (iii)
   and
   c = a + b                   (iv)


We prove 2. by induction over k:

Induction basis:
k=1 is quite obvious: The only case where r(a,b,c)=1 is if a=2b=2c. This makes B) and C) empty statements. The remaining option for A) is r(2n*,n,n)=1 and it is easily verified that indeed r(2n,3n*,n)=2 and r(2n,n,3n)=3.

Induction step:
First show (iv):
If player A can win in round k (as stated by (i)), but a unequal b + c, this must mean player A can rule out option (b+c,b,c) because player B or C would guessed this combination in earlier rounds, i.e. r(b+c,b*,c)=l or r(b+c,b,c*)=l where l<k. But this contradicts our induction assumption (iv). Therefore a=b+c.
Cases B) and C) follow the same line of thought.

Show (ii):
Player B sees the numbers a and c and can therefore consider exactly two options: (a, a+c, c) or (a, a-c, c). But he can rule out the second option because from (i) we know r(a*, a-c, c) = r(a*, b, c)= k, which means player A would have guessed his own number in round k. Therefore player B can guess the combination (a, a+c, c) in round k+1. From this we know r(a, a+c, c) <= k+1.
In order to show  r(a, a+c, c) = k+1, we must prove that no player could have guessed the combination r(a, a+c, c) in an earlier round l where l<=k. These players could not be A or C, because we have just proven iv) for l=k and we know iv) for l<k per induction. This leaves only player B himself, i.e. r(a, a+c*, c) = l. Player B could only win in round l by eliminating the option (a, a-c, c) = (a, b, c) But option (a, b, c) can only be eliminated by knowing that it is a combination that can be guessed in the earlier rounds 1..l-1, in other words if r(a,b,c) < l. This contradicts r(a,b,c) = k in (i).
Cases B) and C) follow the same line of thought.

Show (iii):
Needs a little more thought, but not too much more:
Player C sees the numbers a and b and can therefore consider exactly two options: (a, b, a+b) or (a, b, a-b). But he can rule out the second option because from i) we know r(a*, b, a-b)=r(a*, b, c)=k, which means player A would have guessed his own number two round earlier. Therefore player B can guess the combination (a, b,a+b) in round k+2, i.e. r(a, b, a+b) <= k+2. In order to show  r(a, b,a+b) = k+2, we must prove that no player could have guessed the combination r(a, b, a+b) in an earlier round l where l<=k+1. Consider first the case l<=k. These players could not be A or B, because we have just proven iv) for l=k and know iv) for l<k per induction. This leaves only player C himself, i.e. r(a, b, a+b*) = l. Player C could only win in round l by eliminating the option (a, b, a-b) = (a, b, c) But option (a, b, c) can only be eliminated by knowing that it is a combination that can be guessed in the earlier rounds 1..l-1, in other words if r(a,b,c) < l. This contradicts r(a,b,c) = k in (i).
Now the case l=k+1: This is where we need more thought than for (ii): We must contradict r(a, b*, a+b) = k+1. Too bad we cannot use (iv) because we have proven it so far only for 1,..,k, not k+1. OK, let's assume r(a, b*, a+b) = k+1 then. This means player B can rule out option (a, 2a+b, a+b) because it is a combination that would have been guessed in earlier rounds, i.e. r(a, 2a+b, a+b) = m where m <= k. Which player could have made this guess? Well, since m<=k we can again use (iv) to determine that it could only be player B himself. But how could player B have figured? Only by ruling out (a, (a+b)-a, a+b)=(a,b,a+b). Follows r(a,b,a+b) < m <= k. This contradicts our assumption r(a, b*, a+b) = k+1 and we can also rule out the case l=k+1.
Cases B) and C) follow the same line of thought.


Now the proof that
a = 1691, b = 356  , c = 1335
a = 1691, b = 623  , c = 1068
a = 1691, b = 646  , c = 1045
a = 1691, b = 712  , c = 979
a = 1691, b = 979  , c = 712
a = 1691, b = 1068 , c = 623
a = 1691, b = 1246 , c = 445
are solutions to the problem. I am only doing this for the first solution, which is an alternative to the solution Avin had in mind. The others are left as an exercise...

We must show r(1691,356,1335) = 10.

From 1. follows
r(89, 178*, 89)      = 2

From 2. B) (iii) follows
r(276*, 178, 89)     = 4

From 2. A) (ii) follows
r(276, 356*, 89)     = 5

From 2. B) (ii) follows
r(276, 356, 623*)    = 6

From 2. C) (ii) follows
r(979*, 356, 623)    = 7

From 2. A) (iii) follows
r(979, 356, 1335*)   = 9

From 2. C) (ii) follows
r(1691*, 356, 1335)  = 10


Finally some bold statements (without proof) for the general problem of n logicians, n>=3, where one number is the sum of all other numbers:

1. For any valid combination of numbers the puzzle will always end
2. The winning player will be the one with the highest number
3. The winning strategy for the player is to apply a simple recursion: The player assumes that he has NOT the highest number. From that assumption he derives the only possible combination left, by subtracting from the highest number he sees all the other numbers he sees. Now he puts himself in the shoes of the player with the highest number he can see (the supposedly winning player) and repeats the same line of thought. He does that until he comes to a contradiction (which will happen after sufficiently many rounds, when we arrive at a combination where no number that one can see is larger than the sum of the others one can see and therefore a candidate for the sum of all the others, including your own) after which he knows his number and wins. The players that do not have the highest number follows the same thought, only they will never have the chance to lead their recursion to a contradiction because the highest-number player does that before them.
4. For any invalid combination of numbers (i.e. no number is the sum of the others), the puzzle will also always end, but obviously with a wrong guess
5. For the majority of puzzles a la "Player A figures his number to be X after Y rounds" there will be more than one solution.

Posted by JLo on 2006-08-18 17:52:08