囚人と箱

囚人に関する別のタスク。 今回はそれほど理論的ではありません。



1から30までの番号が付けられた30人の囚人がいます。誰もが自分の番号を含むすべての番号を知っています。 アルゴリズムについて議論する時間があります。 次に、それらは1つずつ30個の番号付きボックスがある部屋に運ばれます。 各ボックスには、囚人の番号を持つキーが1つあります（ボックス番号とその中のキー番号は異なる場合があります）。 ボックス内のキーは完全にランダムに分散されます（つまり、ボックス内のキーのすべての順列が同様に発生します）。 各囚人は順番に15個の箱を開けて、どのキーが入っているかを調べます。別の箱を開けると、まずどのキーが入っているかを確認し、次にどのキーを開くかを決定できます。 これらの15個の箱の1つにその番号のキーがあれば、彼らは彼を解放し、そうでなければ彼を撃ちます。 その後、部屋とその中のすべてのボックスが元の状態に戻ります。 次の囚人は、前の囚人に何が起こったかについての情報を受け取りません。

すべての囚人が少なくとも30％の確率で生き残るようにアルゴリズムを考え出します。



PSあなたは電卓を使用することができます。



コメントの UPDソリューション。