第五版杀拉五题串烧

21457 · 发表于 2018-4-22 09:51:35

5.
从前有两个无聊的小孩，他们在地上玩石子。
第五天，他们把所有石子排成一排，同时在地上画出N个格子。
格子从左到右画成一排。在某些格子上放上了石子。
他们商量好轮流移动一颗石子，操作的规定是：
①只能向左移动，并且不能超过这颗石子的左边第一颗石子
②一个格子中最多只能放一颗石子
③到了最左边格子的石子无法再次移动
无法进行这个操作的人算输
A先移动，B后移动。

以下情况时谁有必胜法？
1.N=10,石子位置1,6,9
2.N=200,石子位置2,6,8,9,45,66,105,199
3.N=1000,石子位置1,6,57,69,153,156,567,496,689,899

22568 · 发表于 2018-4-23 15:09:24

5.
为方便表述,若石子总数为奇数,则在最左边增加一格并放入石子.
显然此操作对局面无影响,故不妨设石子总数为偶数.
将所有石子从左到右依次两两分为若干对,考虑每对石子之间空格的数量.
我们证明如下命题:

引用
原题局面等价于所有上述空格数组成的nim博弈局面.

证明:
I.对某胜局,nim中策略为将某数减小.在原题局面中将对应石子对中右石左移以减少左边空格数即可.
II.对某败局,若原题中移动某对的左石,对手将右石左移相同格数即保持对应nim局面不变,仍为原先败局.
III.对某败局,若原题中移动某对的右石,对应nim局面改变,成为胜局,对手按I操作即可.

21457 · 发表于 2018-4-24 10:03:21

本期五题结束，我们下期再见（如果还有下期的话）

[逻辑推理] 第五版杀拉五题串烧