フォーマットのあるゲーム

ゲームをプレイすることをお勧めします。 一部のセルが塗りつぶされ、一部のセルが空のままになる正方形のグリッドを提供します。 これを「テンプレート」と呼びます。 たとえば、グリッドは次のパターンのいずれかになります。









グリッドのサイズと形状に一致する透明なプラスチックシートのスタックがあり、その上に黒いドットのパターンが適用されます。









これらのパターンのそれぞれには、正確に3つのポイントがあり、各行と列に1つのポイントがあることに注意してください。 表示されている6つの組み合わせは、このプロパティを持つ3×3グリッドのみです。



あなたの仕事は、透明なシートのサブセットを収集し、それらをテンプレート上に置いて、ドットが塗りつぶされたすべての正方形をカバーするようにしますが、空の正方形に落ちないようにすることです。 塗りつぶされた正方形のいずれかに複数のドットを重ねることができますが、一般的には、できるだけ少ないシートを使用するよう努力する必要があります。 それをもっと面白くするために、私は入札することを提案します：3×3テンプレートを正しくカバーするために、私は3ドルを支払いますが、使用するシートごとに1ドルを支払う必要があります。 これはあなたにとって有益な賭けですか？



先に進む前に、このような規則に従ってすべての可能なテンプレートを閉じることができるとは限りません。 明白な例を見てみましょう-3つ未満の正方形が塗りつぶされている3×3テンプレートは、ドット付きの6つの透明なシートの組み合わせで閉じることはできません。 ただし、利用可能なドットパターンの組み合わせで閉じることができるパターンのみを提供することをお約束します。 これを間違えると、置いたお金を失います。



ゲームの結果はどうなりますか？ 上記で「1」とマークされたテンプレートを提供すると、簡単に勝つことができます。すべての塗りつぶされた正方形のみをカバーする組み合わせaとbを選択するだけです。 あなたは2ドルを支払い、3を与えます。9つの正方形がすべて満たされているテンプレート2は、最も難しいタスクのように思えるかもしれません。 明らかに、合計で9ポイント必要なので、パターン付きの3枚未満のシートで閉じることは不可能です。 そして、正確に3枚のシートが必要であることがわかりました。 実際、テンプレートを3つのシートでカバーする方法は2つあります： a + d + eおよびb + c + f 。 したがって、このテンプレートは損益分岐点の解決策を提供します。3ドルを稼ぎ、3ドルを使うことです。



次に、テンプレート3に進みます。テンプレート3では、塗りつぶされた正方形があり、1つは空です。 3つのシートだけで9つの正方形すべてを閉じることができる場合、8つを閉じることができることは明らかです。 試してみることをお勧めします。 実際、単一の適切な組み合わせには、 b + d + e + fの 4つのシートが必要です。 したがって、私の提案は受け入れられるべきではありません。私はいつでも空の正方形が1つだけのテンプレートを提供でき、あなたの損失は$ 1になります。

いくつかの背景情報

すぐにゲームテーブルに戻りますが、最初に、このタスクがどこから来たのかを説明します。 私はかつて「推定間隔」について書き 、それが順列行列のトピックを研究するようになりました。 すでに言ったことを繰り返します。

• 順列行列は、各列と各行に1つの1がある正方行列です。 残りの要素は0です。
• Ormatは、置換行列の対応する要素にブール関数ORを適用することにより形成される置換行列の重ね合わせです。 例：
  
  
  
  
  
  
  
  
  
  
• 要素（0,1）を持つすべての正方行列が順列行列のOR演算によって作成できるわけではありませんが、特定の行列が形式であるかどうかを判断するための効果的なアルゴリズムがあります。
• マトリックスの単位要素を通過できる形式の順列パスの総数は、マトリックスのパーマネントと同じです。 パーマネントの定義は、複雑な計算タスクと見なされます。

コメントで、Barry Zipraは次の質問をします。

パーマネントは、特定の形式を取得するためにORで合計できるさまざまな順列の最大数を示しますが、対応する最小数は何ですか？ また、最小値に到達する方法はいくつありますか？

これで、フォーマットと私の小さなゲームとの関係は明らかだと思います。 塗りつぶされた正方形と空の正方形のパターンが形式です。 ドット付きのシートは順列行列を示します。 ゲームでの勝利を最大化する（または損失を最小化する）には、最小数の順列を見つけてバリーの最初の質問に答える必要があります。



3×3行列の場合、6つの3×3順列行列1、2、3、...、6の可能なすべての組み合わせのOR和を同時に計算する徹底的な検索により、この問題を解決できます。 最近のフライトで、私は紙と鉛筆でこれをなんとかしました。 その結果、次の結果が得られました。









このカードの数字のいくつかは簡単に説明できます。 単一要素が3つしかない6つの形式は、順列行列そのものです。 3つの要素に対して3つが可能なため、6つあります！ = 6順列。 単一の要素が4つある形式はありません。反映すると、これは理解できます。1つの要素だけが互いに異なる順列はありません。 記事の冒頭に示されている6つのシートのいずれかを重ねると、3、5、または6ポイントを獲得できますが、4ポイントは獲得できません。



一方、9つの単一要素を持つ1つの形式があり、それを作成するには3つの順列が必要であることは驚くことではありません。 また、4つの順列に対してORを実行する必要がある8つの単一要素を持つ9つの形式があります。 これらは、テンプレート3の上に示すように、1つの空の正方形を持つテンプレートになります。



これらの結果に基づいて、4×4のすべての形式をテーブルに入れると何が得られるかを考え始めました。









4になります！ = 4つのユニット要素を持つ24パターン、および4つの順列のOR演算から作成されたすべてのユニットを持つ1つのパターン。 そして、5つの順列を必要とする16の形式、つまり単一のゼロ要素を持つ16の行列が必要です。 最後の予測は、他の予測ほど明白ではないようでした。

ポケットと朝食用シリアルからささいなこと

私はこのような単一のゼロ（または単一の空の正方形）の場合について話しました：それぞれ4つのポイントのセットで15の正方形を閉じるには、少なくとも4つのセットが必要です、そうでなければ、十分なポイントがありません。 したがって、有用な出発点は、スペースやオーバーレイなしで16個すべての正方形をカバーする最適なパターンの1つです。 この時点で、私は何十億ものポイントを描くのにうんざりしていたので、コインで作業を始めました。









このスキームでは、各コインの種類は順列を形成します。ペニー、5、10、または25セントの2つのコインは同じ列または行にありません。 塗りつぶされたすべての正方形を正常に閉じましたが、残念ながら、右下隅の空の正方形を閉じました。 このようなコインスキームは許容できる解決策ではありませんが、修正できるでしょうか。









空の正方形から同じ列の別の正方形にペニーを移動することで、1つの問題を解決しますが、別の問題を作成します。ペニーのレイアウトは順列ではなくなりました。3行目に2ペニーがあります。









つまり、「列と行ごとに1コイン」というプロパティを復元するために、もう1ペニーシフトする必要があります。 この場合、塗りつぶされた正方形は必然的に開いたままになります。 この自由な正方形を閉じることができる唯一の方法は、5番目の順列を追加することです。 コインの種類がなくなったので、朝食には人気のトロイドブランドを使用しています。 出来上がり：









このスキームのために私が行った動きは珍しいことではありません。 他のテンプレートを試してみると、空の正方形を覆うペニーを4列目（または4行目）の他の正方形に移動するとまったく同じ状況になることがわかります。 同様に、1つの空の正方形がグリッドの他の場所にある場合、ゲームの結果は同じになります。 また、ソースの順列の別のセットから開始することもできます（すべての正方形をカバーしている場合）。



このコインシフトの演習では、5つ以下の順列の組み合わせにより、1つの空の正方形で4×4のパターンを閉じることができることを示していますが、正確に5つが必要なものをどのように知ることができますか？ おそらく、たった4つの順列を処理できる完全に異なるスキームがあるのでしょうか？ そのようなスキームがどのように見えるかを仮定しましょう。 16個の正方形のグリッドを完全にカバーする他の置換スキームとは、1つの位置が正確に異なる必要があります。 ただし、1つのポイントで2つの順列が異なることはありません。 つまり、15個の正方形をカバーする4つの順列のスキームは存在できないという議論は、4×4形式のテンプレートでは5つの正方形しかカバーできないという議論と本質的に同じです。



この引数は、 k × k行列に一般化できます。任意の整数kに対して 、 k +1未満の順列で閉じることができない少なくともk個のオーマティックスキームが必要です。 しかし、その後、推論をさらに飛躍させることができます。おそらくk +1が上限です。 おそらく、Barryの質問に対する答えの一部は、 k × kのフォーマットスキームの場合、 k + 1を超える置換は必要ないということです。 ある時点で、私はこの仮説の「証拠」さえ持っていました。 それから、飛行機のポイントで行ったのとほぼ同じ作業を実行するプログラムを書きました。

国境を越えて行った

私のプログラムは、5つの順列を必要とする16の予想されるレイアウトスキームを見つけましたが、他にも多くのものを見つけました。 合計で、彼女は5個未満の順列で構成できない2,032個の4×4形式を見つけました。 それから大きな驚きがありました：プログラムはまた、 6つの順列を必要とする480の回路を見つけました。 私の推定上限には多すぎます。



これらの480の問題のあるフォーマットの1つは次のとおりです。









このパターンを見て、以前の推論の誤りの理由を理解したと思いました。 この行列は、ゼロが2つしかないゼロが1つあるテンプレートとまったく同じです。 （この文は理にかなっていると思います。私の議論に従ってください。）2つの空の正方形を含むグリッド全体を完全にカバーする4つの順列のセットからやり直すと仮定します。









その後、コインの再配置で行ったのと同じ方法で各空の正方形を開くことができますが、これら2つの動きが互いに影響しないように注意する必要があります。 （空の四角からペニーを取り除き、すぐにペニーを入れることはあまり意味がありません。）「列と行に1つ」の順列プロパティを保持して、両方の空の四角を開く戦略は次のとおりです。









2つの空の正方形を開くとき、2つの塗りつぶされた正方形からコインを削除することは避けられません。 ここで最も重要なことは、2つの開いた塗りつぶされた正方形が同じ線上にあるため、この問題は単一の再配置では解消できないことです。 これらの正方形の両方を閉じるには、 2つの追加の順列が必要です。



コインを移動する他の方法は、同じ列または行にある2つの開いた正方形の場所を回避しますが、5つの順列でカバレッジを完了するためのすべての試行に失敗します。 次の図に4つのリングを追加してみてください。 開いている青い正方形の両方を閉じると、空の正方形のいずれかを閉じるか、同じ行に2つのリングが表示されます。









つまり、4×4形式を閉じるには6つの順列が必要であることがわかりました。 これは、一般的な場合の上限がk +1ではなくk +2に等しくなることを意味しますか？ または、正しい式は2 k –2でしょうか？ 最後の仮説を支持して、私は、それぞれ8個と10個の順列を必要とする次の2人のオルメイトを考慮することを提案します：

別の賭け

別の賭けを提供する前に、oratの最小カバレッジの上限で数回欺かれて、エラーのための小さなスペースを作成したいと思います。 k × k形式をカバーするには最大2 k –2の順列が必要になるという直接的な証拠がすでにあります。 したがって、私は寛大であり、正しいカバレッジのために2 kドルを提供し、順列ごとに1ドルを請求します。 k = 3またはk = 4の場合、この取引で間違いなくお金を稼ぐことができます。 しかし、それは大きなkにとって有益ですか？ （ヒント：実際のお金のためにこれらのルールでゲームをプレイします。）



誰もそのような賭けを受け入れることに同意しませんか？ すみません-私はすでに賞金を使いました。



オーマットの最小限のカバレッジについて尋ねたバリー・ジプラは、私に素晴らしい手紙を送りました：

特定の形式を取得するために必要な順列の最小数の観点から、「最悪の場合」の動作がkに対してここに示す形式の場合に生じるという仮説（実際、単なる予言）の手短なヒントを示します。 = 7：

マトリックスの既存の用語に違反しないように、このタイプの（正方形）マトリックスを呼び出します。 このように、主な対角線の下にあるすべての要素は0、「ar慢な三角形」です。 k = 7のこのrog慢な三角形の形式には16以上の順列が必要であり、このkの値から数が急激に増加することを示すことができます（そしてそれを行います！）。 したがって、個人的に、私は間違いなくあなたの2 kドルの入札を受け入れないでしょう。



秘Theは、各フォーマットを「addmat」（addmat）と呼ぶものの「影」と見なすことです。 P 1、 P 2、...、 Prを順列k × kの行列とする。 アドオンは通常の加算結果になります： S = P 1 + P 2 + ... + Pr 、その要素は正の整数で、置換の1つ以上のコンポーネントが1を持ち、それ以外の場合はゼロです。 対応する形式は、ゼロ要素を保持しながら、非ゼロ要素のそれぞれを1で置き換えることによって取得されます。 この意味で、オーマテートの個々の要素は、アドマットの肯定的な要素の「影」です。



最も重要なことは、アドオンにはそのシャドウにはない素敵な小さなプロパティがあることです。アドオン要素の行と列の合計はすべて、それらを作成した順列の数に等しいrです。



一緒に考えましょう。 k慢な三角形のオルメート（ k = 7の場合）の上記の例は、次の形式のaddmatから取得する必要があります。

ここで 、 a 、 b 、およびすべての*は正の数です。 特に、各*には少なくとも1の値があります。行と列の合計はすべて同じである必要があるため、 a + bの合計はbとその上の6つすべて*に等しくなければなりません。 したがって、 aの値は6以上です。同様に、 a + bの合計はaとその上の6つすべての*の合計に等しくなければなりません。つまり、 bの値も6以上です。したがって、 a + bは 12以上、つまり、特定の形式を作成するには、少なくとも12個の順列が必要です。



これらの考慮事項は、任意のkに一般化できます。つまり、 k × k形式には最大2 k –2の順列が必要な「直接的な証拠」ではなく、これは厳密な証明です。 しかし、少なくとも特定のケースについては、すぐに改善できます。 この慢な三角形のオルメイトの順列を12個だけにしようとすると、すぐに問題が発生します。 明らかに、 a = b = 6が必要です。したがって、それらの上の*はすべて単位です（この列で合計12を取得するため）。 つまり、アドオンがあります

「@」とマークされたアイテムに注意を引きたいと思います。 彼の行の合計を12にするには、@ = 10が必要です。しかし、これは彼の列の合計（その上に5つの*がある）が少なくとも15であることを意味します。 これは、 aおよび/またはbのより大きな値を見つけようとする必要があることを意味します。つまり、このアドオンを作成するには、より多くの置換行列が必要です。



a = b = 8になるまで行と列の合計の条件を満たすことができないことがわかります。すべてのステップを説明するのではなく、最後から2番目の可能な組み合わせa = 7、 b = 8を示します。この場合の希望：

最後の2列では、可能な限り7と8に近くなるように「重み」をできるだけ多く与え、5つの正の要素を持つ要素として可能な限り小さい値（10）を使用できることに注意してください。 このため、最後の3行と右3行の合計（15）は同じですが、要素12の列に問題があります。合計が16以上であるため、繰り返しますが、行き止まりです。 矛盾を回避するには、次の試みが必要です。

最後に、行列の行と列の合計はすべて同じです。 これは、16個の置換行列のセットに対する実際のアドオンである場合とそうでない場合があることを考慮する価値があります。 これはまだアドオンであると思われますが、確認したくありません。 わかっているのは、必要なアドオン条件を満たしていること、つまり、行と列の合計がすべて同じであることだけです。 （これが十分な条件であれば素晴らしいと思いますが、そうではないことを教えてくれます。）



kのより高い値で正確に再現できるこの例は、ゲームを提供するプレーヤーが2 kドルのレートで勝つだけではないことを明確にします。 （2 k +2）ドル以上でも。 私はこれを少し実験して、順列行列の数がk = 10で2 kをはるかに超えることを確認しました。 私がすべてを正しければ、24個の順列が必要になります（-慢三角形マトリックスの分析により、それが実際のアドオンではないことが示された場合はさらに多くなります）。 慎重に検討した後、分析を簡素化して便利でエレガントな証拠にできると確信しています。 すでに間違いを犯しているかどうか、推論からカードの家を建てたかどうかはわかりません。



上記のすべてはあなたが来たことに対応していますか？

確実に一貫しています。



最初に、Barryが開いたままにした小さな質問に答えるために、彼の7×7の「ar慢三角形」行列を正常に閉じる16個の順列の多くを紹介します。



{1,2,3,4,5,6,7} {2,1,4,3,6,7,5} {1,3,2,5,4,7,6} {1,3,4,2,6,5,7}

{2,3,1,5,6,4,7} {1,2,3,5,6,7,4} {1,2,4,5,3,6,7} {1,2,4,5,6,3,7}

{1,2,4,5,6,7,3} {1,3,4,5,2,6,7} {1,3,4,5,6,2,7} {1,3,4,5,6,7,2}

{2,3,4,1,5,6,7} {2,3,4,5,1,6,7} {2,3,4,5,6,1,7} {2,3,4,5,6,7,1}







貪欲な簡単な検索で発見しました。



上限を見つけるための私自身の試みは、慢な三角形のマトリックスではなく、7×7のこの例のように「フラグ」と呼ばれるマトリックスに焦点を合わせました。









このマトリックスを正しくカバーするには、16個の順列も必要です。 この理由を確認するには、マトリックスの列を左端から交換し、各列で異なる行の要素1（および0でない）を選択してみてください。 左上隅にゼロのブロックがあるため、各順列の最初の3つの要素は4〜7行目になければなりません。 つまり、各順列は最初の3列の最後の4行のうち3行を「占有」し、残りの順列は再びこの行間隔に1回しか入ることができません。 したがって、各順列は、マトリックスの右下隅にある単位要素の4×4ブロック内の1つの要素のみに関係し、すべての単位要素を閉じるには少なくとも16個の順列が必要です。 16個の順列で十分であることを証明することはそれほど難しくありません。



この種の分析は、任意の奇数kで機能します。したがって、このような行列には









順列。 （ kでさえ、状況はあまり対称的ではなく、私はそれを詳細に検討しませんでした。）



これらの結果は、 k × k形式を閉じるために必要な順列の数の上限の下限を示しています。 しかし、これが有効な上限であることを証明していません。 さらに並べ替えが必要な他の形式はありますか？ 私はそうは思わないが、この記事で作成した私の仮説のほとんどすべてが間違っていることが判明したことを忘れないでください。