[Guest]

This is an extension to

How do we save maximum prisoners if there are hats of:

1. 3 colours: red, black and white?

2. n colours? (generalized solution)

[Guest]

I had worked this out earlier, but didn't post since I didn't want to check the 38 pages of discussion on the original topic to check if this is a duplicate..

..is that it doesn't matter what 'n' is. We still can save the same number of prisoners. Ofcourse, the probability for the last guy in the row keeps getting lower as 'n' increases..

[Guest]

I had worked this out earlier, but didn't post since I didn't want to check the 38 pages of discussion on the original topic to check if this is a duplicate..

..is that it doesn't matter what 'n' is. We still can save the same number of prisoners. Ofcourse, the probability for the last guy in the row keeps getting lower as 'n' increases..

"We still can save the same number of prisoners."

The question is: how? (the odd even approach wont work if there are more than 2 colours)

[Guest]

I don't know how to save all but 1 like the original problem but I can save all but n-1 (where n is the number of hat colors)

say the colors are a,b,c,....,y,z then the 1st person says y or z if they see an even or odd number of 'a' color hats. The second person then says a if that is their hat color, otherwise says y or z if they see an even or odd number of 'b' color hats. If the 2nd say 'a' then the 3rd says either 'a' if they know that or even/odd for the 'b' color hats but if the 2nd declared the even/odd of 'b' hats then the 3rd now knows if that have 'a' or 'b' color hat (and says 'a' or 'b' if they have it or otherwise does the same for 'c' color hats. So as long as the prisoners have great memories and keep track (and can see all the hats in front of them and can count), all but n-1 prisoners are guarenteed saved and the probability of the non-guarenteed goes 1/n,1/(n-1),...,1/2

[Guest]

I don't know how to save all but 1 like the original problem but I can save all but n-1 (where n is the number of hat colors)

say the colors are a,b,c,....,y,z then the 1st person says y or z if they see an even or odd number of 'a' color hats. The second person then says a if that is their hat color, otherwise says y or z if they see an even or odd number of 'b' color hats. If the 2nd say 'a' then the 3rd says either 'a' if they know that or even/odd for the 'b' color hats but if the 2nd declared the even/odd of 'b' hats then the 3rd now knows if that have 'a' or 'b' color hat (and says 'a' or 'b' if they have it or otherwise does the same for 'c' color hats. So as long as the prisoners have great memories and keep track (and can see all the hats in front of them and can count), all but n-1 prisoners are guarenteed saved and the probability of the non-guarenteed goes 1/n,1/(n-1),...,1/2

Nice work! But there is also a way to save all but 1...

Try numbering the colours

[bushindo]

I don't know how to save all but 1 like the original problem but I can save all but n-1 (where n is the number of hat colors)

say the colors are a,b,c,....,y,z then the 1st person says y or z if they see an even or odd number of 'a' color hats. The second person then says a if that is their hat color, otherwise says y or z if they see an even or odd number of 'b' color hats. If the 2nd say 'a' then the 3rd says either 'a' if they know that or even/odd for the 'b' color hats but if the 2nd declared the even/odd of 'b' hats then the 3rd now knows if that have 'a' or 'b' color hat (and says 'a' or 'b' if they have it or otherwise does the same for 'c' color hats. So as long as the prisoners have great memories and keep track (and can see all the hats in front of them and can count), all but n-1 prisoners are guarenteed saved and the probability of the non-guarenteed goes 1/n,1/(n-1),...,1/2

General N-hats solution

Let's consider the case of N different types of hats. Without lack of generality, let the types of hat be indicated by numbers from 0 to (N-1), rather than the color. The general algorithm goes as follows

1) Last prisoner sums up the value of all the hats he sees, divide the total by N and take the remainder, say that remainder out loud. His chance of survival is 1/N

2) Next prisoner looks at all the hats he sees and compute the remainder also. Computing his own hat color is simple. For instance, if there are 4 hats, and the sequence goes as follows (0,2,1,3), the last person (number 3) would say ((0+1+2) mod 4 ) = 3. The next person sees (( 0 + 2) mod 4) = 2, so he would know that his hat is number 1.

3) Repeat step 2 down to the first prisoner in line. Each person will need to keep track of the numbers previously announced. Chance of survival for all prisoners besides the first one is 100%.

Edited October 14, 2009 by bushindo

[Guest]

General N-hats solution

Let's consider the case of N different types of hats. Without lack of generality, let the types of hat be indicated by numbers from 0 to (N-1), rather than the color. The general algorithm goes as follows

1) Last prisoner sums up the value of all the hats he sees, divide the total by N and take the remainder, say that remainder out loud. His chance of survival is 1/N

2) Next prisoner looks at all the hats he sees and compute the remainder also. Computing his own hat color is simple. For instance, if there are 4 hats, and the sequence goes as follows (1,3,2,4), the last person (number 4) would say ((1+2+3) mod 4 ) = 2. The next person sees (( 1 + 3) mod 3) = 0, so he would know that his hat is number 2.

3) Repeat step 2 down the first prisoner in line. Each person will need to keep track of the numbers previously announced. Chance of survival for all prisoners besides the first one is 100%.

Wow..we post nos. 5 and 6 at the same time!

newaz..u cracked it..Cheers!

[Guest]

ignore, I see the answer was posted

Edited October 14, 2009 by Doctor Moshe

[Guest]

Each color hat was assigned a prime number, i.e. red=2 blue=3 green=5 black=7 yellow=11 and orange=13, then the last guy in line can simply multiply together the values of each of the hats in front of him and shout it out. He will of course be killed, but from that everyone else can simply do a prime factorization of his number and determine how many of each color hat there is, then they 19th person should be able to demise his hat color, and the rest should simply keep track as the line moves along...

This is in response to another post that was locked, but posed this problem with 20 prisoners and 6 colors of hats. Would it not work if