Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -


  • Please log in to reply
26 replies to this topic

#1 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 01 June 2009 - 05:59 AM

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, 01 June 2009 - 06:06 AM.

  • 0

#2 frenchtoasted

frenchtoasted

    Newbie

  • Members
  • Pip
  • 1 posts

Posted 01 June 2009 - 06:53 AM

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.
  • 0

#3 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 01 June 2009 - 07:02 AM

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.
  • 0

#4 Phatfingers

Phatfingers

    Advanced Member

  • Members
  • PipPipPip
  • 188 posts

Posted 01 June 2009 - 07:24 AM

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.


Spoiler for Yes, there is a strategy that could work.


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

Edited by Phatfingers, 01 June 2009 - 07:26 AM.

  • 0

#5 adiace

adiace

    Advanced Member

  • Members
  • PipPipPip
  • 113 posts

Posted 01 June 2009 - 07:47 AM

Spoiler for a simple solution

  • 0

#6 adiace

adiace

    Advanced Member

  • Members
  • PipPipPip
  • 113 posts

Posted 01 June 2009 - 08:03 AM

Spoiler for Example of hamming code

  • 0

#7 James8421

James8421

    Advanced Member

  • Members
  • PipPipPip
  • 468 posts

Posted 01 June 2009 - 10:59 AM

Spoiler for this is where i'm at..

  • 0

#8 ReArtemis

ReArtemis

    Newbie

  • Members
  • Pip
  • 7 posts

Posted 02 June 2009 - 06:51 PM

Spoiler for This is my solution.....

  • 0

#9 Phatfingers

Phatfingers

    Advanced Member

  • Members
  • PipPipPip
  • 188 posts

Posted 03 June 2009 - 08:13 AM

Spoiler for Yes, there is a strategy that could work.


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


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.

Spoiler for How the prisoners could make practical use of a Hamming Code.

  • 0

#10 James8421

James8421

    Advanced Member

  • Members
  • PipPipPip
  • 468 posts

Posted 03 June 2009 - 06:31 PM

So is there an answer? Anyone working on this one? I would like to know the answer. I like learning from others on here. ;)
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users