3
$\begingroup$

There are five logicians seated around a table. They are blindfolded and hats are placed on their heads. After removing the blindfolds, they are told a true statement:

Each of you has either one hat or two hats on his head. The total number of hats is 7, 8 or 9.

The actual number is 9, but this is not told to them.

They are then told to answer the question "How many hats are on your head?" in clockwise fashion (starting from any of the 5). If it is possible to logically deduce the number of hats on their own heads, they do so, otherwise reply "I don't know." and wait till the question cycles back to them.

They have no means of knowing the number of hats on their own heads (except logically), but can see every other person. They have no other means of communication, and no tricks involved.

At what number should the one-hatted logician be placed so that:

  • The game is completed?
  • The game goes on forever?

Note

I made a small error while posting the question. Since people have anyway up-voted and answered this one, I've left it as it is and posted the actual question as a second version (click here to view)

$\endgroup$
  • $\begingroup$ I suppose that it's implied by the first part of the question, but each logician is wearing at least one hat, correct? $\endgroup$ – blakeoft Mar 31 '15 at 16:29
  • $\begingroup$ @blakeoft "Each of you has either one hat or two hats on your head." $\endgroup$ – itriedacrab Mar 31 '15 at 17:21
  • $\begingroup$ @itriedacrab Ah yes, thanks for pointing that out. I feel silly. $\endgroup$ – blakeoft Mar 31 '15 at 20:47
  • 1
    $\begingroup$ Wait, this doesn't specify when the game completes. I assumed the game completes only when everyone correctly determines their hat count, but ending the game when anyone determines their own hat count is also a valid interpretation. $\endgroup$ – Brilliand Mar 31 '15 at 21:10
  • $\begingroup$ @Brilliand Yes, the game completes only when everyone figures out their hat count. $\endgroup$ – ghosts_in_the_code Apr 1 '15 at 8:35
5
$\begingroup$

Preamble: The following are all of the possible (unordered) hat combinations that could exist for a total of 7, 8, or 9 hats:
22221: 9 hats
22211: 8 hats
22111: 7 hats

TL;DR

The game only completes when the logician with 1 hat is asked first.

In order for 7 hats to be on the logicians heads, none of the logicians can see three 2-hatted logicians. All of the logicians see at least three 2-hatted logicians, so 7 hats is not possible. This leaves the logicians considering only the 8- and 9-hat scenarios.

Case 12222:

$L_1$ sees 8 hats and can immediately deduce "I have one hat on my head."
From the viewpoint of the other logicians, $L_1$ must have seen zero 1-hatted logicians. Had he seen one, $L_1$ would not have enough information to deduce whether this was an 8-hat or 9-hat scenario.
$\therefore L_{2,3,4,5}$ are all able to deduce that they each wear 2 hats and the game completes.

Case 21222:

$L_1$ sees 7 hats. He cannot determine if he has 1 or 2 hats. The table could be arranged as 11222 or 21222 from the perspective of $L_1$.
It is unknown to the logicians at this point that 7 is not a valid hat count. As such, $L_1$ would also not be able to determine if he saw two 1-hatted logicians.
So at this point, $L_{3,4,5}$ see the table as 21x22, 212x2, 2122x respectively, where x is still unknown.
$L_2$ sees 8 hats and can determine that he has 1 hat.
If $L_2$ saw 1 hat on any of $L_{3,4,5}$, he would be unable to deduce that he is wearing 1 hat. It is at this point that $L_{3,4,5}$ know they are each wearing 2 hats.
If $L_2$ saw 1 hat on $L_1$, he would still be able to make his statement, so $L_1$ is not able to guess and the game does not complete.

Case 22122:

$L_1$ sees 7 hats. He cannot determine if he has 1 or 2 hats. The table could be arranged as 12122 or 22122 from the perspective of $L_1$.
From the perspective of $L_{2,4,5}$, the table could additionally be set up as 2x122, 221x2, 2212x respectively.
$L_2$ having no new information cannot make a decision when seeing only one hat.
$L_3$ of course knows that he's wearing 1 hat because he sees 8.
Again, if $L_3$ saw 1 hat on either of $L_{4,5}$, he would be unable to deduce that he is wearing 1 hat. It is at this point that $L_{4,5}$ know they are each wearing 2 hats.
If $L_3$ saw 1 hat on $L_2$, he would still be able to make his statement because he knows $L_2$ was unable to guess (i.e., he knows $L_2$ did not see 8 hats), so $L_2$ is not able to guess and the game does not complete.

Case 22212:

$L_1$ sees 7 hats. He cannot determine if he has 1 or 2 hats. The table could be arranged as 12122 or 22122 from the perspective of $L_1$.
From the perspective of $L_{2,3,5}$, the table could additionally be set up as 2x212, 22x12, 2221x respectively.
$L_2$ having no new information cannot make a decision when seeing only one hat.
$L_3$ having no new information cannot make a decision when seeing only one hat.
$L_4$ of course knows that he's wearing 1 hat because he sees 8.
Again, if $L_4$ saw 1 hat on any of $L_{1,2,5}$, he would be unable to deduce that he is wearing 1 hat. It is at this point that $L_{1,2,5}$ know they are each wearing 2 hats.
If $L_4$ saw 1 hat on $L_3$, he would still be able to make his statement because he knows $L_3$ was unable to guess (i.e., he knows $L_3$ did not see 8 hats), so $L_3$ is not able to guess and the game does not complete.

Case 22221:

$L_1$ sees 7 hats. He cannot determine if he has 1 or 2 hats. The table could be arranged as 12122 or 22122 from the perspective of $L_1$.
From the perspective of $L_{2,3,5}$, the table could additionally be set up as 2x212, 22x12, 2221x respectively.
$L_2$ having no new information cannot make a decision when seeing only one hat.
$L_3$ having no new information cannot make a decision when seeing only one hat.
$L_4$ having no new information cannot make a decision when seeing only one hat.
$L_5$ of course knows that he's wearing 1 hat because he sees 8.
Again, if $L_5$ saw 1 hat on any of $L_{1,2,3}$, he would be unable to deduce that he is wearing 1 hat. It is at this point that $L_{1,2,3}$ know they are each wearing 2 hats.
If $L_5$ saw 1 hat on $L_4$, he would still be able to make his statement because he knows $L_4$ was unable to guess (i.e., he knows $L_4$ did not see 8 hats), so $L_4$ is not able to guess and the game does not complete.

$\endgroup$
  • $\begingroup$ By my reasoning, the logician who goes first will always be the (only) one who gets stuck, unless he's the one with 1 hat, in which case the game ends. I'm not understanding how you wind up with L2 getting stuck. $\endgroup$ – Brilliand Mar 31 '15 at 19:49
  • $\begingroup$ Did I not explain it well enough? $\endgroup$ – Ian MacDonald Mar 31 '15 at 20:04
  • $\begingroup$ I think you're wrong, actually; in the 21222 case, L1 is stuck, rather than the game ending. I've posted an answer with my own reasoning. $\endgroup$ – Brilliand Mar 31 '15 at 20:10
  • $\begingroup$ I agree. $L_1$ could be wearing 1 hat and that would still provide $L_2$ with sufficient information to confidently say he's wearing 1 hat. When I extend my proof tonight to cover all of the cases properly, I'll update this. $\endgroup$ – Ian MacDonald Mar 31 '15 at 20:17
  • $\begingroup$ I'm perplexed. What information does the logician with one hat require from the other logicians? I propose that the answer is 'none'. Thus the game will always complete. $\endgroup$ – Dancrumb Mar 31 '15 at 21:27
3
$\begingroup$

It doesn't matter

Because:

No matter where he sits, when it's his turn he sees 4 other logicians and each of them has 2 hats, so that makes a total of 8. It's impossible that there are only 7 hats. If there would be 8 hats, then he would have no hats at all which contradicts with the statement that each of them has 1 or 2 hats. So there are 9 hats and $9-8=1$, so he only has 1 hat.
The next logician will see that 1 hat is gone, so there are at most 8 hats left(or 6 or 7). He also sees 6 hats on other's heads, so there are either 7 or 8 hats left. If it would be 7, then he only has 1 hat, but then the first one would not be able to guess that he only has 1 hat, so it's logical to say that there are 8 hats left. $8-6=2$, so second one can be sure about it.
Each following will just repeat the logic until they all win

$\endgroup$
  • $\begingroup$ Not quite true. $\endgroup$ – Ian MacDonald Mar 31 '15 at 16:30
  • $\begingroup$ @IanMacDonald Could you explain where the flaw is? I come to the same conclusion as Novarg. $\endgroup$ – Brian Mar 31 '15 at 20:02
  • $\begingroup$ @Brian The flaw is that if the logician with 1 hat didn't go first, he could have figured out that he had 1 hat even with only a total of 8 hats in play, so his answer doesn't solve the puzzle for everyone unless he goes first. This answer pretends that "I don't know" provides no information. $\endgroup$ – Brilliand Mar 31 '15 at 20:04
  • $\begingroup$ @Brilliand - No, this is correct. How do you justify your statement " if the logician with 1 hat didn't go first, he could have figured out that he had 1 hat even with only a total of 8 hats in play"? $\endgroup$ – mbeckish Mar 31 '15 at 20:35
  • $\begingroup$ @mbeckish If someone says "I don't know", that means they see at least one 1-hat logician among the others. If it's your turn, and the only other person with 1 hat already said "I don't know", then you must be the other person with 1 hat who he saw - so you know you have 1 hat even with only 8 hats in play total. As far as the logicians who said "I don't know" know, that's exactly what happened. $\endgroup$ – Brilliand Mar 31 '15 at 21:04
1
$\begingroup$

I think Ian's answer is correct but am leaving this here for an example of an incorrect logic.

The first person counts the number of hats on the other's heads. If the number is 5 or 8, he knows he is wearing 2 or 1 respectively and says so. If this is the case, it is trivial for the others to know what they are wearing. They subtract the sum they see from the one the first person must have had.

This means the easiest solution that leads to completion is for the logician with one hat to be the first one asked. The others see that everyone else is wearing 2 hats and knew he counted 8 so knew that they are also wearing 2 hats.

If the first person is not the one with 1 hat, he will count 7 hats and his passing will tell the next person that he saw either 6 or 7 hats.

If the second person sees 8 hats, he will know he has the solitary hat. If he sees 7 hats as well, he will not be able to determine how many hats he has on. Like the first person he will pass and the next person will know he saw 6 or 7 hats.

This pattern will repeat until it is the person wearing 1 hat's turn. He will see 8 and know the answer. The issue is that, now, no one else is exactly sure if he determined this by using the fact that the others passed or if he determined it. It does not appear, however, that this will continue indefinitely.

Imagine a case where 3 people are wearing only 1 hat. Anyone wearing 2 hats will see 5 hats, he will then immediately know that he has on 2 hats. If you see exactly two people wearing only 1 hat and a person wearing 2 hats passes, you know that you have on 2 hats.

Imagine a case where 2 people are wearing only 1 hat. The first one with 1 hat will not know how many he is wearing. The second with only 1 hat will know the first one would have answered correctly if the second were wearing 2 hats so can correctly determine he is wearing only 1. This should tell all others except for the one wearing only 1 hat that they have one 2 hats. When the first one with 1 hat finds himself the last one left, he will know he has on 1 hat. If someone wearing 2 hats passes before the second person wearing 1 hat has his turn, this will tell everyone who sees 2 people wearing 1 hat each that they are wearing 2 hats and everyone who only sees 1 person wearing only 1 hat that they are wearing only 1 hat. This is the most likely outcome.

If eventually no solution is found they will eventually realise they all have 2 hats. This means while eventually every pattern will result in a finite solution, the first person being the #1 is easiest.

$\endgroup$
1
$\begingroup$

To guarantee that the game is completed,

Place the logician with one hat at the first position so that he/she's asked first.

The reason:

There are 3 possible configurations that the logicians can have, with no particular ordering: 2 2 1 1 1, 2 2 2 1 1, 2 2 2 2 1. The first logician will see four logicians wearing two hats each, thus eliminating two of the configurations, and also being able to deduce that there's one hat on his/her head. The other logicians will also know that they're wearing two hats as there's no other way that the first logician would have been able to come to that conclusion immediately otherwise with what they were seeing.

To guarantee that the game never ends,

Place the logician with one hat at the very end so he/she's asked last.

The reason:

The other logicians will see 2 2 2 1, meaning they could be in one of two configurations. All four will say they don't know, except for the last guy, because of the same logic stated above. In the second iteration of the loop, the logicians won't be able to differentiate whether he/she (the last logician) was able to come to the conclusion because of their own uncertainty or because of the raw information he/she was able to see. In other words, if this were a configuration with 8 hats, one way to be able to know how many hats you're wearing is through observing that the others aren't able to differentiate whether this is the 8 hat or 9 hat case. Everyone sees 2 2 2 1, and only the last logician could then deduce from their uncertainty that he's wearing only one hat. If they were in a 9 hat configuration, then the other logician with one hat would have declared how many hats were on his/her head before the end of the cycle.

I'll probably try cleaning up my logic later, since it's just a blob of text.

$\endgroup$
  • $\begingroup$ But one would see 2211 in the 8 hat case. That one would deduce "If I had 1, one of the 2 hatted people would see 2111 and know it is the 7 hat case. They didn't do that, so it must be the 8 hat case." This could happen before a round completes. $\endgroup$ – Trenin Mar 31 '15 at 19:12
  • $\begingroup$ Nobody is questioning whether this is even remotely close to the 7 hat case. They're trying to distinguish between the 8 or 9 hat case. Ah, I see the error in my logic though, so it's more complicated than the reasoning I'm presenting. $\endgroup$ – itriedacrab Mar 31 '15 at 20:56
1
$\begingroup$

In all situations, there are at least 2 guys with a double hat, at max 4. Before the game starts, they all agree to answer this way:

  • "Don't know" if the person sees 2 or 3 people with a double hat.
  • "I have a hat" if the person sees 4 people with a double hat.
  • "I have two hats" if the person sees only 1 man with a double hat.

At the end of a cycle, in the following situations, this happens:

  • Hats=7. Two people could determine the number of their hats, the other three deduce this is a 7-hats situation from that. In the 2nd cycle, all can easily determine the number of their hats with a difference.
  • Hats=8. Nobody could determine his hat(s), so they all deduce that this is a 8-hats situation. In the 2nd cycle, all can easily determine the number of their hats with a difference.
  • Hats=9. Only one could determine the number of his hats (1), the other three deduce this is a 9-hats situation from that. In the 2nd cycle, all can easily determine the number of their hats with a difference.

So, at what number does the 1-hat logician to be?

No specific position, as they all can determine their numbers in any situation.

If you want the game to go forever:

Then your logicians are dumb.

$\endgroup$
  • $\begingroup$ Interesting! I like this, but it requires them to answer a specific way even if they know the answer earlier. If the logicians never get to meet before hand to agree on this, then they must only use deductions, which make this answer invalid. Still gave you a +1 though! $\endgroup$ – Trenin Mar 31 '15 at 19:09
  • $\begingroup$ Actually those agreements are pretty obvious, as the logicians would answer the same even if they didn't talk earlier. $\endgroup$ – leoll2 Mar 31 '15 at 19:29
  • $\begingroup$ @leoll2 Those agreements aren't exhaustive, though - a good logician will know his hat count in a few other cases as well. The agreement, then, is to not announce your own hat count on your first turn when the total number of hats is 8, so that everyone can know for sure how many hats there are. $\endgroup$ – Brilliand Mar 31 '15 at 22:13
0
$\begingroup$

The logician with 1 hat must go first for the game to end.

Reasoning:

  • Each logician before the one with 1 hat will answer "I don't know", demonstrating that he sees either 1 or 2 logicians with 1 hat among those who haven't had a turn.
  • When the logician with 1 hat states that he has 1 hat, that demonstrates that he sees no logicians with 1 hat among those who haven't had a turn yet. All logicians who haven't had a turn yet thus know that they have 2 hats. Of the logicians who said "I don't know", at most one of them has 1 hat (to their knowledge).
  • The logician who went first gets his second turn, and again says "I don't know", indicating that he sees no other 1-hat logicians among those still undecided. They all know that they have 2 hats (Exception: if the logician with 1 hat was third, the second logician still doesn't know).
  • The logician who went first is now stuck, unless he was the logician with 1 hat to begin with.

I've worked out the sequence of moves the logicians will make in each possible arrangement, with each possible total number of hats (7, 8, 9).

Legend:

  • 1: "1 hat"
  • 2: "2 hats"
  • ?: "I don't know"
  • -: Passed turn (already said hat count)

These sequences complete:

  • 12222: 12222*
  • 21112: 21112*
  • 21121: 21121*
  • 22111: 22111*
  • 12112: ?21121*
  • 12121: ?21211*
  • 11212: ??21211*
  • 11221: ??22111*
  • 22112: ???12221*
  • 21212: ???12?212*
  • 21221: ????12122*
  • 22121: ????12212*

These sequences do not complete:

  • 11222: ?1222?----
  • 21222: ?1222?----
  • 12122: ??122??---
  • 22122: ??122??---
  • 11122: ??122??---
  • 21122: ??122??---
  • 12212: ???12?22--?----
  • 22212: ???12?22--?----
  • 22211: ?22?1?--11?----
  • 12211: ?22?1?--11?----
  • 12221: ????1?222-?----
  • 22221: ????1?222-?----
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.