45 注意： 45 注意： 46 必勝 + 必勝 = 必敗 46 必勝 + 必勝 = 必敗 47 は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる 47 は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる 48 48 49 補題：G+G は必敗 49 補題：G+G は必敗 50 　- まねっこmoveをされると負けるしかない 50 　- まねっこmoveをされると負けるしかない 51 51 > 52 -------------------------------------------------------------------------------- 52 補題：A≡A', B≡B' ならば A+B≡A'+B' 53 補題：A≡A', B≡B' ならば A+B≡A'+B' 53 - A+B+A'+B' = (A+A')+(B+B') = 必敗+必敗 = 必敗 54 - A+B+A'+B' = (A+A')+(B+B') = 必敗+必敗 = 必敗 54 55 55 補題：Ai≡Ai' ならば {A0,A1,A2,...}≡{A0',A1',A2',...} < 56 　- {A0,A1,A2,...}+{A0',A1',A2',...} は必敗。なぜならこちらがどう動かしても < 57 A0+A0', A1+A1', A2+A2', ... のいずれかの必敗状態に遷移させられるから。 < 58 < 59 -------------------------------------------------------------------------------- < 60 定理【ゲームの和はxor】 56 定理【ゲームの和はxor】 61 - *n1 + *n2 = *(n1 xor n2) 57 - *n1 + *n2 = *(n1 xor n2) 62 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 58 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 63 59 64 証明 60 証明 65 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 61 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 66 - (n1 xor n2 xor (n1 xor n2)) は 0 である 62 - (n1 xor n2 xor (n1 xor n2)) は 0 である ................................................................................................................................................................................ 71 >> つまりa,b,cのどれかは^xすると減ることを言えばよい。 67 >> つまりa,b,cのどれかは^xすると減ることを言えばよい。 72 >> a,b,cのうち最上位ビットが立っているものが奇数個ならxも立つのでxorすれば減る 68 >> a,b,cのうち最上位ビットが立っているものが奇数個ならxも立つのでxorすれば減る 73 >> 偶数個(2個)なら、その最上位ビットを無視した残りをa',b',c'とするとこれも 69 >> 偶数個(2個)なら、その最上位ビットを無視した残りをa',b',c'とするとこれも 74 >> xorがxなので数学的帰納法的にやることにより巧い減らし方が見つかる。 70 >> xorがxなので数学的帰納法的にやることにより巧い減らし方が見つかる。 75 - よって最終局面"全部 0"になるのは絶対に自分のターン 71 - よって最終局面"全部 0"になるのは絶対に自分のターン 76 72 77 -------------------------------------------------------------------------------- 73 -------------------------------------------------------------------------------- > 74 補題：Ai≡Ai' ならば {A0,A1,A2,...}≡{A0',A1',A2',...} > 75 　- {A0,A1,A2,...}+{A0',A1',A2',...} は必敗。なぜならこちらがどう動かしても > 76 A0+A0', A1+A1', A2+A2', ... のいずれかの必敗状態に遷移させられるから。 > 77 78 定理【ゲームの状態遷移はmex】 78 定理【ゲームの状態遷移はmex】 79 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 79 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 80 where mex(S) = min(nat \setminus S) 80 where mex(S) = min(nat \setminus S) 81 81 82 - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 82 - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 83 帰納的に、全てのゲームはなんらかの *n と等価 83 帰納的に、全てのゲームはなんらかの *n と等価 84 84 ................................................................................................................................................................................ 91 で両側等価を保ててしまう。 91 で両側等価を保ててしまう。 92 92 93 93 94 -------------------------------------------------------------------------------- 94 -------------------------------------------------------------------------------- 95 まとめ 95 まとめ 96 96 97 ・一手動かした次の局面が *n1 または *n2 または ... なゲーム 97 ・一手動かした次の局面が *n1 または *n2 または ... なゲーム 98 　　{*n1, ..., *nk} = *mex(n1, ..., nk) | 98 　　{*n1, ..., *nk} ≡ *mex(n1, ..., nk) > 99 99 ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 100 ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 100 　　*n1 + *n2 = *(n1 xor n2) | 101 　　*n1 + *n2 ≡ *(n1 xor n2) > 102 > 103 > 104 -------------------------------------------------------------------------------- > 105 その他のゲームの組み合わせ（証明があやしい） > 106 101 ・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム | 107 定理： ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム > 108 　　*n1 <+> *n2 ≡ *(n1 + n2) 102 　　*n1 <+> *n2 = *(n1 + n2) //単に１個の山なのとかわらない | 109 証明： 単に１個の山なのとかわらないので勝敗一致どころか同型 > 110 > 111 補題：A≡A' かつ B≡B' ならば (A<+>B)≡(A'<+>B')。 > 112 　　　ゆえに一般に G1≡*n1, G2≡*n2 ならば G1<+>G2 ≡ *(n1+n2) > 113 証明：(A<+>B)+(A'<+>B')が必敗であることを言えばよい。 > 114 　　　相手がどう動かしても A<+>B ==> a<+>b > 115 　　　a+a'、b+b'が必敗であるように (a<+>b)+(a'<+>b') と動かせ��。 > 116 　　　いずれ相手は死ぬ > 117 > 118 103 ・両方一手ずつ進めるゲーム？？？？？ | 119 定理： 先手はゲーム *n1、後手はゲーム *n2 を交互に一手ずつ進めるゲーム 104 　　*n1 X *n2 = ? | 120 　　*n1 X *n2 ≡ *(n1<=n2 ? 0 : n2+1) > 121 　　　　　　 後手 > 122 　　 0 1 2 3 4 > 123 　　------+---------- > 124 　　先手 0|0 0 0 0 0 > 125 　　 1|1 0 0 0 0 > 126 　　 2|1 2 0 0 0 > 127 　　 3|1 2 3 0 0 > 128 　　 4|1 2 3 4 0 > 129 　左辺のゲームのmex計算してみるとこうなる。 > 130 > 131 補題：A≡A' かつ B≡B' ならば (A X B)≡(A' X B')。 > 132 　　　ゆえに一般に G1≡*n1, G2≡*n2 ならば G1 X G2 ≡ *(n1<=n2 ? 0 : n2+1) > 133 証明：AxB + A'xB' を Bxa + A'xB' と動かされたら Bxa + B'xa' に動かせて≡が > 134 　　　保てるのでいずれ相手は死ぬ