ニム
補題1: S = 0 {\displaystyle S=0} のとき、任意の操作について T ≠ 0 {\displaystyle T\neq 0} である。
証明: A k ⊕ B k ≠ 0 {\displaystyle A_{k}\oplus B_{k}\neq 0} であることから明らかである。
補題2: S ≠ 0 {\displaystyle S\neq 0} のとき、ある操作について T = 0 {\displaystyle T=0} である。
証明: S {\displaystyle S} の 0 でないビットのうち最も桁の大きいものの位置を d {\displaystyle d} 番目とする。 A k {\displaystyle A_{k}} の d {\displaystyle d} 番目のビットが 0 でないような k {\displaystyle k} を一つ選ぶ(このような k {\displaystyle k} は必ず存在する)。 S ⊕ A k < A k {\displaystyle S\oplus A_{k}<A_{k}} であるため、 k {\displaystyle k} 番目の山から何枚かのコインを取り除いて B k = S ⊕ A k {\displaystyle B_{k}=S\oplus A_{k}} 枚にすることができる。 このとき、 T = 0 {\displaystyle T=0} となる。
先手がコインを取り除いた後の各山のコインの枚数を B 1 , ... , B N {\displaystyle B_{1},\,\dots ,\,B_{N}} とし、 T = B 1 ⊕ ⋯ ⊕ B N {\displaystyle T=B_{1}\oplus \cdots \oplus B_{N}} とする。コインが k {\displaystyle k} 番目の山から取り除かれるとき、 A l ⊕ B l = 0 ( l ≠ k ) {\displaystyle A_{l}\oplus B_{l}=0\;(l\neq k)} である。排他的論理和は結合法則と交換法則および X ⊕ X = 0 {\displaystyle X\oplus X=0} をみたすため、次の等式が成り立つ。
T = S ⊕ S ⊕ T = S ⊕ ( A 1 ⊕ B 1 ) ⊕ ⋯ ⊕ ( A n ⊕ B n ) = S ⊕ A k ⊕ B k {\displaystyle {\begin{aligned}T&=S\oplus S\oplus T\\&=S\oplus (A_{1}\oplus B_{1})\oplus \cdots \oplus (A_{n}\oplus B_{n})\\&=S\oplus A_{k}\oplus B_{k}\end{aligned}}}
次の二つの補題から従う。