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.



at

16 comments:

  1. Anonymous8:58 PM, July 10, 2016

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

    ReplyDelete
    Replies
    1. GASARCH9:01 PM, July 10, 2016

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

      Delete
  2. Eldar Fischer9:22 PM, July 10, 2016

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

    http://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.

    ReplyDelete
    Replies
    1. GASARCH9:57 PM, July 10, 2016

      Thanks for the pointer to an old post of Lances.
      A good question is worth repeating!.
      The question I post thursday will be new to this blog.

      Delete
  3. Anonymous9:51 PM, July 10, 2016

    "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
    Replies
    1. GASARCH10:00 PM, July 10, 2016

      A finite number of them (possibly 0) when they yell a color its not THEIR hat.
      Example:
      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.

      Delete
  4. GASARCH9:53 PM, July 10, 2016

    This comment has been removed by the author.

    ReplyDelete
  5. Alan Skelley2:36 AM, July 11, 2016

    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
    Replies
    1. GASARCH7:15 AM, July 11, 2016

      Try to prove this rigorously!

      Delete
    2. Unknown8:52 AM, July 11, 2016

      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
  6. Micha3:01 AM, July 12, 2016

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

    ReplyDelete
    Replies
    1. GASARCH6:14 AM, July 12, 2016

      After the hats go on their heads NO other form of communication is allowed.
      THanks for bringing this up and allowing me a chance to clarify.

      bill g.

      Delete
  7. Unknown9:57 AM, July 12, 2016

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

    ReplyDelete
    Replies
    1. GASARCH12:20 PM, July 12, 2016

      You an assume they have infinite computing power
      They can solve HALT, etc.

      Delete
  8. Emanuele Natale4:54 AM, July 14, 2016

    I heard the problem for the first time in 2011, proposed by a student during a
    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) :)

    ReplyDelete
  9. Anonymous6:02 AM, July 21, 2016

    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?

    B. Bartsch

    ReplyDelete