ライン上の素数を訪問
最近、私はDicast：Rules of Chaosと呼ばれる素晴らしいモバイルゲームをプレイしていて、このパズルを作るように促されました。
このパズルは、各整数がセルとして表される無限の数直線上を進みます。0とマークされたセルから始めます。次の10枚のカードが利用可能です。
- 1つ：セルを1つ右に移動します
- 2：2つのセルを右に移動します
- 3：3つのセルを右に移動します
- 4：4つのセルを右に移動します
- 5：5つのセルを右に移動します
- 6：6セルを右に移動します
- マイナス：1セル左に移動します
- 奇数：1、3、または5セルを右に移動します。数はランダムに均一に選択されます
- 偶数：2、4、または6セルを右に移動します。数はランダムに均一に選択されます
- ランダム：1、2、3、4、5、または6個のセルを右に移動します。数はランダムに均一に選択されます
カードを使用すると、最終目的地に直接移動できるため、間にある他のセルにアクセスすることはありません。各カードを1回使用して、任意の順序でプレイできます。カードをプレイして、最も多くの異なる素数に着地することを保証するにはどうすればよいですか？言い換えれば、どの乱数を選択しても、着陸できる個別の素数の最大数はいくつですか？がんばろう！
回答
私たちが得ることができる最高のものは
6素数
合計で。
1つの可能な戦略
ランダムでないカードのみを使用して、できるだけ多くの素数を生成することから始めます。2を除くすべての素数は奇数であり、0（偶数）から開始するため、ステップオーバーできるのは最大5つの奇数の素数（奇数、偶数、偶数、偶数、奇数+奇数）のみです。しかし、2を超えると、奇数、奇数（2）、奇数、偶数、偶数、偶数のように、奇数カードを最大限に活用できます。これは実際に可能です。$0 \to 3 \to 2 \to 7 \to 11 \to 13 \to 19$、カードを使用して $3, -1, 5, 4, 2, 6$順番に。7枚のカードがあり（すべてのステップで素数が得られると7枚の素数が得られます）、7枚のカードの合計は20（複合）であるため、この時点では6枚の素数が最適です。
6つの素数（現在の数は17または19）を踏んだ後、4枚のカードがあります：1または3、奇数、偶数、およびランダム。残りの定数が1の場合、ランダムカードはあなたにどちらかを取得するように強制することができます$6k+2$ または $6k+3$ その結果と同様に $+1$複合です。3がある場合、ランダムによって3の倍数に強制される可能性があります。したがって、この時点でこれ以上素数を保証することはできないため、取得できる最良の素数は6個です。
他の戦略がそれ以上進まない理由
厳密な議論ではありませんが、考えられる理由は次のとおりです。
7枚の数字カードを使用すると、それらすべての合計が複合であるため、最大6つの素数を取得できます。間にランダムカードのいずれかを挿入すると、「悪魔」がランダムプールから数字を選択できる可能性が非常に高くなり、ターンは合成数になり、全体の合計は合成数のままになります（したがって、試行しても素数はゼロになります） 。私が考えることができる唯一の例外は2+奇数と1+偶数ですが、1は素数ではなく（途中で素数を失う）、奇数の前に3を超えた場合（6のように）、2 +奇数は最大の効用を失います-プライムソリューションはすでに提示されています）。
コンピューターによる検証
最適な結果が実際にあることを確認できました
素朴なPython3プログラムを使用した6つの素数。リンクされたバージョンは9枚のカード（ランダムカードを除く）のみを使用し、ローカルマシンで完全なコードを実行するのに約20分かかりました。
履歴チェックを削除すると、7つの素数が得られます。（残念ながら、プログラムは最適な動きを示していません。）どうやら、最適な動きは奇数と偶数の両方を利用しています。どちらも使用しない場合、最適なスコアは6です。