[bushindo]

Twenty prisoners are on a death row and are allowed a chance to live through a game. The game is as follows. Each prisoner, as they enter the room on the day of the game, is given a hat with a random number ranging from 1 to 20. The numbers of the hats are independent of one another. The prisoners then stand in a circle, and each one can see what the other nineteen have on their hat, but not his own hat.

After the prisoners stand in a circle, the prisoners are allowed 3 minutes to think of a guess for the hat they are wearing. At any time that a prisoner is ready with his answer, he can raise his hand to indicate that he is ready. The other 19 prisoners, being in the same room, can see whenever someone raises his hand. Assume the prisoners can not communicate with each other in any other ways such as raising his hand with different number of fingers extended, raise it with different speed, make his fist into a prearranged shape, etc. The only information available to each prisoner is the other 19 numbers, and the order in which his fellow prisoners indicate they are ready.

After 3 minutes, or after all 20 indicate that they are ready, whichever is sooner, each prisoner is required to write his guess for his hat number without being seen by the other 19. All prisoners write down their guess simultaneously. If all 20 guesses are correct, the prisoners win and all are released. If 1 or more is incorrect, all 20 will die.

With optimal strategy, what is the chance of winning for the prisoners? Describe the strategy.

Edited July 6, 2009 by bushindo

[Guest]

They can decide the strategy as follows:

For any prisoner, the prisoner standing to his right will indicate his number. Now, the prisoner standing to the right of prisoner with hat 1 will indicate that his number is 1, for prisoner 2, the prisoner standing to his right will indicate his number 2 and so on...

The way to indicate will be given by the order in which they raise their hands. So the prisoner standing to the prisoner with number 1 hat will raise his hand first, the prisoner to the right of hat 2 will raise his hand second and so on... all prisoners would know the number on their hats.

Edited July 6, 2009 by DeeGee

[Guest]

They can decide the strategy as follows:

For any prisoner, the prisoner standing to his right will indicate his number. Now, the prisoner standing to the right of prisoner with hat 1 will indicate that his number is 1, for prisoner 2, the prisoner standing to his right will indicate his number 2 and so on...

The way to indicate will be given by the order in which they raise their hands. So the prisoner standing to the prisoner with number 1 hat will raise his hand first, the prisoner to the right of hat 2 will raise his hand second and so on... all prisoners would know the number on their hats.

I am confused why to have any stretagy in place as if they can see other 19 numbers then it will be clear that missing number is on his hat.

Am I missing anything here?

[Guest]

I just realised a grave mistake in the answer I gave before as some prisoners may have the same number on their hat... will rethink and come back

[Guest]

the prisoners can work in pairs. each will indicate the other's number by the time it takes to put up their hands. since it's may not be as easy as counting the seconds, they could use 5 sec increments, counting in their head. eg. prisoner A has 5 on his hat and prisoner B has 12 on his hat.

After 25 seconds, prisoner B puts his hand up (so A knows he's got 5)

After 60 seconds, prisoner A puts his hand up (and B knows he's got 12)

[Guest]

I think that before the game, the prisoners need to have the following plan ready to go.

19 or 20 of the prisoners will survive the game. The odds for the last prisoner is 1:20.

I think that the first prisoner to raise his hand (who is also at the highest risk) needs to count up the total of all the numbers on all the hats. With the total in mind, and beginning at the 3 minute count-down, he begins to count the seconds.

When the second-count comes to the total of the all the hats he can see, he raises his hand.

Based on that number, all the prisoners can now calculate the totals on the hats they see, and based on their total (and the difference), discover their own number.

Actually, now that I think about it, if two prisoners perform the countdown ... so they'll all survive!!

Well, I think I have it ... any comments?

[Guest]

Each prisoner could indicate the number off the pris standing at his immediate right/left by the number of seconds he keeps his hands raised for.

An alternate stratergy

This of course is an explanation for if the numbers can be repetitive. If the numbers cannot be repeated then- its as simple as the others prisoners looking at all the other hats and figuring out his own no.

[bushindo]

Twenty prisoners are on a death row and are allowed a chance to live through a game. The game is as follows. Each prisoner, as they enter the room on the day of the game, is given a hat with a random number ranging from 1 to 20. The numbers of the hats are independent of one another. The prisoners then stand in a circle, and each one can see what the other nineteen have on their hat, but not his own hat.

After the prisoners stand in a circle, the prisoners are allowed 3 minutes to think of a guess for the hat they are wearing. At any time that a prisoner is ready with his answer, he can raise his hand to indicate that he is ready. The other 19 prisoners, being in the same room, can see whenever someone raises his hand. Assume the prisoners can not communicate with each other in any other ways such as raising his hand with different number of fingers extended, raise it with different speed, make his fist into a prearranged shape, etc. The only information available to each prisoner is the other 19 numbers, and the order in which his fellow prisoners indicate they are ready.

After 3 minutes, or after all 20 indicate that they are ready, whichever is sooner, each prisoner is required to write his guess for his hat number without being seen by the other 19. All prisoners write down their guess simultaneously. If all 20 guesses are correct, the prisoners win and all are released. If 1 or more is incorrect, all 20 will die.

With optimal strategy, what is the chance of winning for the prisoners? Describe the strategy.

The use of the time variable is a reasonable solution, but that wasn't the intention of the puzzle. Assume that the prisoners do not possess watches, so they can't synchronize their mental clock down to the seconds, or intervals thereof.

Let's say that the game is structured so that each prisoner only has access to the following information: the other 19's hat numbers, and the ordinal sequence ( with the time duration between any two elements stripped) of the prisoners getting ready.

Edited July 6, 2009 by bushindo

[Guest]

A strategy could be: everyone calculates n=(the sum of all numbers he sees) modulo 20. If for someone n=0, that one raises his hand immediately. From this everyone else can derive his number. If there isn't anyone for who n=0, you just wait until the 3 minutes are over and everybody knows that nobody can have n=0. So everyone can calculate which numbers he certainly doesn't have, and by this he decreases the amount of possible numbers on his hat (maybe even to 1). This will give everyone a much bigger chance to guess his number right.

this might not be the optimal solution but it is one.

[Guest]

Well, if there are 20 numbers(1-20) and you can see the numbers everybody else has, then simply use the process of elimination. Based on what hat you do not see, that must be your hat.

I have a feeling that I misread something, because my solution is too simple, and I am still groggy.

EDIT; reading some of the above responses, I think that by "Independent" you meant independent of a patter. I thought you meant independent completely (as in no shared numbers). I might revise my answer when I wake up...

Edited July 6, 2009 by Out4Blood4

[Guest]

weird answer but i think it almost works

[Guest]

woops accidentally hit reply

you have 19 people that can see the same guy say guy zero. So now guys one through 19 are assigned a simple task don't raise your hand if zeros number is equal to your position. So it goes through in slow succesion of raising there hand one through 19. Now from guy zeros perspective. He raises his hand when the position that is equal to the modulo 20 he sees. So if he sees modulo 2 then he raises his hand when 2 does. Now the person that doesnt raise his hand in succession is the zeroes guys number.

So what this does. worst case scenario.

Guy zero sees no one not raise there hand. He has a 50-50 chance of guessin 0 or 20. all the others know there number

guy zero never raises his hand (raises it much after the succesion is done). He sees modulo 0 or modulo his number. 50-50 everyone

other then that i think it is 100% but im sure there could be a couple holes

quick addition this might be considered more of timeing (cheating) but the zero guy could raise his hand when the guy that doesnt raise his hand would of to indicate that modulo. That would simply require that if someone didnt raise there hand there was a longer break so that if zero raises his hand it cant be misconstrued. Now i forgot to mention that if one guys task is to choose 0 or 20 its just good luck which could happen to anyone or everyone.

so something like (20/21)^20 everyone lives or 20/21 individually

[Guest]

Before the game start, all prisoner will agree to count from 1 to 20 in a regular rhytm/beat(1 number per seconds) while rising their right hand. The prisoner must rise his/her right hand if the count is the same with the number of the hat of the prisoner beside him/her in the right. Example, if the count is now "10" and beside him/her in the right have a number 10, he/she must be rise his/her right hand. by being observant, you will know what your hat number will be

[Guest]

Probably something along the lines of:

Everyone sums up the hats that they can see.

The first group raises their hands if the sum mod 20 = 0

the second group to raise their hands if their sum mod 20 = 1

the third group to raise their hands if their sum mod 20 = 2

Wait...that doesn't work. What if none of the sums mod 20 is a group number (i.e. there is no sum mod 20 == 2). Shoot. back to the drawing board.

[Guest]

What if, before going into the room or w.e, each prisoner is given a number 1 through to 20. When all have their hats, First those prisoners which can see 1 hat with their nominated # raise their hands, then those who can see 2 of the hats with their # on others' hats, then those who can see 3 etc... ??

[bushindo]

woops accidentally hit reply

you have 19 people that can see the same guy say guy zero. So now guys one through 19 are assigned a simple task don't raise your hand if zeros number is equal to your position. So it goes through in slow succesion of raising there hand one through 19. Now from guy zeros perspective. He raises his hand when the position that is equal to the modulo 20 he sees. So if he sees modulo 2 then he raises his hand when 2 does. Now the person that doesnt raise his hand in succession is the zeroes guys number.

So what this does. worst case scenario.

Guy zero sees no one not raise there hand. He has a 50-50 chance of guessin 0 or 20. all the others know there number

guy zero never raises his hand (raises it much after the succesion is done). He sees modulo 0 or modulo his number. 50-50 everyone

other then that i think it is 100% but im sure there could be a couple holes

quick addition this might be considered more of timeing (cheating) but the zero guy could raise his hand when the guy that doesnt raise his hand would of to indicate that modulo. That would simply require that if someone didnt raise there hand there was a longer break so that if zero raises his hand it cant be misconstrued. Now i forgot to mention that if one guys task is to choose 0 or 20 its just good luck which could happen to anyone or everyone.

so something like (20/21)^20 everyone lives or 20/21 individually

I like this answer. This sounds like it would save all the prisoners 100% of the time. Well done.

[Guest]

What if they just write down what the person to there left has then everyone swaps the paper with the person on the left

[Guest]

Could I have a clarification please?

When it says "The numbers of hats are independent," that basically means repeats are allowed?

[Guest]

independent means each person has a 1/20 chance to get any number.

the independent really means that what any other prisoner got does not alter your chances at all. They are similar to completely separate trials.

Or more complicated like (P(A) intersect P(B))/P(B)= P(A) or P(A)and P(B)=P(A)P(B)

[CaptainEd]

I like this answer. This sounds like it would save all the prisoners 100% of the time. Well done.

Once again, Bushindo, you are far better at interpreting people's suggestions than I. I'm clueless what this procedure was. Here's what I think I understood, and it saves one guy:

* Everybody has a position number, 0 to 19 (or 1 to 20)

* Everybody look at person zero (20). The one person whose position number matches Zero's number raises his hand.

So now, Zero knows his number.

After that, I'm clueless. Somebody does something with "their modulo 20", somebody does something with "their modulo 2", but I don't see how all the other guys learn their numbers.

Could you please translate this procedure?

[bushindo]

Once again, Bushindo, you are far better at interpreting people's suggestions than I. I'm clueless what this procedure was. Here's what I think I understood, and it saves one guy:

* Everybody has a position number, 0 to 19 (or 1 to 20)

* Everybody look at person zero (20). The one person whose position number matches Zero's number raises his hand.

So now, Zero knows his number.

After that, I'm clueless. Somebody does something with "their modulo 20", somebody does something with "their modulo 2", but I don't see how all the other guys learn their numbers.

Could you please translate this procedure?

I think I have an edge in interpreting final's solution because it is along the line of what I was thinking when I posted the puzzle. It's easier to understand someone's instruction when you have a similar roadmap. I think what final was trying to communicate was the following:

Let's label all the prisoners 0-19. Divide the prisoners into two groups: the first group with prisoner 0 and second group with prisoners 1-19.

To win the game, the second group need to communicate Prisoner 0's number to him, and prisoner 0 needs to communicate X to the second group, where X = modulo( P1's hat + P2's hat ... P19's hat , 20 ). For any prisoner in the group P1-P19, if he knows the remainder of (sum of hat 1 to hat 19) /20, then he can figure out his own hat number, since he can see the other 18 in the group.

final's strategy is as follows

1) starting from P1 and going to P19, let each prisoner raise his hand in order, allowing a small pause in between.

2) If any prisoner's index is the same as prisoner 0's hat, then he won't raise his hand at all. So we are guaranteed to have at least 18 prisoners raise their hand. If all 19 raises his hand, then prisoner 0 knows that his number is 20. Otherwise, prisoner 0 can get his hat number from the position of the guy who didn't raise his hand.

3) Prisoner 0, at the same time, would compute X, the sum of hat 1 to hat 19 modulo 20. Prisoner 0 then would communicate X to the rest of the group by raising his hand at the same time as the prisoner whose index correspond to X. In his example, if X = 2, then prisoner 0 would wait until P2's turn, and then raise his hand at the same time as P2.

[Guest]

I haven't been looking at other posts in this thread, so sorry if this has already been figured out, but I don't want it... spoiled

Pretend like you're the guy on your right. If you have the lowest number, raise your hand. If others have the same number (say, three people are number one), try to raise your hand simultaneously. If you have the second lowest number, then raise your hand next. And so on.

So by looking at when the person on your left raises their hand, you know your own number. It wouldn't work if say the second lowest number was three, and there was only one person with the lowest number. But in that case, you have a 50% chance to guess right, and you might be able to tell by how long they hesitate to raise their hand.

So yeah, I have no idea what the probability would be... but I think it'd be pretty good odds

[Guest]

as usual bushindo explains my answer better then i did, but i try. also i have a mistake in my solution because i thought that it was 0-20. I dont know where i gleaned this information from, but its wrong. Now it should be noted that its rare that i say im wrong and honestly almost mean it, so this moment should be cherished.

[roolstar]

Assuming we cannot know the position we will have at the final circle, and that memorizing a number for each other prisoner with us can be tricky.

Just start by chosing one of the prisoners before going in the final circle. We will call him Mr. A

Method 1: CHANGING POSITIONS SIGNALS

Now all we need to so is to look at his number and then by counting clockwise starting from his position in the circle, count as many people as the number on A's hat and that guy raises his hand.

Example: if A has 13 on his hat, the 13th person on his left will raise his hand first. (Now if the number is 20, no hands will be raised after 5 seconds.)

After that, everybody will focus on the second guy to the left of Mr. A and the corresponding person to his number raise his hand this turn.

After 20 rounds, we have effectively told each prisoner the number on his hat.

Method 2: FIXED POSITIONS SIGNALS

In this method, I'm trying to avoid having the prisoners count their new position after each round.

So we can start by the guy on the left of Mr. A being #1 and continuing clockwise till #19. This number represented by the prisoners position will remain till the end of the exercise.

After showing Mr. A his number like in the previous method. Mr. A will then take #1 at the second round, #2 at the third... (In fact taking the place of the guy on which we are focusing in this round) and he will raise his hand if the prisoner's starting position matched the number on his hat by some coincidence.

After 20 rounds, we have effectively told each prisoner the number on his hat.

Oh and by the way,

1- Since the longest round would takes 5 seconds, they should be done before the 3 minutes are up. (and for that METHOD 2 would work a bit better in term on speed)

2- Since we have numbers from 1 to 20 and 20 prisoners (none of them having 20 as an index), there's no chance for all of them to raise their hands before the 20 rounds are up!

My reply comes a bit more than a year after the last reply.

Well, better late than never I suppose

Edited July 31, 2010 by roolstar