Home

The prisoners and the switch

1,439.6K Views

N prisoners get together to decide on a strategy.  Then, each prisoner is taken to his own isolated cell.  A prison guard goes to a cell and takes its prisoner to a room where there is a switch.  The switch can either be up or down.  The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch.  The prisoner is then taken back to his cell.  The prison guard repeats this process infinitely often, each time choosing fairly among the prisoners.  That is, the prison guard will choose each prisoner infinitely often.

At any time, any prisoner can exclaim “Now, every prisoner has been in the room with the switch”.  If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed.  What strategy should the prisoners use to ensure their eventual freedom?

(Just in case there’s any confusion:  The initial state of the switch is unknown to the prisoners.  The state of the switch is changed only by the prisoners.)

As a warm-up, you may consider the same problem but with a known initial state of the switch.

Share
ronret45 Expert Asked on 1st August 2015 in Microsoft Interview Puzzles.
Add Comment
Cancel

    • 1 Answer(s)

    Reserve one prisoner with a special assignment (I’ll call her Sam). Each prisoner will turn on the light once, and only once, sending a signal to Sam. When Sam receives it, he notes that a signal has been received, and turns the light off. Once 99 signals are received, Sam knows that everybody has been in the room. Thus the instructions for each prisoner are:

    • If you enter the room with the light off, and you have never turned it on, then turn it on.
    • Otherwise, leave it.
    Cancel
    ronit Guru Answered on 5th August 2015.
    Add Comment
    Cancel

    • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.

  • More puzzles to try-

  • Accenture Interview PuzzlesAdobe Interview PuzzlesAge RiddleAkbar Birbal PuzzlesAlgorithm PuzzlesAlphabet riddleAmazon Interview PuzzlesAnalytical MathematicsAptitude PuzzleBank PuzzlesBetting PuzzlesBrain TeasersCalendar PuzzlesCards PuzzlesChess Board PuzzleChess PuzzlesChristmas Puzzlecipher PuzzleCivil Services PuzzleClock time puzzleCognizant Interview PuzzlesCoins PuzzleComputational PuzzleconundrumCoronavirus PuzzleCoupondunia Interview PuzzleCritical Thinking Puzzledata analyticsData Structure Interview QuestionsDecode PuzzleDetective PuzzlesDice PuzzleDictionary Riddlesdifficult riddleEasy Math puzzlesEasy puzzlesEinstein puzzleEnglish RiddleFamily Tree Puzzlefamous puzzleFill in the blanks riddlesFinding Killer RiddlesFlipkart interview puzzlesFunny RiddlesGeneral KnowledgeGeographical PuzzleGoogle Code Jam 2014Google Interview PuzzlesGRE PuzzleHard Puzzle