The Prisoners and the Switch Room Problem

The Problem

You are one of a hundred prisoners. You all put into a game described below, in which you will be set free if you win but will be executed if you lose.

• When the game starts, you will be in isolated cells.
  • You cannot talk to other prisoners during the game.
• You will randomly picked one by one into a switch room.
  • Each prisoner will visit the room arbitrarily often if he waits enough.
  • You will never know who is in the room now except when you are in the room.
  • There are only two switches (A and B) in the room and nothing else.
  • Nobody except the prisoners will enter this room.
• You can do only two things in the switch room:
  • see the state ("on" or "off") of the switches, and,
  • toggle one of / both of / none of the two switches.
• Every prisoner can assert at any time that "everybody visited the switch room at least once".
  • If it is true, then you win the game.
  • If it is false, i.e., someone has not yet visited the switch room, then you lose the game.
• The initial states of the two switches are decided at random.

Before starting the game, you all may meet together and plan a strategy. Provide a strategy which guarantees you can always win the game.

---

If this is too easy for you, improve the strategy by

• minimizing (the expected value of) the total number of visits to the switch room, or,
• using only one switch throughout the game.

Giving a Solution by a Program

You can give a solution by forking this repository and making a pull request. It will be automatically verified that it is a correct strategy. Follow the instructions below to make a pull request.

1. You need Golang environment.
2. Fork this repository to, say, yourname/prisoners-switch.
3. go get github.com/tarao/prisoners-switch
   • Note that it isn't yourname/prisoners-switch but tarao/prisoners-switch.
4. cd "$GOPATH"/src/github.com/tarao/prisoners-switch
5. git remote add yourname [email protected]:yourname/prisoners-switch
6. git checkout -b your-answer
7. Edit strategy/my_strategy.go and write your strategy, and then git commit it.
8. git push --set-upstream yourname your-answer
9. Make a pull request from your-answer branch to the master of tarao/prisoners-switch.

There are some restrictions you need to follow.

• You can change nothing other than files under strategy/.
  • You may create a new file
  • The maximum number of changed files is 20.
• You can import nothing other than github.com/tarao/prisoners-switch/rule.

To verify the strategy locally, run verifier/run.

問題

あなたは100人の囚人の一人です. 全員で以下のようなゲームをして, 見事勝利できれば全員釈放, 負ければ全員死刑となります.

• ゲーム開始と同時に全員別々の独房に入ります
  • 独房内や通路で他の囚人とやりとりすることはできません
• ランダムに1人ずつスイッチの部屋に呼ばれます
  • 十分な時間待てば同じ人が何度でも呼ばれます
  • いま誰が呼ばれているかは本人以外にはわかりません
  • 部屋にはスイッチが2つ(AとB)ある以外はなにもありません
  • ゲームに参加中の囚人以外がこの部屋に入ることはありません
• スイッチの部屋では以下のことができます
  • 2つあるスイッチのon/offの状態を確認する
  • 2つあるスイッチのいずれか, もしくは両方のon/offを切り替える
• 囚人はいつでも「全員スイッチの部屋に入った!」と宣言することができます
  • 本当であれば勝利となります
  • まだ一度も部屋に入っていない人がいたらその時点で負けです
• ゲーム開始時点でのスイッチの状態はランダムに決められます

ゲームを開始する前に, 囚人全員で集まって作戦を立てることができます. 必ず勝利できる作戦を考えてください.

---

答えがわかって物足りなければ以下についても考えてください.

• スイッチの部屋に入った総回数(の期待値)がなるべく少なくなるような作戦を立ててください
• スイッチを1つしか使わずに勝利する方法を考えてください

プログラムによる解答方法

このリポジトリをForkしてPull Requestすることで解答できます. 正しく解答できているかどうかは自動的にチェックされます. 以下の手順に従ってPull Requestしてください.

1. Golang環境を用意
2. このリポジトリをyourname/prisoners-switchにFork
3. go get github.com/tarao/prisoners-switch
   • yourname/prisoners-switchではなくtarao/prisoners-switchな点に注意
4. cd "$GOPATH"/src/github.com/tarao/prisoners-switch
5. git remote add yourname [email protected]:yourname/prisoners-switch
6. git checkout -b your-answer
7. strategy/my_strategy.goを編集して解答してgit commit
8. git push --set-upstream yourname your-answer
9. your-answerブランチをtarao/prisoners-switchのmasterブランチにPull Requestする

解答は以下の制限に合致している必要があります.

• 書き換えてよいのはstrategy/以下のみ
  • ファイルを追加してもよい
  • 変更ファイル数の上限は20
• github.com/tarao/prisoners-switch/rule以外をimportしてはいけない

うまく解けているか手元で確認したい場合はverifier/runを実行すると確認できます.

License

• MIT