• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Modified lib/doc/nim.txt from [d63874d4c871cfe6] to [5e1e68bb34c03f9d].

    27     27           *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない
    28     28   
    29     29       定理
    30     30         - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk)
    31     31           where mex(S) = min(nat \setminus S)
    32     32           帰納的に、全てのゲームはなんらかの *n と等価
    33     33   
           34  +    定理の証明
           35  +      - {G1, ..., Gk} は *mex(n1,...,nk) と等価。
           36  +        つまり和を取ると必敗。
           37  +        *mex(n1,...,nk) 側を動かした場合、相手は対応する Gi に遷移する。
           38  +        {G} 側を mex(n1,...,nk) より小さいゲームに動かした場合、mex側を対応する値に変える。
           39  +        {G} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。
           40  +        で両側等価を保ててしまう。
           41  +
           42  +    等価(和を取ると必敗) => 勝ち負け一致 の証明
           43  +      - 偶奇を考えれば良い。必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えて常にその状態を
           44  +        保てば勝てる。ゆえに一致しないなら和をとったゲームは必勝。
           45  +
    34     46   
    35     47   おまけ
    36     48     @G を G のnim値とする。つまりG≡*@G
    37     49     G = X + Y ならば @G = @X xor @Y
    38     50     山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。