免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 有$n$个石子,甲乙轮流取,取到最后一颗获胜。

如题。这类问题的一般解法是什么?假设规定每次只能取走$p_1<p_2<\cdots<p_k<n$个。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

比如30颗石头,甲乙轮流取,每次取2~5颗。
要抢到第30颗,就须抢到第23颗(30-2-5=23)
要抢到第23颗,就须抢到第16颗(23-2-5=16)
要抢到第16颗,就须抢到第9颗
要抢到第9颗,就须抢到第2颗,先抢赢了.

字母p1,p2,n有些复杂,要不具体数字再试下.
比如30颗石头,甲乙轮流取,每次取3或5颗.
模仿上题一方取第25,27的时候,接下来一方就赢了
一方取第23,24(对方接下来一定不取3颗),26,28,29那么和局.
取第22颗,会迫使对方取25,27,如此要赢的话,依次取第30,22,14,6,这样先取的人一定取第5颗,最终和局.

TOP

TOP

巴什博弈、斐波那契博弈、尼姆博弈、威佐夫博弈
类似的一些东西

TOP

回复 4# mowxqq

谢谢,很有帮助。不过这里取走的都是最少1,最多无限个,数量是整数连续的,而这里的$p_1,p_2,\cdots,p_k$可以不是整数连续,也会出现2楼的和局情形。

TOP

如果$n=\sum_{i\in\{1,2,\cdots,k\}}p_i$且允许$p_i$重复相加,能不能说明当加数个数为偶数时先手必败,为奇数是先手必胜?
如果$n$不能写成这种形式,则必是合局。

TOP

返回列表 回复 发帖