Solutions: sum freedom
I have revised this problem to make the answer unique. Apologies to all who already ‘dug in.’ -jd
This is the space for answers to the “sum freedom” puzzle. For questions, clarifications, comments, post back at the puzzle.
Three perfectly logical prisoners are seated facing each other, with hats on their heads. Each hat has a counting number {1, 2, 3, 4, …} on it, and each prisoner can see the hat of the other two prisoners, but not his own.
The warden says, “I will set free the man who can tell me his own number, but execute any man guessing incorrectly.“
They look back at him in stunned silence.
“OK, a hint. One of your numbers is the sum of the two. Alan?”
— “I don’t know my number.”
“Bert?”
— “I don’t know my number.”
“Graham?”
— “I don’t know my number.”
“Alan?”
— “I still don’t know my number.”
“Bert?”
— “My number is 78 26.″
And he went free. What were Alan and Graham’s numbers? (And how did you discover this?)
JD2718 
The third prisoner looks up and sees that the other two prisoners both have the number 39. Clearly neither of the other two numbers can be a sum of his and the third, since 0 has been excluded from the set of numbers, so he know that his number must be the sum of the two 39s he sees. Each of the other prisoners saw two numbers (78 and 39) and had two guesses: either their number was 39 or 117.
In the problem the third prisoner (Graham) doesn’t know.
I think, that as long as two of the numbers are allowed to be the same, the answer is that Alan has 26, Bert has 78 and Graham has 52. (Even though none of the numbers are the same, it turns out that that possibility has to be out there, or Bert would have known the answer on his first turn.)
On his first turn, Bert sees the numbers 26 and 52. He knows that either his number is 26, or 78.
Then Graham announces that he doesn’t know his number. From this Bert can concluded that Bert does not have the number 26, for if he did, Graham would have known immediately that his number could only be 52, since it cannot be zero.
So then when Bert gets his next turn, he can confidently announce that his number is 78.
How I discovered it… First I thought about how in most cases, each prisoner will have two possible numbers that they could have, either the sum or (positive) difference of the two numbers they see. So then I began to think about what are the special cases, where this isn’t so. And I realized that this happens in the the case where the prisoner sees two numbers that are the same — he then knows that his number must be the sum of the two, since the difference is zero, which is not permitted. Then I basically used experience with this type of problem to go to the next level, where I wanted to set it up so that Bert would have two choices (and thus not know in his first turn) but be able to rule out one of his choices based on the fact that no one else knew on the first round either. So… the only way that happens is if one of Bert’s possible numbers is identical to one of the others he sees, which means he must see one number which is twice the other. So, if he sees n and 2n, he knows that he either has n or 3n. If he has n, the prisoner with 2n will be able to determine that immediately. So if the prisoner with 2n says he doesn’t know his number, that must mean that Bert has 3n.
Finally, I knew that it must be Alan with 26 and Graham with 52 because Bert has to wait until after Graham speaks to be sure. If it were Alan with 52, Bert would have been able to answer on his first turn, as soon as Alan said he didn’t know.
Now, does the Warden let the other two have another guess? Because if so they should both be able to use the same reasoning I did to come up with their own answers.
I also think you should specify that the prisoners are risk-averse, that is they would not take a guess and risk death unless they are certain of their guess. I think that otherwise, it might be perfectly “logical” to take a guess with a 50% chance of freedom versus a 50% chance of death.
For Bert especially, even though he knows he will be able to solve it for sure by his second turn, he also knows that he may not get a second turn. So if only one man is allowed to “win” and go free, it might be “sensible” for him to take the risk and guess on his first turn.
The warden says, “I will set free the man who can tell me his own number, but execute any man guessing incorrectly.“
I need to review your answer closely. There may be a gap allowing two correct sets of analysis, which I did not intend.
hmm, well in that case, I’ll also see if I can come up with your other solution….
Your solution looks good.
This is the second time I’ve flubbed this problem (it was intended to be far trickier). I’ll be back in a week with an extension!
Note: I’ve altered Bert’s number (26) to make the solution (I hope this time) unique.
I was thinking it was odd that my answer only relied on Graham not knowing once, and not on Alan not knowing twice. I’m guess I’ll need all that to solve it this time….
Interesting problem. Here’s my solution. Let’s call the players A, B, C, and their numbers a, b, c (we’ll give Graham a middle name of Charlie).
(1) A knows that a=b+c or a=|b-c|, but doesn’t know which one. What would give it away? If b=c. A doesn’t know, so we can’t have that.
(2) B knows that b=a+c or b=|a-c|. What would give it away? If a=c, or if either a+c or |a-c| were equal to c (since we know that can’t happen from (1), B would only be left with one option). Since we are only dealing with positive integers, a+c=c or |a-c|=c yield only a=2c as a valid solution. So we can’t have that. (Everyone now knows that none of these can be true: b=c, a=c, a=2c.)
(3) C knows that c=a+b or c=|a-b|. What would give it away? He also knows that c cannot be equal to b, a, or a/2. So if we had a=b, or if if a+b or |a-b| fell into the disallowed set {b,a,a/2}, he’d have only one option left. Since he doesn’t know the answer yet, we can’t have that. In other words, we can’t have either a+b or |a-b| in the disallowed set {b,a,a/2}. I.e. we can’t have a=2b, or b=2a, or b=3a/2.
(4) A’s turn again. He still knows a=b+c or a=|b-c|. He also knows what relationships can’t be, in particular, a can’t be equal to any of {c, 2c, b, 2b, b/2, 2b/3}. He still doesn’t know the answer though so it must be that neither b+c nor |b-c| are equal to anything in this disallowed set {c, 2c, b, 2b, b/2, 2b/3}. This is getting complicated, but if you work out all the inequalities, you’ll get (so I hope) that we cannot have b=2c, b=3c, b=c/2, b=c/3, b=3c/5, b=2c/3. And everybody knows none of these can be true, or A would’ve been able to exclude one of the two options and answer correctly.
(5) Lastly B’s turn again. He knows that b=a+c or b=|a-c|. Moreover, he is finally able to exclude one of the options. So it must be that either a+c or |a-c| don’t make a valid value for b, because they equal one of the disallowed values. The disallowed set for b at this point is {a, c, 2c, 3c, c/2, c/3, 3c/5, 2c/3, a/2, 2a, 3a/2}. If a+c were in this set, then that’s only possible if a=c or a=2c; but this would’ve given away the answer to B last time (these values were already disallowed then). So it must be that |a-c| is in the set. Again by working through the possibilities, we find that this means that a is in the set {c/2, 3c/2, 2c/3, 4c/3, 2c/5, 8c/5, 3c, c/3, 5c/3}. So B can exclude |a-c|, and be left with b=a+c, which, he says, is 26.
Now we are almost home. If a is in the set just listed, then 26=a+c is in the set {3c/2, 5c/2, 5c/3, 7c/3, 7c/5, 13c/5, 4c, 4c/3, 8c/3}. But c is a whole number, and all these fractions are irreducible. So the numerator of the fraction has to divide 26. There is only one such fraction: 26=13c/5. So c=10, and so a=b-c=16.
I’d be happy to hear a simpler solution. This is admittedly pretty involved. And I can only hope it’s right :)
jd2718, cheers from New York Math Circle! (Jack told me about your website.)
There is an alternate analysis, but not simpler.
Now, is that the strangest context you’ve seen those ratios pop up?