[bonanova]

Nothing new except the survival criterion.

1. N prisoners, each with a red or black hat.
   
2. Each can see all the others, but not his own.
   
3. No one hears the others' guesses.
   
4. No communication.
   

If all guess correctly or if all guess incorrectly they go free.

Otherwise ... well, you know.

How do you advise them?

[Guest]

You divide up the time into equal turns. Instruct everyone to wait for as many turns as red hats they can see + 1. Now, if any person ever reaches this point, he knows he is wearing a red hat. If someone goes before he has a chance to, he knows he is wearing a black hat.

This guess is based off intuition, not any kind of real analysis, so it may be incorrect in some edge cases.

[bonanova]

No turns or waiting, just guessing.

They just guess, and they don't know what each other's guesses are.

[HoustonHokie]

If there's an even number of prisoners, the easiest way is to have the prisoners say the color of the hat they see an even number of times. For example, if there are 5 red and 5 black, each person will guess correctly and they win. If its 4 red and 6 black, each guesses incorrectly and they win again. You can carry it out for different values of N and distributions of hats, but I think it works every time. So that's half the puzzle...

For an odd number of prisoners, its different, as both colors will be odd or even. Gonna have to think about that some more.

[Guest]

Since they can all be wrong and all of the hats are black or red, they should all guess WHITE!

[Guest]

Not exactly a logical solution, but...

They could all say "Blue" or any color other than "Black" or "Red"

If those are the only two reply options, well then I'll figure out something different

[bonanova]

Since they can all be wrong and all of the hats are black or red, they should all guess WHITE!

You are way out of the box on that one!

Good job.

You too, Mumbles, but by all means try for a red/black solution as well.

HoustonHokie has the seed of a more satisfying solution, but yours is no less correct.

[Guest]

Since they can all be wrong and all of the hats are black or red, they should all guess WHITE!

Sorry, didn't read yours before I posted

[HoustonHokie]

If there's an even number of prisoners, the easiest way is to have the prisoners say the color of the hat they see an even number of times. For example, if there are 5 red and 5 black, each person will guess correctly and they win. If its 4 red and 6 black, each guesses incorrectly and they win again. You can carry it out for different values of N and distributions of hats, but I think it works every time. So that's half the puzzle...

For an odd number of prisoners, its different, as both colors will be odd or even. Gonna have to think about that some more.

If the number of prisoners is odd, they will either see odd red & black or even red & black. If they see evens, guess red. If they see odds, guess black. (Or vice-versa). This works because if the red prisoners see odd numbers, the black prisoners will see even numbers (and vice-versa), so all red prisoners will guess one answer and all the black prisoners will guess the other.

[TalkSiQ]

Aiming for the wrong answer seems to be the way to go.

Count how many of either color, the only hat you dont know is yours, so be off count by two

so lets say 3R and 2B and you 1? so just say 5R and 1B or 4B and 2R

I think the only way it doesn't work if there's just you and one other person

[TalkSiQ]

hey wait even with two it still works, right?

[Guest]

hey wait even with two it still works, right?

I think you misunderstood the problem. You have to guess the color of your own hat only, not the total number of red and black hats. Everyone has to guess their own color correctly, or everyone has to guess their own color incorrectly.

[k-man]

Hint: I think the key here is that all people wearing black hats must be consistent in their answers and all say either "red" or "black". The red hat wearers must say the opposite.

Let's say you are wearing a black hat and see X black hats. All other people wearing black hats also see X black hats. All red hat wearers see X+1 black hats. Therefore the rule for everyone to follow is - say BLACK if you see an even number of black hats and say RED if you see an odd number of black hats.

[Guest]

Select a Coordinator.

Coordinator pushes reds to one side and blacks to the other.

Once all have been pushed, the group with the matching color pushes itself into Coordinator.

Now, if you are in a group with more than one member vote according to your color,

otherwise vote according to the opposite of the other groups color.

-Geodepe

[Guest]

the only thing comes to my mind now:D

the only 100% sollution is possible when n=1

[Guest]

Aiming for the wrong answer seems to be the way to go.

Count how many of either color, the only hat you dont know is yours, so be off count by two

so lets say 3R and 2B and you 1? so just say 5R and 1B or 4B and 2R

I think the only way it doesn't work if there's just you and one other person

No where does it state that half wear black and half wear red. By the sounds of it many people as assuming this for the answer

[EventHorizon]

How do you advise them?

Given the first hat problem is very related....I got this in no time flat.

First, tell everyone to assume that there will be an odd number of black hats.

If there is an odd number of black hats, then everyone will guess correctly.

If they have a black hat on, they will count an even number of black hats and guess black.

If they have a red hat on, they will count an odd number of black hats and guess red.

If there is an even number of black hats, then everyone will guess incorrectly.

If they have a black hat on, they will count an odd number of black hats and guess red.

If they have a red hat on, they will count an even number of black hats and guess black.

As always, another great puzzle from bonanova.

[bonanova]

HoustonHokie, k-man and EventHorizon have it.

Nice job.

[Guest]

No where does it state that half wear black and half wear red. By the sounds of it many people as assuming this for the answer

I see now.. Sorry my bad

[Guest]

N number one goes to one corner. N number 2 goes to another corner. N number 3 sees 2R, 2B or 1R/1B. Number 3 goes to N1, N2 observes N1 and N3. If there are 2R or 2B, N2 knows his color and stays put, N2 and N3 know their color (opposite of N2). If N2 and N3 are different colors (1R/1B), then N2 goes next to N3 (or N1) and N1 (or N3) goes to other corner. Black and red corners are now known and process continues until all N's are in their correct corners

[Guest]

HoustonHokie, k-man and EventHorizon have it.

Nice job.

If there is no communication how can you "say" or "tell"?

[Guest]

N number one goes to one corner. N number 2 goes to another corner. N number 3 sees 2R, 2B or 1R/1B. Number 3 goes to N1, N2 observes N1 and N3. If there are 2R or 2B, N2 knows his color and stays put, N2 and N3 know their color (opposite of N2). If N2 and N3 are different colors (1R/1B), then N2 goes next to N3 (or N1) and N1 (or N3) goes to other corner. Black and red corners are now known and process continues until all N's are in their correct corners

I'm not sure if that will work, because "If there are 2R or 2B, N2 knows his color" isn't true (unless I misunderstand your idea). I do have a similar idea, though, that I work (unless this constitutes "communication," which I guess it does in the strictest sense).

N1 and N2 stand next to each other. N3 approaches them - if they are the same color, he stands either before N1 or after N2 in line (doesn't matter which). If they are different colors, he stands between them. N4 now comes up, and sees either RRR, RRB, RBB, or BBB (or in the opposite order). You know, though, that you do not have RBR or BRB.

N4-NX continue this - if they see all one color, they stand at either end. If they see two different colors, they stand in between the two people of different colors. Continuing this, you are guaranteed to have all the reds together and all the blacks together. By looking at the people on either side of them, and knowing where the next person goes to stand, everyone in line then knows their color except for NX. This can then be remedied by having N1 stepping out of line and repeating the procedure as if they were N(X+1).

I do have to admit, though, that the evens/odds solutions are easier and more satisfying (since this is "communicating" on some level).

Edited for clarity (hopefully, at least)

Edited August 13, 2008 by Chuck Rampart