Nim（古典的なゲーム）

Nim

石の山が $ n $ 個あって、それぞれ $ a_i $ 個の石を含んでいます。

Nancy と Tom は交互に空ではない山を１つ選び、そこから１つ以上の石を取ります。

Nancy の番からはじまり、最後の石を取った方が勝ちです。

両者が最善を尽くした場合、どちらが勝つでしょうか？

解法・ソースコード

この問題は Nim と呼ばれる古典的なゲームです。

このゲームの考え方は多くのゲームの基礎となります。

このゲームの勝ち負けの判定には 排他的論理和(XOR) を使います。

　 $ a_1　XOR　a_2　XOR　…　a_n \neq 0 → 勝ちの状態 $
　 $ a_1　XOR　a_2　XOR　…　a_n = 0 → 負けの状態 $

排他的論理和(XOR) を計算し、0でなければNancyの勝ち、0ならばBobの勝ちとなります。

上記を証明します。

  • 負けの状態からは勝ちの状態にしかいけない。
    XORが0の状態から１つ以上石を取ると、XORは必ず0ではなくなります。
  • 勝ちの状態からは常に負けの状態を作れる。
    XORの結果を２進数で見たとき一番上のビットが立っているような山を選びます。
    そこから１番上のビットが0になり、かつ残りのXOR結果が1ビットが反転するように石を取るとXORを0にできます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
#--------- 入力例 1 ---------
n = 3           # 山の数
a = [1, 2, 4]   # 山ごとにある石の数
#--------- 入力例 2 ---------
# n = 3           # 山の数
# a = [1, 2, 3]   # 山ごとにある石の数
#----------------------------
x = 0
for a1 in a:
    x ^= a1
    print(bin(x))

print('解：', 'Tom' if x == 0 else 'Nancy')

[実行結果(入力例1)]

0b1

0b11

0b111

解： Nancy

[実行結果(入力例2)]

0b1

0b11

0b0

解： Tom