[Guest]

This is a twist on a classic puzzle. N prisoners are going to play a game and if they win, they will all be released. They are allowed to develop a team strategy before the game starts, but once it starts, they can't communicate in any way. As each prisoner enters a room, they will be given a hat with a random whole number on it that can be anything from 0 to N-1. For example, if 5 prisoners are playing, they can have any combination of numbers from 0 to 4. It would be possible that all of them would have the same number.

Once all the prisoners are in the room, they all can look at the numbers on all the other prisoners' hats, but they have no way to know the number on their own hat. After looking at the hats, they are then allowed to consider a guess at what number may be on their own hat. But at some point in time, they must simultaneously guess and to win the game, they must all be right.

What is the optimal strategy to maximize their chances to win? And given that they play optimally, what are the chances they will win, expressed as a function of N?

[bushindo]

This is a twist on a classic puzzle. N prisoners are going to play a game and if they win, they will all be released. They are allowed to develop a team strategy before the game starts, but once it starts, they can't communicate in any way. As each prisoner enters a room, they will be given a hat with a random whole number on it that can be anything from 0 to N-1. For example, if 5 prisoners are playing, they can have any combination of numbers from 0 to 4. It would be possible that all of them would have the same number.

Once all the prisoners are in the room, they all can look at the numbers on all the other prisoners' hats, but they have no way to know the number on their own hat. After looking at the hats, they are then allowed to consider a guess at what number may be on their own hat. But at some point in time, they must simultaneously guess and to win the game, they must all be right.

What is the optimal strategy to maximize their chances to win? And given that they play optimally, what are the chances they will win, expressed as a function of N?

This part isn't clear to me. I assume that the prisoners don't go in sequential order and call out their guesses like the typical prisoners and hat puzzle. Also, do the prisoners get to pick when to call out their guesses, or is there a set time limit to consider their guess?

[Guest]

i'm guessing each prisoner can only say the numbers 1 to N.

for 1 prisoner, he can say 1 and gets off.

for 2 prisoners, the first can say the other and he would be right 50% of the time. the second prisoner would then be guaranteed to get off.

for 3 prisoners, the first prisoner would add the two hats. if the number is divisible by 3, he would say 3. if 2 then 2, if neither, then 1.

form this the second prisoner by looking at the last prisoners hat can determine his hat. if he see 3, and prisoner 1 said 1, then he knows his hat is 2, for example. this would guarantee two hats and the first prisoner would have 33% chance.

a similar strategy can be used for N hats.

for example, with 10 prisoners,

let's say the hats are

2,4,3,7,1,3,5,8,4,9

the first prisoner, 2, would add. 4+3+7+1+3+5+8+4+9 = 44. 44 mod 10 = 4. therefore prisoner 1 would say 4. then prisoner 2 would add the other prisoners. 3+7+1+3+5+8+4+9 = 40. 40 mod 10 = 0, so he knows he's wearing 4. and so on.

[Guest]

This part isn't clear to me. I assume that the prisoners don't go in sequential order and call out their guesses like the typical prisoners and hat puzzle. Also, do the prisoners get to pick when to call out their guesses, or is there a set time limit to consider their guess?

You are correct. There is no sequential guessing. To execute a strategy, it would take more time if the number of prisoners is higher. So we could say they get as much time as they want looking at the other hats and considering a guess. Once all the prisoners have indicated they are ready, they all call out their number at the same time.

As for expressing the chances as a function of N. Let's say they have no strategy and all simply guess. Then the chances the group all get it right is 1/(N^N). One player would know he has a 0 and have a 1/1 chance. But the odds get bad really fast. 2 players would be 1/4 and 3 would be 1/9. Optimal strategy does much better.

[Guest]

i'm guessing each prisoner can only say the numbers 1 to N.

for 1 prisoner, he can say 1 and gets off.

for 2 prisoners, the first can say the other and he would be right 50% of the time. the second prisoner would then be guaranteed to get off.

for 3 prisoners, the first prisoner would add the two hats. if the number is divisible by 3, he would say 3. if 2 then 2, if neither, then 1.

form this the second prisoner by looking at the last prisoners hat can determine his hat. if he see 3, and prisoner 1 said 1, then he knows his hat is 2, for example. this would guarantee two hats and the first prisoner would have 33% chance.

a similar strategy can be used for N hats.

for example, with 10 prisoners,

let's say the hats are

2,4,3,7,1,3,5,8,4,9

the first prisoner, 2, would add. 4+3+7+1+3+5+8+4+9 = 44. 44 mod 10 = 4. therefore prisoner 1 would say 4. then prisoner 2 would add the other prisoners. 3+7+1+3+5+8+4+9 = 40. 40 mod 10 = 0, so he knows he's wearing 4. and so on.

In this puzzle there is no sequential guessing. They must all call out their guess at the same time.

[bushindo]

You are correct. There is no sequential guessing. To execute a strategy, it would take more time if the number of prisoners is higher. So we could say they get as much time as they want looking at the other hats and considering a guess. Once all the prisoners have indicated they are ready, they all call out their number at the same time.

As for expressing the chances as a function of N. Let's say they have no strategy and all simply guess. Then the chances the group all get it right is 1/(N^N). One player would know he has a 0 and have a 1/1 chance. But the odds get bad really fast. 2 players would be 1/4 and 3 would be 1/9. Optimal strategy does much better.

This seems to indicate that each prisoner may, at any time he chooses, indicate to the warden or the official that he is ready. I'm making the reasonable assumption that since everyone is in the same room, all prisoners can see when one of their own indicates that he is ready.

1) Since the prisoners can get as much time as they need to think of a guess , they can simply pretend to think for the rest of their natural lives. This is a great option if they are on the death row.

2) Let the prisoners be labelled P_1, P_2, ..., P_n, and let the hats be labeled H_1, H_2, ..., H_n. In this strategy, P_n will always be the first to indicate that he is ready, but P_n would wait x seconds before indicating that he is ready. Let x = H_1* n^(n-1) + H_2* n^(n-2) + .. + H_(n-1). P_1 to P_(n-1) can easily factor their hat values from x. Suppose P_1 goes next, he can easily convey P_n's hat value to him by the same strategy. This method has the drawback that for large n, the sun might burn out before P_n indicates that he is ready. (win chance = 100%, downside = takes a loooong time for large n)

3) Let the prisoners agree on a decided order in which to indicate that they are ready. Let's say the order is P_1, P_2, P_3, ... , P_n. P_1 would wait y seconds before indicating that he is ready, where y is the value of of P_2's hat. P_2 then looks that P_3's hat, and wait precisely that many seconds before indicating that he is ready. Continue all the way to P_n. P_n will then conveys P_1's value during his turn. (Win chance = 100%)

[Guest]

This is a twist on a classic puzzle. N prisoners are going to play a game and if they win, they will all be released. They are allowed to develop a team strategy before the game starts, but once it starts, they can't communicate in any way. As each prisoner enters a room, they will be given a hat with a random whole number on it that can be anything from 0 to N-1. For example, if 5 prisoners are playing, they can have any combination of numbers from 0 to 4. It would be possible that all of them would have the same number.

Once all the prisoners are in the room, they all can look at the numbers on all the other prisoners' hats, but they have no way to know the number on their own hat. After looking at the hats, they are then allowed to consider a guess at what number may be on their own hat. But at some point in time, they must simultaneously guess and to win the game, they must all be right.What is the optimal strategy to maximize their chances to win? And given that they play optimally, what are the chances they will win, expressed as a function of N?

What do you mean they are allowed to consider a geuss? Do they get to think out loud or something?(before they all say their hat number). Or did you just put that in there to let us know they are able to look and think for a while before they answer?

This seems to indicate that each prisoner may, at any time he chooses, indicate to the warden or the official that he is ready. I'm making the reasonable assumption that since everyone is in the same room, all prisoners can see when one of their own indicates that he is ready.

1) Since the prisoners can get as much time as they need to think of a guess , they can simply pretend to think for the rest of their natural lives. This is a great option if they are on the death row.

2) Let the prisoners be labelled P_1, P_2, ..., P_n, and let the hats be labeled H_1, H_2, ..., H_n. In this strategy, P_n will always be the first to indicate that he is ready, but P_n would wait x seconds before indicating that he is ready. Let x = H_1* n^(n-1) + H_2* n^(n-2) + .. + H_(n-1). P_1 to P_(n-1) can easily factor their hat values from x. Suppose P_1 goes next, he can easily convey P_n's hat value to him by the same strategy. This method has the drawback that for large n, the sun might burn out before P_n indicates that he is ready. (win chance = 100%, downside = takes a loooong time for large n)

3) Let the prisoners agree on a decided order in which to indicate that they are ready. Let's say the order is P_1, P_2, P_3, ... , P_n. P_1 would wait y seconds before indicating that he is ready, where y is the value of of P_2's hat. P_2 then looks that P_3's hat, and wait precisely that many seconds before indicating that he is ready. Continue all the way to P_n. P_n will then conveys P_1's value during his turn. (Win chance = 100%)

I think number 2 and 3 would work...you'd just need to determine how you would represent 0....I suppose an immediate response could work...I think for a worse case, other than a large number, could be if their were a bunch of hats that were 0s and 1s...that might get a little confusing

[Guest]

as i understand the problem they all have to answer at the same time so this is the only way i see to do it

so they magically can perfectly tell time so they count down from N*N (the highest sum). The prisoners raise there hand when the sum they can see on the hats is counted (in their head). after the first two they stop. Now this can be allowed because to respond simultaneously they have to be able to signal when to start anyway so small signalling must be allowed. Anyway from these two numbers everyone knows there number. then one person raises there hand at some random time after this and then they all say there numbers a second later (this is just to simlutaneous the math is already done).

other then this if they have to respond simultaneously without signaling they would have had to have set a set time to speak before hand and without any other communication they each only have a 1/n chance of getting it right.

[Guest]

This seems to indicate that each prisoner may, at any time he chooses, indicate to the warden or the official that he is ready. I'm making the reasonable assumption that since everyone is in the same room, all prisoners can see when one of their own indicates that he is ready.

1) Since the prisoners can get as much time as they need to think of a guess , they can simply pretend to think for the rest of their natural lives. This is a great option if they are on the death row.

2) Let the prisoners be labelled P_1, P_2, ..., P_n, and let the hats be labeled H_1, H_2, ..., H_n. In this strategy, P_n will always be the first to indicate that he is ready, but P_n would wait x seconds before indicating that he is ready. Let x = H_1* n^(n-1) + H_2* n^(n-2) + .. + H_(n-1). P_1 to P_(n-1) can easily factor their hat values from x. Suppose P_1 goes next, he can easily convey P_n's hat value to him by the same strategy. This method has the drawback that for large n, the sun might burn out before P_n indicates that he is ready. (win chance = 100%, downside = takes a loooong time for large n)

3) Let the prisoners agree on a decided order in which to indicate that they are ready. Let's say the order is P_1, P_2, P_3, ... , P_n. P_1 would wait y seconds before indicating that he is ready, where y is the value of of P_2's hat. P_2 then looks that P_3's hat, and wait precisely that many seconds before indicating that he is ready. Continue all the way to P_n. P_n will then conveys P_1's value during his turn. (Win chance = 100%)

When I say no communication I mean it. Using time to signal would be communication in my book. There are no tricks here. The only things they can consider are the, agreed to, team strategy and the hat numbers of the other players. That's it.

[Guest]

as i understand the problem they all have to answer at the same time so this is the only way i see to do it

so they magically can perfectly tell time so they count down from N*N (the highest sum). The prisoners raise there hand when the sum they can see on the hats is counted (in their head). after the first two they stop. Now this can be allowed because to respond simultaneously they have to be able to signal when to start anyway so small signalling must be allowed. Anyway from these two numbers everyone knows there number. then one person raises there hand at some random time after this and then they all say there numbers a second later (this is just to simlutaneous the math is already done).

other then this if they have to respond simultaneously without signaling they would have had to have set a set time to speak before hand and without any other communication they each only have a 1/n chance of getting it right.

A assure everyone there is no trick and timing is not involved.

And here's a hint, the classic version of this puzzle has all the same conditions but the goal of the team is to make sure, at least one prisoner gets his number right. Using an optimal strategy, they can do this. Needless to say, the strategy that guarantees at least one correct answer is quite different from the one where they are trying to all be right. But, if you solve one, you will solve the other. Trust me, this is a great puzzle and there is no trick answer. Pure logic.

[Guest]

This is a twist on a classic puzzle. N prisoners are going to play a game and if they win, they will all be released. They are allowed to develop a team strategy before the game starts, but once it starts, they can't communicate in any way. As each prisoner enters a room, they will be given a hat with a random whole number on it that can be anything from 0 to N-1. For example, if 5 prisoners are playing, they can have any combination of numbers from 0 to 4. It would be possible that all of them would have the same number.

Once all the prisoners are in the room, they all can look at the numbers on all the other prisoners' hats, but they have no way to know the number on their own hat. After looking at the hats, they are then allowed to consider a guess at what number may be on their own hat. But at some point in time, they must simultaneously guess and to win the game, they must all be right.

What is the optimal strategy to maximize their chances to win? And given that they play optimally, what are the chances they will win, expressed as a function of N?

The way this reads to me:

Each prisoner's hat number is independent of the other hat numbers.

Each prisoner may be given a hat number that has already been given.

Each prisoner's hat is randomly assigned.

Each prisoner must remain silent and still after entering the room (i.e. each prisoner enters a "dark stall" and after all stalls are filled, the stalls are all lit so each prisoner can see the other hat numbers).

After some time t, each prisoner must yell out their own hat number (i.e. each prisoner has a button in front of them that indicates they are ready. No prisoner can see when the others have pressed their buttons (or can see the prisoners pressing their buttons). Once all the buttons have been pressed, the stalls go dark. At this time, each prisoner must yell out their own hat number.

Or reworded to my own understanding:

Each prisoner is isolated from each other and assigned a number unknown to that prisoner (secret numbers known to the warden). Each prisoner is given a slip of paper that has the other prisoners' numbers on it. The prisoner is now allowed to write down what they think their own number is. The game is won if and only if each prisoner writes down their own number.

1/N^N no matter the strategy. In other words, if each number is independent and random and repeatable, how can i gather any information about my own number if there are 6 prisoners and i'm shown

00000 versus 13142 versus 12345 versus ...

[Guest]

i dont see it

this is like n independent people. They have no contact. The numbers are independent of eachother. If they cant interact at all after the numbers are assigned then this is

n independent events each with a probability of 1/n success.

To explain again assume your one of them you get your number, even if you can see everyone elses you cant interact and their numbers have nothing to do with yours (knowing theres tells you nothing about your number) . You have to react simultaneously but you cant communicate so the time to answer had to be set before (or the previous example of buttons that no one can see). So what information do you have ...none. What information can you give to help others... none.

so no offense but i think you have a flaw in logic or wording of the puzzle...but who knows the universe might have reinvented the laws of physics since i last looked or maybe theyre cats so they dont die they just lose one life. or maybe the gun isnt loaded....

And timing does have to do with it because they have to answer at the exact same time. So it influences the whole event.

[bushindo]

The way this reads to me:

Each prisoner's hat number is independent of the other hat numbers.

Each prisoner may be given a hat number that has already been given.

Each prisoner's hat is randomly assigned.

Each prisoner must remain silent and still after entering the room (i.e. each prisoner enters a "dark stall" and after all stalls are filled, the stalls are all lit so each prisoner can see the other hat numbers).

After some time t, each prisoner must yell out their own hat number (i.e. each prisoner has a button in front of them that indicates they are ready. No prisoner can see when the others have pressed their buttons (or can see the prisoners pressing their buttons). Once all the buttons have been pressed, the stalls go dark. At this time, each prisoner must yell out their own hat number.

Or reworded to my own understanding:

Each prisoner is isolated from each other and assigned a number unknown to that prisoner (secret numbers known to the warden). Each prisoner is given a slip of paper that has the other prisoners' numbers on it. The prisoner is now allowed to write down what they think their own number is. The game is won if and only if each prisoner writes down their own number.

1/N^N no matter the strategy. In other words, if each number is independent and random and repeatable, how can i gather any information about my own number if there are 6 prisoners and i'm shown

00000 versus 13142 versus 12345 versus ...

Not to beat a dead horse, but even assuming the above scenario there is a way to convey information between the prisoners. Let's say that when each prisoner is ready, he presses a button, but no other prisoners can see the act. The light will dim when all buttons are pressed to let the prisoners know that all buttons have been pressed.

Let all prisoners except the first prisoner (P1) immediately press the button to indicate that he is ready when the game just starts. P1 then looks at all the hats he sees and convert that into a base-N number, call it x. Wait x seconds before indicating that he is ready, thus dimming the lights. All prisoners except P1 can then factor his own number from x.

Another possible way to solve this without using the time variable is to assume that each prisoner can see the others indicating whether they are ready or not. The order in which the prisoners indicate they are ready may convey some information also. But not as much.

There probably is a flaw in the logic or wording of this puzzle, as final have observed. With absolutely no communication between the prisoners during the game, which the original post seems to suggest, there is no way to improve the (1/n)^n odds.

[Guest]

The way this reads to me:

Each prisoner's hat number is independent of the other hat numbers.

Each prisoner may be given a hat number that has already been given.

Each prisoner's hat is randomly assigned.

Each prisoner must remain silent and still after entering the room (i.e. each prisoner enters a "dark stall" and after all stalls are filled, the stalls are all lit so each prisoner can see the other hat numbers).

After some time t, each prisoner must yell out their own hat number (i.e. each prisoner has a button in front of them that indicates they are ready. No prisoner can see when the others have pressed their buttons (or can see the prisoners pressing their buttons). Once all the buttons have been pressed, the stalls go dark. At this time, each prisoner must yell out their own hat number.

Or reworded to my own understanding:

Each prisoner is isolated from each other and assigned a number unknown to that prisoner (secret numbers known to the warden). Each prisoner is given a slip of paper that has the other prisoners' numbers on it. The prisoner is now allowed to write down what they think their own number is. The game is won if and only if each prisoner writes down their own number.

1/N^N no matter the strategy. In other words, if each number is independent and random and repeatable, how can i gather any information about my own number if there are 6 prisoners and i'm shown

00000 versus 13142 versus 12345 versus ...

All of your assumptions are correct. And the function you have for the chances is correct if they don't use a strategy. The team strategy is all important, and increases your chances an enormous amount. What I love about this puzzle is, it seems completely impossible, yet the solution is wonderfully simple.

[Guest]

Not to beat a dead horse, but even assuming the above scenario there is a way to convey information between the prisoners. Let's say that when each prisoner is ready, he presses a button, but no other prisoners can see the act. The light will dim when all buttons are pressed to let the prisoners know that all buttons have been pressed.

Let all prisoners except the first prisoner (P1) immediately press the button to indicate that he is ready when the game just starts. P1 then looks at all the hats he sees and convert that into a base-N number, call it x. Wait x seconds before indicating that he is ready, thus dimming the lights. All prisoners except P1 can then factor his own number from x.

Another possible way to solve this without using the time variable is to assume that each prisoner can see the others indicating whether they are ready or not. The order in which the prisoners indicate they are ready may convey some information also. But not as much.

There probably is a flaw in the logic or wording of this puzzle, as final have observed. With absolutely no communication between the prisoners during the game, which the original post seems to suggest, there is no way to improve the (1/n)^n odds.

That would be cheating. No communication. Only use the numbers on the other hats and the team strategy. No timing.

[Guest]

i dont see it

this is like n independent people. They have no contact. The numbers are independent of eachother. If they cant interact at all after the numbers are assigned then this is

n independent events each with a probability of 1/n success.

To explain again assume your one of them you get your number, even if you can see everyone elses you cant interact and their numbers have nothing to do with yours (knowing theres tells you nothing about your number) . You have to react simultaneously but you cant communicate so the time to answer had to be set before (or the previous example of buttons that no one can see). So what information do you have ...none. What information can you give to help others... none.

so no offense but i think you have a flaw in logic or wording of the puzzle...but who knows the universe might have reinvented the laws of physics since i last looked or maybe theyre cats so they dont die they just lose one life. or maybe the gun isnt loaded....

And timing does have to do with it because they have to answer at the exact same time. So it influences the whole event.

I guarantee no flaws. This is a great puzzle. All team members see every number but their own. So they are sharing quite a bit of information. If 10 players are in the game, Player 1 will see 8 of the same numbers that player 2 sees. And they can base their guess in a way that correlates with their team members.

[Guest]

I guarantee no flaws. This is a great puzzle. All team members see every number but their own. So they are sharing quite a bit of information. If 10 players are in the game, Player 1 will see 8 of the same numbers that player 2 sees. And they can base their guess in a way that correlates with their team members.

Sharing quite a bit of useless information, since they cannot in any way communicate or signal to each other.

And how is that supposed to help you determine what is on your hat?

So if P1 has a 2 on his hat, and P2 has a 0 on his hat...the other 8 that they see all have a 6 on their hats....and that's all the info they can use, how is that supposed to get P1 to say 2, and P2 to say 0?

I just don't see any strategy that would work for every scenario....I geuss I would ruin it for everybody if I was put in that situation..

[Guest]

Sharing quite a bit of useless information, since they cannot in any way communicate or signal to each other.

And how is that supposed to help you determine what is on your hat?

So if P1 has a 2 on his hat, and P2 has a 0 on his hat...the other 8 that they see all have a 6 on their hats....and that's all the info they can use, how is that supposed to get P1 to say 2, and P2 to say 0?

I just don't see any strategy that would work for every scenario....I geuss I would ruin it for everybody if I was put in that situation..

I understand your frustration. I found this puzzle quite confounding also. I'm not sure of the forum etiquette where posting solutions is concerned. I was am going to post the solution tomorrow. But first, here is a hint that may also convince you that a solution is quite possible.

First you are absolutely correct that there is nothing each player can do that will increase his individual chances that he will guess correctly. No matter what they do, each prisoner has exactly a 1/N chance of being right. But here is where the awesome power of team strategy comes into play.

In the version of the game where the team is trying to all get their hat numbers right, it is possible that, even though each individual has a 1/N chance, the team is also 1/N to get all their hats right!

If the task is to ensure that at least 1 prisoner is right, they can do it by also making sure that exactly 1 will get it right. This also means that all the other prisoners will be wrong. They can't know who will be right, just that 1 of them will be right.

As you can see, in each scenario, at the individual level, they are all 1/N, so we haven't defied the laws of probability. They've simply found a way to distribute their guesses to accomplish the task (or in the case of all of them getting it right, maximized their chances).

The proper strategy is a powerful thing. If 10 prisoners play the game where they all have to be right, they can be 1/10 to succeed instead of 1/10^10. Quite an improvement.

Edited June 29, 2009 by howardl1963

[CaptainEd]

S1: each player chooses the smallest permissible number that he/she does not see

S2: each player chooses the smallest permissible number that he/she DOES see

S3: S1, largest

S4: S2, largest

[Guest]

I think I've got it.

to choose a common remainder when dividing the sum of all hats, including your own, by N. When the sum of their hats is divided by N, the result must be between 0 and N-1, inclusive. While no prisoner know what this remainder is, each can determine what his/her number must be in order to achieve an arbitrary remainder established by the group.

For example, assume there are 5 prisoners, with hats of 0,1,2,3,4. They decide to use a remainder of 0. The prisoner with the number 3 sees that the sum of the remaining prisoners' hats is 7. 7 divided by 5 gives a remainder of 2. In order for the sum of the group to have a remainder of 0 when divided by 5, the sum must be 10. Therefore he/she guesses 3 as his/her number. Similarly, each prisoner can use this method, and they are then either all correct or all incorrect.

Clearly, the probability that the group chooses the correct remainder is 1/N.

Edited June 29, 2009 by hookemhorns

[Guest]

Each prisoner does the following:

1) Adds the numbers on all the hats that he sees

2) Subtract the total from (N-1)^2

3) Divide the answer by N

4) The remainder is the number he announces.

The chances of getting the answer right is 1/N, but if he gets it right, everyone gets it right, so overall the chances of freedom for all are 1/N.

[dyalDragon]

each prisoner is assigned another prisoner to watch

if the person you are watching has a 0 you raise your hand immediately...after 1 second if they have a 1 you raise your hand...after 2 seconds if they have a 2...etc

this way everyone knows their own number

[Guest]

Each prisoner does the following:

1) Adds the numbers on all the hats that he sees

2) Subtract the total from (N-1)^2

3) Divide the answer by N

4) The remainder is the number he announces.

The chances of getting the answer right is 1/N, but if he gets it right, everyone gets it right, so overall the chances of freedom for all are 1/N.

I'll be damned that works.

[Guest]

its quite simple your just guessing what the numbers add up to and go from there...quite simple...

however i think all you have to do is add the numbers you see mod it. And then if you agreed to guess it would have a remainder of A then guess A-n. But anyway good job guys i thought of something similar and dismissed as impossible...

[bushindo]

its quite simple your just guessing what the numbers add up to and go from there...quite simple...

however i think all you have to do is add the numbers you see mod it. And then if you agreed to guess it would have a remainder of A then guess A-n. But anyway good job guys i thought of something similar and dismissed as impossible...

That was a good solution. Serves me right for not thinking outside the box.

[Guest]

its quite simple your just guessing what the numbers add up to and go from there...quite simple...

however i think all you have to do is add the numbers you see mod it. And then if you agreed to guess it would have a remainder of A then guess A-n. But anyway good job guys i thought of something similar and dismissed as impossible...

Yes, this is the solution. The puzzle was given to me a little different and I changed it to add the twist of all being right. The original puzzle calls for at least one prisoner getting their number right. You may want to think about that one before looking in my spoiler:

There is no way to increase the chances of each prisoner getting it right, but we can make sure one gets it right and everyone else gets it wrong. All the hats must add up to something Mod(N). Since there are only N possible sums, the prisoners number themselves from 0 to N-1. Prisoner 0 will guess that the sum of all the hats is 0, prisoner 1 will guess the sum is 1 and so on. If a prisoner's guess is G then uses this formula: G-(sum of seen hats) as his guess.