◆北海道 Darth Maul さんからの解答。
Notation:
N number of Yamas
Yi number of stones in i-th Yama （i=1..N）
yij j-th digit of the nubmer of stones in i-th Yama in binary ( 0 or 1 ) （j=1..K）, where K is the highest binary digit of the largetst Yama's number of stones.
x bitwise exclusive-or operation
(1) Y1 x Y2 x ... x YN != 0 →
for some n : Yn > Y'n and Y1 x Y2 x .. x Y'n x .. YN = 0
(2) Y1 x Y2 x ... x YN = 0 →
for all i : Yi > Y'i → Y1 x Y2 x .. x Y'i x .. YN != 0
(1) and (2) implies
"You win if you always keep the stone state after your move such that
Y1 x Y2 x ... x YN = 0"
Proof:
(1) Let m = max{ j: y1j x y2j x .. x yNj != 0},
Take some n such that ynm != 0 and compose Y'n with
y'nj = ynj for j=K,..,m+1,
y'nj = y1j x .. x yn-1,j x yn+1,j x .. x yNj for j=m, .. ,1
Y'n satisfies Yn > Y'n and Y1 x Y2 x .. x Y'n x .. YN = 0.
(2) For i, Yi > Y'i, there exists some j: yij=1 and y'ij=0,
For this j, y1j x ... x y'ij x .. x yNj = 1,
so Y1 x Y2 x .. x Y'ix .. YN != 0
Note:
"bitwise exclusive-or operation" was used for notational consiceness.
It is the same as taking modulo 2 for the number of "1" bits for each binary digit.
This leads to the solution of a more general case where stones can be removed from at most p Yamas in a move; "keep modulo( p+1 ) zero".
◆岡山県 Von Hinge さんからの解答。
【問題１】
石が１個の山M個と石が（１０-M）個の山１個の場合です。
（０≦M≦１０）
●M＝２Lの場合
ルール１の場合まず華子が
石が２L個の山から２L個の石を全てとると、残りは石が１つの山が偶数個で、ルール上２つの以上の山をまたいでとることができないので最後の石は華子がとることになります。
ルール２の場合は華子が
石が２L個の山から（２L-１）個の石をとると、残りは石が１つの山が奇数個になり、ルール１のときとは逆に最後の石は太郎が取ることになります。
●M＝２L+１の場合
M＝２Lの場合と逆で、
ルール１の場合は華子が
石が（２L+1）個の山から２L個の石をとると、残りは石が１つの山が偶数個になり、最後の石は華子が取ることになります。
ルール２の場合は華子が
石が（２L+1）個の山から（２L+1）個の石をとると、残りは石が１つの山が奇数個になり、ルール１のときとは逆に最後の石は太郎が取ることになります。
【問題２】
石が１個の山L個と石が（N−L）個の山１個です。
●N＝２M の場合（M＞０）
手順は問題１と同じです
●N＝２M+１の場合（M＞０）
同様にして
ルール１の場合は石１つの山が偶数個残るようにとればよい
ルール２の場合は石１つの山が奇数個残るようにとればよい
N＝１の場合はルール１の場合先手の勝ち、ルール２の場合は後手の勝ちであることは自明ですから、この場合は華子は嘘を言っています。
以上より
『石がL個の山１個と石が１個の山（N−L）個。
（N＞１、０≦L≦L）』
というようにわけた場合、華子が必ず勝ちます。
１度に取れる石の個数の制限がないので、山にある石の数が１個か複数かが問題で、石が複数の山は石が２個の山と同様と考えていいでしょう。
石が複数の山は順目を替える（選択する）ことができるので、自分の番の時に石が複数の山が１個と石が１個の山複数個という状況が両方のルールで必勝のパターンだと思います。
石の数が複数の山が複数あるとどうやっても相手に順目の選択のチャンスを与えてしまうので必勝のパターンは存在しないと思います。
また。石が複数個の山の個数に関してもそれが偶数か奇数かだけが問題だと思います。
【出題者の清川 育男 さんからのコメント】
問題の意図が伝わっていないので一言コメントさせてもらいます。
まず、勝つ方法は理解していて、実際の個数を尋ねています。
これが１番アピールしたいことなのですが、ルール１でもルール２のいずれでも勝てる初期状態が存在するというのが、私としては不思議な感じがしたので出題しました。
通常の「２人ゲーム」ではこういったことはあまりないと思います。
◆東京都 ＭｃＫｅｎｔａｒｏｗ さんからの解答。
【問題１】（石が１０個ある場合について）
＊ルール１でもルール２でも先手が勝つ方法が存在する状態
10 1+9 2+8 3+7 4+6 1+1+8 1+2+7 1+3+6 2+2+6 2+3+5 2+4+4 3+3+4 1+1+1+7 1+1+2+6 1+1+3+5 1+2+2+5 1+2+3+4 1+3+3+3 2+2+2+4 1+1+1+1+6 1+1+1+2+5 1+1+1+3+4 1+1+2+2+4 1+1+2+3+3 2+2+2+2+2 1+1+1+1+1+5 1+1+1+1+2+4 1+1+1+2+2+3 1+1+1+1+1+1+4 1+1+1+1+2+2+2 1+1+1+1+1+1+1+3 1+1+1+1+1+1+1+1+2
＊ルール１でもルール２でも後手が勝つ方法が存在する状態
5+5 1+4+5 1+1+4+4 2+2+3+3 1+2+2+2+3 1+1+1+1+3+3 1+1+2+2+2+2 1+1+1+1+1+2+3 1+1+1+1+1+1+2+2＊勝ち負けがルール１、ルール２のどちらを採用するかに依存する状態
1+1+1+1+1+1+1+1+1+1
以上は、問題２の解答で述べる判別法によって調べた結果です。
【問題２】（石がＮ個ある場合について）
◆定義１
すべての山の石の個数が１個である状態を「死状態」とよぶ。
（ex. 1+1+1+1+1)
●命題１
初期状態が「死状態」のとき、勝敗はルール１をとるかルール2をとるかで一意的に決まる。
●命題２
「死状態」でない任意の初期状態は、次の２つのいずれかの状態である。
(1)後手がいかなる手順を踏もうとも、ルール１、ルール２のいずれでも先手に勝つ方法が存在する状態
（以下「勝ち状態」）
(2)先手がいかなる手順を踏もうとも、ルール１、ルール２のいずれでも後手に勝つ方法が存在する状態
（以下「負け状態」）
[注]命題２の意味することは、どんな初期状態でも先手・後手のいずれか一方に必勝法が存在するということです。
石の取り方の任意性にも関わらず、どちらかには必勝法が存在するわけです。
これは、石の数が３個のときを個別に証明し、以下数学的帰納法を用いて証明することができます。
この命題は、「勝ち状態」と「負け状態」の存在を保証しているにすぎず、
・個々の初期状態がいずれのタイプに属するのか
・必勝法の具体的手順とはどのようなものか
については何も言及していません。
この２点については、以下の命題３、４、５で明らかにします。
以下、Ｎ個の石がいくつかずつｋ個の山に分けられている状態(初期状態でなくてもよい）を考え、石の数の少ない山から順に1〜ｋまでの番号を与えます。
◆定義２
ｊ番目の山の石の個数をｎ(j)で表すとき、
ｍ(j) ＝ [ｎ(ｊ)/２］とおく。
ただし、[ｘ]は実数ｘを超えない最大の整数を表すものとする。
このとき、Ｒを
Ｒ＝ｍ(ｋ)−ｍ(ｋ-1)＋ｍ(ｋ-2)−・・・(−1)k-1ｍ(1)
と定義する。
◆定義３
ある状態について、奇数個の石からなる山の個数をΩとする。
●命題３（判別法）
「死状態」でない初期状態について、
(1)Ｒ≧１ならば、「勝ち状態」である。
(2)Ｒ＝０ かつ Ωが奇数ならば、「勝ち状態」である。
(3)Ｒ＝０ かつ Ωが偶数ならば、「負け状態」である。
●命題４（必勝法）
1回の(石をとる)操作で「勝ち状態」を「負け状態」に遷移させることができる。
（コメント）
Ｒ≧１のとき
Ωが偶数なら最大個数の山から２Ｒ個の石をとる
Ωが奇数なら最大個数の山から２Ｒ−１個の石をとる
Ｒ＝０かつΩ:奇数のとき
任意の奇数山から1個石を取る
●命題５
1回の操作で「負け状態」から「負け状態」へ遷移させることはできない。
[注]命題３，４，５の証明には、指数表記を使いました。
しかし、数式ツールの互換性が心配なので証明は省略します。
＊命題３の例
・1+2+3+4
Ｒ＝[4/2]-[3/2]+[2/2]-[1/2]
＝２−１＋１−０
＝２
より「勝ち状態」
・1+2+2+2+3
Ｒ＝[3/2]-[2/2]+[2/2]-[2/2]+[1/2]
＝1−1＋１−１＋０
＝０
Ω＝２より「負け状態」
命題４が必勝法です。
ただし、あとで述べるようにこの必勝法の適用には若干の注意が必要です。
というのも「勝ち状態」があとで述べるＬＢＳという特別な状態であるときには、ルール１，２のどちらが採用されているかによって、石の取り方を決めなければならないからです。
結果のみを書いてしまってわかりにくいかもしれません。
どれも証明は一応できています。
ただ、考え違いをしてるかもしれません。
反例があれば、ぜひお知らせください。
○感想など
＊いきなり１０個の場合は考えられなかったので、2個の場合から考え始めました。
石の数を増やしていくとちょうどパスカルの三角形のように、初期状態が石の数のより少ない状態から生成されることに気づき、命題２に気づきました。
＊命題３，４，５に思い至ったのは、どのような初期状態からはじめても何回か操作するうちに必ずある特別な状態に遷移することに気づいたことがきっかけです。
その特別な状態とは、Von Hingeさんが解答で詳しく調べられていた状態です。
つまり「石が2個以上の山がただ１つしかない状態」です。
この状態は、プレーヤーに石の取り方の任意性が許される最期の状態であることから、
ＬＢＳ(last bifacated states)と呼ぶことにします。
＊実はこのゲームは、ＬＢＳを自分の番にまわせるようにプレーできるかどうかが鍵です。
ＬＢＳが自分の番に回ってきさえすればVon Hingeさんが述べられていたように、ルール１でもルール２でも勝つことができるのです。
つまり、ルール１、２はどちらかに決めなければゲームの勝敗は決まらないのですが、どちらを採用するか はＬＢＳにおいてはじめて重要になるわけで、そこに至る前段階での「ＬＢＳを自分の番にまわす」という勝負においてはどっちだっていいのです。
このことは、出題者の清川さんの
「ルール１でもルール２のいずれでも勝てる初期状態が存在するというのが、私としては不思議な感じがする」
という疑問へのひとつの解答にはなっていないでしょうか。
＊命題３はＬＢＳに対しても適用可能であり、ＬＢＳはもちろん勝ち状態です。
ところが、命題４については注意が必要です。
というのも、「勝ち状態」がＬＢＳであるとき、どう操作するかはルール１，２のどちらが採用されているかに依存するからです。
しかし、その方法はVon Hingeさんが解答で示されています。
つまり、完全な必勝法は、命題４とVon Hingeさんの方法を合わせたものです。
ＬＢＳを自分の番にまわす方法が命題4、自分の番に回ってきたＬＢＳを操作し勝つための方法がVon Hingeさんの解答だということです。
＊命題３，４，５の証明法はいろいろあると思います。
僕自身は、山の数だけ異なる文字を用意し、それぞれの山の石の個数をその文字の指数で表す方法を使いました。
こうすると、見通しがよく、状態を符号化できるばかりか石をとる操作までも符号化できました。
＊僕自身の興味としては、「勝ち状態」、「負け状態」に属する初期状態の頻度分布が石の個数や山の個数にどう依存するかということです。
石１０個の場合を見る限り７５％以上の初期状態が「勝ち状態」であり、このゲームは圧倒的に先手有利なのか？と思えてしまいますが、どうなのでしょう？
いまのところ、手計算でこの問題を扱う方法を考え中ですが、どうもムリくさい感じです。
なにか思いついた方がいらしたら、教えてください。
＊また、一度に取れる石の個数に制限を加えた場合にはどうなるかということにも興味があります。
この場合必勝法が 存在しなくなる可能性もあるでしょうし、先ほどの頻度分布に、物理学でいう相転移のようなものが見られるのではないかと予想しているのですがどうでしょうか。
＊さらに、この前別のサイトで見かけた「棒消し」というゲームとの関連性です。
http://www.19.alphatec.or.jp/~oohashi/seitomon.htm
僕自身、中学生のころ友人たちとこのゲームをやったことがあり、必勝法を考え出そうとしていた記憶があります。
「Ｎ山崩し」に似ているのですが、事情はより複雑です。
というのも、「Ｎ山崩し」の場合は状態を２つのパラメータＲ、Ωで表すことができましたが、「棒消し」の場合、状態の構造を評価するようなパラメータが必要になるからです。
◆東京都 未菜実 さんからのコメント。
McKentarowさんの解析に関して 参考までに
「死状態」を除くと、各数を２進法で表し、その各桁の「ニム和」（でしたっけ？）がすべて０の時が「負状態」、そうでない時が「勝状態」になります。
（ニム和：0+0＝0、1+1＝0、1+0＝1、0+1＝1）
◆広島県 清川 育男 さんからのコメント。
解答をくださった皆さまに感謝します。
パズルが数学化される過程がよくわかり、勉強になりました。
Darth Maul さんの解答にあるように、勝ち方は排他的論理和（Xor）に関係していますね。
◆埼玉県 ごろー さんからのコメント。
McKentarowさんからの解答の命題について
下の組が反例だと思います。
●命題３（判別法）の反例
（６，４，２）は正しくは「負け状態」ですが
命題３では「勝ち状態」と判定されてしまいます。
●命題４（必勝法）の反例
（６，５，２）は「勝ち状態」ですが
命題４を使うと（３，５，２）となって、再び「勝ち状態」になってしまいます。
正しい取り方は
（６，５，２）→（６，４，２）です。
命題１、命題２、命題５は正しいと思います。
◆埼玉県 ごろー さんからの解答。
［結果のみ］
［１］Ｎ山崩し（最後にとったほうの勝ち）
［２］Ｎ山崩し（最後にとったほうの負け）
［３］棒取り（消し）ゲーム（最後にとったほうの勝ち）
［４］棒取り（消し）ゲーム（最後にとったほうの負け）
［１］から［４］の順で複雑になるとおもいます。
ａ個の山，ｂ個の山，ｃ個の山・・を（ａ，ｂ，ｃ・・）と書くことにします。
ａ*ｂ*ｃ*・・・を次のように決める。
各数を二進数表示して各桁ごとに１が奇数個なら１、偶数個なら０とした二進数とする。
（これはａ XOR ｂ XOR ｃ XOR ・・・と等しいものです。）
［１］［３］の勝敗条件
(1)ａ*ｂ*ｃ*・・=０ →（この場面の時の）後手が必勝
(2)ａ*ｂ*ｃ*・・=０でない→（この場面の時の）先手が必勝
［２］［４］の勝敗条件
(1)ａ=ｂ=ｃ=・・=１かつ１が奇数個 →（この場面の時の）後手が必勝 (2)ａ=ｂ=ｃ=・・=１かつ１が偶数個 →（この場面の時の）先手が必勝 (3)ａ,ｂ,ｃ,・・の一個だけが１でない →（この場面の時の）先手が必勝 (4)ａ,ｂ,ｃ,・・の二個以上が１でないかつａ*ｂ*ｃ*・・・=０でない →（この場面の時の）先手が必勝 (5)ａ,ｂ,ｃ,・・の二個以上が１でないかつａ*ｂ*ｃ*・・・=０ →（この場面の時の）後手が必勝証明は複雑な［４］についてやればあとはほとんど同じです。
◆埼玉県 ごろー さんからの解答。
与えられた合計本数に対する考察
棒または石の合計本数が奇数なら、任意の配置に対し先手の勝ちです。
［ただし、最後に取った方の負けルールでは
（1，1，1，，，1）の配置は除く］
易しいので証明は省略します。
※合計本数が奇数本のとき、相手に好きなように配置させるかわりに先手をやらせて貰えば確実に勝てます。
合計本数が偶数のときはよくわかりません。
しかし勝敗条件は判っているので、パソコンを使えば先手必勝の配置の割合は計算できます。
プログラムは苦手なのでやってません。
何割ぐらいか興味があります。
◆埼玉県 ごろー さんからの解答。
Ｎ山崩し、棒取りゲームの合計本数（偶数）に関する考察
（奇数のときは１００％なので計算していません。）
以下はＣプログラムによるもの 合計本数が１０のときの先手必勝形の割合７６.２％ 合計本数が２０のときの先手必勝形の割合８４.４％ 合計本数が３０のときの先手必勝形の割合８７.４％ 合計本数が４０のときの先手必勝形の割合８９.６％ 合計本数が５０のときの先手必勝形の割合９１.０％ 合計本数が６０のときの先手必勝形の割合９２.２％ 合計本数が７０のときの先手必勝形の割合９３.０％計算に用いたプログラムが下にあります。
配列ａはａ[0]はデータ個数、そのあとにそれぞれの山の個数（列の個数）を入れる。
たとえば
［○○］［○］［○］［○］なら｛４，２，１，１，１｝ ［○○○］［○○○○］ なら｛２，３，４｝関数prnt
関数saizente
入力:配列ａ、ルール
出力:
［必勝法があるとき］「reru列をnokosuにする」のように値を入れる。
［必勝法がないとき］reruに０を入れる。
最後に取ったら勝ちルールにするときはルールに1を入れてください。
#include<stdio.h>
#define saigotorumake 0
#define saigotorukati 1
void prnt(int *a){int y;printf("(");for(y=1;y<=a[0];y++)printf("%d ",a[y]);printf(")");}
void saizente(int *a,int role,int &retu,int &nokosu);
/* メインは合計本数がｎになる組をもとめる */
void main(){
int s,re,n,a[100],retu,no;
printf("Nyama Boutori(saigonitottaramake) katikata\n");
for(n=5;n<7;n++){/* 合計本数が５から７まで */
s=0;re=n;
for(;;){
s++;a[s]=re;re=0;a[0]=s;
saizente(a,saigotorumake,retu,no);
prnt(a);
if(retu==0)printf(" gote no kati\n");
else printf(" %d retu wo %d nisuru\n",retu,no);
if(a[1]==1)break;
while(a[s]<=1){s--;re++;}
a[s]--;re++;
while(a[s]<re){a[s+1]=a[s];re-=a[s];s++;}
}}}
void saizente(int *a,int role,int &retu,int &nokosu){
int xor=0,k=0,i,j;
for(i=1;i<=a[0];i++){if(a[i]>1)k++;xor^=a[i];}
if(xor==0||(role==0&&xor==1&&k==0)){retu=0;return;}
if(k==0){retu=a[0];nokosu=0;return;}
for(i=0;;i++)if(xor<(2<<i))break;
for(j=a[0];;j--)if((a[j]&(1<<i))!=0)break;
nokosu=xor^a[j];retu=j;
if(role==0&&k==1)nokosu^=1;
return;
}◆大阪府 KG さんからの解答。
Darth Maul さんの解答を自分なりに翻訳してみました。
(翻訳があってるかどうかはわかりませんが...)
記号:
N :山の数
Yi :i番目の山の石の数を2進数であらわしたもの（i=1..N）
yij :Yiのj桁目の数字( 0 か 1 ) （j=1..K）,
ここで K はY1からYNまでの中で一番大きい数の桁の数
Yi x Yj :YiとYjのそれぞれj桁目の数字の排他的論理和
( 0 x 0 = 0, 0 x 1 = 1, 1 x 0 = 1, 1 x 1 = 0 )をj桁目とする数
定理:
(1) Y1 x Y2 x ... x YN ＞ 0 のとき
n ( 1 ≦ n ≦ N ) をうまく選び, Y'n を Yn ＞Y'n となるようにうまく選ぶと
Y1 x Y2 x .. x Y'n x .. x YN = 0 とすることができる
(2) Y1 x Y2 x ... x YN = 0 のとき
どの i ( 1≦i≦ N ) を選んでも, Y'i が Yi > Y'i を満たすなら
必ず Y1 x Y2 x .. x Y'i x .. x YN ＞ 0 となる
定理(1) および (2) より
"常に Y1 x Y2 x ... x YN = 0 となるように石を取れば必ず勝つことができます"
(最後の石を取ったほうが勝ちというルールの場合)
証明:
(1) m = max{ j: y1j x y2j x .. x yNj ＞ 0} とおきます
n を ynm = 1 となるように選び, Y'n を次のように決めます
y'nj = ynj (j=K,..,m+1),
y'nj = y1j x .. x yn-1,j x yn+1,j x .. x yNj (j=m, .. ,1)
このとき Yn ＞ Y'n を満たし, Y1 x Y2 x .. x Y'n x .. x YN = 0 となります
(2) どの i に対しても Yi ＞ Y'i なら yij=1 かつ y'ij=0 を満たす j があります
この j に対して y1j x ... x y'ij x .. x yNj = 1 を満たすので
必ず Y1 x Y2 x .. x Y'i x .. x YN ＞ 0 となります
注釈:
" x "(各桁の排他的論理和)は, 2進数であらわされた数のそれぞれj桁目の数字の和を"2で割った余り"をj桁目にする操作とみることができます.
これをより一般的な場合に拡張すると, 一度に p 以下の山から石を取ることができるというルールのときには"p+1 で割った余り"を 0 にするように石を取ればよいことになります.
（最後に書いていることはホントでしょうか。誰か確かめてください。）