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. How can you 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.
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.
- You need Golang environment.
- Fork this repository to, say,
yourname/prisoners-switch. go get github.com/tarao/prisoners-switch- Note that it isn't
yourname/prisoners-switchbuttarao/prisoners-switch.
- Note that it isn't
cd "$GOPATH"/src/github.com/tarao/prisoners-switchgit remote add yourname git@github.com:yourname/prisoners-switchgit checkout -b your-answer- Edit
strategy/my_strategy.goand write your strategy, and thengit commitit. git push --set-upstream yourname your-answer- Make a pull request from
your-answerbranch to themasteroftarao/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
importnothing other thangithub.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してください.
- Golang環境を用意
- このリポジトリを
yourname/prisoners-switchにFork go get github.com/tarao/prisoners-switchyourname/prisoners-switchではなくtarao/prisoners-switchな点に注意
cd "$GOPATH"/src/github.com/tarao/prisoners-switchgit remote add yourname git@github.com:yourname/prisoners-switchgit checkout -b your-answerstrategy/my_strategy.goを編集して解答してgit commitgit push --set-upstream yourname your-answeryour-answerブランチをtarao/prisoners-switchのmasterブランチにPull Requestする
解答は以下の制限に合致している必要があります.
- 書き換えてよいのは
strategy/以下のみ- ファイルを追加してもよい
- 変更ファイル数の上限は20
github.com/tarao/prisoners-switch/rule以外をimportしてはいけない
うまく解けているか手元で確認したい場合はverifier/runを実行すると確認できます.
- MIT