Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Google Analytics and Mathjax
Sunday, July 10, 2016
An infinite hat problem and later a point
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.
Subscribe to: Post Comments (Atom)
So everyone can see the colors of the other people but not their own?ReplyDelete
Yes, thanks for that- I have added a clarifying note to the post.Delete
Actually, I recalled the problem from this very blog a long time ago:ReplyDelete
(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.Delete
A 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?ReplyDelete
A finite number of them (possibly 0) when they yell a color its not THEIR hat.Delete
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.ReplyDelete
It 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.ReplyDelete
Try to prove this rigorously!Delete
If 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?Delete
So, what prevents person n+1 to make a hand sign indicating the color of person n's hat?ReplyDelete
After the hats go on their heads NO other form of communication is allowed.Delete
THanks for bringing this up and allowing me a chance to clarify.
I still do not know if this helps, but can they solve only decidable problems?ReplyDelete
You an assume they have infinite computing powerDelete
They can solve HALT, etc.
I heard the problem for the first time in 2011, proposed by a student during aReplyDelete
dinner 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?ReplyDelete