Red, Yellow, and Green Hats
A new hat puzzle from Gribalko, reminding me of traffic lights.
Puzzle. You and six of your mathematician friends each have a hat placed on your head. Each of you can see the hats of all the others but cannot see your own. You were all told that there were three red, three yellow, and three green hats in total, but two of them were hidden. Your friends began to say the following phrases in sequence:
- First: “I don’t know what color my hat is.”
- Second: “I also don’t know what color my hat is.”
- Third: “I also don’t know what color my hat is.”
- Fourth: “I know that my hat is red.”
- Fifth: “But I still don’t know what color my hat is.”
- Sixth: “And I am sure that my hat is yellow.”
Can you determine what color hat you have on your head?
Share:
Sanandan Swaminathan:
It looks like the 7th mathematician has a green hat based on lengthy case work. Let the mathematicians be numbered M1 through M7 in sequence. Let R = red, Y = yellow, G = green, X = wildcard color. M4 has a red hat, and M6 has a yellow hat.
If neither M5 nor M7 has a green hat, the 7-hat pattern is XXXRRYR, XXXRRYY, XXXRYYR or XXXRYYY. In this scenario, we see that both M2 and M3 must have green hats. If M3 did not have green…
XXYRRYR: M2 would have been able to deduce that he does not have yellow (otherwise M1 would have determined his color). M2 would have determined his color as green which he did not.
XXRRRYY or XXYRRYY: Again, M2 would have been able to determine his color.
XXRRYYR or XXYRYYR: Again, M2 would have been able to determine his color.
XXRRYYY: Again, M2 would have been able to determine his color.
If M2 did not have green…
XYXRRYR: M3 would have been able to deduce that he does not have yellow (otherwise M2 would have determined his color based on M1 not determining his).
XRXRRYY or XYXRRYY, XRXRYYR or XYXRYYR, XRXRYYY: Again, M3 would have been able to deduce.
Thus, the pattern would have been XGGRRYR, XGGRRYY, XGGRYYR or XGGRYYY. If M1 had red or yellow in any of these cases, M3 would have been able to deduce his color based on M2 not deducing his. Thus, the patterns must be:
GGGRRYR: Based on M2’s response, M3 would have deduced that he does not have yellow, and hence has green.
GGGRRYY or GGGRYYR: Based on M2’s response, M3 would have deduced that he does not have red or yellow, and hence has green.
GGGRYYY: Based on M2’s response, M3 would have deduced that he does not have red, and hence has green.
Thus, at least one of M5 and M7 has a green hat. Assume that M5 has a green hat but M7 has a red hat. The hat pattern would be XXXRGYR. At least one of the X’s must be green, otherwise M5 would have deduced his color. We can consider the various cases:
GRYRGYR, GYRRGYR, RGYRGYR, RYGRGYR, YGRRGYR, YRGRGYR: From M4’s perspective, M1, M2, and M3 wouldn’t have been able to deduce their colors regardless of whether M4 was wearing G, R or Y.
GGRRGYR: Based on M2 not deducing his color, M5 would know that he does not have yellow. Hence M5 have deduced his color as green.
GRGRGYR or RGGRGYR: M5 would know that he does not have yellow, and has green, otherwise M3 would have deduced his color.
GGYRGYR: If M5 had red or yellow, M2 would have deduced that he has green (otherwise M1 would have determined his color). Thus M5 would determine his color as green.
GYGRGYR: If M5 had red or yellow, M3 would have deduced that he has green (otherwise M2 would have determined his color based on M1 not determining his). Thus M5 would determine his color as green.
YGGRGYR: If M5 had red or yellow, M3 would have deduced that he has green (otherwise M2 would have determined his color based on M1 not determining his). Thus M5 would determine his color as green.
Now assume that M5 has a green hat but M7 has a yellow hat. The hat pattern would be XXXRGYY. At least one of the X’s must be green, otherwise M5 would have deduced his color. We can analyze the various cases exactly as the previous situation where we assumed that M5 has a green hat and M7 has a yellow hat.
We can conclude that M7 did not have a red or yellow hat, hence must have been wearing a green hat. An example where the six statements could have been uttered in sequence with M7 wearing a green hat is YYGRGYG.
20 November 2024, 12:52 pmIvan:
I do not think things are that complicated.
1. We start with the observation that the two hidden hats are red (otherwise Player4 wouldn’t know his hat is red).
20 November 2024, 1:30 pm2. The hats of the first three players are not all green (otherwise Player5 would know his hat is yellow).
3. If there were two yellow hats among the first three, then Player5 would know his hat is green (but he does not, therefore two of the first three hats are green and the other one is yellow).
4. If the hat of Player 5 was yellow, then the Player6 wouldn’t be sure his hat is yellow (but he is, therefore the hat of Player5 is green).
5. The above leads us to conclude that the hat of Player7 is yellow.
Sanandan Swaminathan:
Ivan, if there are two greens and one yellow among the first three, 4th hat is red, 5th hat is green, 6th hat is yellow, and 7th hat is yellow, then the hat distribution is GGYRGYY or GYGRGYY or YGGRGYY. We can see that none of those patterns can cause the given conversation.
If GGYRGYY: When it is the 5th person’s turn to speak, he can determine that he has a red or green hat (since he sees all 3 yellow hats). If he assumes that he has a red hat, then the hat pattern would be GGYRRYY. If so, the 2nd person would have figured that he is not wearing red (otherwise, the 1st person would have seen RYRRYY and announced that he has green, which he did not). Since the 2nd person sees 3 yellow hats, and knows that he is not wearing red, he would have announced that he is wearing green, which he did not. Hence the 5th person would conclude that he couldn’t be wearing red, and since he sees 3 yellows, he would have announced that he is wearing green, which he did not. Thus GGYRGYY is not a feasible hat pattern for the conversation.
If GYGRGYY: When it is the 5th person’s turn to speak, he can determine that he has a red or green hat (since he sees all 3 yellow hats). If he assumes that he has a red hat, then the hat pattern would be GYGRRYY. If so, the 3rd person would have figured that he is not wearing red (otherwise, the 1st person would have seen YRRRYY and announced that he has green, which he did not). Since the 3rd person sees 3 yellow hats, and knows that he is not wearing red, he would have announced that he is wearing green, which he did not. Hence the 5th person would conclude that he couldn’t be wearing red, and since he sees 3 yellows, he would have announced that he is wearing green, which he did not. Thus GYGRGYY is not a feasible hat pattern for the conversation.
If YGGRGYY: When it is the 5th person’s turn to speak, he can determine that he has a red or green hat (since he sees all 3 yellow hats). If he assumes that he has a red hat, then the hat pattern would be YGGRRYY. If so, the 3rd person would have figured that he is not wearing red (otherwise, the 2nd person would have seen YRRRYY and announced that he has green, which he did not). Since the 3rd person sees 3 yellow hats, and knows that he is not wearing red, he would have announced that he is wearing green, which he did not. Hence the 5th person would conclude that he couldn’t be wearing red, and since he sees 3 yellows, he would have announced that he is wearing green, which he did not. Thus YGGRGYY is not a feasible hat pattern for the conversation.
20 November 2024, 3:43 pmSanandan Swaminathan:
Thinking more about this exquisite hat puzzle, it seems that proving that a given hat sequence results in the exact sequence of 6 statements is far trickier than rejecting some hat sequence (where we only need to show one anomaly). Too much recursive logic involved. A good example of a hat distribution with the 7th mathematician (M7) wearing a green hat that would lead to the given sequence of 6 sentences is GRRRYYG. Note: Below, an underscore in a hat pattern represents a mathematician’s own unseen hat color.
a) With hat pattern GRRRYYG, M1 would see _RRRYYG, hence can’t decide if he has yellow or green. M1 would say he doesn’t know his color.
b) M2 would see G_RRYYG. If M2 assumes that he has yellow, M1 would have seen _YRRYYG, and can’t decide if he has red or green. If M2 assumes that he has green, M1 would have seen _GRRYYG, and can’t decide if he has red, yellow or green. Similar situation will occur if M2 assumes he has red. There is more than one color choice for M2 that would cause the same response of “I don’t know” from M1. Hence M2 can’t decide his own color, and M2 would say he doesn’t know his color.
c) M3 would see GR_RYYG. If M3 assumes that he has yellow, M2 would have seen G_YRYYG. If M2 assumed that he has green, M1 would have seen _GYRYYG, and can’t decide if he has red or green. If M2 assumed that he has red, M1 would have seen _RYRYYG ,and can’t decide if he has red or green. There is more than one color choice for M2 that would cause the same response from M1. Hence M2 can’t decide his own color, and M2 would say he doesn’t know his color. On the other hand, if M3 assumes that he has red, M2 would have seen G_RRYYG. Again, whether M2 assumes that he has red, yellow or green, M1 would say “I don’t know.” There is more than one color choice for M2 that would cause the same response from M1. Hence M2 can’t decide his own color. Similar situation will occur if M3 assumes he has green. So, there is more than one color choice for M3 that would cause the same responses from M1 and M2. Hence M3 can’t decide his own color, and M3 would say he doesn’t know his color.
d) M4 would see GRR_YYG. If M4 assumes that he has yellow, M3 would have seen GR_YYYG. If M3 assumed that he had green, M2 would have seen G_GYYYG, and M2 would have said that his color is red. Since M2 didn’t say it, M3 would determine that he doesn’t have green, and would have said that he has red. Since M3 didn’t say it, M4 would determine that he doesn’t have yellow. On the other hand, if M4 assumes that he has green, M3 would have seen GR_GYYG. M3 would determine that he doesn’t have yellow (otherwise M2 would have guessed red correctly). Hence M3 would announce that he has red. Since M3 didn’t say it, M4 would determine that he doesn’t have green. Thus, M4 would know that he has red, and would say it.
e) M5 would see GRRR_YG. If M5 assumes that he has green, M4 would have seen GRR_GYG. If M4 assumes that he has yellow, M3 would have deduced that he has red (otherwise, M3 would have yellow, and M2 would have known his color as red). Since M3 didn’t say that he has red, M4 would know that he doesn’t have yellow. Hence M4 would conclude and announce that he has red. We can also see that, if M5 assumes that he has green, M1, M2, M3 would all say that they don’t know their colors. On the other hand, if M5 assumes that he has yellow, M4 would have seen GRR_YYG. If M4 assumes that he has green, M3 would have deduced his color as red (if M3 assumes yellow, M2 would have announced red). If M4 assumes his color as yellow, again M3 would have deduced his color as red. Thus, M4 would conclude and announce that he has red. We can also see that, if M5 assumes that he has yellow, M1, M2, M3 would all say that they don’t know their colors. There is more than one color choice for M5 that would cause the same responses from M1, M2, M3, M4. Hence M5 would say that he doesn’t know his color.
f) M6 sees GRRRY_G. If M6 assumes that he has green, M5 would have seen GRRR_GG. M5 would conclude and announce that he has yellow, which he didn’t. Hence M6 knows that he doesn’t have green, and would conclude and announce that he has yellow.
Thus, hat sequence GRRRYYG would result in the exact conversation given.
21 November 2024, 12:39 pmAlan Listoe:
Key Insight: If a hat-wearer says “I don’t know my hat color”, then they see all 3 colors among those who have not so far said “I don’t know.”
Proof could be by induction, but I will unroll the special case of Green:
If First didn’t see Green, then as there are only 3 Red and 3 Yellow hats, they would know their own hat was Green. But they don’t know; so they see Green.
If Second didn’t see Green among 3-7, they would know that the Green that First sees would be on their own head. But they don’t know; so they see Green among 3-7.
If Third didn’t see Green among 4-7, they would know that the Green that Second sees would be on their own head. But they don’t know; so they see Green among 4-7.
If Fifth didn’t see Green among 4,6,7, they would know that the Green that Third sees would be on their own head. But they don’t know; so they see Green among 4,6,7.
But now we are done. Fifth sees Green; Fourth is Red; Sixth is Yellow. So Seventh must be Green.
22 November 2024, 6:45 amtanyakh:
The last person with a particular color will know their color. So, by the end of everyone speaking, we should hear at least three people with three different colors to say that they know there color.
22 November 2024, 10:18 am