2

ここでパターンを見る簡単な方法があるかどうか疑問に思っていました。私はこれについて何時間も考えてきましたが、完全に定式化することはできませんでした.

ゲームの仕組みは 2 人のプレーヤー、N石の塔です。プレーヤーの番になったら、塔から少なくとも 1 つの石を取り除く必要があり、最後の石を取り除いたプレーヤーが勝ちです。

塔の高さから誰が勝つかの地図として、これまでに描いたものは次のとおりです。

// {1} ---> "First" (remove the single stone)
// {2} ---> "First" (remove both stones)
// {n}, n > 2 ---> "First" (remove all the stones)
// {1, 1} ---> "Second" (because your only option is to remove 1 stone and then your opponent only has to remove 1 stone to win)
// {1, 2} ---> "First" (because you can remove 1 stone from the 2nd tower and then your opponent is left with {1, 1} which makes him lose as I explained in the last one)
// {1, 3} ---> "First"
// {1, n}, n > 1 ---> "First"
// {2, 2} ---> "Second"
// {2, 3} ---> "First"
// {2, 4} ---> "First"
// {2, n}, n > 2 ---> "First"
// {m, n} ---> m < n ---> "First"
// {1, 1, 1} ---> "First"
// {1, 1, 2} ---> "First"
// {1, 1, 3} ---> "First"
// {1, 1, n} ---> "First"
// {1, 2, 2} ---> "First"
// {1, 2, 3} ---> "Second"
// {1, 2, 4} ---> "First"
// {1, 2, 5} ---> "First"
// {1, 2, n}, n > 3 ---> "First"
// {2, 2, 2} ---> "First"
// {2, 2, 3} ---> "First"
// {2, 2, n}, n > 1 ---> "First"

私が思いついた事実：

  • 各タワーに石が 1 つある場合、タワーの数が奇数の場合はそのターンのプレイヤーが勝ち、それ以外の場合は負けです。
  • 塔の数が でN、いずれかの塔の高さが より大きい場合N+1、その塔の高さが である場合と同じ結果になります。N+1

それどころか、線形解を書くのに十分なパターンを理解することはできません。

何か助けはありますか？

4

1 に答える 1

3

このゲームは NIM として知られています。勝利戦略は、各塔の石の数の XOR が 0 になる位置を後にすることです。これにより、対戦相手はゼロ以外の XOR 値を持つ構成に移動することを余儀なくされます。最初のプレーヤーは、XOR 値が 0 の位置に再び到達できます。

たとえば、{1,2,4} から始めて、{1,2,3} に進むのが勝ち手です。1 XOR 2 XOR 3 = 0 であることに注意してください。対戦相手が最後の山 {1,2,1} から 2 つの石を取り、次の勝利の動きが 2 番目の山を完全に取り除くとしましょう: {1, 0, 1} 再び XOR を作成します。値 0; 等々。

于 2016-10-18T04:28:27.153 に答える