石の山がいくつかあって、2人で交互に石の山から石を取っていき、最後の石を取ったほうが負けというゲームがあります。
山の数はいくつでもいいのですが、それぞれ山の石の個数をa,b,c,d,・・・・としたとき、
最初の山の状態は、a≧b≧c≧d≧・・・とします。
石の取り方は、
・好きな山から、任意の個数を取る。
・取ったあと、a≧b≧c≧d≧・・・の関係が成り立つように別の山から石が除かれる。
たとえば、
(10,9,9,6,3)の山があった場合、
2番目の山から4個とって5個にしたら、3番目以降の山からも5個を超えた分だけ石が除かれて、
(10,5,5,5,3)となります。
山が2つの場合は、(k,k-1)の状態を良形とすれば、
自分の手番のときに、良形にできれば必勝となります。
では、山が3つの場合や4つの場合、必勝となるための良形とはどんな状態でしょうか。
良形かどうかを簡単に確認する方法はあるでしょうか。
No.6ベストアンサー
- 回答日時:
No.2です。
了解しました。チョンプですね。だったら未解決ですね。この形だと、少し先にいけるかもと思ったけど。
あまり深く追求するのはやめておきましょう^^;
(4,2,1)は勝てないですね すみません。
(4,2,2)で、手番負けなんですね・・・。
(3,1,1)も手番負けだから、ひょっとすると、
(j+2、j,j) のときは、手番負けなのかも?
で、話が変わりますが、順序が違ってしまったけど
何をやろうとしていたかを書いていなかったです。
2つの山の場合、勝つパターンは分かった。
↓
3つの山のとき、勝つパターンと、負けるパターンを探し出し
一般化する。
↓
4つの山のとき、一部ではあるだろうけれど拡張可能。と見ていました。
なので、3つの山での、「手番勝ち」、「手番負け」を探していました。
多分、(k,k,k)は手番勝ちですね。
だとすると、(2,2,2,1)となったとき、手番負けですよね。
#多分そうだよ・・・。
この形式なら少し先にいけるのかもね。
気が向いたら^-^
紹介していただいたサイトに書かれていましたが、
(k,k,k,・・・,k)は先手必勝ですね。
チョンプの盤で考えると縦と横を入れ替えてもゲームとしては同じなので、
(k,k-1)
と
(2,2,2,・・・,2,1)
は同じ形になり、どちらも後手必勝です。
3つの山で、3番目の山が0~2個の場合は、
(k,k-1,0) (k≧1)
(3,1,1)
(2,2,1)
(k,k-2,2) (k≧4)
が後手必勝になることまでは分かったのですが、3個以上の場合は不規則になるようで、何か規則性はないかと質問した次第です。
とりあえず締め切りますが、何か分かったらまた質問しますので、よろしく願いします。
No.5
- 回答日時:
こんばんは No.2です
えっと、チョンプ なのかどうかちょっと分かりかねますが、
こういうページがありましたので、一応。
http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/lect …
アクロバットリーダーがいるけど、組み合わせゲーム理論の講義内容みたいですね。
これは正直、難しいと思う。
何でもかんでも式化すればいいかって話で・・・。
私どちらかというと普段はやらないんだよね。
#なので、半分本職なのね。
3つの山を考えていますが
それぞれ 大きい順に L、M、S (ポテトかっヽ(・∀・)ノ )
としておきます。
今、LとMの差が 1 のとき、 何も考えず、先手必勝。
(L,M,S)・・(k+1,k,any(≦k) )
こうなっているときは、黙って、anyを全部とって、2つにして勝ちですね!
何も断りを入れていないけど、kは自然数ね。
any≠0ね
LとMの差が2以上のとき、条件満たさなければ先手必敗だと思うんだけどね~。
#まだ微妙・・・。
(k+2,k,any) のときに、 any(Sの山から)全部は取れないですね。
#(k+1,k)作られて負け。
k+1も作れないよね (Lの山から一本)
#これは any 全部取られて負けだね。
(3,1,1)で、先手が勝てる手があるかどうか。
多分ないかなぁ~??
ところが(4,2,2)なら勝ちなのよね。
Sの山から 一本とって (4,2,1)で勝ちですね。
これで後手は動けない。
2進数で考えたほうが少し得かな?
4=(100)2進数 → これを 一本とみなす。
2=(10)2進数 → 同じく一本とみなす。
そうすると、 (4,2,1)は (1,1,1)と同じ。
でもこの場合はダメなのよね。う~ん、難しいね。
(1,1,1)は先手勝ち。 Mの山を取れば、(1,0,0)で終わり。
(4,2,1)は、この方法が使えない。(4,0,0)なら、先手勝ちだもん。
(4,1,1)にするしかないけど、先手は(3,1,1)にして、後手に手無し。
#(3,2,1)は、Sとって先手勝ちね。
今のところ考えている三つの山の場合、「LとMの差が1のとき」
「(1,1,1)~(4,4,4) 同じ数の山」
#(5,5,5)が大丈夫かどうか検討中。
#(5,3,3)で後手に手がなければ、先手勝ち。
#これができれば、(J(≦k+2),k,k(≠1) が大丈夫)
これは大変な問題だ! 数学オリンピックかなんかかな?
回答ありがとうございます。
このゲームは表現方法はちょっと違いますが、まさしくチョンプでした。
LとMの差とか2進数で考えるというのは参考になりました。自分でももう少し考えてみます。
この問題は、(5,5,5,5,5)のときどうすれば勝てるかというクイズがあって、
正解は、(5,1,1,1,1)にして、あとは1番目の数と山の数を同じにしていけば勝てるということでした。
例えば、
(5,1,1,1,1)→(4,1,1,1,1)→(4,1,1,1,0)
(5,1,1,1,1)→(5,1,1,0,0)→(3,1,1,0,0)
これを一般化したらどうなるかと考えてしまいました。
このことから、(3,1,1)は後手の勝ちですね。
(4,2,1)は後手勝ちと書かれていますが、
(2,2,1)にすればいいので、先手勝ちではないでしょうか。
(4,2,2)が後手勝ちのようです。
ともかく、未解決の問題だということが分かっただけでも質問した甲斐がありました。
No.4
- 回答日時:
これはチョンプと言うゲームで、多分現在でも未解決だろうと思います。
必勝法が知られているのは、(N,1,1,1,・・・,1)と言うパタンと、
(2,2,2,・・・,2,1,1,・・・,1)と言うパタンくらいではないかと思います。
チョンプと言う名前があったんですね。知りませんでした。
ありがとうございます。
未解決でしたか。
三山崩しのように簡単な計算で判断できないかと思ったんですが無理のようですね。
(N,1,1,1,・・・,1)(山の数がN個)のパタンは分かっていましたが、
(2,2,2,・・・,2,1,1,・・・,1)と言うのは?
(2,2,2,・・・,2,1)ではないですか?
No.2
- 回答日時:
ゲーム理論かな?
ニムのゲームに似ているけど、少し違うんだね。
半分本職領域なので、ちょっと考えておきますね
m(_ _)m
一つだけ確認。山が二つで、(2,1)が勝ちなら、
相手は二個取れば負けでいいんだね。取り除かれた分も自分がとったことになるんだね。
これだけ確認させてください。補足して貰えると助かります。
#まぁ、でもそういうことなんだろうけど。
自分(2,1){にする} → 相手(1,1) →自分(1,0) これで勝ちだよね。
後は拡張すればいいのか・・・。ちょっと考えさせて。
>取り除かれた分も自分がとったことになるんだね。
そうです。
(k,k-1)のとき、
相手が1番目の山から何個か(全部じゃなく)取った場合、(k,k)の形になるので、自分は2番目の山から1個取れば、(k,k-1)の形になります。
相手が2番目の山から何個か取った場合、自分は1番目の山から同じ数だけ取れば、(k,k-1)の形になります。
最終的に(1,0)になって、相手が最後の石を取ることになります。
問題は、山が3つ以上の場合です。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Java Java 石取りゲーム 3 2023/02/02 15:46
- C言語・C++・C# 石取りゲームをC言語プログラムで教えてください 1 2022/04/09 14:16
- 中国・四国 大阪(難波)から山陰への旅行プラン 3 2022/10/11 10:02
- その他(地域情報・旅行・お出掛け) この11月or12月に小学校中学年の息子と行く旅行場所について。 1 2022/10/25 23:56
- タレント・お笑い芸人 石橋貴明と極楽とんぼ山本圭一の関係 2 2022/11/22 19:49
- 政治 ガーシー議員は、29万票を取って当選されましたが、これは江戸時代の大大名の石高に匹敵しますね? 44 2023/03/10 10:04
- Excel(エクセル) EXCEL 関数を教えてください。(A列の同じ値が複数ある場合vlookupで出来ますか) 4 2022/12/07 20:54
- 教育・ドキュメンタリー 今、日本を変えた昭和遺産と言う番組で池島について放送していました。簡単に言うと軍艦島のような島で唯一 1 2022/10/26 19:47
- 日本語 普遍・特殊・個別をハガの違いに適用しようとするのは無理筋 139 2022/11/17 19:59
- ガーデニング・家庭菜園 庭のブヨブヨした「青のり」の様な物は? 3 2022/07/16 20:29
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
石取りゲームの必勝法
-
人工少女2の操作について
-
お金を使うことについて
-
ファイナルファンタジータクテ...
-
上目遣いの自撮りを撮るのはキ...
-
モンストで位置情報を取得でき...
-
ナンプレ 数独 ここから仮置き...
-
手を挙げるのが右手のときもあ...
-
太鼓の達人の上達についていく...
-
ドラゴンボールZ スパーキング!...
-
ドラゴンクエスト7魔法の絨毯(...
-
BLACK/MATRIX+
-
パズルが下手すぎて……
-
ファイアーエムブレム聖戦の系...
-
携帯ゲーム ちゅら海物語
-
FF7で出てくるせりふ お前の...
-
メタルギアソリッド メリルの...
-
動物の角や骨が欲しいです。ア...
-
最近、誕生日プレゼントに祖母...
-
Panasonic LF-D102ソフトのダウ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
石取りゲームの必勝法
-
つるかめ算
-
ケンカに勝敗はありますか?
-
怒ったら負け。黙ったらボロ負...
-
少し疑問を思ったのですが、 『...
-
この数学ゲームの必勝法をおし...
-
○×ゲームの必勝法
-
もしもの話です 乃木坂46の握手...
-
匂い元
-
朝日新聞の【天声人語】をネッ...
-
動物の角や骨が欲しいです。ア...
-
お金を使うことについて
-
私のぱそこん教室でのWordの練...
-
ビオフェルミンの瓶(のような...
-
ファミコン オバケのQ太郎 ワン...
-
ドラゴンボールZ スパーキング!...
-
レクサスのトランクをあけたら ...
-
ファイナルファンタジー7の質問...
-
フォートナイトで住所特定された
-
ドラゴンクエスト7魔法の絨毯(...
おすすめ情報