# Prisoner' Hats

• Nov 21st 2009, 03:44 PM
Focus
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).
• Nov 23rd 2009, 08:12 PM
Drexel28
Quote:

Originally Posted by Focus
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 :(
• Nov 24th 2009, 03:03 AM
Focus
Quote:

Originally Posted by Drexel28
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.