Results 1 to 3 of 3

Math Help - Prisoner' Hats

  1. #1
    Member Focus's Avatar
    Joined
    Aug 2009
    Posts
    228

    Prisoner' Hats

    Suppose that there are n prisoners. The next day the prisoners will be put in a line (each one can see those in front of him) and they will each get a hat that is either black or white. They cannot see their own hat but they can see all the ones in front. The executioner will start from the back (one who can see all) and shoot the prisoner if they get their hat colour wrong. The prisoners can save n-1 of themselves using a strategy that I will outline now.
    Spoiler:
    Number the hats 0,1 and work in \mathbb{Z}_2. The prisoner at the very back sums the hats in front of him and guesses that as his hat colour. The k-th in line sums the ones in front of him and takes it away from what the guy behind him said.


    Now here is the puzzle. If there are countably infinite number of prisoners, and they are all deaf or cannot communicate with each other at all (so the system for the finite case will not work), show by using the AC you can save all but finitely many of them.
    Here is a hint if you want it:
    Spoiler:
    Make equivalence class of hat colours. The relation will involve somthing finite (as you are trying to save the rest).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Focus View Post
    Suppose that there are n prisoners. The next day the prisoners will be put in a line (each one can see those in front of him) and they will each get a hat that is either black or white. They cannot see their own hat but they can see all the ones in front. The executioner will start from the back (one who can see all) and shoot the prisoner if they get their hat colour wrong. The prisoners can save n-1 of themselves using a strategy that I will outline now.
    Spoiler:
    Number the hats 0,1 and work in \mathbb{Z}_2. The prisoner at the very back sums the hats in front of him and guesses that as his hat colour. The k-th in line sums the ones in front of him and takes it away from what the guy behind him said.


    Now here is the puzzle. If there are countably infinite number of prisoners, and they are all deaf or cannot communicate with each other at all (so the system for the finite case will not work), show by using the AC you can save all but finitely many of them.
    Here is a hint if you want it:
    Spoiler:
    Make equivalence class of hat colours. The relation will involve somthing finite (as you are trying to save the rest).
    Spoiler:
    I am about 85% sure that Laurent has already postd a thread asking these exact two questions. I will attempt to locate it if you'd like. This time this spoiler really does contain a spoiler
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Focus's Avatar
    Joined
    Aug 2009
    Posts
    228
    Quote Originally Posted by Drexel28 View Post
    Spoiler:
    I am about 85% sure that Laurent has already postd a thread asking these exact two questions. I will attempt to locate it if you'd like. This time this spoiler really does contain a spoiler
    Awww. Shame.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Problem of hats
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 23rd 2010, 11:07 AM
  2. Looking for Hats
    Posted in the Advanced Statistics Forum
    Replies: 7
    Last Post: March 17th 2010, 04:57 PM
  3. Variations on colours and hats
    Posted in the Math Challenge Problems Forum
    Replies: 12
    Last Post: July 8th 2009, 04:38 PM
  4. Hats off to helpful mathaticians
    Posted in the Statistics Forum
    Replies: 1
    Last Post: May 30th 2009, 09:41 PM

Search Tags


/mathhelpforum @mathhelpforum