囚人と帽子問題
様々なバリエーションがある
有名な問題
P人の囚人がいる
3人のパターンはカイジのやつ.
それぞれの囚人が赤か青の帽子をかぶる.
自分の帽子が赤い帽子か青い帽子を列の後ろから順番に答えていく.
自分の後ろの囚人の解答は聞こえる.
その解答が正解かどうかはわからない.
自分の前の囚人の帽子の色は見えるのでわかる.
回答すること以外のメッセージングは禁止.
少なくともP人のうちP-1人が正解する方法は？
↑に加えていろいろ条件がつくことがある
「耳栓をしている場合」
「前の帽子の色も見えない場合」
「解答までの時間はすべて1msとする」場合
プログラミングの問題っぽくないが、並行処理の教科書に載っていたnikezono.icon
「解答までの時間はすべて1msとする」(カイジ的解法を禁止する)場合が面白い
難しいね 増井俊之.icon
ていうか帽子はどこいったの
寝ぼけてました、帽子とスイッチ別の問題だったnikezono.icon
w
パス発声が可能な囚人と帽子問題
shoko.icon
囚人3人が白か赤の帽子をかぶります。(自分のは見えない、他2人の帽子は見える)
3人それぞれが以下の3ついずれかの行動をとります。
自分の帽子は白だと言う
自分の帽子は赤だと言う
パスする
全員がパスしたら全員死亡します。
「白」か「赤」の選択をして、帽子の色を答えた人が「全員正解」したら、3人とも生き延びます
もっとも生存率を高める戦略として、どんな戦略が考えられるでしょうか？
増井俊之.icon
ふたりパスしてももうひとりが正解したら良いてこと?
他人の答は聞こえるの?
聞こえなければ情報ゼロだから聞こえるのかな?
他人の答えを聞いた後に言うことは出来ず、全員「せーの！」で上記3択のいずれかを答えますshoko.icon
shoko.icon
1番に思いつく答えとして「Bさん、Cさんはパスして。Aさんが答える」だと、50％ですが、
それより成功率を上げる方法があります（ただし、100%には出来ません）
ytanaka.icon
自分以外の２人が同色ならそれと反対の色（例: 自分以外が２人が黒なら白と答える）それ以外の場合はパスする
こうすると全員同色の場合以外は正解できる（6/8=75%で正解なので50%よりも高い）
とかですかね？
正解ですー！shoko.icon
お、ありがとうございます！
解答が見えてしまうと良くないので表示方法考えたいですね