[Guest]

16 prisoners are each wearing a hat with a number 1 to 4 (inclusive). after seeing the hats of the other members, the warden blindfold them and randomly switches the hats of the prisoners around, then takes the blindfolds off. this process is repeated twice more. after they see the new hats for the final time, each are taken to a secluded room to guess the hat they are currently wearing. if more than half the prisoners guess right, they go free, else it's the firing squad for all of them. is there a way to gaurentee they all go free? there should be no signaling, and yes the prisioners are allowed to form a strategy beforehand.

[curr3nt]

No guarantee.

Although very unlikely it is possible for each of them to get the same hat all four times. In this case there is no way for half to pick the correct hat number at the end. (Luck if half can guess but no guarantee)

So if the hat switch is truely random then no. But I believe the spirit of the puzzle is to get half to guess correctly most of the time so will spend some time on that.

[curr3nt]

Built a script to generate random distribution of hat values and placements.

If anyone wants to test theories here is one.

P	Hat 1	Hat 2	Hat 3	Hat 4

1	3	4	2	3

2	3	3	3	3

3	4	2	3	2

4	1	1	2	3

5	1	3	2	2

6	3	2	3	2

7	2	2	4	3

8	2	3	3	2

9	2	4	2	3

10	3	2	4	1

11	2	3	3	4

12	2	1	3	2

13	3	3	2	4

14	2	2	1	1

15	3	2	1	3

16	4	3	2	2

Edited May 3, 2011 by curr3nt

[Guest]

is to have each prisoner count how many times they see each number and compare that each time. If I see 5 2's one time and 4 2's the next time I have to have a 2 on my head.

[Guest]

they all guess the word "right"

[Guest]

They are allowed to see the other hats everytime, so all they need do is total all the 1, 2, 3, 4 they see the first time and remember those totals. Then whenever hats are changed, look to see if any total went up. If so, that is the hat they were wearing at first and should be added to the original totals. They now know how many hats there are. For the final time, simply look to see which total is low and that is their own hat.

A sadistic jailer would never really change their hats around though, leaving them totally in trouble.

[Guest]

I look around the room and add up the numbers on everybody else's hats. Let's say this comes to 35. The total of all hats is thus 35 plus my hat. Ie 36, 37, 38, or 39.

After the swapping I repeat the process. Hopefully the total is different (otherwise no new information is gained). Let us say the second visible total is 37. This means that the actual total is 38, 39, 40 or 41.

The third round gives another set of data. If the visible total is 34 then the actual total is 35, 36, 37 or 38.

In this case, the only actual total that occurs in all three cases is 38, I can see 34, so I must be wearing the 4.

Depending on the visible totals, there may be one possibility, or two, three or (if very unlucky and you've been wearing the same number each time) four.

But I think this gives the best chance of a prisoner being able to have a good guess at his number if not to know it for sure.

Probabilities:

The probability of wearing the same hat each time should be P=1/16 (1/4 chance that whatever number I wear the first time gets picked the second (assuming they're randomly distributed) and 1/4 again for the third.

In this situation you have no data and a 1/4 chance of guessing the right total.

Chances that I get a different hat for the second round is 3/4 and for a different hat again for the third round is 2/4, giving an overall chance of 6/16 or 3/8 of having a full set of data. This does not guarantee a single possibility for the actual total, that needs totals that have a range of 3. But from three different reading out of a possible four the chances of getting the highest and the lowest work out to exactly 1/2. In that case you know your hat and in the other half you have either the highest or the lowest total plus two intermediates, a range of 2, with two possible actual totals and so have a 1/2 chance of guessing right.

The chances that I have two hats the same and one different is 1-the other two, which is 3/8. In this case I will have only two stabs at getting the highest and the lowest totals. Probabilities work out to be 1/6 that I get both highest and lowest, 2/3 that I get on or the other and 1/6 that I have two intermediate totals.

I need to go do mumsy stuff now, so I'll leave someone else to work out the overall probability that I can guess my hat correctly.

good puzzle!

[Guest]

The first time one just counts the no of 1's, 2's, 3's and 4's in the room.

The next time they do the same, only to find one deviation from their previous count, which gives them the no of hat they were wearing previously and the one they are wearing right now.

Eg. 1st time the count was 1=4,2=4,3=5,4=2

2nd time the count was 1=3,2=4,3=6,4=2 prev Hat was 3 and the current one is 1

Thus, after each iteration they can come to know the current hat no..