algorithm - 箱の中から自分の番号を見つける

Question

100 人 (または偶数 2N :-) の囚人が部屋 A にいます。囚人には 1 から 100 までの番号が付けられています。

囚人1号から100号の順に1人ずつ、1から100までの100個の箱が並ぶ部屋Bに入れられます。(閉じた) ボックスの中には 1 から 100 までの数字があります (ボックスの中の数字はランダムに並べ替えられています!)。

部屋Bに入ると、各囚人は50個の箱を開けることができます（彼はどの箱を開けるかを選択します）. 彼がこれらの 50 個のボックスの 1 つに割り当てられた番号を見つけた場合、囚人は部屋 C に入ることができ、次のボックスが部屋 A から部屋 B に入る前に、すべてのボックスが再び閉じられます。部屋A、B、C）が殺されます。

部屋 B に入る前に、囚人は戦略 (アルゴリズム) に同意することができます。部屋間で通信する方法はありません (部屋 B にメッセージを残すことはできません!)。

すべての囚人が生き残る確率を最大化するアルゴリズムはありますか? そのアルゴリズムが達成する確率は?

ノート：

• 物事をランダムに行う (「戦略なし」と呼ばれるもの) と、確かに各囚人に 1/2 の確率が与えられますが、すべての囚人が生き残る確率は 1/2^100 (非常に低い) です。もっとうまくやれる！

• 囚人は箱を並べ替えることはできません！

• 囚人が最初に自分の番号を見つけられなかった場合、すべての囚人が殺されます。しかも通信不可。

• ヒント:平均して30 人以上の囚人を救うことができます。これは (50/100) * (50/99) * [...] * 1 よりもはるかに多くなります。

Answer 1

このパズルはhttp://www.math.princeton.edu/~wwong/blog/blog200608191813.shtmlで説明されており、その人は問題をよりうまく説明しています。

「すべての囚人が殺される」という声明は間違っています。「平均して 30 人以上救える」というのも間違いで、記事には 30% の確率で 100% の囚人を救えると書かれています。

Answer 2

この種の問題に対するローテクな解決策が常に最善の方法だと思います。

まず、状況についていくつかの仮定を立てます

• 囚人はすべてのプログラマーや数学者ではありません
• 彼らは死にたくない
• 警備員は十分に武装しています

したがって、彼らが明日目にする可能性は0.005％であり、この問題に対する非常にシンプルでローテクな解決策があります。暴動

損失と潜在的な利益のすべてについて、囚人が警備員の数をはるかに上回り、お互いを人間の盾として使用している可能性があります。警備員、彼らが彼の武器を手に入れると、チャンスが上がり、より多くの警備員がより多くの火力を得て生存率をさらに高めるのを助けます。警備員が何が起こっているのかを理解すると、おそらく丘に向かって走り、刑務所を封鎖します。これにより、メディアは頭を上げ、人権問題になります。

Answer 3

並べ替えアルゴリズムを実装し、ボックス内の数字に従ってボックスを並べ替えます。

最初の囚人は 50 個の箱を仕分けし、2 番目の囚人は残りの 50 個を仕分けして最初の箱と合流させます。(2 番目の囚人は、最初の 50 ボックス内の値を推測できることに注意してください)

2人目の囚人以降は、すべての箱が並び順になります!!!

そうすれば、他の誰もが自分の番号が入った箱を簡単に開けることができます。

Answer 4

これが許可されているかどうかはわかりませんが、私が見つけることができる最良の概算は次のとおりです。

編集：わかりました、これでうまくいくと思います。もちろん、私はこれをコンピューティングの問題として扱っています。囚人がこれを実行できるとは思いませんが、そうでない場合はかなり簡単です。

最初の 50 個の素数を見つけます。それらを素数という配列に保持しているとしましょう。

• 最初の囚人は部屋 B に入り、最初の箱を開けて数 m を見つけます。
• 素数[1] ^ mを待ちます（3 ^ mになります）
• ボックス 2 を開き、数字を読み取ります --> n
• Wait (primes[2]^n - 1) * primes[1]^m、それは (5^n - 1) * 3^m となり、彼が待っていた合計時間は 3^n * 5^n になります。

繰り返す。最初の囚人の後の合計時間は次のようになります: 3^m * 5^n * 7^p ... = X

2 番目の囚人が部屋に入る前に、X を因数分解します。使用された素数は事前にわかっているので、因数分解は自明です。そうすることで、m、n、p などを取得できるため、2 番目の囚人は、前の囚人が使用したすべてのボックス/数字の組み合わせを知ることができます。

最初のもので全員が殺される確率は 1/2 で、2 番目のものは 50 / (100 - n) (最初のものの試行回数は n) で、3 番目のものは 50 / (100 - n) です。 - m) (n + m = 100 の場合、すべての位置が既知です) など。

明らかに、次の囚人は既知のボックスを飛ばさなければならない (彼の番号を含むボックスが既に知られている場合の最後の選択を除く)。

選択肢の数にもよるので正確な可能性はわかりませんが、かなり高いと思います。

編集: 再読すると、囚人が自分の番号を取得するときに停止する必要がない場合、グループ全体の確率は大幅に改善され、正確に 50% になります。

EDIT2：@OysterDはこのように見てください。最初の囚人が 50 個のボックスを開くことができた場合、2 番目の囚人は自分の番号がそのボックスのいずれかにあるかどうかを知っています。そうである場合、彼は他の 49 を開き (そして、100 個のボックスのボックス/番号の組み合わせを学習することによって)、最終的に自分の 1 つを開きます。したがって、最初の囚人が成功すれば、全員が成功します。各囚人は、彼が開くすべてのボックスのボックス/番号の組み合わせを正確に知る方法を他の囚人に提供することを忘れないでください.

Answer 5

正しく読んでいないのかもしれませんが、質問の構成が間違っているか、情報が不足しているようです。

これらの50個のボックスのいずれかで自分に割り当てられた番号を見つけた場合、囚人は部屋Cに入り、次のボックスが部屋Aから部屋Bに入る前に、すべてのボックスが再び閉じられます。部屋A、B、C）が殺されます。

そこにある最後の文は、囚人が最初に自分の番号を見つけられなかったときにすべての囚人が殺されることを意味しますか？そうでない場合、自分の番号が見つからない囚人はどうなりますか？

通信が不可能で、囚人が部屋Bに入るときはいつでも、それは常に同じ状態にある場合、戦略の可能性はありません。

囚人は、部屋Aを出る前に、どのナンバーボックスを開けるかを言うことができます。しかし、次の囚人が部屋Bに入るときに、次の囚人が成功したかどうかを知らなくても（1人の失敗がすべての失敗ではないと仮定して）、前の囚人と同じ番号を選ぶ確率があります（常に1：100） 。

一人の失敗がすべての失敗である場合、前の囚人がどの箱を開けたかを知ることによって、そして彼らがすべて殺されていないという事実によって、連続する囚人はそれぞれ、間違った箱を選ぶ確率を1箱減らすことができます。つまり、最初の囚人は1：100、2番目の囚人は1:99、最後の囚人は1：1になります。

Answer 6

囚人は、囚人1が箱1-50を開くことに同意することができます。

彼ら全員がまだ生きている場合、彼らは次の囚人がボックス2-51を開くことに同意します。（2は任意ですが、このルールを覚えるのは簡単です）P1が生き残ったとすると、彼が生き残る確率は50/99になります。前の男が彼を見つけたことがわかっているときに、箱を開けることを排除したいとします。

それが最適かどうかはわかりませんが、ランダムよりもはるかに優れています。

次のように見える生き残る確率

50/100 * 50/99 *50/98*。。.50 / 51 * 1

Answer 7

誰かが番号を見つけられなかったときにすべての囚人が殺された場合、100人を救うか0人を救うかのどちらかです.30人を救う方法はありません.

Answer 8

コミュニケーションが取れないので、最善の戦略は

各囚人の確率をできるだけ均等に分配する

私は正しい道を進んでいますか？

各囚人が入手できる情報:

• 生き残った囚人の数なので、囚人が部屋Bに入る順序を利用した効率的なボックスピッキングシステムがあれば、戦略は間違いなく可能です
• 以前の囚人が選んだ箱。もちろん、実行中の通信は不可能であり、100 のボックス ピッキング順列を思い出すことはできません。ただし、この情報を使用して、実行を開始する前にシステムで計算できます。

私の見解：

1. 2 列の数字の表を作成します。最初の列にはボックス番号 (ボックス #1 からボックス #100 まで) が含まれます。次に、各囚人は 50 個の箱を選ぶことができ、どの箱を選んでも、2 列目の対応する行に 1 つのマークを付ける必要があります。
2. ただし、すべての囚人は、ボックスを 2 回選択してはいけません。また、ボックスに 50 を超えるマークを付けることはできません。一部のボックスが最初に 50 マークに満たされる可能性があるため、一部の囚人は他の人よりも選択肢が少ない場合があります。
3. 囚人が部屋 B に移されたとき、彼/彼女は自分がマークした箱を開けます。

Answer 9

同じコンセプト。

別のテイク：

1. 50 個の 1 と 50 個の 0 を含む最初の 100 個の 2 進数のリストを書き留めます。
2. それらを最低から最高に並べ替えます。
3. 囚人 #1 は最初の数字、囚人 #2 は 2 番目、囚人 #3 は 3 番目というように...
4. 各囚人は自分の 2 進数を覚えています。
5. 囚人が部屋 B に移動すると、覚えている数字の 2 進数を各ボックスと照合し、最も高いビットを左端のボックスと照合し、次に高いビットを左から 2 番目のボックスと照合します。 .. 最下位ビットは右端のボックスと一致します。
6. 彼/彼女は、1 に一致するボックスをすべて開き、0 に一致する閉じたボックスをそのままにします。

初期の囚人は後の囚人とは異なる数字を取得し、番号が互いに近い囚人は数字が互いに近づくため、これにより確率が最小限に抑えられます。これは生存可能性を保証するものではありませんが、初期の囚人が生き残った場合、後の囚人も生き残る可能性が高くなります.

正確な数字や根拠はまだ考えていませんが、現時点で思いつく手っ取り早い解決策の 1 つです。

Answer 10

質問には時間制限がないので、囚人は箱ごとに 1 時間かけて提示された順序で開けることをお勧めします。2 番目の囚人が 2 時間後に部屋に入ることを許可された場合、最初の囚人がボックス 2 で自分の番号を見つけたことがわかります。したがって、彼はボックス 2 をスキップしてボックス 1、3、4...51 を順番に開くことを知っています。囚人が負ける確率は 50/100 最初の囚人が生き残ったとすると、2 番目の囚人が勝つ確率は 50/99 なので、答えは ((50 ^51)*49!)/100! グーグルによると 2.89*10^-9 となり、これはほぼゼロです。したがって、囚人が箱を知っていたとしても、以前は幸運だった囚人が自分の番号を見つけたとしても、希望はありません。