ワイソフのニム

概要

• 2つの山を使う。1つの山から1つ以上の石をとる、または2つの山から同じ数を1つ以上取る。石が取れなくなったほうが負け。
  • チェスのクイーンを2人で交互に左上に動かすゲームだと思える (Corner The Queen)
    • Corner は「端に追いやる」という動詞
• 後手必勝局面は閉じた式で表せる
• grundy数の閉じた式は知られていない（未解決問題）

後手勝ち局面

$\varphi = (1 + \sqrt{5})/2$ (黄金数) とする。

$a_n = \lfloor \varphi n\rfloor, b_n = a_n + n\ (n=0,1,\ldots)$ とする。

$P = \{(a_n, b_n), (b_n, a_n) \mid n = 0, 1,\ldots\}$ が後手必勝局面全体の集合

（局面（2つの山のコインの数、または クイーンのいる座標）を順序対で表す）

証明

• 補題

  • 補題1: 数列 $(a_n){n=1}^\infty$ と $(b_n){n=1}^\infty$ は ビーティ数列になっている。

    • つまり、$A=\{a_n\mid n=1,2,\ldots\}$$A=\{a_n\mid n=1,2,\ldots\}$ $B=\{b_n\mid n=1,2,\ldots\}$ としたとき、$(A, B)$ は $\mathbb{N}_{\geq 1}$ の分割になっている
    • 数列 $(a_n){n=1}^\infty$ と $(b_n){n=1}^\infty$ はレイリーの定理で $(\varphi, \varphi^2)$ を考えたものである。
      • $b_n = \lfloor \varphi^2 n\rfloor$ である。
      • $\varphi^2 = \varphi + 1$ なので、$1/\varphi + 1/\varphi^2 = (1 + \varphi)/\varphi^2 = 1$ を満たす
      • 参照: 床関数と天井関数 の「レイリーの定理」

  • 補題2: 各行に対して、その行に現れる P の元はちょうど1つ。各列、座標の値の差が一定の斜めの線に対しても同様のことが言える。

    • 任意の $x\in \mathbb{N}$ に対して、ある $y\in \mathbb{N}$ が一意に存在して、$(x,y) \in P$ が成り立つ
    • 任意の $y\in \mathbb{N}$ に対して、ある $x\in \mathbb{N}$ が一意に存在して、$(x,y) \in P$ が成り立つ
    • 任意の $k \in \mathbb{Z}$ に対して、ある $(x,y) \in \mathbb{N}^2$ が一意に存在して、$y-x = k$ かつ $(x,y) \in P$ が成り立つ

    補題2は $P$ の点にいるとき、クイーンの動きをすると $P$ の外に出るということを言っている。

• 「$(x, y) \in P$ ⟺ $(x,y)$ が後手必勝局面」を数学的帰納法で示す

  • $(0,0) \in P$ で $(0,0)$ は後手必勝局面
  • $(x,y)$ から1手以上でいける局面 $(x',y')$ に対して、「$(x', y') \in P$ ⟺ $(x',y')$ が後手必勝局面」であると仮定し、「$(x, y) \in P$ ⟺ $(x,y)$ が後手必勝局面」を示す

  以上で示された。

補足

• $a_n = \lfloor \varphi n\rfloor,\ b_n = \lfloor \varphi^2 n\rfloor$ について
  • 下ワイソフ列、上ワイソフ列
    • $(a_n)_{n=1}^\infty$ は下ワイソフ列と呼ばれる (OEIS A000201)
    • $(b_n)_{n=1}^\infty$ は上ワイソフ列と呼ばれる (OEIS A001950)
  • 具体的な値
    • tbw
• 可視化

メモ

• シンプルに考察力が足りなくて理解に時間がかかりがち