A harder version of a Richard Hess logical hat problem

Question

In the July/August 2021 issue of MIT Technology Review, there was a "logical hat" problem by Richard Hess in the Puzzle Corner. I noticed that it could be generalized. Here is the "next level" version of Hess's puzzle; once you solve it, you should see how to generalize it further. (The description below is self-contained; I recommend that you solve it before clicking on the link to see Hess's original puzzle.)

Alice, Bob, and Chris are honest perfect logicians. A referee places a hat on each of their heads. Each hat has a strictly positive integer (i.e., zero is not allowed) written on it, which the other two logicians can see but which the wearer cannot. One of these numbers is the sum of the other two (so for example, the three numbers could be 3, 7, 4, or another possibility is 6, 6, 12). Everything I've said so far is public knowledge.

Alice announces for all to hear, "I can't deduce the number on my hat."

Bob then announces, "I can't deduce the number on my hat."

Alice announces, "The number on my hat is 20."

What is the number on Chris's hat?

Answer 1

Here's the scene with the passed meta-knowledge translated into English:

• Alice (thinking): I see two numbers. Mine is either the sum or the difference of them. The only way I could tell my number is if the difference is zero.
• Alice: "Bob and Chris have different numbers"
• Bob (thinking): with that extra information I would also know my number if the sum or difference of the two numbers I see were equal to Chris's number.
• Bob: "Alice and Chris have different numbers. Also, Alice's number is not twice Chris's. (And Alice's number is not zero.)"
• Alice: "One of the things Bob said eliminates either the sum or the difference of the two numbers I see as an option for my number, so my number is 20"

Now we can work out the solution:

If the crucial bit of information was the first thing Bob said, then Alice having the same number as Chris was an option, meaning that Bob's number is twice that of Chris. But there are no integers with that property that add up to 20.

So Alice having twice Chris's number was the possibility that got eliminated. Since we know Alice didn't see doubles, this can only occur if Chris's number is the smallest, and Bob's number is 3 times that.

This exhausts all the possibilities, and therefore

Chris had a 5.

For the generalisation, had Alice said, "I don't know" one more time, that would have been equivalent to saying "Bob's number is not the same as Chris's, and neither is it double that. Also, Bob's number is not three times Chris's."

If Bob can now deduce their number which turns out to be suitably indivisible (by 3 and 4 this time), but divisible by 5 (to allow a solution to exist), we can again solve the numbers using the same kind of deduction as before.

Now, if this would go on for yet another round, the deduced number cannot be divisible by 6, because it isn't divisible by 3. Because a person's comments always come with another person's comment in between, a multiple of 5 might still work, but I'll need to double check that when I have the time. (If this works, as I suspect it might, then the number that got deduced in the previous paragraph's setting could also be a multiple of 4 that's not divisible by 5 or 3)

In any case, even if the previous paragraph's trick works, this way of generalising cannot extend forever, since at one point the deduced value has to be divisible by either 8 or 9, both ruled out by it not being divisible by neither 3 nor 4.

Answer 2

The three hats could be:

Alice: 20
Bob: 15
Chris: 5

Before any hints are given

Alice sees 15 and 5, so she is not sure whether it's (20, 15, 5) or (10, 15, 5).

One of those is the true case. Bob's clue disproves the alternative; in order to see how the disproof works, let's inhabit that false world for a moment.

Imagine that the numbers were (10, 15, 5), Bob would see a 10 and 5, so he wouldn't be sure whether its (10, 15, 5) or (10, 5, 5). However, if Alice saw two 5's, she would know that her hat must be 10. Therefore, Alice's clue proves to Bob that he is in the (10, 15, 5) case.
Therefore, if the hats were (10, 15, 5), Bob would be able to deduce his hat.

Because Bob cannot deduce his hat after Alice's clue, Alice can eliminate that possibility and deduce her true hat.

This line of reasoning generalizes for other final results, with the clues translated as...

Alice: Your two hats are not the same.
Bob: Your two hats are not the same and also, Alice's hat is not double Charlie's.
Alice: Bob's hat is triple Charlie's. Since mine is not double Charlie's, it cannot be the difference, therefore it must be the sum.

Answer 3

My attempt at a more detailed proof of uniqueness: First assume that each round players know 1) their number is a strictly positive integer and 2) any conditions imposed by previous rounds and nothing else.

Round one Alice has possibility B+C or |B-C|. These are both non-negative and the first is stircty positive so can only exclude an option if |B-C|=0 => B=C. Since she doesn't make this inference everyone knows B!= C.

Round two Bob has possibility A+C or |A-C|. Again, using the criteria of strict positivity, A+C=0 is impossible by assumption. If |A-C|=0 Bob could exclude this. The fact that he doesn't implies A!=C.

Now, using the criteria from previous round his possible contradictions he could exclude are

A+C=C=> A=0 (impossible) or 2) |A-C|=C => A=2C or A=0. We can conclude from his failure to make a deduction that A!=2C.

Round three: Alice knows that A!=C, A!=2C, and A>0 She also knows A=B+C or A=|B-C| We know she deduces the answer at some point so she must be able to exclude one possibility. Combining these three inequalities with each possibility to try to exclude one, (and knowing B!=C):

i) B+C=0 (impossible by assumption)

ii) |B-C|=0 (already ruled out)

iii) B+C=C => B=0 (impossible)

iv) |B-C|=C; either B=0 or B=2C. The first is impossible. The second implies A=B+C=3C. This would lead to alternative solutions if Alice had simply stated that she had the answer, but since 20 is not divisible by three this cannot be the case.

v) B+C=2C => B=C (already ruled out)

vi) |B-C| = 2C => B=-C (impossible) or B=3C.

The only way Alice can infer a contradiction and exclude an option (while having a number not divisible by three) is if B=3C in which case she rules out |B-C|, since else Bob would have deduced the answer in round two. She thus knows that A=B+C=4C. She can see C and knows 4C is 20, so C=5. B=3C = 15.

Answer 4

Try of generalization:

Let $A, B, C$ denote the numbers of the three hats.

Alice reveals that $B\neq C$. Bob knows that $B=A+C$ or $B=|A-C|$, but he cannot differentiate between the two using only the information $B\neq C$.

Towards a contradiction, assume $A=2C$. Bob knows that either $B=A-C=C$ or $B=A+C=3C$. The information $B\neq C$ would be sufficient to for him to conclude $B=3C$. But in reality Bob could not deduce $B$ from the information $B\neq C$. Thus we must have $A\neq 2C$.

Before her second statement, Alice got two pieces of information: (1) $A\neq C$, and (2) $A\neq 2C$.

Suppose only (1) reveals the true solution. This means that her two scenarios ($A=B+C$ and $A=|B-C|$) could be differentiated by (1). This means that one of the scenarios can only hold under the opposite assumption $A=C$. Following the same line of argument as above, this would be $A=|B-C|$ and thus $B=2C$. However, as we have $A\neq C$, the other scenario ($A=B+C$) must hold, but with $A=20$ this would imply $B=40/3$ and $C=20/3$ which are not whole.

Now suppose (2) reveals the true solution. This again means that one of the scenarios can only hold under the opposite assumption $A=2C$. If that scenario was $A=B+C$ then $B=C$ would follow. But in this case she would have known her number immediately. So the scenario that holds only under the assumption that $A=2C$ must be $A=|B-C|=2C$. This has only one positive solution, which is $B=3C$. In the real scenario where $A\neq 2C$ and thus $A=B+C$ with $A=20$ this gives the solution of $B=15$ and $C=5$.

---

Where I think this is a bit shaky...

Is that I used the knowledge that Alice could deduce somehting from the information present. If I was Alice in this scenario I would not have this information.

But if the line of argument holds, then...

The solution relies on the divisibiliy by $3$ and $4$. If $A$ is divisible by neither, the puzzle would not work (i.e., Alice could never conclude anything from the first two statements). If $A$ is divisible by $4$ but not $3$, then $A=4C$ as here. If $A$ is divisible by $3$ but not $4$, then $A=C$. However, in this case the puzzle is simpler as her first statement is not required. You could also start as Bob's statement and still give Alice enough information to immediately deduce $A$. If the number is divisible by $3$ and $4$ then Alice could again not deduce anything.

---

Edit: Assuming my conclusion is correct, we can continue the puzzle:

Alice announces for all to hear, "I can't deduce the number on my hat."

Bob then announces, "I can't deduce the number on my hat."

Alice then announces, "I still can't deduce the number on my hat."

Bob announces, "The number on my hat is 20."

What is the number on Chris's hat?

When Alice says "I still can't deduce the number on my hat." she signals to everyone that neither $A\neq C$ nor $A\neq 2C$ is sufficient for her to deduce $A$. As we have seen, from $B=3C$ and $A\neq 2C$ Alice could deduce $A$, this means Bob know knows $B\neq 3C$. If this is sufficient for Bob to tell $B=20$, this means there must be a scenario ($B=A+C$ or $B=|A-C|$) that holds only if $B=3C$. If it's the first we would have $A=2C$ which we know is not the case. So $B=3C$ in the $B=|A-C|$ scenario, thus $A=4C$. As we are in the $B=A+C$ scenario, we must have $B=5C$, hence $C=4$ and $A=16$.

As for generalization...

Consider the chain of announcements where Alice says she can't deduce her number, then Bob saying he cant deduce his number and so on. When Alice says "I can't deduce my number" she gives Bob information of type $B\neq kC$. If Bob then says "I still can't deduce my number" he announces that $A\neq (k+1)C$, as the case $A=(k+1)C$ along with the information $B\neq kC$ would imply that $B=|A-C|$ (i.e., Bob could deduce $B$). Analogously, if Alice then said "I still can't deduce my number", it means she announces that $A=(k+2)C$ and so on. In general, the $k$-th statement in the sequence states that $B\neq kC$ for odd $k$ and $A\neq kC$ for even $k$.

If Alice now says as the $m$-th statement "The number on my hat is $A$", this means the most recent information $A\neq (m-1)C$ was sufficient for her to deduce her number. By the same argument as before, $B=mA$ and $A=B+C$, and hence $C=A/(m+1)$. Analogously, if Bob said in the $m$-th statement: "The number on my hat is $B$", we have $C=B/(m+1)$.

The only exception to this

is the case originally poster here, since Bob's first statement states two different pieces of information since it's the first time he announces anything.

The thing I am not sure about is what would happen if Chris also said something...

Answer 5

Following @Tim C's answer, here is a proof of uniqueness:

Define the actual values of the hats as $A$, $B$ and $C$.

Alice has two choices of her hat value: $A$ or $B-C$. Define the latter of these to be $A_I$ (For Alice's Imagined value). Given Alice didn't know her hat, Bob knows that $B\neq C$.

In the hypothetical case that Alice's hat equals $A_I$, Bob has two choices for his hat value: $B$ or $A_I-C$. In order for the puzzle to work (Bob not knowing his hat at this stage), this hypothetical case must cause a contradiction. Therefore, we search for cases where $A_I-C=C$.

For completeness, here is the complement of the previous paragraph: In reality, Alice's hat equals $A$. Bob has two choices for his hat value: $B$ or $A-C$. In order for the puzzle to work, the real case cannot cause a contradiction, so $A-C\neq C$.

This is now a set of three linear equations for three unknowns: $B+C=20$, $A_I=B-C$ and $A_I-C=C$. These equations are linearly independent, so the unique solution is $A_I=10$, $B=15$ and $C=5$.

Answer 6

New result, edited answer!

Preconditions

At first, Alice doesn't know her hat only if

$b\ne c$

Then, Bob doesn't know his hat only if

$2*a\ne c$ and $a\ne c$

Options left for $a$

At this point, there are 2 possibilities for the value of a:

$a \in {b+c,|b-c|} $

Alice can only know her hat number with certainty if one of these two choices violates the conditions set forth above but not the other.

Find where conditions reduce options for $a$

Let's check $2*a\ne c$

$b+c=2c$ when $b=c$, which is negated by the precondition $b\ne c$. This means that for all valid combinations, a=b+c does not violate $2*a\ne c$.

$2*|b-c|=c$ when 2b=3c or c=b=0. This means that when 2b=3c, Alice can conclude that a=b+c

Let's check $a\ne c$

$b+c=c$ when $b=0$, which is negated by the precondition $b>0$. This means that for all valid combinations, a=b+c does not violate $a\ne c$.

$|b-c|=c$ when b=2c or 2b=c or c=b=0. This means that when b=2c or 2b=c , Alice can conclude that a=b+c

The case where $a$ is 20

Since Alice asserts that a=20, and the only covered cases where Alice knows her number require a=b+c:

$20=b+c$

When Alice knows her number:

$b=2*c$

or

$2*b=c$

or

$2*b=3*c$

The only integer solution satisfying these conditions is

a=20 b=12 c=8

A sanity check: the other option for c=8 b=12 is a=4, which violates 2*a!=c.

Phew. Hopefully this is a complete explanation.

Numerical help

I tried to ignore this while working on it, but it really helps to have a computer tell you when you're wrong.

Here's an incomplete list of solutions Alice could have solved for with this method:

a must be 3 for b=1 and c=2
a must be 3 for b=2 and c=1
a must be 6 for b=2 and c=4
a must be 5 for b=3 and c=2
a must be 9 for b=3 and c=6
a must be 6 for b=4 and c=2
a must be 12 for b=4 and c=8
a must be 15 for b=5 and c=10
a must be 9 for b=6 and c=3
a must be 10 for b=6 and c=4
a must be 18 for b=6 and c=12
a must be 21 for b=7 and c=14
a must be 12 for b=8 and c=4
a must be 24 for b=8 and c=16
a must be 15 for b=9 and c=6
a must be 27 for b=9 and c=18
a must be 15 for b=10 and c=5
a must be 30 for b=10 and c=20
a must be 33 for b=11 and c=22
a must be 18 for b=12 and c=6
a must be 20 for b=12 and c=8
a must be 36 for b=12 and c=24
a must be 39 for b=13 and c=26
a must be 21 for b=14 and c=7
a must be 42 for b=14 and c=28
a must be 25 for b=15 and c=10
a must be 45 for b=15 and c=30
a must be 24 for b=16 and c=8
a must be 48 for b=16 and c=32
a must be 51 for b=17 and c=34
a must be 27 for b=18 and c=9
a must be 30 for b=18 and c=12
a must be 54 for b=18 and c=36
a must be 57 for b=19 and c=38
a must be 30 for b=20 and c=10
a must be 60 for b=20 and c=40
a must be 35 for b=21 and c=14
a must be 63 for b=21 and c=42
a must be 33 for b=22 and c=11
a must be 66 for b=22 and c=44
a must be 69 for b=23 and c=46
a must be 36 for b=24 and c=12
a must be 40 for b=24 and c=16
a must be 72 for b=24 and c=48
a must be 75 for b=25 and c=50
a must be 39 for b=26 and c=13
a must be 78 for b=26 and c=52
a must be 45 for b=27 and c=18
a must be 81 for b=27 and c=54
a must be 42 for b=28 and c=14
a must be 84 for b=28 and c=56
a must be 87 for b=29 and c=58
a must be 45 for b=30 and c=15
a must be 50 for b=30 and c=20
a must be 90 for b=30 and c=60
a must be 93 for b=31 and c=62
a must be 48 for b=32 and c=16
a must be 96 for b=32 and c=64
a must be 55 for b=33 and c=22
a must be 99 for b=33 and c=66
a must be 51 for b=34 and c=17
a must be 102 for b=34 and c=68
a must be 105 for b=35 and c=70
a must be 54 for b=36 and c=18
a must be 60 for b=36 and c=24
a must be 108 for b=36 and c=72
a must be 111 for b=37 and c=74
a must be 57 for b=38 and c=19
a must be 114 for b=38 and c=76
a must be 65 for b=39 and c=26
a must be 117 for b=39 and c=78
a must be 60 for b=40 and c=20
a must be 63 for b=42 and c=21
a must be 70 for b=42 and c=28
a must be 66 for b=44 and c=22
a must be 75 for b=45 and c=30
a must be 69 for b=46 and c=23
a must be 72 for b=48 and c=24
a must be 80 for b=48 and c=32
a must be 75 for b=50 and c=25
a must be 85 for b=51 and c=34
a must be 78 for b=52 and c=26
a must be 81 for b=54 and c=27
a must be 90 for b=54 and c=36
a must be 84 for b=56 and c=28
a must be 95 for b=57 and c=38
a must be 87 for b=58 and c=29
a must be 90 for b=60 and c=30
a must be 100 for b=60 and c=40
a must be 93 for b=62 and c=31
a must be 105 for b=63 and c=42
a must be 96 for b=64 and c=32
a must be 99 for b=66 and c=33
a must be 110 for b=66 and c=44
a must be 102 for b=68 and c=34
a must be 115 for b=69 and c=46
a must be 105 for b=70 and c=35
a must be 108 for b=72 and c=36
a must be 120 for b=72 and c=48
a must be 111 for b=74 and c=37
a must be 125 for b=75 and c=50
a must be 114 for b=76 and c=38
a must be 117 for b=78 and c=39
a must be 130 for b=78 and c=52

Generated with ATO