TimeSpaceLightForce 11 Report post Posted July 7, 2014 Everyday, six prisoners: numbered #1 #2 #3 #4 #5 #6 were randomly locked-up inside six prison cells: [1] [2] [3] [4] [5] [6]... No one have any information about the other locked-up prisoners. They do not have any means of communications once inside the closed room. During a dinner the warden offered the prisoners to participate in a game of chance. Anyone who can guess all the prisoner's # in every prison cell correctly shall be freed together with one of the other prisoners he selects. If the guess is wrong, both of them shall be hanged. Anyone who wont guess will be hanged. For accepting his challenge he would grant the prisoners request that one of the prison cells must contain a boxed dice to play and share. Provided they can only send it once to other cell and received it once from other cell with the assistance of prison guard. The six prisoners talked it over and all agreed to take the challenge. On the next day they were all locked-up with blindfold .. but they were all saved by the dice. How can this be done? 1 Share this post Link to post Share on other sites

0 plasmid 39 Report post Posted July 10, 2014 Looks like you've mostly solved your own puzzle And no one tried to argue that it's impossible because there are only 6*6*4*4 = 576 ways to orient the dice, while there are 6! = 720 ways to arrange the prisoners, so the dice can't encode all possible arrangements of prisoners. [spoiler=Well, here's my implementation]First, agree on a cycle to pass the dice. For example, if the guard will ask you to name a prisoner to give the dice, then agree on some order like prisoner A -> prisoner B -> prisoner C -> prisoner D -> prisoner E -> prisoner F -> prisoner A. Represent the orientation of the dice with four numbers as follows. The first number (from one to six) is the number facing the lion on the die that's on the side with the “D”, the second number (also from one to six) is the number facing the lion on the die that's on the side with the “E”. The third number (from one to four) is derived by considering the die on the side with the “D”, looking at the number facing the “DNE” and seeing where that is among the four numbers that do not face toward or away from the lion. For example, if face 2 were toward the lion and face 5 were away from the lion, then if face 4 is pointing toward the DME then 4 is the third number among {1, 3, 4, 6} that don't face toward or away from the lion, and represents a 3 as the third digit in the code. The fourth digit is obtained similarly by considering the die on the side with the “E”. The first prisoner to get the dice will consider his cell number, call it A, and pass the dice to the next prisoner arranged with the code [A A 1 1]. The fact that the first two numbers are the same and the second two numbers are both 1 will let the prisoner who receives the dice know that he's the second prisoner to get them, and will tell him that the prisoner before him in the cycle is in cell A. The second prisoner will consider his cell number to be B, and will pass the dice in the orientation [A A 1+int(B/3) 1+(Bmod3)]. The third prisoner to receive the dice will know that he's the third because the first two numbers are the same and the last two numbers are not both 1, and he will know the cell numbers of the two prisoners before him in the cycle. The third prisoner will consider his cell number to be C. He will calculate X as the number that C would be if A and B were excluded – for example, if C=5 and A=2 and B=6, then C=5 would be the fourth number out of the numbers left if A and B are removed {1, 3, 4, 5}, so X would be 4. The third prisoner will pass the dice in the orientation [A B X X], which will let the fourth prisoner know that he's the fourth to get the dice because the first two numbers are different and the last two numbers are the same. The fourth prisoner will similarly calculate Y based on his cell number using the same method that the third prisoner used to calculate X, and will pass the dice in the orientation [A B X Y]. The fact that the first and second numbers are different and the third and fourth numbers are different will let the next prisoner know that at least four other prisoners have seen the dice, and will tell him which cells each of the four prisoners preceding him are in, so knowing that in combination with knowing his own cell number will mean that the fifth prisoner will know everyone's cell number. Since the fifth prisoner knows everyone's cell number, he can pass the dice on to the sixth player with the same [A B X Y] orientation that he would have used if he were the fourth prisoner. It doesn't really matter if the sixth prisoner knows that he's sixth and not fifth, as long as he gets enough information to know that he's somewhere after the fourth and can figure out everyone else's cell number. The sixth prisoner then passes it back to the first prisoner, again using the orientation [A B X Y] that he would have used if he were the fourth prisoner. Now the fifth, sixth, and first prisoners to get the dice know everyone's cell number, and they can each free themselves and the prisoner that is three steps ahead of them in the cycle that was agreed upon at the beginning. Share this post Link to post Share on other sites

0 k-man 26 Report post Posted July 7, 2014 Interesting puzzle. I have some clarifying questions: 1) Do the prisoners know the number of their own cell? I would guess yes, but better ask than guess. 2) When you say that "they can only send it once to other cell and received it once from other cell" do you mean there is only one pass of dice allowed? Or each prisoner can do a single pass for a total of 6 passes of the dice? 3) Can the prisoner with the dice specify the cell number of the prisoner number that shall receive the dice from him? 4) What is the significance of the blindfold? They obviously need to be able to set the dice to something specific and read the dice. Some people may be able to feel the numbers on the dice using their fingers, but not all people can do that reliably. Share this post Link to post Share on other sites

0 TimeSpaceLightForce 11 Report post Posted July 7, 2014 Thanks for clarifying and interest k-man.. 1) No, not on the challenge day. 2) They are allowed 6 passes. 3) The dice holder can specify the prison cell or the prisoner number (not in OP but Ok) 4) They can take off the blinders when inside the cells (hope the lights are on) It is a matter of freedom and doom and everyone should be very efficient. Share this post Link to post Share on other sites

0 k-man 26 Report post Posted July 7, 2014 (edited) Thanks for clarifying, but it seems that something is still missing... There are 720 ways to put 6 prisoners in 6 cells, but there are only 552 ways to place 2 dice in a box including different orientations of the dice, so even if each prisoner knew their own cell number of the first prisoner knew about all other prisoners, there isn't enough ways to encode every possible permutation of 6 prisoners with 2 dice. If, when passing the dice, the prisoner specifies the cell number, then he runs the risk of passing it to himself or closing the loop too early - no more passes will be allowed. If he instructs the guard to pass to the room number 1 greater than his own, then nothing can be learned about the room numbers. Also, if prisoner #1 guessed correctly and wants to save prisoner #2, who guessed incorrectly or refused to guess what happens to prisoner #2? Edited July 7, 2014 by k-man Share this post Link to post Share on other sites

0 TimeSpaceLightForce 11 Report post Posted July 8, 2014 Interesting puzzle. I have some clarifying questions: 1) Do the prisoners know the number of their own cell? I would guess yes, but better ask than guess. 2) When you say that "they can only send it once to other cell and received it once from other cell" do you mean there is only one pass of dice allowed? Or each prisoner can do a single pass for a total of 6 passes of the dice? 3) Can the prisoner with the dice specify the cell number of the prisoner number that shall receive the dice from him? 4) What is the significance of the blindfold? They obviously need to be able to set the dice to something specific and read the dice. Some people may be able to feel the numbers on the dice using their fingers, but not all people can do that reliably. Correction: Post #3 1) No, not on the start of challenge day. Eventually they must take off the blindfoldr to find the dice box inside and know what cell they are in by familiarity.and cell no sign.. Share this post Link to post Share on other sites

0 TimeSpaceLightForce 11 Report post Posted July 8, 2014 @ K-man: what missing is.. When done with dice one prisoner will volunteer to see the warden, select a partner to be saved and guess correctly for their freedom.. then the next prisoner shall do the same..until all of them are free. Share this post Link to post Share on other sites

0 plasmid 39 Report post Posted July 8, 2014 The picture has a box that can hold two dice, and has an orientation so that if someone were to hand you the box then you could distinctly talk about "the die on the side with the D" versus "the die on the side with the E", and define faces of the dice as "pointing toward the DNE" or "pointing toward the lion" when you send or receive the box. Is that what the prisoners will get in the puzzle? When a prisoner receives the dice, will he be told how many other prisoners have already had the dice? After the first prisoner guesses and two prisoners get released or get hanged, do the remaining four prisoners only need to guess which cells the remaining four prisoners are in, or do they also need to guess about the two prisoners that are now gone? Share this post Link to post Share on other sites

0 TimeSpaceLightForce 11 Report post Posted July 8, 2014 (edited) @ plasmid: 1) Is that what the prisoners will get in the puzzle? ...Exactly! 2)When a prisoner receives the dice, will he be told how many other prisoners have already had the dice? The written guess of the 3 savers should be like: Ex: [1]#2 [2]#5 [3]#1 [4]#4 [5}#6 [6}#3 Edited July 8, 2014 by TimeSpaceLightForce Share this post Link to post Share on other sites

0 TimeSpaceLightForce 11 Report post Posted July 8, 2014 @ plasmid: 2)When a prisoner receives the dice, will he be told how many other prisoners have already had the dice? ans: The dice might carry that information.. Share this post Link to post Share on other sites

0 TimeSpaceLightForce 11 Report post Posted July 8, 2014 Share this post Link to post Share on other sites

0 plasmid 39 Report post Posted July 8, 2014 Ok, now we have enough information from what's been posted so far. I wonder if anyone will simultaneously give an algorithm that saves everyone, and prove that it's impossible to save everyone. Share this post Link to post Share on other sites

0 TimeSpaceLightForce 11 Report post Posted July 8, 2014 Ok, now we have enough information from what's been posted so far. I wonder if anyone will simultaneously give an algorithm that saves everyone, and prove that it's impossible to save everyone. Lets hope it works..there are two ways this can be solved. a)The convenient way : If the cell nos. can be known inside the cell just ask the guard to pass the dice to the prisoner on certain cell no. b)The other way: if the cell nos. will be known outside the cell when going to the warden's office. The prisoners would ask the guard to pass the dice clockwise to the next cell. Note: The 24x24=576 of dice arrangements has 60 spares more than the required assignments. [permut(6,1)+permut(6,2)+permut(6,3)+permut(6,4)=6+30+120+360=516] *The permut(6,5) or permut(6,6) =720 is over budget The 4th receiver got the solution string.His and 5th receiver's no. are known! He then drops the first digit,add his no.on string end then pass to 5th receiver. **(the arrangement is available from permut(6,4) assignment) The 5th receiver got the solution string.His and 6th receiver's no. are known! He then drops the first digit,add his no.on string end then pass to 6th receiver. The 6th receiver got the solution string.His and 1st receiver's no. are known! Ex. 6135 #2 R6 picks #1 (opposite on round string) > 461352 2 #4 R1 24 #6 R2 246 #1 R3 2461 #3 R4 picks #4 (opposite on round string) > 524613 4613 #5 R5 picks #6 (opposite on round string) > 246135 The prison cell string must be succeding and looping 123456,234561,345612,456123,561234,612345 Share this post Link to post Share on other sites

0 Yoruichi-san 116 Report post Posted July 11, 2014 Ohhhh...it wasn't until I read the answer that I understood what the question actually meant ...anyways that's a really nice problem, and a nice solve as well. Share this post Link to post Share on other sites

## Share this post

## Link to post

## Share on other sites