とりあえず棒消し！

　　　　｜
　　　｜　｜
　　｜　｜　｜
　｜　｜　｜　｜
｜　｜　｜　｜　｜

　　　　｜
　　　｜　｜
　　｜　｜　｜
　｜　｜　｜　｜
｜　｜　｜　　 ｜

　　　　｜
　　　｜　｜
　　｜終｜了｜
　｜死｜ま｜す｜
｜　｜　　｜　 ｜

昔「とりあえず山崩し」っていうスレッドあったよね。

　そこでいろいろ研究しつくしてるからね。

「とりあえず山崩し」っていうスレッドはどこにあるのでしょうか？

「とりあえず山崩し」っていうスレッド、結局どこにあるか
分からずか・・・

とりあえず、このスレッドを進めてみよう。
棒を消すのはどうすればいいのかな？
とりあえず「φ」にしてみます。

　　　　｜
　　　｜　｜
　　｜　｜　｜
　｜　｜　｜　｜
φ　｜　｜　｜　｜

次、後攻の方。

　　　　｜
　　　｜　｜
　　｜　｜　｜
　｜　｜　｜　｜
φ　φ　｜　｜　｜
次、後攻の方。

慎重に・・・ということで、一個だけ消します。

　　　　｜
　　　｜　｜
　　｜　｜　｜
　φ　｜　｜　｜
φ　φ　｜　｜　｜

次、後攻の方どうぞ〜(^o^)丿

これじゃ、文字化けしちゃうかな？

　　　　｜
　　　｜　｜
　　｜　｜　｜
　┼　｜　｜　｜
┼─┼　｜　｜　｜

良さそうな感じだね。
いいアイデアがあったら、またお願いします。

この展開を待っていました！
最後の１個を消したほうが負け、でいいよね？

　　　　｜
　　　｜　｜
　　｜　┼　｜
　┼　｜　｜　｜
┼─┼　｜　｜　｜

＞最後の１個を消したほうが負け、でいいよね？
そうだね。

これで、先攻の勝ちを読みきりました。(-_☆)キラリ

　　　　｜
　　　｜　｜
　　｜　┼　｜
　┼　｜　｜　｜
┼─┼─┼─┼─┼

次、後攻さんですよ。

次の人（後攻の人）、見やすい方を
採用してね。

’’’’｜
’’’｜’｜
’’｜’┼’｜
’┼’｜’｜’｜
┼─┼─┼─┼─┼

これでどうだ！！

�V�V�V�V｜
�V�V�V｜�V｜
�V�V｜�V┼�V｜
�V┼�V｜�V｜�V｜
┼─┼─┼─┼─┼

小細工ないほうが良さそうね。
みんなごめん。

馬鹿じゃねーの。これは最初に一番下の端の一本消せば
勝敗は決まってんだよ。

>>12
>これで、先攻の勝ちを読みきりました。(-_☆)キラリ

ぐはぁ、、負けた、、ということで、２回戦

　　　　　｜
　　　　｜　｜
　　　｜　｜　｜
　　｜　｜　｜　｜
　｜　｜　｜　｜　｜
｜　｜　｜　｜　｜　｜

>>16 (ﾟдﾟ)ﾊｧ?

>１７
一列増やしたその場合も終わってるぜ。先にやる奴が一番下の列の５本を
まとめて引くと勝負はついてんだよ。

＞一列増やしたその場合も終わってるぜ。先にやる奴が一番下の列の５本を
＞まとめて引くと勝負はついてんだよ。

かなり研究されてるんだね。
ということは、先手必勝か・・・

試しにやってみよう。

　　　　　｜
　　　　｜　｜
　　　｜　｜　｜
　　｜　｜　｜　｜
　｜　｜　｜　｜　｜
┼─┼─┼─┼─┼　｜

次、後手さん。

　　　　　｜
　　　　｜　｜
　　　｜　｜　┼
　　｜　｜　｜　｜
　｜　｜　｜　｜　｜
┼─┼─┼─┼─┼　｜

私も必勝法を知っているのでやらせていただきマース。
先手さんどーぞ。

必勝法、知りたいな〜。
知っている人、気が向いたら、教えてね。

　　　　　｜
　　　　｜　｜
　　　｜　｜　┼
　　｜　｜　｜　｜
　｜　｜　｜　｜　┼
┼─┼─┼─┼─┼　｜

後手さんど〜ぞ〜

もう私の負けなんだけどね＾＾;
　　　　　┼
　　　　｜　｜
　　　｜　｜　┼
　　｜　｜　｜　｜
　｜　｜　｜　｜　┼
┼─┼─┼─┼─┼　｜

かなり、考えた結果、以下がいいのではという
結論になりました。
どうでしょう？
まだ、先手有利ですか？

　　　　　┼
　　　　｜　┼
　　　｜　｜　┼
　　｜　｜　｜　｜
　｜　｜　｜　｜　┼
┼─┼─┼─┼─┼　｜

次、後手さんど〜ぞ〜。

うーむ。
　　　　　┼
　　　　｜　┼
　　　┼─┼─┼
　　｜　｜　｜　｜
　｜　｜　｜　｜　┼
┼─┼─┼─┼─┼　｜

ほいっ、どうぞー。

はは逆転してる

私の負けなの？
う〜ん、そんな気がする。

じゃ、>>25は、待ったということで・・・
許してくだしゃれ。

再考、再考。
これで、どうだ！

　　　　　┼
　　　　｜　｜
　　　｜　｜　┼
　　｜　｜　｜　｜
　｜　｜　｜　｜　┼
┼─┼─┼─┼─┼─┼

次、後手さん

そうそうそれで正解。
もう投了してもいいんだけど最後にもっかいだけ。
　　　　　┼
　　　　｜　｜
　　　｜　｜　┼
　　｜　｜　｜　｜
　┼　｜　｜　｜　┼
┼─┼─┼─┼─┼─┼

はい、先手さん。

http://cocoa.2ch.net/cgame/index2.html
このネタは↑ですよ。

＞１９
＞一列増やしたその場合も終わってるぜ。先にやる奴が一番下の列の５本を

もなにも、先手必勝と後手必勝とを見分ける方法があるので、
それを知ってる人間から見れば、どんな場合でも終わってるんだけど。

例えば、

lll…lll　→１００本
lll……lll　→２００本
lll……………lll　→７４３本
lll…………………lll　→１０００本

この場合先手必勝。
最下段の１０００本の列をはじから４１３本消せばよい。
（手計算したので疲れた…）

その見分ける方法、教えて欲しいな〜。
ダメかな？

２１さん、付き合ってくれてありがとう。
２１さんのおかげで、私なりにある必勝法を見つけました。

以下の形 2・2・3・3 は、私の勝ちであることが（必勝形）
もう分かりました。

　　　　　┼
　　　　｜　｜
　　　｜　｜　┼
　　｜　｜　｜　┼
　┼　｜　｜　｜　┼
┼─┼─┼─┼─┼─┼

次、後手さん。

>>31 教えてage

私が厨房の時に、棒消しをうんと研究したあげくに見つけました。
（ひまだったんだね）
かなりエレガントな解法なので、自分で見つけると感動するよ。
面倒だったら数学板の人に解いてもらえば。
数学板住人なら、まさか、わからないはずないよね。たぶん。

>>16
馬鹿じゃねーの。どんな場合でも勝敗は決まってんだよ。
知ったような口聞くなよ厨房未満が。

>31
エレガントな解法を教えてください

土日に私が考えた必勝法をまとめたいと思います。
月曜日あたりに UP します。

<<37

「馬鹿じゃねーの」って言われないようにがんばって!

『棒消し』を私なりに、解析してみました。
かなり長文ですが、興味のある方は読んでみてください。

ただし、文才がないのでうまく説明できているかは自信がありません。
また、理論的な説明は抜きにして、結果のみを知りたい方は、

★★−６−★★
★★−７−★★
★★−８−★★

だけを見てもらえればいいです。

★★−１−★★
最初に、以下の定理（A）を考えてみます。

≪3・3、4・4といった同じ本数のペアは、必勝形である。≫・・・・（A）

数学的帰納法を用いて証明してみます。

まず、2・2が必勝形であることは自明です。・・・・（甲）

以下の図に示すような k・k （k≧2）までの同じ本数のペアが全て必勝形
であると仮定します。・・・・（乙）

│　│　　　2本
│　│　　　2本

│　│　│　　　　3本
│　│　│　　　　3本
　　　　・
　　　　・
　　　　・
│　│　│　・・・　│　│　　　k本
│　│　│　・・・　│　│　　　k本

それに1本を加えた以下の（k+1）・（k+1）のペアが必勝形であるかどうかを、
考えてみます。

│　│　│　・・・　│　│　│　　　k+1本
│　│　│　・・・　│　│　│　　　k+1本

相手が p本（p≧1）、棒を消したならば、自分は相手が消していない方の段を
p本消せばいいです。そうすれば、（k+1-p）・（k+1-p）の形となり、これは（乙）の
仮定より、必勝形です。

したがって、（乙）の仮定が成り立つならば、
（k+1）・（k+1）の組み合わせは必勝形です。・・・・（丙）

（甲）、（乙）、（丙）より、定理（A）は正しい。

★★−２−★★
次に、以下の定理（B）を考えてみます。

≪必勝形と必勝形の組み合わせは、必勝形である。≫・・・・（B）

今、α、β、γを必勝形だとします。
たとえば、

　　α＝2・2の形
　　β＝1・2・3の形
　　γ＝3・3の形

など。

もし、相手が必勝形βを崩しにきたら、自分は崩れた必勝形βの棒を
操作して（消して）、新たな必勝形β’になるようにすればよいのです。

そうすれば、この新しくできた、α、β’、γもまた必勝形の組み合わせです。

　　　α−β−γ　→　α−β’−γ
　　　　（必勝形）　　　　　（必勝形）

同様に、αを崩されれば、αの棒を操作して（消して）新たな必勝形α’に、
そして、γを崩されれば、γの棒を操作して（消して）新たな必勝形γ’に
すればいいのです。

これを、繰り返していけば、いつまでも必勝形の組み合わせのままです。
そして、α、β、γは徐々に消滅していき、最終的には 1つの必勝形になります。

★★−３−★★
定理（A）と（B）より以下の定理（C）が導かれます

≪3・3、4・4といった同じ本数のペアは、必勝形である。≫・・・・（A）
≪必勝形と必勝形の組み合わせは、必勝形である。≫・・・・（B）

　　　　　　　　　　　　　　　↓

≪同じ本数の棒の偶数組は必勝形である。≫・・・・（C）

これは例えば

　　2・2・2・2　　　　　2が4組
　　5・5・5・5・5・5　　5が6組

というように、同じ本数の棒が偶数組ある場合です。
そして、これは定理（A）と（B）より必勝形であることが分かります。

★★−４−★★
次に、以下の定理（D）を考えてみます。

≪奇数本の棒は、1本と偶数本に分解して考えることができる。≫・・・・（D）

これは、例えば、下図の5・5の形は、（5は奇数）

　　　│　│　│　│　│
　　　│　│　│　│　│

下図のように、1本と、4本（偶数本）に分解することが可能であるということです。

　　　│　・　│　│　│　│
　　　│　・　│　│　│　│

この場合、1・1と4・4の二つがあると考えていいです。

この定理（D）の証明は後に回します。

★★−５−★★
定理（D）を適用することにより、定理（C）は以下の定理（E）となります。

≪1本の棒と、偶数本の棒が全て偶数組の場合は必勝形である。≫・・・・（E）

これは、既存の必勝形である以下の1・2・3を例に出して説明してみます。

　　│
　│　│
│　│　│

定理（D）を適用すると、最下段の3本は、1本と2本に分解できます。

　　│
　│　│
│　・　│　│　　　最下段を1本と2本に分解

これは、

　　　1本の棒・・・2組・・・（偶数組）
　　　2本の棒・・・2組・・・（偶数組）

であり、定理（E）より必勝形であることが分かります。

★★−６−★★
ここで、必勝形の見分け方をまとめておきます。
要は、定理（D）と定理（E）を適用すればよいだけです。

(�T) 奇数本の棒は、1本と偶数本に分解する。
(�U) それぞれの棒が何組あるかを数える。
(�V) 全て偶数組ならば、それは必勝形である。

★★−７−★★
それでは実践形式で進めていきましょう。

　　　　│
　　　│　│
　　│　│　│
　│　│　│　│
│　│　│　│　│

まず、奇数本の棒を1本と偶数本に分解します。
この場合、3段目の3本と、5段目（最下段）の5本の二箇所です。

　　　　│
　　　│　│
　　│　・　│　│　　　　　　1本と2本に分解
　│　│　│　│
│　・　│　│　│　│　　　1本と4本に分解

次に、それぞれの棒が何組あるかを数えます。

　　　1本の棒・・・3組・・・（奇数組）
　　　2本の棒・・・2組・・・（偶数組）
　　　4本の棒・・・2組・・・（偶数組）

さて、必勝形である『全て偶数組』ではありません。
全て偶数組にするには・・・、

そうです！
1本の棒のどれかを消せばいいのです。
下図にその例をあげます。

　　　　┼
　　　│　│
　　│　・　│　│
　│　│　│　│
│　・　│　│　│　│

　　　　│
　　　│　│
　　┼　・　│　│
　│　│　│　│
│　・　│　│　│　│

　　　　│
　　　│　│
　　│　・　│　│
　│　│　│　│
┼　・　│　│　│　│

これで、

　　　1本の棒・・・2組・・・（偶数組）
　　　2本の棒・・・2組・・・（偶数組）
　　　4本の棒・・・2組・・・（偶数組）

となり、必勝形になりました。
以上より、この棒消しは先手必勝であることが分かります。

さて、先手は最下段の1本を消したとして話を進めていきましょう（下図）。

　　　　│
　　　│　│
　　│　・　│　│
　│　│　│　│
┼　・　│　│　│　│

そこで後手は、下図のように4段目の4本の棒を1本消したとします。

　　　　│
　　　│　│
　　│　・　│　│
　┼　│　│　│
┼　・　│　│　│　│

これにより、4段目が奇数である3本になったので、これも1本と2本に分解します。

　　　　│
　　　│　│
　　│　・　│　│
　┼　│　・　│　│　　　　1本と2本に分解
┼　・　│　│　│　│

それぞれの棒が何組あるかを数えてみましょう。

　　　1本の棒・・・3組・・・（奇数組）
　　　2本の棒・・・3組・・・（奇数組）
　　　4本の棒・・・1組・・・（奇数組）

全て奇数組です。

さて、相手に崩されたのは4本の棒です。
だからこちらは、ペアを失った（偶数でなくなった）最下段の4本の棒を
操作するのです。（ここが重要なポイントです）

ここでは、下図のように最下段の4本の棒を、1本と2本の棒に分かれるようにして
消せば、全て偶数組となり必勝形になります。

　　　　│
　　　│　│
　　│　・　│　│
　┼　│　・　│　│
┼　・　│　┼　│　│

　　1本の棒・・・4組・・・（偶数組）
　　2本の棒・・・4組・・・（偶数組）
　　4本の棒・・・消滅

以上の説明で、この定理の使い方がお分かり頂けましたでしょうか？
要は、崩された棒と同じ本数の他の棒を操作すればいいのです。

上記の例でいいますと、相手は4段目の4本の棒を崩したわけですから、
同じ4本である最下段を操作すればいいのです。

★★−８−★★
段数が増えた場合どうなるかを検証してみましょう。
まず、6段。

　　　　　│
　　　　│　│
　　　│　│　│
　　│　│　│　│
　│　│　│　│　│
│　│　│　│　│　│

例によって、奇数棒を分解して、それぞれの棒の組数を計算してみます。

　　　　　│
　　　　│　│
　　　│　・　│　│
　　│　│　│　│
　│　・　│　│　│　│
│　│　│　│　│　│

　　1本の棒・・・3組・・・（奇数組）
　　2本の棒・・・2組・・・（偶数組）
　　4本の棒・・・2組・・・（偶数組）
　　6本の棒・・・1組・・・（奇数組）

全て、偶数組の必勝形にするには・・・
そうです！！　　最下段の6本の棒を、1本の棒にすればいいのです。

　　　　　│
　　　　│　│
　　　│　・　│　│
　　│　│　│　│
　│　・　│　│　│　│
┼─┼─┼─┼─┼　│

　　1本の棒・・・4組・・・（偶数組）
　　2本の棒・・・2組・・・（偶数組）
　　4本の棒・・・2組・・・（偶数組）
　　6本の棒・・・消滅

次に、7段を検証してみます。

　　　　　　│
　　　　　│　│
　　　　│　│　│
　　　│　│　│　│
　　│　│　│　│　│
　│　│　│　│　│　│
│　│　│　│　│　│　│

まず、奇数棒を分解します。

　　　　　　│
　　　　　│　│
　　　　│　・　│　│
　　　│　│　│　│
　　│　・　│　│　│　│
　│　│　│　│　│　│
│　・　│　│　│　│　│　│

　　1本の棒・・・4組・・・（偶数組）
　　2本の棒・・・2組・・・（偶数組）
　　4本の棒・・・2組・・・（偶数組）
　　6本の棒・・・2組・・・（偶数組）

なんと、全て偶数組です。
つまり、この初期の状態ですでに必勝形なのです。

したがって、7段の場合は後手が必勝となります。

★★−９−★★
最後に、残っていた以下の定理（D）を証明してみます。

≪奇数本の棒は、1本と偶数本に分解して考えることができる。≫・・・・（D）

まず、この定理の意味するところを具体例をあげて説明してみます。

例えば、下図の左の3本の棒は、右の1・2の組み合わせの棒と同等の
扱いをしていいということです。　（「�V」マークは無視してね。単なる行合わせです）

�V　�V　�V　　�V　　│
│　│　│　　＝　│　│

上図の左と右の違いは何でしょうか？
それは、左の3本の棒は一度で消すことができますが、右はできない
ということです。

そこで、3本まとめて消す（すなわち、1本と2本を同時に消す）と、
どういう結果になるのかを次に考えてみます。

例として、2・3・4・5の必勝形を取り上げてみます。
まず分解して、組数を数えます。

　　　　　│　│
　　　　│　・　│　│
　　　│　│　│　│
　　│　・　│　│　│　│

　　1本の棒・・・2組・・・（偶数組）
　　2本の棒・・・2組・・・（偶数組）
　　4本の棒・・・2組・・・（偶数組）

2段目の3本を全て消してみます。（2段目の1本と2本を消す）

　　　　　│　│
　　　　┼─┼─┼
　　　│　│　│　│
　　│　・　│　│　│　│

　　1本の棒・・・1組・・・（奇数組）
　　2本の棒・・・1組・・・（奇数組）
　　4本の棒・・・2組・・・（偶数組）

1本と 2本を消したわけですから、当然、1本の棒と 2本の棒が、奇数組になります。
そこで、消された2本のペアである1段目の 2本の棒を1本にするようにして消します。
そうすれば、2本の棒は消滅し、1本の棒が偶数組なり、必勝形に戻ります（下図）。

　　　　　┼　│
　　　　┼─┼─┼
　　　│　│　│　│
　　│　・　│　│　│　│

　　1本の棒・・・2組・・・（偶数組）
　　2本の棒・・・消滅
　　4本の棒・・・2組・・・（偶数組）

すなわち、3本まとめて消しても（1本と2本を同時に消しても）、必勝形に
戻すことができるのです。

ここで、一般化します。

必勝形から 1本の棒と m本の棒（m≧2で偶数）を同時に消すと、
1本の棒と m本の棒が奇数組になります。

そこで、残った m本の棒のどれかを （m-1）本消せば、この操作した
m本の棒はなくなり（m本の棒が一つなくなり）、1本の棒が一つ増える
ことになります。

今、1本の棒と m本の棒は奇数組なので、この操作により両方とも
偶数組になり、結局必勝形に戻るのです。

以上より、全てを偶数組にするという必勝形を作る上では、奇数本の棒を
1本と偶数本に分解して考えても支障がないのです。

★★−１０−★★
今回の理論では説明できない必勝形は他にも沢山あると思います。
たとえば、2・4・6は（多分）必勝形だと思いますが、私の考えた理論
では説明がつきません。

私なりに一生懸命考えてみましたが、残念ながら完璧な理論を
導くことはできませんでした。

ただし、実際に棒消しをする上では問題なく利用できる理論だと思います。

前の山崩しに書き込みしてた者です。

まず棒の数を２進数に変換します
１：１
２：１０
３：１１
４：１００
５：１０１
６：１１０
７：１１１
８：１０００

そして次のように計算。２、４、６だと
１０
１００
＋ １１０
ーーーーー
２２０

このように計算してすべての桁が偶数だと必勝形になるようです。

上のスペース（空白）が上手くいかなかった。。。

＞フォン・ノイマンさんへ

数学的で、よさそうな理論ですね。
でも、何故

＞１０
＞１００
＞＋ １１０
＞ーーーーー
＞２２０

なのでしょうか？
スペースはとりあえず、「�V」を使ってみて下さい。
そしたらずれないですよ。

＞５６

つまりですね。
各桁ごとに、１がいくつあるか数えるのですよ。
１０と１００と１１０の場合、
下から１けた目には　１は０個、
下から２けた目には　１は２個、
下から３けた目には　１は２個、
というのが、上の式の意味です。

なぜ、すべての桁を偶数にすると必勝なのかはないしょ。

２進表記した各桁毎の排他的論理和ですね。
Windowsのアクセサリの電卓で関数モードにすると xor てキーがあります
それがこの演算でです。

実は私は最近、上記排他的論理輪の理論を使って、Javaで棒消しゲームを
作ったものです。
URLは
http://users.goo.ne.jp/kaguri/
です。やってみてください。

↑排他的論理和です。

↑ところで、関係の無い僕がこんなところに書き込んでしまって
ごめんなさい。

は、話が難し過ぎてついていけない・・・

とりあえず、グズミさん、あんたエライです。

知らない間に、このスレ上がってましたね。

>>57、>>58さん
説明、ありがとうございます。

>>kaguriさん
す、すごいです。
よくできたゲームです。

>>62
残念ながら、排他的論理和を使うといった高度な解答は
私には導けませんでした。
数学版にもスレを立てたので、見てみてください。
こっちはもっと難しいかもしれませんが・・・

http://cheese.2ch.net/test/read.cgi?bbs=math&key=977132567&ls=50

私は C言語を少し操れるので、論理演算自体は知っていました。

あげええええええ

試合しよー。
先手必敗といわれるこれで。

1
2
3
4
5
6
7

では私が先手で。
1
2
3
4
5
6
2･4

棒はなしでやるの？

わからん

>>65
余裕ですがな。

2
3
4
5
6
2･4

むむできる・・・

2
3
4
5
2･3
2･4

>>69
やっぱりルールを少しひねらないとね。結果でちゃってるし…
なにかエレガントで破綻していない追加ルールないかな?

2
3
4
2
2･3
2･4

これ以上やるのは意味なさそうだね。
投了しておきます。
追加ルールか・・・
誰かいい案ないのかな？