15×15ボード上の5枚のコイン

[注:このパズルは HackerRank
をクリックします。質問はもはやそこでは積極的に使用されていません。もともとはそこから直接コピー&ペーストされたコンテンツで投稿されましたが、今では書き直されています。]

2人のプレイヤーが15×15のチェス盤で試合をしています。一つの種類の作品しかありません。彼らがコインを使っているとしよう。ルールは次のとおりです。

  • プレイヤーは順番にプレイします。
  • あなたが移動できない場合にのみ、あなたはすぐに失います。
  • 移動は、「北西」の騎士の動きによってコインを移動することから成ります。つまり、ボード上の正方形の番号を北と東の数字が小さい「明白な」方法で指定すると、$(x、y)$から$(x-2、y
    pm1)$または$(x pm1、y-2)$。
  • ボードからコインを移動することはできません。
  • 1つのコインを別のコインの上に移動できます。

(したがって、すべてのコインがボードの左上2×2領域にあるときにゲームが終了し、そこから移動することはできません)。

If we begin with five coins at positions (15,4), (8,12),
(14,14), (10,3), (1,15) — in coordinates where the top left corner
of the board is at (1,1) — then who wins with best play on
both sides? What should the first player do?

ベストアンサー

私は別の硬貨の上に硬貨を置くことが可能であると仮定します。この場合、

いわゆる「公平なゲーム」の理論を適用することができます。ゲームは、1つのコインだけを使用する単純なゲームの5つのインスタンスの「合計」です。ゲームの合計でプレイするには、それらの1つを選んでその中を移動します。すべてのゲーム位置には負でない整数値があり、時には
“Nim値”と呼ばれます。ある意味では、そのサイズの1つの山ほどのNimのゲームと同等です。
Nim値は「最小の排除物」の略称である「メックス・ルール」と呼ばれることがあります。位置の値は、移動可能な位置の値ではない最小の非負整数です。

従って

合法的な動きがない位置(すなわち、ボードの左上2×2領域)から始まる位置から始めて、これらの値を段階的に計算することができます。これらの値はゼロです。
(あなたはこれを直接見ることができます – サイズゼロの1つのパイルを持つNimゲームからの法的な動きがないのと同じように、または
“mexルール”を介して、法的な動きはありません。負の整数はゼロです)。

そして

you can compute the value of a sum of game-positions by
computing the values of the individual positions, そして taking what
computer people call their bitwise exclusive-or. In other words,
write each as a sum of distinct powers of 2; put those all
together; cancel out any pairs of equal powers of 2; そして
add up the rest.

残っているのは単純な計算なので、やってみましょう。 …実際には、

コピーを取得した場合は、 Winning Ways
の第1巻58ページにすでに記載されている数字を見つけることができます。テーブルの規則性に気付くかもしれませんが、グリッド線を追加することで強調しています。

$$begin{array}{r|rrrr|rrrr|rrrr|rrr} & 1 & 2 & 3 & 4 & 5 & 6 &
7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \ hline 1 & 0 & 0 & 1 & 1
& 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \ 2 & 0 & 0 & 2 & 1 &
0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \ 3 & 1 & 2 & 2 & 2 & 3
& 2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 2 & 2 \ 4 & 1 & 1 & 2 & 1 & 4 &
3 & 2 & 3 & 3 & 3 & 2 & 3 & 3 & 3 & 2 \ hline 5 & 0 & 0 & 3 & 4 &
0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \ 6 & 0 & 0 & 2 & 3 & 0
& 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \ 7 & 1 & 1 & 2 & 2 & 1 &
2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 2 & 2 \ 8 & 1 & 1 & 2 & 3 & 1 & 1
& 2 & 1 & 4 & 3 & 2 & 3 & 3 & 3 & 2 \ hline 9 & 0 & 0 & 3 & 3 & 0
& 0 & 3 & 4 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \ 10 & 0 & 0 & 2 & 3 & 0 &
0 & 2 & 3 & 0 & 0 & 2 & 1 & 0 & 0 & 1 \ 11 & 1 & 1 & 2 & 2 & 1 & 1
& 2 & 2 & 1 & 2 & 2 & 2 & 3 & 2 & 2 \ 12 & 1 & 1 & 2 & 3 & 1 & 1 &
2 & 3 & 1 & 1 & 2 & 1 & 4 & 3 & 2 \ hline 13 & 0 & 0 & 3 & 3 & 0
& 0 & 3 & 3 & 0 & 0 & 3 & 4 & 0 & 0 & 1 \ 14 & 0 & 0 & 2 & 3 & 0 &
0 & 2 & 3 & 0 & 0 & 2 & 3 & 0 & 0 & 2 \ 15 & 1 & 1 & 2 & 2 & 1 & 1
& 2 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 2 \ end{array}$$

ここで、初期位置は(15,4)、(8,12)、(14,14)、(10,3)、(1,15)

ここで、数字はそれぞれ2,3、0,2,1です。これらのNim-sumまたはExclusive-orは2なので、このゲームは十分なレベルの抽象化で、サイズ2のNim-heapのように動きます。特に、サイズ2のNim-heapのように、これはファーストプレイヤー優勝最初のプレイヤーはコインを(8,12)から(6,11)に移動することで2,1,0,2,1に移動する必要があります。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です