Puzzle: prisoners and switches

Toda I saw this puzzle I’ve not seen for a long time:

A warden meets with 23 newly arrived prisoners. He tells them, “You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

“In the prison is a switch room, which contains two light switches, each of which can be in either the on or the off position. I am not telling you their present positions. The switches are not connected to anything.

“After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can’t move both, but he can’t move none, either. Then he’ll be led back to his cell.

“No one else will enter the switch room until I lead the next prisoner there, and he’ll be instructed to do the same thing. I’m going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

“But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, ‘We have all visited the switch room.’

“If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will all be executed.”

What strategy do the prisoners devise?

I had to think about it again for a few minutes but the solution is not that tricky (if you used to hack a lot).
Anyway I wanted to “experiment” with my solution and wanted to share the simulation with you – so that you can try to get your idea/solution working too:

A F# template to experiment with:

Here is a simple template you can experiment with:

namespace PrisonerPuzzle

type Switches = bool * bool

module Prisoners =
    let Count = 23
    type Action =
        | SwitchLeft
        | SwitchRight
        | DemandRelease

    type Prisoner = Switches -> Action

    let prisoners : Prioner array =
        failwith "please fill this in with your 23 prisoners"

module Warden =

    type Action =
        | Continue of Switches
        | ReleaseAll
        | ExecuteAll

    let private rnd = System.Random()

    let initialState : Switches = 
        (rnd.Next 2 = 0, rnd.Next 2 = 0)

    type T = Switches -> Action

    let createWarden (prisoners : Prisoners.Prisoner array) : T =
        let took = System.Collections.Generic.HashSet<Prisoners.Prisoner>()
        fun ((left,right) : Switches) ->
            let pNr = rnd.Next Prisoners.Count
            let prisoner = prisoners.[pNr]
            took.Add prisoner |> ignore

            System.Console.WriteLine ("pick prisoner number {0}", pNr)
            System.Console.WriteLine ("{0} of {1} have been in the room", took.Count, Prisoners.Count)

            match prisoner (left,right) with
            | Prisoners.SwitchLeft  -> Continue (not left ,right)
            | Prisoners.SwitchRight -> Continue (left, not right)
            | Prisoners.DemandRelease when took.Count = Prisoners.Count
                -> ReleaseAll
            | _ -> ExecuteAll

module Main =

    let rec loop (warden : Warden.T) (state : Switches) =
        match warden state with
        | Warden.Continue state' -> loop warden state'
        | Warden.ReleaseAll      -> printf "relase them all ... grmpf"
        | Warden.ExecuteAll      -> printf "bring me their HEADS ... yeah"

    let main _ = 
        printfn "Starting the game..." 
        let prisoners = Prisoners.prisoners
        let warden = Warden.createWarden prisoners
        let switches = Warden.initialState
        loop warden switches
        0 // return an integer exit code

All you have to do is add some code to get the Prisoners.prisoners array filled (with 23 functions of type Prisoner.Prisoner – which are just functions from the switch state to some prisoners action) and run it.

Of course this simulation can onle give you proof that your idea might be wrong but if you got the right one then every single run should frustrate the poor warden…

PS: of course I will post my solution (and maybe even a formal proof for it) in a few days…