百箱と囚人の救出の仕事-最後の和音

歴史に残る確実な方法は、両方の完璧なゲーム（白、黒、または友情）で誰がチェスに勝つかを答えることです。 グランドマスターとスーパーコンピューターは真実を知る必要がありますか？ それとも鉛筆、紙、そして美しいアイデアですか？



数学は希望を呼び起こします。オブジェクトを提示せずに存在の証明ができ、その理由を説明せずに答えを見つけられるからです。



囚人と百箱の問題では、同様の状況。 膨大な数の可能なゲーム戦略があり、そのうちの1つは直感的に最高のように思えました。 しかし、オプションの混乱に陥ることなく、その最適性を正当化することは可能ですか？



問題に関する投稿では、この質問は提起されていません。 しかし、彼に関する最初の解説ですでに、ユーザーmayorovpはトピックを取り上げており、 avfonarevのすぐ下に、秘密を明らかにする素晴らしい記事が報告されています。



特に推論はシンプルでエレガントなので、吹き込む価値があります。 一般的に、この投稿の主なアイデアは、特定の問題（それ自体も興味深い）を解決することではなく、力や、Wignerが言うように、数学の不可解な有効性に疑問を持つ理由をもう一度与えることです。

問題の状態と解決策について簡単に

100人のプレイヤーが100個のボックスに配置された番号のトークンを見つけなければならないことを思い出させてください。 誰もが好きな順序で半数以下を覗くことができます。 テスト中、すべてのボックスとトークンはそのまま残り、プレイヤーは会わず、他の方法で情報を交換することはできません。ボックスは、一見した後、再び閉じられます。 すべての参加者が自分の番号を見つけることができた場合にのみ、チームが勝ちます。



プレイヤーがランダムにボックスを開くと、勝利の確率は（50/100） ¹⁰⁰ 、つまり約10 ^-29 ％になります。 ただし、最初に同意する必要があります（注意、ネタバレ！）勝つ可能性はほぼ31.2％になります！



これを行うには、次の戦略を使用します。各参加者は、独自の番号を持つボックスで検索を開始し、新しく発見されたトークンの番号でボックスを開く必要があります。



さらに詳しく思い出すには、タスクに関する元の投稿を読むか、 andreymironovが説明した1 分半のビデオ「 不可能な賭けの解決策 」を見ることができます。



しかし、ケースの31.2％よりも頻繁に勝つことが不可能（または可能）な理由を理解したいと考えています。

回避策-新しいゲームを検討する

上記のストラテジー（ 基本と呼びましょう）は、100 ¹⁰⁰ * 99 ^{100 * 99} * ... * 51 ^{100 * 99 * ... * 51}プレーヤーがプレイできるオプションの1つです（「ストラテジー数のカウント」セクションを参照）。 したがって、単純に基本戦略を他のすべてのものと直接比較するだけではうまくいきません。



「 The Locker Puzzle 」の記事では、別のゲーム（ newまたはsecondと呼びます）の探索から始めることが提案されています。 このゲームでは、ボックスが閉じず、プレイヤーは試行回数に制限なく番号を探します。 正確なルールは次のとおりです。



-プレーヤーは順番にテストに合格します-最初は最初、次に2番目、3番目など。



-最初のプレーヤーは、何回の試行が必要であっても、自分の番号が見つかるまでボックスを開かなければなりません。 彼が開いた箱は閉じません。



-2番目、3番目、およびそれ以降のプレイヤーは、まず、すべての開いているボックスで自分の番号を見つけようとします（開いているボックスを調べることは試行とは見なされません）。 これが成功しなかった場合（のみ）、目的のトークンが見つかるまで閉じたボックスを開く必要があります。 開いているボックスも閉じません。



-チームが勝つのは、参加者が自分の番号を見つけるために50回を超える試行を必要としない場合、つまり、ボックスの総数の半分以上を開く必要がなかった場合のみです。



ボックスは閉じないので、開いているほど、プレイヤーが勝ちやすくなります。 たとえば、最初の参加者が35個のボックスを開かなければならなかった場合、別の34人のプレイヤーは数字を検索する必要がなく、残りのプレイヤーはトークンを見つけることができる65個のオプションしかありません。



さらに、自分の番号を探しているプレイヤーが、たとえば20個以上のボックスを開いた場合、100-35-20 = 45個の未開封のボックスがあるため、チームはまったく失うことができません。不可能。



勝利の条件は非常に興味深いものです。 誰かが50個以上のボックスを開いた場合、単にゲームを中断できるように思えます。 しかし、さらなる議論のために、明らかに負けたとしても、プレイヤーが任意の数のボックスを開くことができるようにする方がより有益であることがわかります。





紹介した新しいゲームには3つの興味深い特性がありますが、これについては後で説明し、合理的な答えを出します-基本的な戦略が勝利の最大確率を提供するかどうか。

プロパティ1-新しいゲームでの勝利をより簡単に

箱が閉じないため、チームは元のゲームよりも新しいゲームに勝つ方が簡単だと思われます。



実際、参加者がどの戦略を最初のテストで受けたとしても、新しい戦略を取るためにそれを適応させることができます。



これを行うには、開いているボックスで数字を見つけられなかったプレーヤーは、最初のゲームと同じようにボックスを開く必要があります。 さらに、戦略が既に開いているボックスを開くように指示した場合、彼らは単に試行を保存します。



ボックス内の数字の同じ配置に対して、プレーヤーが最初のゲームに勝った場合、2番目に勝つことは明らかです。 したがって、最初のテストに合格する最大の確率は、新しいテストより大きくなることはできません。



言い換えれば、最初のゲームに勝つ最大確率が40％だった場合、同じテスト以上のチャンスで新しいテストに合格することができます。このプロパティを1と呼びます 。

プロパティ2-新しいゲームでは、チームの戦略に依存するものはありません

考えてみれば、最初のプレイヤーがどの戦略に従うべきかは関係ありません-どんなに頑張っても、試行回数の制限内で数を見つける確率は50/100 =½になります。 それは、彼が選択したアルゴリズムと、彼が開くボックスの数（1、2、30、100）に依存しません。



前の参加者が既にトークンを見つけたプレイヤーは、ゲームの状況に応じて、完全にゼロ試行で自分の数を見つけます-アクションのアルゴリズムを改善することはできません。



実際に自分の番号を探すことを余儀なくされる同じチームメンバーは、実際には最初のプレーヤーと同じ状況にあります。成功する可能性は、既に開いている戦略や選択した戦略の内容ではなく、閉じたボックスの数に依存します。



新しいゲームに勝つ確率は、チームのアルゴリズムに依存しないという感覚があります。 このプロパティを2と呼び、より正式に正当化します。



便宜上、6つのボックスとプレーヤー、および3つの試行があると仮定します。



参加者が新しいルールに従ってテストに合格し始め、成功の概要を説明したいと考えています。 ゲームプロセスは、チームが発見したトークンの番号を、発見された順序で示す1行の数字で十分詳細に説明できることがわかりました。



たとえば、レコード（2、5、1、3、6、4）を簡単に解読できます。 実際、ゲームの条件によれば、最初のプレイヤーは1が見つかるまでボックスを開かなければなりませんでした。したがって、2、5、1の3つの（重要ではない）ボックスを開いた最初の参加者を明確に復元できます。する必要はありませんでした。彼のトークンは、最初のプレイヤーが既に開いた箱の中にありました。 その後、3番目は最初の試行で成功し、最後に4番目は6と4を見つけました。5番目と6番目の参加者、および2番目の参加者は、作業する必要がありませんでした。



別の例-テストに合格した結果が行（6、1、5、3、4、2）で記述されているとしましょう。 最初の参加者が既に2番目のオープンボックスでバッジを見つけたのは簡単です。2番目のプレーヤーは不運でしたが、4回の試行が必要だったため、チームは敗北を数えました。



プレーヤーが見つけたトークンの数に対応する6つの数字の行が、テストの結果（チームの勝敗）を一意に決定することがわかります。



ちなみに、（2、5、1、3、6、4）や（6、1、5、3、4、2）などの文字列、つまり1から6までの数字を繰り返しなく含む文字列は、 1から6まで。合計6個のそのような置換があることが知られています。 = 6 * 5 * 4 * 3 * 2 * 1。



トークンはランダムにボックスに配置されているため、等しい確率の各ボックスには6つの数字を使用できます。 したがって、最初のプレイヤーがどのアルゴリズムに準拠していても（たとえランダムに選択したとしても）、1/6の等しい確率で、彼が開いた最初のボックスに6つの数字を見つけることができます。



チームによって開かれた2番目のボックス（誰でも-最初の参加者でも2番目の参加者でも-考慮事項に応じて）同じ確率で、1/5は残りの5つの数字のいずれかです。



議論を続けると、トークンの数をそれらが見つかった順序で書き留めると、同じ確率（1/6）*（1/5）* ...（1/2）*（1/1）= 1/6！ 6のいずれかを入手してください！ 1から6までの数字の可能な順列。



上記のように、たとえば（2、5、1、3、6、6、4）などの順列はプレーヤーのゲインを示し、特に（6、1、5、3、4、2）-損失を示します。 Aをチームの勝利を意味するすべての順列のセットとします。 A |、それぞれ、そのような順列の数。



すべての順列はゲームから等しく発生する可能性があるため、プレーヤーに勝つ可能性は等しくなります。 A | / 6！ そして、あなたが見ることができるように、彼らは彼らが選んだ戦略に依存しません。 プロパティ2が証明されました。

特性3-基本戦略を使用した場合の勝利の確率は、新しいゲームに勝つ可能性に等しい

元のゲームに戻ります。 基本的な戦略（プレイヤーが自分の番号のボックスで検索を開始し、見つかったトークンの番号に従う必要がある戦略）を使用して勝つ確率は、<長さサイクルを含まない1から6までの番号の順列の数に等しいことを思い出してください3> / 6以上！ （以前と同様に、6つのボックスとプレーヤー、および3回の試行があると想定されています）。



B -1から6までの数の順列のセットを表す場合、3を超える長さのサイクルは含まれません。 B |、それぞれ、そのような順列の数、上記の式は形式を取ります| B | / 6！





また、前のセクションで実行したばかりの引数を思い出してください。新しいゲームに勝つ最大（そして唯一の）確率は、<プレイヤーの勝利を意味する順列の数> / <順列の総数>または| A | / 6！ 表記法で。



セットAとBの順列はやや似ていることに注意してください。 特に、それらも他のものも、3つ以下の数字を含む「断片に」壊れています。



したがって、Aからの順列（2、5、1、3、6、4）は、各部分のみという原理に従って、条件付きで3つの部分<2、5、1>、<3>、<6、4>に分割できます。 1人のプレーヤーが開く番号（<2、5、1>は最初の参加者が、<3>が3番目、<6、4>が4番目）。



このような「ピース」の特徴は、それらの最小要素が常に最後の場所にあり、「ピース」自体が最小要素の昇順で配置されることです。 これを強調するために、最小要素を太字で強調表示しています：<2、5、1>、< 3 >、<6、4>。



同様に、 Bからの順列、たとえば（2、5、3、6、1、4）は、互いに素なサイクルの積として表すことができます：（2、5、3、6、1、4）= [1、2、 5] [3] [4、6] = [3] [1、2、5] [4、6] = [3] [5、1、2] [6、4] = ...



そのような表現のすべての可能な変形のうち、サイクルの最小要素が最後の場所にあり、サイクル自体が最小要素の昇順で配置されている唯一のものを選択します。 （2、5、3、6、1、4）= [2、5、1] [ 3 ] [6、4]。



Bの順列（2、5、3、6、1、4） は条件付きで「ピース」<2、5、1>、< 3 >、<6、4>に分割されます。 Aの順列（2、5、1、3、6、4） これは、 Aからの順列をBからの順列に、またはその逆に変換できるアルゴリズムを示しています。



実際、 Aから順列（2、5、1、3、6、4）を取得し、上記のように「ピース」<2、5、1>、< 3 >、<6、4>に分割し、これに置き換えます角カッコを四角に、コンマをサイクルの乗算記号（この場合はスペース）に書き込み、[2、5、1] [ 3 ] [6、4] =（2、5、3、6、1、4 ） Bから



反対方向にも：（2、5、3、6、1、4） Bから[ 2、5、1 ] [ 3 ] [6、4]の形式で表し、括弧を変更し、コンマを追加し、結果のピースを「接着」する<2、5、1>、< 3 >、<6、4>をAの順列（2、5、1、3、6、4）に変換します。



相互変換の別の例を次に示します。（6、1、4、2、3、5）from A <-> <6、1>、<4、2>、< 3 >、< 5 > <-> [6、1 ] [4、2] [ 3 ] [ 5 ] = Bの（6、4、3、2、5、1 ） 。



したがって、集合AとBの要素は、上記の順列アルゴリズムに従って相互に変わるペアに分割されます。 数学の言語では、これは集合AとBの間で全単射が構築されることを意味します。したがって、それらは同じ数の要素を持ちます。 | A | = | B |。



これは、基本戦略（| B | / 6！）を使用して初期テストに合格する可能性と、新しいゲームに勝つ確率（| A | / 6！）が等しいことを意味します。 このプロパティを3と呼びます 。

結論-基本的な戦略の最適性

明確にするために、プロパティ1、2、および3は、6つのボックス、6人のプレーヤー、および3回の試行があるゲームの例で証明されています。 ボックスとプレイヤーがn （100など）で、試行がk （50など）の一般的な場合でも、まったく同じ推論を繰り返すことができることは明らかです。



考慮されたプロパティから、2つのステートメントが続きます。



1）新しいゲームに勝つ確率は、チームの戦略（プロパティ2）に依存せず、基本戦略（プロパティ3）を使用したときに最初のテストに合格する可能性とまったく同じです。



2） 基本戦略は、チームが元のゲームに勝つ可能性を最大限に高めます。これは、他の戦略が勝利の確率を高める場合、成功の可能性が高くなると、新しいテストに合格する可能性があるためです（プロパティー1）。これはステートメント1と矛盾します。 ）上記。



したがって、各プレイヤーが自分の番号を持つボックスで検索を開始し、新しく発見されたトークンの番号でボックスを開くと、チームは可能な限り高い確率で勝ちます。 参加者はこれ以上何も考えられません。 これは直感的な提案であるだけでなく、実証済みの事実でもあります！



考えてみてください。考えられる膨大な数のゲーム戦略がそのまま残っています-他のゲーム戦略との根本的な違いを理解せずに、そのうちの1つの最適性に関する質問に答えました。



この勝利の可能性を計算する必要さえありませんでした。 このような問題を本質的に考える必要はありませんでした。戦略とは何で、いくつあるのでしょうか。 基本戦略が唯一の最適な戦略ですか、それとも他にありますか？ n個のボックス、 m人のプレイヤー、 k回の試行の場合、勝利の最大確率を計算する式は何ですか？



だから、最初に数学が勇気づけられると書いたのです。例えば、両サイドに完璧なゲームがあるチェスでは、常に白か黒の引き分けまたは勝利があることを証明するだけで、歴史に残ることができます。 zugzwangで最初の動きから白！）。 数学の「理解できない効率」、提起された質問に美しく正確に答える驚くべき能力により、チェス理論に深く入り込む必要も考えられない計算能力を使用する必要もまったくない可能性があります。



新しい高みへ！ 百箱の仕事をより深く理解し、囚人を救うことに興味がある人のために、ボーナスの章が用意されています。

ボーナス 戦略の数を数える

チームのアクションのアルゴリズム（プレーヤーの集合戦略と呼びましょう）は、各プレーヤーのアクションのアルゴリズムで構成されています（プレーヤーの個々の戦略と呼びます）。



参加者は、バックグラウンドに基づいて、開いている次のボックスの番号を明確に選択する、つまり、ランダムなメカニズムを使用しないことを前提としています（たとえば、残りのボックスを偶然選択することはできません）。



次に、たとえば最初のプレーヤーの個々の戦略は、次の形式の表の行で説明できます。

ターン1	移動2				移動3
	2	3	...	n	...

最初のプレーヤーが検索を開始するボックスの番号は、最初の列に書き込まれます（「ターン1」）。 列2、3、...、 n （共通の見出し「移動2」の下）には、次のボックスの番号が書き込まれます。それぞれ、番号2、3、...、 nのトークンが開かれた最初のボックスで見つかった場合に開きます。 。 移動2を設定するには、 n -1の番号が必要です（名前1の列がないため、 nではなく、参加者1が番号1のトークン（つまり、自分のトークン）を見つけた場合、検索を続行する必要はありません）。



共通の見出し「移動3」の下の列には、最初に開いた2つの引き出しで見つけた数字に応じて、プレーヤーがトークンを探す3番目のボックスの番号が記録されます。 移動3を設定するには、すでに（ n -1）*（ n -2）の数字を示す必要があります（1の過程で、 n -1の数字の1つを検出でき、2の過程で： n -2 、もう捕まることはありません）。



「移動3」のキャップは次のようになります。

移動3
2				3	...	n
3	4	...	n	...	...	...

コースkを設定する必要がある場合は、 （ n -1）*（ n -2）* ... *（ n - k + 1）列が必要です。



このようなテーブルの行に入力できる方法の数を計算します。



最初の列には、 n個の数字を書くことができます。 （ n -1）の各セルには、まだ開いていない（ n -1）個のボックスを含めることができるため、2回目の試行の列には（ n -1） ^{n -1の}メソッドを入力できます。



^{（ n -2）の}いずれかのセルを（ n -1）*（ n -2）の各セルに置き換えることができるため、3回目の試行で列を埋めるオプションは既に（ n -2） ^{（ n -1）*（ n -2）です} 2）まだ開いていない箱の数など



k回目の試行に対応する列は、（ n - k + 1） ^{（ n -1）*（ n -2）* ... *（ n - k + 1）}メソッドで埋めることができます。



その結果、 n *（ n -1） ^{n -1} *（ n -2） ^{（ n -1）*（ n -2）} * ... *（ n - k + 1） ^{（ n -1）*（ n- 2）* ... *（ n - k + 1）}最初のプレイヤーの個々の戦略。 他のプレイヤーが同じ数の戦略を持っていることは明らかです。



プレイヤーは互いに独立して行動します。 集合戦略は個々の戦略の組み合わせであるため、合計数は各プレイヤーの個々の戦略の数を掛けることで得られます。

n *（ n -1） ^{n -1} *（ n -2） ^{（ n -1）*（ n -2）} * ... *（ n - k + 1） ^{（ n -1）*（ n -2）* ... *（ n - k + 1）}のn乗はn ⁿ *（ n -1） ^{n *（ n -1）} *（ n -2） ^{n *（ n -1）*（ n -2）} * ... *（ n - k + 1） ^{n *（ n -1）*（ n -2）* ... *（ n - k + 1）} 。



プレイヤーがボックスほど多くない場合は、 nの累乗ではなくmの累乗に上げる必要があります。ここで、 mはプレイヤーの数です。

ボーナス 最適戦略の一意性

興味深い質問は、基本戦略が唯一の最適な戦略であるかどうかです。 たとえば、プレイヤーは自分の番号のボックスからではなく、他の番号から検索を開始できますか？



テストの開始直前にボックスの番号が付け直されたと想像してください。 これがプレイヤーの戦略や勝利の確率に影響を与えないことは明らかです。 結局のところ、ボックスの番号を変更することはトークンを移動することと同じですが、すでに偶然に配置されると考えています。



プレイヤーは自分でメンタル的にボックスに番号を付け直すことができます。 たとえば、5番目のボックスを7番目、7番目を10番目、10番目を5番目と考えます。 この場合、同じ基本戦略の原理を使用して、5番目のプレーヤーが7番目のボックスから検索を開始し、テストで7が見つかった場合は10番目に、10が見つかったら5番目に移動するとします。



すべてのプレイヤーが精神的に同じ方法でボックスの番号を付け直した場合、チームが勝利する確率はまったく同じままになります。 上記の推論に加えて、この事実の正式な、純粋に技術的な証拠を与えることもできます（この投稿で書き直すほど興味深いものではないと思います）。



その結果、 n個のボックスに番号を付け直すことができるので、 n ！ メソッド、その後最適な戦略、少なくともn ！、しかし実際には、これらはすべて同じアクションアルゴリズムのバリエーションです。 ほとんどの場合、ボックスと同じ数のプレーヤーがいる場合、基本戦略とは本当に異なる他の最適な戦略はありません。 私の友人と私は、この事実の証拠をまだ見つけていません。



ボックスよりもプレイヤーの数が少ない場合、他の最適な戦略が可能です。これは実際の基本戦略とは異なります。 たとえば、4つのボックス、2人のプレーヤー、2回の試行がある場合、参加者は次のように行動できます。



最初のプレーヤーの戦略は、表の行で説明されています。

ターン1	移動2
	2	3	4
1	2	3	3

2番目のプレーヤーの戦略は、表の行で説明されています。

ターン1	移動2
	1	3	4
2	1	4	4

この場合、基本戦略を使用する場合と同様に、チームは10/24（4のうち10！= 24個のトークンをボックスに配置できるオプション）の確率で勝ちます。

一般的な場合の決定について

ゲームの現在の理解を考えると、 nボックス、 mプレーヤー、 k試行の場合の勝利の最大確率は次の式で計算されると仮定できます。

<要素1、2、...、 mが kより大きい長さのサイクルに含まれない順列の数> / n ！



たとえば、 n = mの場合、k≥n / 2の最も単純なケースでは、1-1 /（ k +1）-1 /（ k + 2）-...-1 / n



式の正式な証明と、さまざまなパラメーター値の明示的な導出は興味深い問題です。 興味のある順列の数が計算されるか、同様の組み合わせの問題が解決される記事へのリンクに感謝します。