＿棒消しの解法＿

囲碁・将棋板で棒消し（山崩し）のスレ（下記URL）がたちましたが、
その中でエレガントな解法があるとのレスが出ました。

http://cocoa.2ch.net/test/read.cgi?bbs=bgame&key=973153276&ls=50

２進法を使う解法があるようです。
数学が得意な方なら、エレガントな解法を導き出してくださるのでは
と思い、このスレをたててみました。

　　　　　　☆
　　 λ　　/　：。
　 < ゜-゜>ρ　 ‥
σ(　　 )　　　　・` 。・ ； ’ 、∴ ﾟ ，・・` 。・ ： ’ ∵、‘｡‥ ﾟ ，・・` 。∴ ､’．
　 υυ　　　　　、’　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　・ﾟ
　　　　　　　　　 ・　　　MilkTeaって不思議！！　　　　　　　　　　　　　　　 ‘．
　　　　　　　　　。：　　　　　作：ファンシー乙女　　　　　　　　　　　　　　　　　 ；
　　　 　 　 　 　 …　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　`。
　　　　　　　　　 ；　　 MilkTeaって不思議！能も無いのにいばってばかり 。 ‘
　　　　　　　　　∵　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　‘．
　　　　　　　　　 ･ 　　その自信は何を拠り所にしてるのかしら？　 　　　 ＠｀‘．
　　　　　　　　　`。　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　　　。
　　　　　　　　　‘．　　MilkTeaって不思議！苦し紛れに嘘ばかり。　　　　‘．
　　　　　　　　　。：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　；
　　　　　　　　　…　　その妄言の発想はどこから来るのかしら？　　　　 　`。
　　　　　　　　　｀ ;　　　　　 　　　　　　　　　　　　　　　　　　　　　　　　　　　 ﾟ ・
　　　　　　　　　｀ ;　　根拠、根拠と壊れたラジオのようね　　　　　 ：・
　　　　　　　　　 ’。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　‥
　　　　　　　　　 ‘・∴ 。’∵ 、 ; ｡…． ・ ” ，・` 。・ ； ’ 、∴ ・・ ﾟ､ ，` ： ’

おい、このスレでMilkTeaの話が出てるぞ。

童貞みるく

素人童貞うぜえ

NIMだと、山の石の数の排他的論理和
（２進表現して各桁ごとに独立した排他的論理和をとる）
が０になるようにして相手に手番を渡せば勝ちます。

歯痛さん、レスありがとうございます。
ところで、NIMとは何でしょうか？

三山くずしのことです。
ルール
　　石が三つの山（３つじゃなくてもいい4つで5つもよいが）
　　に別れて固まっておいてる。
　
　　プレーヤは自分の手番で次の行為を行う。
　　　ひとつの山から０個でない任意個の石を取り去る

　　これを２人のプレーヤが交互に繰り返す。

　　これができなくなった時点で終了。全ての石がなくなった
　　状態で手番が回ってきた方が負け。

例　３つの山の石の数が (4＠｀2＠｀1)
排他的論理和演算子を xorと表記する
　1.　4 xor 2 xor 1 = 7 なので
0になるように左の山から１つとる (3＠｀2＠｀1)
3 xor 2 xor 1 = 0
2. (3＠｀2＠｀1)の状態で手番になった相手は0にはできない
　　　とりあえず　左から 2ことる (1＠｀2＠｀1)

3. こっちは真中を全部取る (1＠｀0＠｀1)
　　 1 xor 0 xor 1 = 0-----------
以下　(0＠｀0＠｀0)で 手番をわたすことができる。

------------------------------------------------------
結局
次のことを示すことができればいいと必勝法の証明になります。

　勝手な負でない整数 3つ組(x＠｀y＠｀z)について
1. x xor y xor z が　0でないとき
この３つの数字のうちひとつだけを非負の範囲で小さくして
　残る２つは元のままという３つ組(u＠｀v＠｀w) があって
u xor v xor w = 0
とできる。

2. x xor y xor z =0 のとき
　x＠｀y＠｀zのうち１つだけを変化させた任意の３つ組（u＠｀w＠｀z)に
　ついて
u xor v xor w は0にはならない。





　　

＞歯痛的論理和さん
説明ありがとうございます。
最後の証明は、難しそうですね。

後半は案外に簡単です
（排他的論理和が０の状態からひとつ変化させると０ではないの方）
　
x = u
y = v
z ≠ w
x xor y xor z = 0
のとき、
　 u xor v xor w
= ( u xor v xor w) xor ( x xor y xor z ) ; 勝手な pについて p xor 0 = p
= ( u xor x) xor ( v xor y) xor ( w xor z) ; (a xor b) xor c = a xor (b xor c)
= ( x xor x) xor ( y xor y) xor ( w xor z)
= 0 xor 0 xor ( w xor z) ; 勝手な pについて p xor p =0
= w xor z
≠ 0 ; 相異なる　p＠｀qについて p xor q ≠0

ついで　前段
　x xor y xor z ≠ 0 のとき
ひとつだけ数字を小さくして
u xor v xor w = 0とできる。

d = x xor y xor zとおく。
２進表記したdの最上位桁が１であるものが
x＠｀y＠｀z の中にすくなくともひとつはある。
（筆算の絵をかけばわかるね）
それが x だとする　 (x xor d ) < x
( x中のdの最上位桁が０になりそれより上の桁が元のままだから）

(x xor d) xor y xor z
= ( x xor ( x xor y xor z)) xor y xor z
= (y xor z) xor y xor z
= 0

３つ組 ((x xor d)＠｀y＠｀z)は
排他的論理和は０で (x xor d) < x

＞９さん
丁寧に説明（証明）してくださり、ありがとうございました。
排他的論理和の性質をうまく利用するのですね。
（その性質を私は知りませんでしたが・・(^_^；）

数学的に厳密な解答が得られたので、これで溜飲が
下がりました。

排他的論理和が0になるとなぜ勝てるのですか？
排他的論理和が0になることの意味等を分かりやすく教えて下さい。

1 . 排他的論理和が0の状態から１手指した状態は0ではない。
一方で
2. 排他的論理和が0でない状態からは、0にできる手が存在する。
(11＠｀12に書いてあることだね）

　したがって
　　　１.　0の状態で相手に手番をわたす。
　　　２.　相手が１手指した状態は0ではない

3.　再び１を実行できる。
　。。。。以下　これを繰り返して、
　　　　そのうち　全部の山の石の数が0の状態で
　　　　相手に手番を渡せる。勝ち。

もちろん　相手がこの理屈を知っていて
初期状態が排他的論理和0でこっちの手番
なら　必ず負けです。

>15
ありがとうございます。
では最後の一個をとったら負けという場合はどうしたら良いのでしょうか？

終盤までは、最期を取った方が勝ちと同じで進行

終盤になったら個別対応
(1＠｀1＠｀1)で相手に渡したら勝ち
など

というか、
このゲームのルールを
最後の一個をとった方が勝ちにしても、負けにしても

2以上のところが1箇所になったとき(例(1＠｀1＠｀1＠｀1＠｀3)など)は
次の手の人が自由に1の箇所数を
奇数（最後の一個をとった方が負け）か
偶数（最後の一個をとった方が勝ち）に出来るので、
このゲームは結局、
”2以上のところを 1箇所だけ にしてしまった人が負け”というルールに等しいのですね。

そして、これまでに皆さんが書かれてきたことを、まとめさせて頂くと、
1. 排他的論理和が0の状態から次の一手で0の状態にすることはできない。
2. 排他的論理和が0でない状態から次の一手で必ず0にできる手が存在する。
のだから、
排他的論理和を0の状態に保ちながらやりつづけることにより、
必ず最後に相手が”2以上のところを 1箇所だけ ”にしてくれるわけです。
なぜなら、”2以上のところが1箇所だけ ”の状態は
排他的論理和が0でない状態だからです。

.....という説明はどうだろう。

ニムのバリエーション　いろいろ
　その１　シャノン　
　　　取る石の数を１か素数に限定!

ヒマな人は挑戦しよう

　　　

それぞれの番で、1人、1箇所だけじゃなくて、
2箇所まで消しても良い、というのはどうよ。
これでもう、排他的論理和は使えない。

その３　ラスカル
石を取る　の変わりに
　　山を２つに分けるという行動も可能。
　（0と元の数という分割はなし）

　　

↑これだと、排他的論理和の方法で必勝じゃないの？
（山を2つに分けても、
排他的論理和が0の状態から次の一手で0の状態にすることはできない）
から。

例えば
(1＠｀2＠｀3)　（ XOR 0になっている）
手番がまわってきたとき
石をとるかわりに
３の山を2と１にわけると
(1＠｀2＠｀1＠｀2)
この状態も XORは 0だよ
排他的論理和 ０で手番がまわってきても、
０を保って相手手番にできるので
ひとひねり必要

ちなみにラスカルはアライグマじゃなくてチェスの名人

そうですね。
22取り下げます。