次の石とりゲームに必勝法はありますか

質問

二人で石を取り合うゲームがあります。
ゲームのルールは次の通りです。

・石の数は60個。
・二人で交互に石を取り合う。
・1回の手番で取れる石の数は1個～3個。
・石がなくなったとき、とった石の数が多いほうが勝ち。
・ただし、最後の1個は、石30個分として扱う。

このゲームに必勝法はありますか。
もしあるなら、どうしたら勝てますか。

また、最初の石の数が60個ではなく、N個だった場合、
どういう戦略なら勝つことができるのでしょうか。

回答No.2

stomachman · ベストアンサー

> ・石がなくなったとき、とった石の数が多いほうが勝ち。

>・ただし、最後の1個は、石30個分として扱う。

「石1個が1点、ただし最後の石だけは30点」と考えると分かり易くなります。



> このゲームに必勝法はありますか。

　全ての情報が先手後手の双方に見えていて、しかもサイコロのような確率が入って来ないゲームですから、原理的に、（双方が最善を尽くせば）必ず引き分けにできるか、（後手が最善を尽くしても）先手必勝か、（先手が最善を尽くしても）後手必勝か、のどれかです。
　先手の得点と後手の得点の合計は常に(N-1+30)点ですね。N=60の場合には得点の合計が89点であり、ところが双方とも得点は整数なので、引き分けはありえません。従って、先手必勝か、後手必勝か、必ずどっちかです。


> もしあるなら、どうしたら勝てますか。

　Nが1以上60未満なら、「最後の1個を取ったら勝ち」というゲームと同じです。必勝法は、「（相手が何をやろうとも）常に4の倍数個を残す」だけ。なのでNが4の倍数なら後手必勝、さもなければ先手必勝です。

　たとえばN=56の場合は後手必勝。後手Yは必ず4の倍数個を残せるから、最後の1個はYが必ず取れる。先手Xはなるべく多くの石を取るために毎回3個を取るのが最善手で、それに対してYは常に4の倍数個を残すために1個を取る。これを14回繰り返してゲームは終わり、Xは42個取って42点。Yは14個を取るが、うち1個が30点なので43点、1点差でYの勝ち。（Xが他の手を打てば、点差が広がるだけ。）
　N=57(58, 59)の場合は先手必勝。先手Xは1(2, 3)個を取って4の倍数個である56個を残す。これでXが最後の1個を取れることは確定。後手Yはなるべく多くの石を取るために毎回3個ずつ取るのが最善手で、それに対してXは毎回1個を取る。これを14回繰り返してゲームは終わり、Yは42個を取って42点。Xは15(16, 17)個を取るが、うち1個が30点なので44(45, 46)点で、2(3, 4)点差でXの勝ち。（Yが他の手を打てば、点差が広がるだけ。）

　N=60の場合には4の倍数だけれども話が変わり、先手必勝です。後手Yは最後の1個を取ることを狙って、必ず4の倍数個を残すとしましょう。一方、先手Xはいつも3個を取るとしましょう。すると結局、Xは45個の石を取り、45点。Yは15個の石を取り、うち1個が30点なので合計44点。だから1点差でXの勝ち。
　こうなることを避けるためにYが一度でも2個以上の石を取ると、以後、Xは常に4の倍数個を残すことによって最後の1個の石を取ることができる。しかもXが最初に3個取っているために、Yが取れる石の個数は高々42個(Yが毎回3個ずつ取ったとしても42個)。従って5点以上の差を付けてXが勝つ。なので結局、Yは4の倍数個を残すという方法で最後の1個を取るのが最善（点差が最小）です。

　N=61だとどうか。先手Aが最初に石をs個取ることによって、Aがまずs点獲得する。そして後手Bの手番になります。これで、N=61-s(=60,59,58)の場合にX=B, Y=Aとなったのと同じ状況です。N=60, 59, 58はどれも「X=B必勝」なのだけれども、問題は最初にAが取ったs点。N=60, 59, 58のどれかのゲームでX(=B)がY(=A)にs点未満の差しか付けられないようにY(=A)が打つことが出来れば、結局Aの必勝法があるという事になるし、それが出来なくても、XがYに丁度s点差しか付けられないようにY(=A)が打つことが出来れば、Aには引き分けに持ち込む方法があるということです。どちらでもなければ、Bの必勝法があるということ。
　この結論がどうなるかは、ご自分で考えてみては如何でしょ。それが出来たら、N=62, 63, についてもやってみると宜しいかと。

お礼

回答ありがとうございます。

石の数が60個未満の時はニム？と同じ、60のときは逆に先手必勝ということですね。
61個以上の時は個別に1つ1つ考えないといけないのでしょうか。
少し自分でもしらべてみます。

回答No.4

stomachman

ANo.2へのコメントについてです。

> 61個以上の時は個別に1つ1つ考えないといけないのでしょうか。

　関数f(N) を 「最初の石の数がNであるときに、両者がそれぞれなるべく多くの点を取ろうと最善を尽くした場合、先手が後手に比べて何点多く取るか」という意味だとします。すると、ANo.2により
　　f(58) = 3
　　f(59) = 4
　　f(60) = 1
でした。

N=61のとき。
　先手Aが初手としてs個(s=1,2,3のどれか)を取る場合のそれぞれについて考えます。
・s=3の場合、X=B, Y=AのN=58において、f(58)=3、つまりYが最善手を打ってもXは3個の差をつけて必勝でした。ということは、Aが最初に取ったs=3個を合わせますと、s-f(58) = 0。つまりAが最善手を打つとX=Bは勝てず、しかし引き分けになら持ち込める。
・s=2の場合、X=B, Y=AのN=59において、f(59)=4。ということは、Aが最初に取ったs=2個を合わせますと、s-f(59) = -2。つまりAが最善手を打ってもX=Bは2個の差をつけて必勝である。ですから、先手Aはs=2を選択してはいけませんね。
・s=1の場合、f(N-s)=f(60) = 1。ということは、s-f(60)=0。つまりY=Aが最善手を打つとX=Bは勝てず、しかし引き分けになら持ち込める。
　という訳で、N=61の場合には先手は初手としてs=1か3を選択するのが最善手であり、結果は引き分け。つまり、
　　f(61)=0

N=62のとき。
・s=3の場合、f(N-s) = f(59) = 4なので、s-f(N-s) = -1。つまり後手Bが必勝ですから、先手Aはs=3を選択してはいけませんね。
・s=2の場合、f(N-s) = f(60) = 1、s-f(N-s)=1。先手Aが1個差をつけての必勝です。
・s=1の場合、f(N-s) = f(61) = 0、s-f(N-s)=1。先手Aが1個差をつけての必勝です。
　という訳で、N=62の場合には先手は初手としてs=1か2を選択するのが最善手であり、結果は1個の差をつけて先手必勝です。つまり、
　　f(62) = 1

N=63のとき。
・3-f(N-3) = 2
・2-f(N-2) = 2
・1-f(N-1) = 0
　という訳で、先手は初手としてs=2か3を選択するのが最善手であり、結果は2個の差をつけて先手必勝。つまり、
　　f(63) = 2

　もうお分かりでしょうけれど、N＞60では、f(N)は漸化式
　　f(N) = max{s-f(N-s) | s∈{1,2,3} }
で計算できるわけです。さらに
　　f(N) = (N mod 6)が
　　　　1のとき…0　　　　（引き分け）
　　　　2か0のとき…1　　（先手必勝、1個差）
　　　　3か5のとき…2　　（先手必勝、2個差）
　　　　4のとき…3　　　　（先手必勝、3個差）
になることが証明できるでしょう。

お礼

再度の回答ありがとうございます。
大変よくわかりました。

回答No.3

MagicianKuma

先手が最初に3個とって必勝でしょう。もし次に後手が最後の石を取りに聞く作戦を取ったとしても（すなわち1個を取る)、No1さんの言うとおり45:44で勝ちです。後手がそれ以外の作戦をとると、逆に先手が最後の1個を確実にとりに行くことができ、最悪でも47:42で勝ちます。
N個の時の最後の石の価値はやはり30なの？

お礼

回答ありがとうございます。

No.2の回答で解決しました。

補足

> N個の時の最後の石の価値はやはり30なの？

えーと、繰り返しになってしまいますけど、
質問とNo.1の補足に記載した通り、最後の1個は石30個分として扱います。

回答No.1

bgm38489

後攻なら、負けない方法はありますね。
先攻の人が取った石と合わせて４個になるように、毎回取っていけばいいのです。１個なら３個、２個なら２個、３個なら１個。そうすれば、最後の３０個は必ずとれることになります。問題は、先攻の人が毎回３個取った時。最後の３０個の権利を取るためにはいこで応えていかなくてはなりませんが、そうすると、６０÷（３＋１）で１５回ですから、先攻は３×１５で４５個の石。後攻は１×１４＋３０＝４４、おっと、最後の１個が３０に数えるのであれば、負けてしまうね。最後の１個を取った人には３０個のボーナスが与えられる、というのであれば、足して４になるようにすれば、最低でも引き分け。
３０個のボーナスとすれば、石の個数が４の倍数＋αの場合、各回を４の倍数＋αになるようにしていけば、先攻・後攻のいずれかにおきての必勝パターン、というより、必ず負けない取り方となる。

お礼

回答ありがとうございます。

No.2の回答で解決しました。

補足

ええと、、、

質問に記載した通り、最後の1個は石30個分として扱います。
追加で30個分もらえるという意味ではありません。
つまり、全体では石89個分です。