56 -------------------------------------------------------------------------------- 56 -------------------------------------------------------------------------------- 57 定理【ゲームの和はxor】 57 定理【ゲームの和はxor】 58 - *n1 + *n2 = *(n1 xor n2) 58 - *n1 + *n2 = *(n1 xor n2) 59 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 59 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 60 60 61 証明 61 証明 62 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 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 定理【ゲームの状態遷移はmex】 72 定理【ゲームの状態遷移はmex】 68 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 73 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 69 where mex(S) = min(nat \setminus S) 74 where mex(S) = min(nat \setminus S) 70 75