56 56 ------------------------------------------------------------------------------------------- 57 57 定理【ゲームの和はxor】 58 58 - *n1 + *n2 = *(n1 xor n2) 59 59 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 60 60 61 61 証明 62 62 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 63 - 63 + - (n1 xor n2 xor (n1 xor n2)) は 0 である 64 + - 一手動かすと 0 じゃなくなる 65 + >> n1 と n2 と n1^n2 のどれか一個だけビットが変わるので絶対xorが変わるから 66 + - 相手は一手動かして 0 に戻せる 67 + >> 常に 68 + - よって最終局面"全部 0"になるのは絶対に自分のターン 64 69 65 70 66 71 ------------------------------------------------------------------------------------------- 67 72 定理【ゲームの状態遷移はmex】 68 73 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 69 74 where mex(S) = min(nat \setminus S) 70 75