*Problem*: There are an infinite number of people. They are labelled 1,2,3,... (I am not a number, I am a free man!) There is the Master who I call The Master. The Master will, at the same time, put a hat on each persons head. Some of the hats are RED, some are BLUE. (Clarification added later- everyone can see all the peoples hat colors except their own.)

The people will then all, at the same time, yell out a hat color. (Clarification added later- NO other form of communicationis allowed.)

If only a finite number of them get their own hat color wrong they win (not sure what they win, but they win!)

If an infinite number of them get their own had color wrong, then they lose.

They can discuss strategy ahead of time; however, The Master overhears all conversation.

Assume that the people and The Master are experts at this game.

Who would you bet to win? How much and at what odds?

I'll post the answer, a meta question about it, and another math question, on Thursday.

Feel free to post your answer as comments. If you do then please also comment on if you've seen the problem before since I'm curious (1) how well known the problem is, and (2) how hard it is to solve if you haven't seen it.

If you want to try to solve it yourself, don't look at the comments in case the right solution is there.

So everyone can see the colors of the other people but not their own?

ReplyDeleteYes, thanks for that- I have added a clarifying note to the post.

DeleteActually, I recalled the problem from this very blog a long time ago:

ReplyDeletehttp://blog.computationalcomplexity.org/2006/11/puzzles-that-keep-you-awake-at-night.html

(don't go there unless you want to see the solution)

A very nice one, I discussed it in class once or twice.

Thanks for the pointer to an old post of Lances.

DeleteA good question is worth repeating!.

The question I post thursday will be new to this blog.

"finite number of them get their own hat color wrong " means finite number of them got hats of color not yelled out by the people. Is that true?

ReplyDeleteA finite number of them (possibly 0) when they yell a color its not THEIR hat.

DeleteExample:

If person 3 yells RED but his hat is BLUE, and

person 10 yells BLUE but his hat is RED, and

person 1001 yells BLUE but his hat is RED, and

for all i that is NOT 3, 10, 1001, person i yells out a hat

that is person i's hat color

then they win since 3 (a finite number) got it wrong).

If you still have a question of clarity email me directly.

This comment has been removed by the author.

ReplyDeleteIt seems to me that if The Master assigns all the hat colours randomly then The People will lose. No matter what clever scheme The People have devised for person i to use to yell his hat colour once he sees all the other hats, it can't help him to guess his own colour, which is independent of everything he can see.

ReplyDeleteTry to prove this rigorously!

DeleteIf you are person i and you can see all the other people's hats, your choice will decide between one of only two sequences of hat colors. What if you can strategize a way to know which of those to choose?

DeleteSo, what prevents person n+1 to make a hand sign indicating the color of person n's hat?

ReplyDeleteAfter the hats go on their heads NO other form of communication is allowed.

DeleteTHanks for bringing this up and allowing me a chance to clarify.

bill g.

I still do not know if this helps, but can they solve only decidable problems?

ReplyDeleteYou an assume they have infinite computing power

DeleteThey can solve HALT, etc.

I heard the problem for the first time in 2011, proposed by a student during a

ReplyDeletedinner at an Italian summer school in logic (http://sel.di.unimi.it/, very nice

experience!). If my memory doesn't deceive me, after about half an hour that everybody

were struggling with it, an undergraduate came out with the solution.

I remember I had an hard time digesting it on an intuitive level!

Now it is one of my favourite puzzles while I'm waiting the food at the restaurant with mathematicians and computer scientists (and it's interesting to look how harder it is for the latter ones) :)

Between "putting hats on - all at the same time" and "yelling the color - all at the same time" is there "zero time" or are the people allowed to do something after the got their hat?

ReplyDeleteB. Bartsch