Jump to content
BrainDen.com - Brain Teasers
  • 0


bushindo
 Share

Question

There are 32 prisoners on a death row. The warden gives them a chance to live. In one room, call it room A, the warden puts 26 jars and put a unknown number of balls inside the jars. Each jar is either empty or contains 1 ball. In room B, the warden puts 26 jars, and 26 balls in a separate stack. He divides the prisoners into two groups, 1 group of 31 and 1 group of 1. The group of 31 goes inside room A, and the other prisoner goes into room B.

There is a lever in room A, which is connected to two lights in room B. Depending on how one pulls on the lever, it will either make a red light or a green light goes up in room B. The game proceeds as follows. Each prisoner in room A will take turn going up and examine the 26 jars away from the sight of his fellow prisoners. He can not rearrange or modify the jar in any way, shape, or form. He then must pull the level and make either a red light or green light goes up in room B. If he attempts to communicate any other information besides those two bit of information (i.e. waiting a certain amount of time before pulling the lever, pulling the level more than once, not pull the level at all, etc. ) all prisoners will be executed immediately. The order in which the prisoners take their turn at the jar is randomly determined by the warden.

If the prisoner in room B can reconstruct the arrangement of balls inside the jars in room A at the end of 31 turns, all prisoners will live. However, there's a catch. The warden will randomly intercept the communication of 1 prisoner from room A to room B and flip it. For example, suppose that the warden choose to flip prisoner 16's communication. Let's say that number 16 examines the jar and choose to make the green light goes up, the warden would intercept the electronic signal and make the red light goes up instead. Likewise, if number 16 were to choose to make the red light goes up, the warden would make the green light goes up instead.

The 32 prisoners are informed of this game the night before, so they know that the communication of exactly 1 random person will be compromised during the game. They have 1 night to prepare.

Is there a strategy to guarantee the survival of all prisoners? Describe it.

Edited by bushindo
Link to comment
Share on other sites

Recommended Posts

  • 0

There is a strategy, IF the prisoner in room A who's communication is intercepted is aware of the interception, that prisoner can then report back to the remaining prisoners so they are aware of the prisoners position that has been compromised. Because there are only 26 jars and 31 prisoners, the last 5 prisoners that go can use binary code ( green is one, red is zero) so that they can communicate which prisoner number had been randomly changed and the prisoner in room B can add or remove the ball in that jar. Then they live.

Link to comment
Share on other sites

  • 0
There is a strategy, IF the prisoner in room A who's communication is intercepted is aware of the interception, that prisoner can then report back to the remaining prisoners so they are aware of the prisoners position that has been compromised. Because there are only 26 jars and 31 prisoners, the last 5 prisoners that go can use binary code ( green is one, red is zero) so that they can communicate which prisoner number had been randomly changed and the prisoner in room B can add or remove the ball in that jar. Then they live.

Just a question, what if the interception is in the last 5 prisoners, how do the prisoners handle that? This approach assumes that the each prisoner knows whether their communication has been compromised, and that each prisoner can communicate with his mates afterwards. It is not what I intended but it poses a good question, so please consider it.

Don't forget to work on the harder case too, which assumes that the interception is random, and each prisoner, on his turn, doesn't know whether his communication has been compromised.

Link to comment
Share on other sites

  • 0
There are 32 prisoners on a death row. The warden gives them a chance to live. In one room, call it room A, the warden puts 26 jars and put a unknown number of balls inside the jars. Each jar is either empty or contains 1 ball. In room B, the warden puts 26 jars, and 26 balls in a separate stack. He divides the prisoners into two groups, 1 group of 31 and 1 group of 1. The group of 31 goes inside room A, and the other prisoner goes into room B.

There is a lever in room A, which is connected to two lights in room B. Depending on how one pulls on the lever, it will either make a red light or a green light goes up in room B.

. . .

The 32 prisoners are informed of this game the night before, so they know that the communication of exactly 1 random person will be compromised during the game. They have 1 night to prepare.

Is there a strategy to guarantee the survival of all prisoners? Describe it.

Compression is out of the question. You'll need 26 prisoners to convey the contents of the 26 jars. So, we'll say the 1st 26 do so sequentially, red for containing a ball, green for empty.

Now, we have 5 prisoners left to help determine the one known error in an unknown jar. I'll call them prisoners 1 through 5.

Prisoner 1: Counts the balls in jars 16-26, reporting Red for odd or Green for even.

Prisoner 2: Does likewise for jars 8-15, and 24-26

Prisoner 3: Does likewise for jars 4-7, 12-15, 20-23, reporting Red for odd or Green for even.

Prisoner 4: Does likewise for jars 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26

Prisoner 5: Counts balls in all odd numbered jars, reporting Red for odd or Green for even.

Prisoner #32 populates the 26 jars exactly as indicated by the first 26 prisoners, then writes down the last 5 messages, each representing Red for odd or Green for even. He must count the balls in the corresponding jars to confirm the truth of EACH of the five prisoner's claims (knowing in advance the jars to which they apply). For each of the five messages, if the claim of odd or even is FALSE, then he adds a number according to the following table:

Message 1: 16

Message 2: 8

Message 3: 4

Message 4: 2

Message 5: 1

That sum should be the number of the jar that was compromised. If it contains a ball, then he should remove it, otherwise he should place a ball in that jar.

D'oh! Bushindo, you just disproved it while I was busy writing it down!

Edited by Phatfingers
Link to comment
Share on other sites

  • 0

I'm not convinced the prisoners can be saved. Because of the random number of balls plus the random event of the warden switching someones answer, that would mean any sequence you attempt to convey to prisoner B will have to be repeated 3 times for him to be able to confirm the pattern. The only way I see it possible, is if you can somehow generate the pattern of 26 jars between 31 prisoners three times with only using two indicators (green red).

Reason for 3 times: To make it simple say J1 has a ball, and RED=ball, P1,P2,and P3 all have to light red since they don't know if the warden switches any of them. Say the warden switched P2. Prisoner B sees red,green,red. Now he knows P2 was switched. If Prisoner B sees two reds in a row he can make his conclusion right there, but since Prisoners in A don't know if/when the warden switches, the third guy must still go and light red as well. But after all that only one Jar was revealed, and it took 3 Prisoners.

That should hold true no matter how you attempt to convey any information to Prisoner B. Even when Prisoner B realizes where the warden switched, Prisoners in A do not so they have to continue along passing info the same way. I'm not sure it would be possible.No matter how many Prisoners it takes to represent an x number of jars, you'll have to times that number of prisoners by 3, since they don't know when the warden switches. I'm not sure there is enough prisoners to convey such a pattern.

All in all, I'll say it's not possible (for now) for these reasons:

1. Random number of balls placed in 26 Jars=26^26 possible combos

2. Random event of warden switching 1 answer

3. Prisoners in A have no idea when the switch will occur, and they can't communicate with each other

4. Only 2 ways of passing info (red,green light)

My best solution would be to have the first 26 Prisoners reveal the 26 jars(green for ball red for noball or whatever), then have the remaining 5 Prisoners light the same color, and hope the warden switches one of theirs.

But I'm sure I'm wrong somewhere, so I'll just wait and see someone put up the correct solution. :thumbsup:

Link to comment
Share on other sites

  • 0

Ok - this is how i see it.

The first five inmates report either a ball or no ball in the first five jars RED=Ball, Green=No Ball

The sixth inmate gives a total of the first five with RED=Odd number, Green=Even Number (this all relies on the sole inmate recording the data having access to a pen and paper!)

This continues with the 7th inmate recording Red=Ball, Green=No Ball on Jar 6, Inmate 8 on Jar 7, Inmate 9 on Jar 8, Inmate 10 on Jar 9 and inmate 11 on jar 10. Inmate 12 then reports an odd (RED light) or even (GREEN light) on the total of balls between jars 6 to 10.

This continues until the row containing jars 21 to 25. Here inmate number 25 totals the jars 1.6,11,16 and 21 and gives either a RED=odd number of balls or a GREEN=Even number of balls.

Inmate 26 does the same for jars 2, 7,12,17 and 22. Inmate 27 calculates 3,8,13,18 and 23. Inmate 28 calculates jars 4, 9,14,19 and 24.

Inmate 29 calculates jars 5,10,15,20 and 25

Inmate 30 Has the hardest job. He takes the value of every 6th inmate (this is probably easier to see below) and give a total value of odd (RED) or Even (GREEN).

1 2 3 4 5 6

0 0 1 1 0 0

1 0 1 1 0 1

1 1 0 0 1 0

0 0 1 0 1 1

1 0 1 1 0 0

The table above shows no. wait a minute.....

I have just found a fatal flaw in my system... i'm sure it wasn't there before!!

Back to the drawing board. I was about to finish off with stating that the sixth column was just for error correction and the 31st inmate could report whether he saw a ball or not as if no errors were detected in the first 25 jars then his must have been switched.

Oh well, back to the drawing board. I will still post this to show how much it has been driving me crazy!!! I hope i might have inspired somebody to come up with a solution!

Link to comment
Share on other sites

  • 0

D'oh! Bushindo, you just disproved it while I was busy writing it down!

Compression is out of the question. You'll need 26 prisoners to convey the contents of the 26 jars. So, we'll say the 1st 26 do so sequentially, red for containing a ball, green for empty.

Now, we have 5 prisoners left to help determine the one known error in an unknown jar. I'll call them prisoners 1 through 5.

Prisoner 1: Counts the balls in jars 16-26, reporting Red for odd or Green for even.

Prisoner 2: Does likewise for jars 8-15, and 24-26

Prisoner 3: Does likewise for jars 4-7, 12-15, 20-23, reporting Red for odd or Green for even.

Prisoner 4: Does likewise for jars 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26

Prisoner 5: Counts balls in all odd numbered jars, reporting Red for odd or Green for even.

Prisoner #32 populates the 26 jars exactly as indicated by the first 26 prisoners, then writes down the last 5 messages, each representing Red for odd or Green for even. He must count the balls in the corresponding jars to confirm the truth of EACH of the five prisoner's claims (knowing in advance the jars to which they apply). For each of the five messages, if the claim of odd or even is FALSE, then he adds a number according to the following table:

Message 1: 16

Message 2: 8

Message 3: 4

Message 4: 2

Message 5: 1

That sum should be the number of the jar that was compromised. If it contains a ball, then he should remove it, otherwise he should place a ball in that jar.

In essense, Mr. Hamming (to which adiace refers) employed the same technique as above, but did so in a manner that made the error checking bit self-referencing if the bit itself was changed. For example, an absense of errors would yield a value of zero for all five message confirmations. If you placed "Message 4" in the 4th position, and someone flipped it's value, only it would change, and having the value 4, it would point to itself as having the error.

Line the prisoners up, numbered 1-31

Have the 5 prisoners (1, 2, 4, 8, and 16) step out of the line. We'll call them “parity” prisoners.

Match the remaining 26 prisoners in order with the 26 jars, each putting his hand on his head if his jar has a ball.

Line the prisoners back up again in order of 1-31 (hands still on heads).

Have each of the 5 parity prisoners count every other N prisoners with hands on their heads, pretending a 0th prisoner exists.

For each prisoner doing the counting, N is that prisoner's number. If he counts odd, he puts his hand on his own head.

Prisoner 1 will count every odd prisoner with a hand on his head.

Prisoner 2 will count likewise for prisoners 2-3, 6-7, 10-11, 14-15, 18-19, 22-23, 26-27, 30-31

Prisoner 4 will count head-handed prisoners 4-7, 12-15, 20-23, 28-31

Prisoner 8 will do the same for 8-15, 24-31

Prisoner 16 will count prisoners 16-31 with hands on their heads

Now, each of the prisoners sequentially signal red at the lever if their hand is on their head, or green if not.

The receiving prisoner will number the 24 jars from 1-31, omitting the numbers 1, 2, 4, 8, and 16, which he reserves

for the fingers on his left hand, so the actual jars will be numbered 3, 5, 6, 7, 9-15, and 17-31.

When interpreting the signals, if the ordered number of the signal matches a jar number and is red,

he'll place a ball into that jar. If it matches the numbers 1, 2, 4, 8, or 16 and is red, he'll tear off a fingernail

as close to the quick as he can on his fingers, numbered from pinky to thumb as 1, 2, 4, 8, and 16.

When all signals are in, that prisoner will verify the truth of each of his five digits by counting the jars to which

they apply. If a fingernail doesn't match up with the count (odd or even), he picks the same fingernail on his right hand.

When he's done, he adds up the values of the bleeding fingers on his right hand, pinky=1 through thumb=16.

If the value matches the number of a jar, he changes it's state, adding a ball if empty or removing the ball.

If it doesn't match the number of a jar, he leaves the jars alone.

P.S. The bleeding fingernail action is giving me a strong sense of deja-vu, but I don't remember from where... could be recycled. :-)

Link to comment
Share on other sites

  • 0

i got it ////

the prisoners on death row will count how many jars have balls then divide by 26 this will give them a four digit decimal code. For example, 10 balls = 10/26 = .3846 the first set of 10 prisoners will mark first red for 3 times then blue for 7 /// 2nd set of ten red 8 blue 2 /// 3rd red 4 blue 6. the final prisoner will indicate whether the fourth number is odd or even. this way the only way the warden can mess up the communication is right at the frontier between red and blue. however. since the lone prisoner knows all the four digit combinations he knows when it is wrong. if the light flips somewhere between the reds or the blues then he knows the warden has failed and he can trust all the numbers. if not then he can look for similar numbers since the warden can only mess up one number. if he gets 3 8 5 even he will notice that it is similar to 3 8 4 even and put ten balls in jars. it is fool proof the prisoners can do the calculations the night before and determine the they will go in so maybe prisoner 12 knows that he will only press blue when there are 2, 11, 15, 23, or 26 balls otherwise red. the table will be tattoed to the arm of the lone prisoner.

find a flaw in that suckers.

Link to comment
Share on other sites

  • 0

i haven't thought it all the way through, but i think it's SIMPLE and WORKS...

the first three prisoners all examine the first jar and send green for a ball, red for empty... take the best two of three if there's a difference...

the fourth prisoner examines jars 1 & 2 and sends green for one ball, red for two balls...

the fifth prisoner examines jars 2 & 3 and sends green for one ball, red for two balls...

... repeat ...

the 28th prisoner examines jars 25 & 26 and sends green for one ball, red for two balls...

the last three prisoners all examine the last jar and send green for a ball, red for empty... take the best two of three if there's a difference...

I don't think there's any way to mess this up...

EDIT: The intercepted error may not show up right away, but the first and last balls will verify all the information in between and identify any faltered communication... The intercepted communication will have ACCURATE information on either side of it that will help reconcile the false info...

Edited by icepick1346
Link to comment
Share on other sites

  • 0

Clever strategy. One question...what if jars 1&2 are empty? P4 can only signal for 1 ball or 2 balls

I think if you can somehow work your way around that (if possible) you may be onto something here.

Edited by James8421
Link to comment
Share on other sites

  • 0

In my above post I ignored the sequence of the balls. it didn't seem that the warden set a specific sequence.

PS i noticed the warden randomly selects the order of the prisoners. so its not as easy as i said. but it still fool proof.

Link to comment
Share on other sites

  • 0
Clever strategy. One question...what if jars 1&2 are empty? P4 can only signal for 1 ball or 2 balls

I think if you can somehow work your way around that (if possible) you may be onto something here.

Doh!!!

Guess I didn't think about that... let's see...

the first three prisoners all examine the first jar and send green for a ball, red for empty... take the best two of three if there's a difference...

the fourth prisoner examines jars 1 & 2 and sends green for "same as previous jar", red for "different than previous jar"...

the fifth prisoner examines jars 2 & 3 and sends green for "same as previous jar", red for "different than previous jar"...

... repeat ...

the 28th prisoner examines jars 25 & 26 and sends green for "same as previous jar", red for "different than previous jar"...

the last three prisoners all examine the last jar and send green for a ball, red for empty... take the best two of three if there's a difference...

That should take care of the previous problem I had... And again, the first and last ball will provide the ability to identify if (and where) the intercept occurred...

Edited by icepick1346
Link to comment
Share on other sites

  • 0
Doh!!!

Guess I didn't think about that... let's see...

the first three prisoners all examine the first jar and send green for a ball, red for empty... take the best two of three if there's a difference...

the fourth prisoner examines jars 1 & 2 and sends green for "same as previous jar", red for "different than previous jar"...

the fifth prisoner examines jars 2 & 3 and sends green for "same as previous jar", red for "different than previous jar"...

... repeat ...

the 28th prisoner examines jars 25 & 26 and sends green for "same as previous jar", red for "different than previous jar"...

the last three prisoners all examine the last jar and send green for a ball, red for empty... take the best two of three if there's a difference...

That should take care of the previous problem I had... And again, the first and last ball will provide the ability to identify if (and where) the intercept occurred...

NEVERMIND, there's not enough info to isolate the problem anymore...

Link to comment
Share on other sites

  • 0
i got it ////

the prisoners on death row will count how many jars have balls then divide by 26 this will give them a four digit decimal code. For example, 10 balls = 10/26 = .3846 the first set of 10 prisoners will mark first red for 3 times then blue for 7 /// 2nd set of ten red 8 blue 2 /// 3rd red 4 blue 6. the final prisoner will indicate whether the fourth number is odd or even. this way the only way the warden can mess up the communication is right at the frontier between red and blue. however. since the lone prisoner knows all the four digit combinations he knows when it is wrong. if the light flips somewhere between the reds or the blues then he knows the warden has failed and he can trust all the numbers. if not then he can look for similar numbers since the warden can only mess up one number. if he gets 3 8 5 even he will notice that it is similar to 3 8 4 even and put ten balls in jars. it is fool proof the prisoners can do the calculations the night before and determine the they will go in so maybe prisoner 12 knows that he will only press blue when there are 2, 11, 15, 23, or 26 balls otherwise red. the table will be tattoed to the arm of the lone prisoner.

find a flaw in that suckers.

The problem is not just figuring out how many balls there are but which jars the balls are in... I like your idea, but it doesn't let the lone prisoner replicate the exact pattern of the original jars...

Link to comment
Share on other sites

  • 0

Prisoners 1 to 26 will look at jars 1 to 26 and relay the information about a ball.

The last 5 prisoners will act as a 5 bit Hamming code. Will explain Hamming code's application in this situation later. http://en.wikipedia.org/wiki/Hamming_code

I believe Adiace is correct, with the exception that the five "check" prisoners be interspersed with the others... And it can't be a coincidence you get 31 prisoners since you need that many for this solution...

Edited by icepick1346
Link to comment
Share on other sites

  • 0

There has to be somebody who can resolve this!!

1 2 3 4 5 6

0 1 1 0 1 1

1 1 1 0 0 1

0 1 0 0 1 0

1 0 0 0 1 0

0 1 1 1 0 1

1

If you take the columns 1 to 5 as though 0=no ball and 1=Ball

The 6th column as error detection for the row (total of appropriate row 1-5 = odd (1) or even (0)).

This can detect an error has occured but only on a specific row. That is unless the error detection signal itself was switched!

The last '1' on row 6 is fine as if no error was detected then it must be that one that was switched.

Now the only way i can see something like this working is if there were error correctors running along the bottom row as well (including column 6 as this will tell us the error lies in the error detection column and that all supplied data is correct).

My theory was to attempt to merge a ball detection and error correction into the same signal for the last full row. Example, at the bottom of row 1 (forget the lonely 26th ball jar result for now) the inmate would total jars 1,6,11,16 & 21 and give the result as odd or even)the signal should be 1 if the total of the column including jar 21 is odd and 0 if even.

I am not sure if i am within a whisker of the right answer or am on a different continent altogether.

Will somebody please put me out of my misery!!!

Link to comment
Share on other sites

  • 0
There has to be somebody who can resolve this!!

1 2 3 4 5 6

0 1 1 0 1 1

1 1 1 0 0 1

0 1 0 0 1 0

1 0 0 0 1 0

0 1 1 1 0 1

1

If you take the columns 1 to 5 as though 0=no ball and 1=Ball

The 6th column as error detection for the row (total of appropriate row 1-5 = odd (1) or even (0)).

This can detect an error has occured but only on a specific row. That is unless the error detection signal itself was switched!

The last '1' on row 6 is fine as if no error was detected then it must be that one that was switched.

Now the only way i can see something like this working is if there were error correctors running along the bottom row as well (including column 6 as this will tell us the error lies in the error detection column and that all supplied data is correct).

My theory was to attempt to merge a ball detection and error correction into the same signal for the last full row. Example, at the bottom of row 1 (forget the lonely 26th ball jar result for now) the inmate would total jars 1,6,11,16 & 21 and give the result as odd or even)the signal should be 1 if the total of the column including jar 21 is odd and 0 if even.

I am not sure if i am within a whisker of the right answer or am on a different continent altogether.

Will somebody please put me out of my misery!!!

Hi ReArtemis, sorry for the misery. Your attempt, if I understand it correctly, if to encode the parity (odd, even) of every 5 jars with 1 prisoner. That is a good approach, but it doesn't completely solve the problem. If you want a solution, then you can read the previous posts, especially adiace's post. if you want a hint, here's one

You need 26 prisoners to encode the 26 jars. That's taken for granted. That leaves 5 prisoners to do error correction. Note that 2^5 = 32. That is, using the last 5 prisoners, you can encode up to 32 different states.

But here's a more practical hint, for balance, you should let each of the last 5 prisoner each do the odd-even business on 16 other prisoners. Each of the last 5 should operate on a different set of 16 prisoners though. The details are up to you.

Link to comment
Share on other sites

  • 0

I don't understand the idea of having the 5 error checkers...Does it still work if the warden switches one of them? Also if one does come back to signal odd, but Prisoner B had it down as even, how is he supposed to know what one was switched? Maybe I'm not understanding the concept of that.

Link to comment
Share on other sites

  • 0
I don't understand the idea of having the 5 error checkers...Does it still work if the warden switches one of them? Also if one does come back to signal odd, but Prisoner B had it down as even, how is he supposed to know what one was switched? Maybe I'm not understanding the concept of that.

The basic idea of the Hamming Code (first given by Adiace) is that there are 26 "data signals" (for each jar) and 5 "check signals"... IF the warden intercepts a "data signal", then at least two "check signals" will be wrong and will specifically identify which of the "data signals" was compromised... On the other hand, IF the warden intercepts a "check signal", it will be the only one wrong; if there's only one wrong "check signal", that tells you there are no problems with the "data signals"...

If you are numbering the signals 1-31, the "check signals" would be signals 1,2,4,8 and 16... the first jar would be represented by jar 3 and all subsequent non-"check signals"...

Each "check signal" adds up the number of balls in all jars where (signal# mod(checksignal#))=0 and signal#>checksignal#... For an even number of balls that check signal would send one signal (say green), and for even number it would send the other signal (say red)...

Once all the signals are received, the lone prisoner will check that all the check signals are either true or false... Like I said above, if only one check signal is false, the all the data signals are OK... If more than one check is false, you simply add the position of those signals together to identify the signal that was compromised; for example, if check signals 1, 2 and 8 were false, you would know that signal 11 was compromised and would reverse the signal (in this case referring to jar #7...

That's the basics of the Hamming Code...

Link to comment
Share on other sites

  • 0

My way isn't very different from everyone else's, but I find it much easier to follow.

[spoiler='

']The prisoners should decide the night before that the numbering of the jars will begin on the left when entering the room. Green means “ball”, and red means “no ball". Prisoners 1, 11, 21, and 31 should pull the lever three times with the previously agreed upon sequence Red-Green-Red. Prisoners 2-4 will then each examine jars 1-3 and pull the lever three times, the first time for jar 1, the second for jar 2, and so on. If there is a disparity between their responses, Prisoner B will know which one is compromised. Prisoners 5-7 will do the same for jars 4-6, Prisoners 8-10 will examine jars 7-9, and so forth until Prisoner 11, who pulls the sequence Red-Green-Red. The process would continue until Prisoner 21, who pulls Red-Green-Red, and then continue as planned again until Prisoners 28-30 record jars 25-26. Then Prisoner 31 pulls Red-Green-Red and the game ends.

It would look something like this:

Prisoner: Responsible for:

1 RGR

2 1-3

3 1-3

4 1-3

5 4-6

6 4-6

7 4-6

8 7-9

9 7-9

10 7-9

11 RGR

12 10-12

13 10-12

14 10-12

15 13-15

16 13-15

17 13-15

18 16-18

19 16-18

20 16-18

21 RGR

22 19-21

23 19-21

24 19-21

25 22-24

26 22-24

27 22-24

28 25-26

29 25-26

30 25-26

31 RGR

Link to comment
Share on other sites

  • 0
My way isn't very different from everyone else's, but I find it much easier to follow.

[spoiler='

']The prisoners should decide the night before that the numbering of the jars will begin on the left when entering the room. Green means “ball”, and red means “no ball". Prisoners 1, 11, 21, and 31 should pull the lever three times with the previously agreed upon sequence Red-Green-Red. Prisoners 2-4 will then each examine jars 1-3 and pull the lever three times, the first time for jar 1, the second for jar 2, and so on. If there is a disparity between their responses, Prisoner B will know which one is compromised. Prisoners 5-7 will do the same for jars 4-6, Prisoners 8-10 will examine jars 7-9, and so forth until Prisoner 11, who pulls the sequence Red-Green-Red. The process would continue until Prisoner 21, who pulls Red-Green-Red, and then continue as planned again until Prisoners 28-30 record jars 25-26. Then Prisoner 31 pulls Red-Green-Red and the game ends.

It would look something like this:

Prisoner: Responsible for:

1 RGR

2 1-3

3 1-3

4 1-3

5 4-6

6 4-6

7 4-6

8 7-9

9 7-9

10 7-9

11 RGR

12 10-12

13 10-12

14 10-12

15 13-15

16 13-15

17 13-15

18 16-18

19 16-18

20 16-18

21 RGR

22 19-21

23 19-21

24 19-21

25 22-24

26 22-24

27 22-24

28 25-26

29 25-26

30 25-26

31 RGR

The prisoners can only pull the lever once per prisoner though..... i think

Link to comment
Share on other sites

  • 0
The prisoners can only pull the lever once per prisoner though..... i think

Looking back:

"If he attempts to communicate any other information besides those two bit of information (i.e. waiting a certain amount of time before pulling the lever, pulling the level more than once, not pull the level at all, etc. ) all prisoners will be executed immediately. The order in which the prisoners take their turn at the jar is randomly determined by the warden."

According to the original, they can pull the lever as many times as they want. Also, because the order is randomly determined by the warden, I am assuming each person goes in by himself. This makes it difficult to implement any complicated system. With the one I worked out, as long as the prisoner knows how many people came before him, however, he’ll know what to do. I don’t think they’d have to write it down to remember it. If they could only pull it once, it would be a problem, though. :)

Link to comment
Share on other sites

  • 0
Looking back:

"If he attempts to communicate any other information besides those two bit of information (i.e. waiting a certain amount of time before pulling the lever, pulling the level more than once, not pull the level at all, etc. ) all prisoners will be executed immediately. The order in which the prisoners take their turn at the jar is randomly determined by the warden."

They cannot pull the lever multiple times...

The answer is the Hamming Code as pointed out by Adiace....

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...