Yet Another Hat Problem

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

FiddleMath
Posts: 245
Joined: Wed Oct 11, 2006 7:46 am UTC
Contact:

Yet Another Hat Problem

I know, I know. Hats again. (If this has already been 'round, let me know.)

You and six others are sitting in a circle, so that everyone can see everyone else. Right now, you all have all the time you need to discuss strategy.

When everyone is ready, you will all be blindfolded. While you are blindfolded, a hat will be placed on your head. Each hat is one of seven colors (roygbiv), but the colors may be duplicated.

Everyone's blindfold is then removed. Everyone can see the color of everyone else's hat, but no one can see their own, and no one can communicate in any way with anyone else. Everyone writes, on a piece of paper that no one else can see, a guess at the color of their hat. If everyone is wrong, everyone loses and \$dire_consequence, but if at least one person guesses correctly, everybody wins \$something_nice.

Does any strategy guarantee victory? If yes, what is it? If not, why not?

Gelsamel
Lame and emo
Posts: 8237
Joined: Thu Oct 05, 2006 10:49 am UTC
Location: Melbourne, Victoria, Australia
I think it's indeterminate, because they can be any color, and there can be any number of those colors so looking at other people's hats would give you no information.

The best bet would be to all guess the same thing and hope that someone has that color.

I have to say I'm not good with these hat problems though.

phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
After the blindfolds are removed, is there any way to give any information to the other people? Like, taking your time writing, or writing in a particular way, or arranging your paper in a particualr way, or something? Or are you completely cut off from them?

If the latter, I don't think it's solveable... but in the former it's simple... just being able to indicate a simple "yes" or "no" would be by far sufficient...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Gelsamel
Lame and emo
Posts: 8237
Joined: Thu Oct 05, 2006 10:49 am UTC
Location: Melbourne, Victoria, Australia
It says you can't communicate in anyway, I'm guessing this includings how you write, and your expressions etc.

FiddleMath
Posts: 245
Joined: Wed Oct 11, 2006 7:46 am UTC
Contact:
Right. Once the blindfolds are donned, there's no communication in any way. You cannot influence what anyone else writes, and they can't influence you. This is one of those hypothetical worlds where such things are possible.

Zink
Posts: 30
Joined: Tue Oct 10, 2006 10:05 pm UTC
Oooh. Nice. Very nice.

I agree that it seems impossible for any one to correctly guess his color - indeed, seeing the others' hats doesn't tell him anything about himself. But using some common hats technique, this can be quite solvable.

Gelsamel
Lame and emo
Posts: 8237
Joined: Thu Oct 05, 2006 10:49 am UTC
Location: Melbourne, Victoria, Australia
Usually 'hat' brain teasers involve getting some knowledge from other people not saying anything. However not only would you not gain any information anyway with this technique they don't even get to say anything.

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:
Well, with 2 people and 2 hat colors, this is easily solvable... person A picks the color of the hat on person B's head, and person B picks the color of the hat not on person A's head.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
Oh, oh oh... I misread the question at first as 6 people wearing 7 colours of hats (not you and 6 other people...)

That makes it more differenter...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Zeph
Posts: 6
Joined: Wed Oct 11, 2006 7:26 pm UTC
It is possible, although I'm not sure I can elegantly describe the solution. GreedyAlgorithm's approach does scale up, but the decision table for a 7 person game would be huge.

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:
Zeph wrote:It is possible, although I'm not sure I can elegantly describe the solution. GreedyAlgorithm's approach does scale up, but the decision table for a 7 person game would be huge.

Yeah, that's the problem I'm having. It's not uncomplicated for 3 people.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

aaronspook
Posts: 20
Joined: Thu Jul 20, 2006 9:55 pm UTC
I'm confused. If colors can be duplicated, then presumably not every color has to be used, so your hat color should be completely independent of everybody else's. How does the two-hat solution work, then (and presumably the greedy-algorithm version of it for seven hats)?

Gelsamel
Lame and emo
Posts: 8237
Joined: Thu Oct 05, 2006 10:49 am UTC
Location: Melbourne, Victoria, Australia
Yes, I don't see how in a 2 person situation choosing the other person's color gives you a definate winning strategy.

Edit: Actually I miss read what he said, I get it now.. That would get very complicated.

8ightBall
Posts: 1
Joined: Thu Oct 12, 2006 11:16 am UTC
New to the forums but I thought I'd throw my 2c

If the game relies upon the group collectively knowing their hats:

Everyone writes down the colour of the hat to their left. The all of the hats are accounted for (even if not in the right order).

Did I miss the point?

______
Posts: 4
Joined: Thu Oct 12, 2006 10:53 am UTC
if the colour of each hat is an independant process, unbiased, then there is no optimal stratergy. It makes no difference if everyone guesses the same or randomly.

on the information you have supplied this is exactly the setup: 7 identical, independant, unbiased processes.

This isn't a logic puzzle, its a learn to read puzzle

phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
Yes, it is true that no person is able to figure out their own hat colour, or even have any clues about it whatsoever, but it is possible to have them make guesses such that regardless how the hats are arranged, one of them must be right.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

egg
Posts: 1
Joined: Thu Oct 12, 2006 1:38 pm UTC
Contact:
8ightBall wrote:New to the forums but I thought I'd throw my 2c

If the game relies upon the group collectively knowing their hats:

Everyone writes down the colour of the hat to their left. The all of the hats are accounted for (even if not in the right order).

Did I miss the point?

There is a problem with that solution because each person has to guess the color of THEIR OWN hat. So assume a room where the people got

red blue red blue red blue red
They each guess the wrong color by guessing the person to their left.

aaronspook wrote:How does the two-hat solution work

Brute force to check!

Code: Select all

Person A      Person B
red            red
green          green
red            green
green          red

Person A guesses the color of the hat on Person B's head. This guarantees a success in the cases where they wear the same hats (the top two cases in that list). Person B guesses the color NOT on Person A's head. This guarantees success in the two cases where they have different hat colors (the bottom two of the list). It is assumed that in the 2 player solution there are also only 2 colors. Of course, Person B cannot intuit the color of the hat if they have to guess one of the six colors not worn by A.

Scaling up is obscenely intricate and requires quite the group powwow.

shocksteel
Posts: 1
Joined: Sun Oct 28, 2007 8:33 pm UTC

Re: Yet Another Hat Problem

There is in fact a guarantee strategy for this problem.

Spoiler:
First label each person 0, 1, 2, ..., 6
Then label each color one through seven so that red is 1, orange is 2, yellow is 3...
When person zero looks at the other 6 people's hats he adds up their total and then guesses his hat so that the sum of all the numbers is zero in a mod-7 system. person 1 does the same thing but chooses his hat number so that the sum would be one in mod-7. This assures that there will be at least one person who guesses correctly because the sum of the colors must be 0-6 in mod-7.

This problem can also be generalized for ten people or even 99999999999999 people, even though with the latter u have to hope no one makes an arithmetic mistake.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Yet Another Hat Problem

shocksteel wrote:There is in fact a guarantee strategy for this problem.

Indeed there is. In general, please post solutions in a separate thread, like this one. (You'll notice that your answer appears at the top.)

Also, welcome to the forums! Do post in the Introductions thread.