# Unseen prisoners figuring out their hats

A warden wants to play a game with his prisoners.
He tells them that they have to tell him the color of their own hats if they want to have dinner.
note: The warden may be mean, but the prison has a good cook; everyone wants dinner.

The rules of the game:

1 The prisoners get blindfolded, and positioned on a line by the warden.

2 Then everyone gets supplied a red, green or yellow hat. The warden makes sure the prisoners cannot see their own hat.
note: He has plenty of those hats, he may give everyone a yellow one if he feels like it.

3 Everyone then may remove the blindfold.

4 Everyone may only look straight ahead during the game.
note: So the prisoners have no idea how the people behind them are organized, they know however how many prisoners are participating.
note: The prisoners can see all the hats/persons before them.

5 Then everyone may give one hint.
The prisoners know the warden may end the game any time, so they don't dare say to much.

The hints they give are (in this order):

Alice says : I see two green hats
Bob says: I see two red hats
Carol says: Bob and Ernest wear the same hat
Dennis says: Ernest does not know the color of his hat
Ernest says: I know the color of my hat

Ernest probably should not have said that, because the warden stops the game.
Now everyone has to state the color of their own hat.

Luckily everyone knows the color of their own hat.

Please tell me how Ernest can say this. Bonus points for a solution
note: Yes, you can know the hat colors, even though you are not told were Alice Bob Carol and their fellow inmates are standing.

"I think it is safe to assume that every statement made by the prisoners is not only true, but is provably true": This indeed what you should assume.
"So the prisoners have no idea how the people behind them are organized"; This is supposed to be strict: You cannot deduce the distance or direction of someone behind you talking by the volume of the sound or something similar.

From the solutions brought in:
"we can conclude that Earnest and Dennis are facing each other"
"therefore Ernest must have been facing away from Dennis."
A minor hint:

Both are wrong in their reasoning: You cannot deduce either conclusion from only the statements of Dennis and Ernest. (I may give counter examples in the future)

solution hint:

Nobody talks about prisoner 6, she is so scary even the other prisoners have not dared to ask her name. You can refer to prisoners by number too, the warden does not like you fraternizing with them anyway.

solution hint:

I am convinced a solution requires 7 prisoners.

hint 1

Seems I made my puzzle too easy, Alaiko just answered his question. I should have said the warden had 5 hats of each color. (bonus: please feel free to solve this harder variant)

Then you still can prove not all prisoners face the same direction. Note that the prisoners can look in opposite directions. The warden placed them "on a line", not "in line" (and blindfolded them since he could not easily start behind all prisoners with his pile of hats during hat distribution.)

Since no one seems to care about unseen prisoners: Some visual clues about what can be proved.

And some more visual clues.

(Sorry, I am a lousy artist)

• Do the prisoners know which hats are distributed among them? – Braegh Sep 24 '20 at 17:07
• No (the hats are distributed while they are blindfolded) – Retudin Sep 24 '20 at 17:15
• Are the prisoners all facing in the same direction? – Braegh Sep 24 '20 at 17:26
• Please tell me. – Retudin Sep 24 '20 at 18:41
• Maybe I'm missing something but if the warden has an sufficient supply of all types of hats, then it is impossible for the last person standing right at the back of the line to figure out his own hat colour. I'm going to ask the same question as Braegh - are all the prisoners facing the same direction? – Alaiko Sep 25 '20 at 7:36

Not sure how to give more hints, and not expecting answers anymore; so my solution:

Step 1: determine the relative position of Dennis and Ernest:

Dennis and Ernest are facing each other

If Dennis is in front of Ernest and facing the same direction:
- E knows everything D knows. This means D's statement is useless. (which contradicts the difference between D's and E's statement).
If Dennis is behind Ernest:
- From E's perspective: There is no other statement in which D's facing matters, and thus nothing preventing D from facing E and thus D knowing everything E knows. This means D's statement is useless. (which contradicts the difference between D's and E's statement).

Step 2: Determine the position of Alice and Bob:

Bob is behind Ernest
- Follows trivially from C's and D's statement
Alice is behind Dennis

If (with Bob) Alice is also before Dennis:
* Dennis is fully aware of all clues (since he sees Bob and Ernest, he also sees Caroles statement is true).
* The clues have no directional or positional effect behind Dennis
Therefor, for each configuration of hats/persons that Ernest could see, he knows exactly which configurations may fit from Ernest's perspective. And thus he cannot give useful information with his statement. His statement tells E only what her already knew, that form Es perspective E can be wearing at least two hat colors.

What does change if Alice is behind Dennis:

Now Dennis can pass information to Ernest, namely that he knows the direction Alice is facing. For that to be possible:

* Alice must be able to face the other way i.e. there must be 3 persons behind Dennis
* Dennis must be able to see 3 green hats, to 'force' Alice to look the other way.
The 3 possible configurations (where 1 of the question marks is Carole):
g g g r r g g
? B> E> <D A> ? ?
B> ? E> <D A> ? ?
B> E> ? <D A> ? ?

Is Ds statement correct?

before Ds statement: From Es perspective, B and E could as well wear yellow hats, so Ds statement is true

Is Es statement correct?

after Ds statement, Ernest (knows he) does not wear red and can reason from Ds perspective:

If D saw no green hats: B and I must wear yellow, and I might know if A looks that way, e.g. when
yr y y g g r r
? B> E> <D ? ? <A

If D saw 1 green hats: B and I must wear yellow, and I might know if A looks that way, e.g. when
g y y y g r r
? B> E> <D ? ? <A
If D saw 2 green hats: B and I must wear green, and I might know if A looks that way, e.g. when
ry g g y y r r
? B> E> <D ? ? <A
Note that Ernest must reason out every posibility which Dennis can see individually, but the reasoning is exactly the same

Thus:

D must see 3 hats (to be sure A looks away from him) and thus I wear green.

So the solution is:

Dennis and Alice wear a red hat, the other 5 a green hat (and since we can deduce that so can all prisoners)

Dennis can pass to Ernest the information that he knows the direction Alice is facing, because he sees 3+ green hats. In the right configuration, Ernest will know he wears one of those hats.

Are there other solutions?

The prisoner statements can be true, but not everyone would know their hat color if there were:
- more persons behind Dennis
- more persons (with yellow hats) between D and E
If there were more persons behind Ernest, it would not be possible for Ernest to deduce his hat color.

So there is the mentioned uncertainty in some positions, but the hat colors are uniquely determined.

• I'd meant to come back to this... kind-of forgot, so sorry about that. Will look through your answer in more detail later to see what logical steps I'd completely failed to spot. – Steve Oct 29 '20 at 16:30

[I'd got a draft partial I forgot to post before a busy weekend - now revised, but I've not figured out all the interactions yet]

It seems particularly relevant that

the direction each prisoner is facing is not stated. Some prisoners can be facing left and others right, which allows all hats to be observed.

Working from the last clue:

Earnest gains additional information from Dennis' comment, combined with what Earnest can see. If Dennis were behind Earnest, facing the same direction, then Dennis would see everything that Earnest does. The only new information that Earnest would gain from this would be which way Dennis was facing, which cannot be combined with any other information to learn Earnest's hat colour. Thus we must conclude that Earnest can see at least one hat which Dennis does not - i.e. Earnest must be facing Dennis.

Earnest cannot see Bob, but Carol can see (or conclude the hat colour of) both Bob and Earnest at the time she speaks. Dennis can see Earnest (in order to know that Earnest cannot see Bob)

Given that

Dennis can see Earnest, and Earnest can see at least one person/hat that Dennis cannot (in order to gain additional information), we can conclude that Earnest and Dennis are facing each other, and can see each other.

In order for EVERYONE to know their hat colour

it is necessary that hats at BOTH ends of the line are observed, which is certainly the case as at least one of Dennis and Earnest sees them.

So far, we seemed to be able to conclude (without loss of generality) that the line looks something like this:

      ?       =       =       ?
...  C> ...  B  ...  E> ... <D  ...
or
      =       =       ?       ?
...  B  ...  E> ... <C  ... <D  ...
or
      =       =       ?       ?
...  B  ...  E> ... <D  ... <C  ...

However,

We don't know for sure that Carol can see both Bob and Earnest as initially assumed. For example, in the following arrangement, Carol knows that Bob is behind her as the only prisoner who she cannot see, and she would know his (and her own) hat colour from the earlier statement(s), and Earnest's hat colour from direct observation:

 G   G   ?       G       ?
B>  C> <A  ...  E> ... <D  ...
or
 G   R       G       ?       ?   (only one other red hat besides Carol's)
B>  C> ...  E> ... <A  ... <D  ...
or
 G   R   G   ?       G       ?   (only one other red hat besides Carol's)
B>  C>  F  <A  ...  E> ... <D  ...

At this point

Alice, Carol and any other prisoners' positions in the line are to be deduced relative to the known relative positions of Bob, Ernest and Dennis, and we also need to determine all hat colours and which way Bob is facing.

Whoever is at the two end positions

Might as well be facing inwards so they can see everyone else... any conclusion they can make without seeing hats they can also make whilst seeing hats too.

It seems likely that

Alice and Bob are also facing opposite directions, each observing one of the ends of the line, but I've not fully convinced myself this is absolutely certain - I had a "partial proof" that was flawed.

I strongly suspect that

multiple prisoners learn their hat colour only at the last moment, as Earnest declares he knows his hat colour, thus disproving the alternative scenario each had in mind.

• I am afraid there is a minor flaw in your logic (see the added minor hint) – Retudin Sep 28 '20 at 22:16
• @Retudin I don't see the flaw... I've added more details of the logical steps I elided. I think I failed to write all possible arrangements consistent with the logic so far though... there are a couple of positions for C that hadn't been ruled out yet. Will add those in a moment. – Steve Sep 29 '20 at 8:43
• I think "which cannot be combined with any other information to learn Earnest's hat colour" was missing earlier. If not, my apologies, since that was the flaw I was hinting at. – Retudin Sep 29 '20 at 13:13
• @Retudin yes it was missing earlier, as the logical steps had seemed "obvious"... but given I initially missed some possibilities by taking the "obvious" path for Carol, it's clear we need to justify in more detail even what seems "obvious", as doing so will potentially reveal other ways that the each condition can be met besides the most obvious one... – Steve Sep 29 '20 at 14:10
• I think that if Ernest can see Dennis, then it is impossible for Dennis' statement to give Ernest any information whatsoever. – user3294068 Sep 29 '20 at 14:33