Support NeoGAF

[efyu_lemonardo]

Split the paper in two, write a new (same) number on both halves, and affix one of the halves to the top of the cell over the old number that the warden put there.

that's cheating, but you get brownie points for creativity
edit: reposting for the new page:

Hello again fellow riddle lovers!

Bumping this thread with a new doozy that I recently learned. As with the last riddle, knowledge of higher math is useful but not at all necessary, logic and perseverance are most important. I encourage everyone to participate and contribute! No one should feel bad for getting stumped, and the answer is (in my opinion) quite cool and satisfying.

• Ten prisoners are placed in ten cells. Above each cell the warden places a random number selected from {1,2,3,4,5,6,7,8,9,10} - in other words repetition is allowed and not every number needs to show up.
  [*]Each prisoner is able to look outside their cell and see the nine other cells and their respective numbers. No prisoner is able to see the number above their own cell, and communication between the prisoners is forbidden.
  [*]The warden offers the following challenge to the group: If a single prisoner is able to correctly guess the number above their cell, the entire group will be set free. Each prisoner is given a piece of paper to write down their guess, and after a moment the warden goes around the room, collecting each paper and comparing it with the number above that prisoner's cell - in other words each prisoner has only one guess and while writing down their guess does not know what number the others have guessed, or whether they guessed correctly or not.
  [*]Before the challenge begins (and before the numbers are placed above the cells) the prisoners are given a moment to come up with a strategy that is guaranteed to win (in other words they don't see the numbers until after agreeing on their plan). Can you find the strategy?

Here's a small optional tip to get you started:

Spoiler

try to solve a simplified version of this riddle with 2 prisoners instead of 10. If you can, does your chosen strategy work with 3 prisoners as well?

GOOD LUCK!

 

[iosa]

Each prisoner is given a piece of paper to write down their guess, and after a moment the warden goes around the room, collecting each paper and comparing it with the number above that prisoner's cell.

Hello.

They've got only one try, right?

 

[SolidusDave]

Each prisoner is able to look outside their cell and see the nine other cells and their respective numbers.No prisoner is able to see the number above their own cell, and communication between the prisoners is forbidden.

Before the challenge begins (and before the numbers are placed above the cells) the prisoners are given a moment to come up with strategy that is guaranteed to win.

This confused me. So does each prisoner know the other 9 numbers or not?

Also, that warden is a threat to society

 

[Robot Pants]

Send them to Iosefka.

Hahaha I genuinely laughed out loud

 

[efyu_lemonardo]

Hello.

They've got only one try, right?

This confused me. So does each prisoner know the other 9 numbers or not?

Also, that warden is a threat to society

I'll try to rephrase that to make it more clear. The point was that the prisoners have no knowledge of the numbers at the time they come up with a strategy. And that afterwards, they are allowed a single guess, and that they do not know what the other prisoners have guessed.

 

[SolidusDave]

I'll try to rephrase that to make it more clear. The point was that the prisoners have no knowledge of the numbers at the time they come up with a strategy. And that afterwards, they are allowed a single guess, and that they do not know what the other prisoners have guessed.

Thanks.
...thought about it and will be interested to see the solution lol
Because currently I can't think of a strategy that is a 100% win if the given number is truly random and independent of the numbers of the other inmates.

 

[FinalD]

I'll try to rephrase that to make it more clear. The point was that the prisoners have no knowledge of the numbers at the time they come up with a strategy. And that afterwards, they are allowed a single guess, and that they do not know what the other prisoners have guessed.

Do all prisoners need to have guessed before the warden checks the first cell? Is there an order in which the warden checks the cells? Does the warden show the latest guess to the other prisoners?

 

[efyu_lemonardo]

Do all prisoners need to have guessed before the warden checks the first cell? Is there an order in which the warden checks the cells? Does the warden show the latest guess to the other prisoners?

order of guessing is irrelevant.
the prisoners also don't know if previous guesses were correct or not before the warden comes around to their cell.
edit: You can think of it as if all papers are collected and compared and only at the end is it revealed if someone was right or not.

Thanks.
...thought about it and will be interested to see the solution lol
Because currently I can't think of a strategy that is a 100% win if the given number is truly random and independent of the numbers of the other inmates.

did you try the tip?

 

[Feep]

Are the prisoners allowed to write abstract information on the paper ("the previous guess plus one", "all numbers summed divided by ten", etc.)?

If the problem is a genuine simplification of "you can see nine other numbers which have absolutely no relevance to you and there is literally no way to communicate information in any form to other prisoners prior to your guess and the guess must be a single integer from 1 to 10" I don't see it being possible...

 

[SolidusDave]

did you try the tip?

Even with two people and the numbers 1 and 2 I have my troubles...

Inmate A sees Inmate B having the number 2. But his own numbers can still be 1 or 2... I don't get how it even matters that he can see the numbers of the other inmate if his number is truly random.
edit: see above. I was under the assumption that they are only allowed to write the number itself.

 

[efyu_lemonardo]

Are the prisoners allowed to write abstract information on the paper ("the previous guess plus one", "all numbers summed divided by ten", etc.)?

If the problem is a genuine simplification of "you can see nine other numbers which have absolutely no relevance to you and there is literally no way to communicate information in any form to other prisoners prior to your guess and the guess must be a single integer from 1 to 10" I don't see it being possible...

the prisoners have to write down a final number on their paper, nothing abstract.

I'll also add a small hint:

Spoiler

your logic is sound, and since this riddle has an answer, that means something about your assumptions is wrong.

Even with two people and the numbers 1 and 2 I have my troubles...

Inmate A sees Inmate B having the number 2. But his own numbers can still be 1 or 2... I don't get how it even matters that he can see the numbers of the other inmate if his number is truly random.
edit: see above. I was under the assumption that they are only allowed to write the number itself.

Spoiler

try writing down all possibilities for the 2 prisoner problem, there aren't many.

 

[milanbaros]

I don't see how it is possible without some form of communication. I could see it as possible with one way communication but not zero.

Interested in the answer.

 

[efyu_lemonardo]

I don't see how it is possible without communication. I could see it as possible with one way communication but not zero.

there is communication in the form of an initial strategy, but nothing beyond that.

 

[The_Poet]

A good strategy would

Spoiler

be for them all to agree on guessing the same number (i.e. all guess '3')

but that's not a guaranteed win...

 

[iosa]

Thanks.
...thought about it and will be interested to see the solution lol
Because currently I can't think of a strategy that is a 100% win if the given number is truly random and independent of the numbers of the other inmates.

I'm there too.

Since it's random, I would have think that some kind of communications would be allowed (ie: Prisonner 1 make a guess and everyone see it, then Prisonner 2 make is guess...)

 

[efyu_lemonardo]

A good strategy would

Spoiler

be for them all to agree on guessing the same number (i.e. all guess '3')

but that's not a guaranteed win...

since not every number is guaranteed to show up this isn't a good strategy


edit: Also, don't ignore what information you do have! There are no red herrings in this riddle.

 

[Triggerhappytel]

Solved Riddle:
You walk down a road until you hit a fork. One direction will lead you to your destination, the other will leave you lost. There are two men at the fork in the road. One always lies, the other always tells the truth. You can only ask one question and only one is allowed to answer. What do you ask and who do you ask it to in order to determine the correct way to go. Both know the correct way.

Isn't this riddle from Labyrinth?

Yep, Labyrinth was my first thought too. You always ask one of the doors what the other would say, and it will always be filtered through the liar so you must do the opposite of what they say. However, she does do this in the film and still falls down a trap, so that bit has always confused me.

As for the other one with three questions, I'm not entirely sure. I'll try to work it out before reading answers in this topic.

 

[efyu_lemonardo]

Yep, Labyrinth was my first thought too. You always ask one of the doors what the other would say, and it will always be filtered through the liar so you must do the opposite of what they say. However, she does do this in the film and still falls down a trap, so that bit has always confused me.

As for the other one with three questions, I'm not entirely sure. I'll try to work it out before reading answers in this topic.

there are also other riddles after that if you're interested, including one from today.

 

[Diprosalic]

i will be quite surprised if efyu provides a decent answer.

 

[The_Poet]

since not every number is guaranteed to show up this isn't a good strategy

Yes, but its better then random guessing.

I'm thinking of maybe everyone guessing the median number that they see around them?

idk

 

[milanbaros]

since not every number is guaranteed to show up this isn't a good strategy


edit: Also, don't ignore what information you do have! There are no red herrings in this riddle.

Could they all just agree to look up at the same time and the person on the far left writes the the next person along's number. The person one along doesn't write a number but instead just =left cell guess.

 

[efyu_lemonardo]

i will be quite surprised if efyu provides a decent answer.

I'm an honest riddler, and I try to bring only the kinds of riddles where effort is rewarded, like the last one I asked in here.
try the tip for starters.

Yes, but its better then random guessing.

I'm thinking of maybe everyone guessing the median number that they see around them?

idk

Like the previous riddle I posted here, the answer is not based on statistical analysis. There is a solution that is guaranteed to work.

 

[Triggerhappytel]

there are also other riddles after that if you're interested, including one from today.

I'm just reading your bump now. My mind hurts.

 

[efyu_lemonardo]

Could they all just agree to look up at the same time and the person on the far left writes the the next person along's number. The person one along doesn't write a number but instead just =left cell guess.

How would this person know what their neighbor to the left guessed?

I'm just reading your bump now. My mind hurts.

you can also try the previous one from my earlier bump

 

[SolidusDave]

Spoiler

try writing down all possibilities for the 2 prisoner problem, there aren't many.

Ok I think I got something....

Spoiler

Inmates: [A, B]
Numbers: [1, 2]

A1;B1
A1;B2
A2;B1
A2;B2

50% chance to get it right for one of them. So I guess the solution is to maximize that chance by (basically) combining the chances of the other person with your own. As they get all free if only one answer is correct.
A sees B has a 1. Then he is supposed to write down 2 for himself.
That covers A2;B1
If B has a 2, A writes 1.
That covers A1;B2
However, if B sees that A has a 1, he also writes down 1. Same for the 2
So that covers A1;B1 and A2;B2.

As all 4 combinations are covered, the chance is now 100% that one of them is right.
Will that work for 10 people?

 

[liliththepale]

Ok I think I got something....

Spoiler

Inmates: [A, B]
Numbers: [1, 2]

A1;B1
A1;B2
A2;B1
A2;B2

50% chance to get it right for one of them. So I guess the solution is to maximize that chance by (basically) combining the chances of the other person with your own. As they get all free if only one answer is correct.
A sees B has a 1. Then he is supposed to write down 2 for himself.
That covers A2;B1
If B has a 2, A writes 1.
That covers A1;B2
However, if B sees that A has a 1, he also writes down 1. Same for the 2
So that covers A1;B1 and A2;B2.

As all 4 combinations are covered, the chance is now 100% that one of them is right.
Will that work for 10 people?

No, that counts as communication.

 

[SolidusDave]

No, that counts as communication.

Well they know that the numbers 1-10 will come up so they can agree who has to write what for each number of each other person beforehand. Afterwards they don't need to communicate anymore, only look at the revealed numbers.

 

[efyu_lemonardo]

Ok I think I got something....

Spoiler

As all 4 combinations are covered, the chance is now 100% that one of them is right.
Will that work for 10 people?

As said in the tip:

Spoiler

the challenge now is figuring out how to extrapolate this strategy for 3 prisoners?

 

[efyu_lemonardo]

No, that counts as communication.

No, that strategy is fine since it can be decided upon before knowing the numbers on the other cells.

Well they know that the numbers 1-10 will come up so they can agree what to write for each number of each person beforehand. Afterwards they don't need to communicate anymore, only look at the revealed numbers.

correct.

 

[UncleSporky]

If the problem is a genuine simplification of "you can see nine other numbers which have absolutely no relevance to you and there is literally no way to communicate information in any form to other prisoners prior to your guess and the guess must be a single integer from 1 to 10" I don't see it being possible...

I'll also add a small hint:

Spoiler

your logic is sound, and since this riddle has an answer, that means something about your assumptions is wrong.

If you're saying that the general logic of the riddle as laid out by Feep is incorrect, then it's nobody's fault but your own. You didn't provide clear enough information.

Even if no communication is explicitly allowed, are you assuming the prisoners cheat in some way anyway, such as tapping on the walls of their cells? In other words, is there something about the fact that it's prisoners that makes the riddle unique?


Suppose you phrase it this way:

10 british gentlemen live on a street next to each other. The mailman says he's going to give all of them a fabulous prize if they can guess the number he's randomly assigned to their house, but the numbers are in his head, he's not attaching a paper to the house or anything. He delivers a letter to each man that contains a slip of paper with everyone else's numbers on it (it says "address 301: 5, address 303: 7, etc.).

Is that solvable in the same way, and if not, why not?

 

[liliththepale]

Well they know that the numbers 1-10 will come up so they can agree who has to write what for each number of each other person beforehand. Afterwards they don't need to communicate anymore, only look at the revealed numbers.

Oh, you know what, I misread your post. I think you're actually right.

 

[Feep]

Ok I think I got something....

Spoiler

Inmates: [A, B]
Numbers: [1, 2]

A1;B1
A1;B2
A2;B1
A2;B2

50% chance to get it right for one of them. So I guess the solution is to maximize that chance by (basically) combining the chances of the other person with your own. As they get all free if only one answer is correct.
A sees B has a 1. Then he is supposed to write down 2 for himself.
That covers A2;B1
If B has a 2, A writes 1.
That covers A1;B2
However, if B sees that A has a 1, he also writes down 1. Same for the 2
So that covers A1;B1 and A2;B2.

As all 4 combinations are covered, the chance is now 100% that one of them is right.
Will that work for 10 people?

Huh, yeah. That does work for two people...surprising.

 

[The Friendly Monster]

I think I have a solution:

Spoiler

First we need the prisoners to number themselves 1-10, the order in which the guard placed the numbers will do.

Consider the sum of all the numbers above the cells modulo 10 (i.e. the last digit when you add them all up). There are 10 possibilities.

Prisoner 1 should add up all of the other numbers she sees and then make a guess for her own number which would make the total have last digit 1. e.g. prisoner 1 adds up all the other numbers and gets 47, therefore prisoner 1 should guess 4 for her own number (47+4 = 51).

Prisoner 2 does the same so that the total has last digit 2. And so on up to prisoner 10 who guesses so that the last digit is 0. In each case there is only one possible guess they can make which solves this.

Now of course the total of all the numbers must have a sum, and the prisoner corresponding to the actual last digit must have guessed correctly. Everyone is free.

 

[SolidusDave]

As said in the tip:

Spoiler

the challenge now is figuring out how to extrapolate this strategy for 3 prisoners?

Spoiler

Inmates: [A, B, C]
Numbers: [1, 2, 3]

A1;B1;C1
A1;B1;C2
A1;B1;C3
A1;B2;C1
A1;B2;C2
A1;B2;C3
A1;B3;C1
A1;B3;C2
A1;B3;C3

A2;B1;C1
A2;B1;C2
A2;B1;C3
A2;B2;C1
A2;B2;C2
A2;B2;C3
A2;B3;C1
A2;B3;C2
A2;B3;C3

A3;B1;C1
A3;B1;C2
A3;B1;C3
A3;B2;C1
A3;B2;C2
A3;B2;C3
A3;B3;C1
A3;B3;C2
A3;B3;C3


I'm not sure those inmates can even memorize every combination they have been assigned to

welll...I'll try later again. Back to work

 

[Diprosalic]

if they are smart enough to solve this in a group of 10 and remember the strategy they wouldn't be in a prison.
this is not solvable.

 

[efyu_lemonardo]

If you're saying that the general logic of the riddle as laid out by Feep is incorrect, then it's nobody's fault but your own. You didn't provide clear enough information.

No, Feep's logic was sound, I was just being very subtle about how I replied.

His statement was: 'assuming "something" implies the riddle is unsolvable", or in other words if A is true then B is false. The relationship between A and B is correct, but B is in fact true. What does that say about A?

Even if no communication is explicitly allowed, are you assuming the prisoners cheat in some way anyway, such as tapping on the walls of their cells? In other words, is there something about the fact that it's prisoners that makes the riddle unique?


Suppose you phrase it this way:

10 british gentlemen live on a street next to each other. The mailman says he's going to give all of them a fabulous prize if they can guess the number he's randomly assigned to their house, but the numbers are in his head, he's not attaching a paper to the house or anything. He delivers a letter to each man that contains a slip of paper with everyone else's numbers on it (it says "address 301: 5, address 303: 7, etc.).

Is that solvable in the same way, and if not, why not?

Your version is solvable in the same way as mine.

 

[Feep]

I think I have a solution:

Spoiler

First we need the prisoners to number themselves 1-10, the order in which the guard placed the numbers will do.

Consider the sum of all the numbers above the cells modulo 10 (i.e. the last digit when you add them all up). There are 10 possibilities.

Prisoner 1 should add up all of the other numbers she sees and then make a guess for her own number which would make the total have last digit 1. e.g. prisoner 1 adds up all the other numbers and gets 47, therefore prisoner 1 should guess 4 for her own number (47+4 = 51).

Prisoner 2 does the same so that the total has last digit 2. And so on up to prisoner 10 who guesses so that the last digit is 0. In each case there is only one possible guess they can make which solves this.

Now of course the total of all the numbers must have a sum, and the prisoner corresponding to the actual last digit must have guessed correctly. Everyone is free.

Son you smart

Spoiler

This solution is actually the same as Solidus Dave's solution, but his solution would be described in binary (base 2) to get the last digit to their unique cell number. The reason the riddle is presented with ten prisoners, rather than any other number, is to allow the elegant use of the "last digit" without forcing people to use weird number bases.

Very clever indeed. It guarantees all others will fail to guarantee that one is correct.

 

[Dascu]

I think I have a solution:

Spoiler

First we need the prisoners to number themselves 1-10, the order in which the guard placed the numbers will do.

Consider the sum of all the numbers above the cells modulo 10 (i.e. the last digit when you add them all up). There are 10 possibilities.

Prisoner 1 should add up all of the other numbers she sees and then make a guess for her own number which would make the total have last digit 1. e.g. prisoner 1 adds up all the other numbers and gets 47, therefore prisoner 1 should guess 4 for her own number (47+4 = 51).

Prisoner 2 does the same so that the total has last digit 2. And so on up to prisoner 10 who guesses so that the last digit is 0. In each case there is only one possible guess they can make which solves this.

Now of course the total of all the numbers must have a sum, and the prisoner corresponding to the actual last digit must have guessed correctly. Everyone is free.

 

[milanbaros]

I think I have a solution:

Spoiler

First we need the prisoners to number themselves 1-10, the order in which the guard placed the numbers will do.

Consider the sum of all the numbers above the cells modulo 10 (i.e. the last digit when you add them all up). There are 10 possibilities.

Prisoner 1 should add up all of the other numbers she sees and then make a guess for her own number which would make the total have last digit 1. e.g. prisoner 1 adds up all the other numbers and gets 47, therefore prisoner 1 should guess 4 for her own number (47+4 = 51).

Prisoner 2 does the same so that the total has last digit 2. And so on up to prisoner 10 who guesses so that the last digit is 0. In each case there is only one possible guess they can make which solves this.

Now of course the total of all the numbers must have a sum, and the prisoner corresponding to the actual last digit must have guessed correctly. Everyone is free.

I love it.

 

[Ventilaator]

Man I wish I had known that this thread expanded to more riddles beyond the initial Labyrinth one. I love this stuff.

 

[efyu_lemonardo]

Spoiler

Now of course the total of all the numbers must have a sum, and the prisoner corresponding to the actual last digit must have guessed correctly. Everyone is free.

Spoiler

didn't expect it to be solved this quickly! well done!

Spoiler

could you explain your process?

 

[The Friendly Monster]

Son you smart

Spoiler

This solution is actually the same as Solidus Dave's solution, but his solution would be described in binary (base 2) to get the last digit to their unique cell number. The reason the riddle is presented with ten prisoners, rather than any other number, is to allow the elegant use of the "last digit" without forcing people to use weird number bases.

Very clever indeed. It guarantees all others will fail to guarantee that one is correct.

Spoiler

Exactly, with two people one is betting the sum is odd, one even.

There is a puzzle with a long line of people with rainbow hats on where they take it in turns to guess out loud which uses a similar idea with the modular arithmetic.

 

[efyu_lemonardo]

Son you smart

pretty sure 'son' is inappropriate here

 

[Feep]

pretty sure 'son' is inappropriate here

Shifu then

Edit: Googling around led to another VERY interesting riddle entitled "100 Prisoners", check it out

 

[liliththepale]

Okay, that solution is genius and quite elegant. I had to reread it a couple times because the only thing I ever use modulus for it to make programs run in circles.

 

[The Friendly Monster]

Spoiler

didn't expect it to be solved this quickly! well done!

Spoiler

could you explain your process?

Spoiler

I took it down in my head to the case with one prisoner and two prisoners, got a bit stuck when I thought that two prisoners seeing the same thing would have to make the same guess, but then realised the prisoners were allowed to confer before and number themselves. With the case for two solved the general case was natural as I already knew the idea of encoding all the information of the other numbers by adding them up modulo n from another puzzle.

It's a very elegant puzzle.

I hope people don't just read the spoilers without having a real go at solving it.

 

[efyu_lemonardo]

Shifu then

Edit: Googling around led to another VERY interesting riddle entitled "100 Prisoners", check it out

this seems very similar to the previous riddle I asked here

 

[Septimius]

Spoiler

I took it down in my head to the case with one prisoner and two prisoners, got a bit stuck when I thought that two prisoners seeing the same thing would have to make the same guess, but then realised the prisoners were allowed to confer before and number themselves. With the case for two solved the general case was natural as I already knew the idea of encoding all the information of the other numbers by adding them up modulo n from another puzzle.

It's a very elegant puzzle.

I hope people don't just read the spoilers without having a real go at solving it.

I did. I got as far as

Spoiler

in the case of two, having prisoner "A" and "B" with the number n and m, respectively. A would guess m, B would guess n+1.

From there I couldn't figure out why before I peeked

 

[Evo X]

Today I learned what the word modulo means.

 

[efyu_lemonardo]

Spoiler

I took it down in my head to the case with one prisoner and two prisoners, got a bit stuck when I thought that two prisoners seeing the same thing would have to make the same guess, but then realised the prisoners were allowed to confer before and number themselves. With the case for two solved the general case was natural as I already knew the idea of encoding all the information of the other numbers by adding them up modulo n from another puzzle.

It's a very elegant puzzle.

I hope people don't just read the spoilers without having a real go at solving it.

Spoiler

awesome! I'd never encountered this method before and the transition from 2 to 3 took me forever!