一个比较有趣的问题

113602 · 发表于 2021-3-3 21:38:49

有两堆棋子，一堆114个，一堆514个，
甲和乙两人轮流取棋子，甲先拿乙后拿，每次拿棋子最少拿一颗，最多把一堆全部拿完，也可以同时在两堆拿走同样多的棋子。拿走最后一枚棋子的人获胜。
问题1：甲或乙是否有必胜策略，如果有的话请证明
问题2：如果问题1的答案是肯定的，请问策略是什么，并证明
问题3：如果一堆a个，一堆b个呢。

141002 · 发表于 2021-3-4 12:44:02

其实题主提示前我已经列出了很多题主所说的必败态，由于列举时马虎出了点错误导致通项推得好慢（本来这题也不咋好推），补充题主的提示来说明吧，（1,2）是必败态不赘述了，由此推（1，n）（n>2）和（2，n）（n>1）都是必胜态，而（n,n+1）(n>1)也同样是必胜态，易得下一个必败态中小值为除1,2外的最小值3，而大值为和小值相差大于1的最小值，即3+2=5（具体过程不详述了），这样可以继续推出其他的必败态，下一组是4和4+3，即（4,7），接下来是（6,10），（8,13），（9,15），（11,18），（12,20），（14,23），（16,26），（17,28），（19,31），（21,34）
接下来总结规律归纳，必败态较小值的逐项差分别为
21221 21221 221
对应较大值的逐项差
32332 32332 332
由于后一组两数差总是比前一组多1，容易得出两组逐项差是一一对应的，同时，后面较小值的逐项差又可根据前面大值的差递推得出，每一个3对应一组21，2对应2（可能这块我说的很不好理解），目的只是证明这两组逐项差确实是循环的规律，而且循环体就是13位，这样就可以推出必败数的表达式分别为（1+21n,2+34n）,(3+21n,5+34n)。。。。。（n>=0,正整数）
21221 21221 221
32 3 32 3 2 3
那么回到题目，114,和514，明显两数的差400远大于114，属于安全范围，所以只需要判断114率先落到哪个必败数上就好了，114除以21余9，落到（9+21n,15+34n）上，此时n=5,必败数为（114,185），所以甲把第二堆拿到剩185即可根据策略获胜。
至于a和b,懒得算通项策略了，要判断其中较小数和两数差的关系，再根据余数得出结论
过程写的不那么清楚，请大家见谅

113602 · 发表于 2021-3-5 09:26:55

继续根据五楼的过程

引用
若取一堆肯定有一堆是3或5，而前面的必败态没有一堆是3或5；若同时取两堆则两堆的差是2，而前面的差（0，0）是0，（1，2）是1，所以也不可能。那么（3，5）是必败的。

我们可以总结出必败态的两个条件，
1.较小的那一堆的个数不能和之前已存在的必败态的数目相同，不然可以直接取走一定数目成为那个必败态
2.必败态大数和小数的差不能在前面出现过，同时又得是最小的，所以是0，1，2，3……递增的
那么我们可以确定较小数遵循的规律是前面必败态未出现的最小数，而较大数是较小数加上累积的差值，下面进行相对严格的证明。（由于公式较多我写了以后导出了图片格式）

149457 · 发表于 2021-3-3 22:22:38

不会

142436 · 发表于 2021-3-3 23:03:09

没头绪

141002 · 发表于 2021-3-4 09:32:31

甲先在第二堆拿400个，即使两堆都剩114个，接下来只要保持乙在其中一堆拿n个，甲就在另一堆同样拿n个，即保持甲拿完后两堆剩余数量相等即可，由于乙拿完后两堆数量永远不可能相等，而获胜条件是两堆相等且等于0，则甲必胜；如果一堆a个，一堆b个，若a不等于b,那么和前面一样，甲有必胜策略，若a等于b不等于0，则两边倒转，乙有必胜策略。

113602 · 发表于 2021-3-4 11:59:41

再给点提示吧，（0，0）必败，（0，1）（1，1）（0，2）必胜，（1，2）无论怎么取都会变成前面三种必胜态之一，所以必败，（1，3）（1，4）（1，5）（2，3）（2，4）（2，5）（3，4）可以通过某些方式变成（1，2），（2，2）（3，3）可以通过某些方式变成（0，0），所以上面这些都是必胜态，（3，5）无论怎么操作都会变成必胜态：若取一堆肯定有一堆是3或5，而前面的必败态没有一堆是3或5；若同时取两堆则两堆的差是2，而前面的差（0，0）是0，（1，2）是1，所以也不可能。那么（3，5）是必败的。其实必败态需要满足的两个条件都在上面的推导过程中了。

113602 · 发表于 2021-3-4 23:31:54

先讲一下第一个问题吧。
这个问题是典型的无偏博弈，即玩家的局势与玩家的身份无关，只与当前的状态有关。举个例子，如果给定某一个状态时轮到甲操作，甲取胜了，那么这个状态乙进行操作乙也能取胜。围棋象棋等游戏由于双方的棋子不同，所以所能进行的操作是有差异的，比如五子棋在白棋连了四颗以后下一步若轮到白棋白棋就能赢，而轮到黑棋黑棋却不能赢。
回到这个题目。首先由于是无偏博弈，那么我们可以把玩家先剔除分析，只考虑局势。由于棋子的个数有限，并且每次至少拿一个棋子，所以该博弈是有限次的（貌似也是无偏博弈的前提之一）结合我五楼关于必胜态必败态的讨论可以得到每个状态一定是确定存在必胜策略或是一定会失败（当对方也知道必胜策略时）。所以问题一的答案是肯定的。
二三明天再分析，今天装了几十个g的软件有点累了。

22568 · 发表于 2021-3-5 01:14:24

直接答通项吧..
没记错的话败局用Beatty定理表示,系数是黄金数..

22568 · 发表于 2021-3-5 13:09:46

ls已经有完整过程了,那我简单说几句吧..(毕竟爪机..
简单分析知要把Z+分成两部分,对应项的差依次为Z+.
容易猜到Beatty的格式,于是有[an]-[bn]=n,1/a+1/b=1.
无视[]即得答案是黄金数.
代回去证明确实满足上边那个带[]的式子就做完了.

码过程的话,把前边说的"简单分析"描述好,再直接丢出黄金数证明符合就完了.
顺手再补个Beatty的证明,就可以结帖了.

[数学趣题] 一个比较有趣的问题