分棋子

5、桌子上有8枚棋子，甲乙二人轮流拿棋子。规定第一次不能都拿走，拿几枚都成，以后每次拿的棋子数不能多于上次对方拿的2倍，两个人轮流抓取，拿最后一枚棋子谁就算胜利。怎样拿必然取胜，为什么？

说明，楼主也没有答案。

8枚，穷举法也出来了吧

第一次不能拿3及其以上，就只能1和2。先1，第二次拿2。还剩5个，先拿的怎木都输鸟

先2，第二次拿1，还素剩5个。先拿的还素输

回复 #2 KYOKO 的帖子

先分析少的，从中得到解题思路。

改成361个呢？

似乎后走的每一步只要使余下的棋子数量为奇数且令先走的不能一次拿走余下的棋子就能赢。

而且后走的除了最后一步，每一步只拿一个或两个，但要抢先留八个而避免留下七个.

[color=Silver][[i] 本帖最后由 lcarron78 于 2011-10-1 08:40 编辑 [/i]][/color]

这是养兔子的数列吗？

恩 题目可以变种的，“以后每次拿的棋子数不能多于上次对方拿的2倍”完全可以变成3倍，所以，还得有个整体思路:hz1024:

如果将问题一般化，m枚棋子分别抓取，一次抓的不能超过上次抓的n倍。那么要想先手有必胜策略则必须要使m-1，m-2,一直到m-i的情形下，其中i=[(m-1)/(n+1)]，至少有一种后手有必胜策略。设m=k(n+1)+l,其中k,l是自然数，l∈[0,n]
于是i=k+[(l-1)/(n+1)]当l=0时为k-1,l>0时为k.
1≤m≤n+1时，后手必胜。m=n+2时先手胜。再一直到2n+2时结果是交替的。然后2n+3是先手胜从2n+4开始要讨论n的奇偶性了。大体思路如此，这种问题不难

后手必胜啊！

回复 #8 zhumeng 的帖子

当棋子很多时，对方的选择有很多。

不妨先分析总100个，每次最多拿2倍（3倍也可以）。

列出前面部份的結果：

棋子數    先手勝負
2           負
3           負
4           勝
5           負
6           勝
7           勝
8           負
9           勝
10         勝
11         勝
12         勝
13         負
14         勝
15         勝
16         勝
17         勝
18         勝
19         勝
20         勝
21         負

……

結論是位於兔子數列上的數字，先手要輸。

回复 #11 dimeterio 的帖子

有证明过程吗？

李秀辰猜想~:hz1016:

回复 #12 墨叶 的帖子

严格的证明做不出。

简单说，对于大于某个兔子数的棋子，比如大于13，先手的任务是抢到14号棋子，而且肯定可以实现。对于兔子数，比如21，由于它和13的差是另一个兔子数8，所以先手肯定抢不到14，必败。

回复 #14 dimeterio 的帖子

验证了小数字是正确的。
明白你的意思。

本题最难处是前一个人的选择会影响到后面的过程。
所以严格证明比较困难。

回复 #6 周瑜 的帖子

思考后得到以下结论：

以下为不同棋子数时先拿者的胜负及限定条件。
2  负  <2  （当前一回对方拿的棋子小于2个时成立）。
3  负  <2
4  胜  取1  （要获胜必须取1个）  
5  负  <3
6  胜  取1
7  胜  取2
8  负  <4
9  胜  取1
10 胜  取2
11 胜  取3,>1
12 胜  取1
13 负  <6
14 胜  取1
15 胜  取2
16 胜  取3,>1
17 胜  取4,>1
18 胜  取1；或者取5
19 胜  取2，
20 胜  取3，>1
21 负  <11

可以证明。

8  负  <4
20 胜  取3，>1

=============
先拿为负，4啥意思，具体点。还有>1

头晕ing……:hz1043:

回复 #17 KYOKO 的帖子

2  负  <2  
2颗棋，先拿者输。若不是开始阶段，当前一回对方拿的棋子小于2个时成立。也是输，否则可以获胜。

20 胜  取3，>1
20颗棋，先拿者胜。若不是开始阶段，当前一回对方拿的棋子大于1个时成立。也是胜，否则输。

回复 #19 墨叶 的帖子

若不是开始阶段，当前一回对方拿的棋子大于1个时成立。也是胜，否则输。

=====================
俺汉语理解有问题？还是不懂这句话啥意思。。:hz1043:

[quote]原帖由 [i]KYOKO[/i] 于 2011-10-29 16:29 发表
若不是开始阶段，当前一回对方拿的棋子大于1个时成立。也是胜，否则输。

=====================
俺汉语理解有问题？还是不懂这句话啥意思。。:hz1043: [/quote]


3  负  <2  
3颗棋，先拿者输。若不是开始阶段，当前一回对方拿的棋子小于2个时成立。也是输，否则可以获胜。

比如5颗棋。
甲先拿2颗。剩下3颗。轮到乙拿，乙可以一次拿走剩下的3颗获胜。
甲虽然使棋子剩3颗，还是输了。所以3颗棋不是必败局面。
开始只有4颗棋时，甲可以先拿一颗。此时轮到乙面对3颗棋且上回合对方拿棋小于2。必败。

另， 2 负  <2  有误。

[color=Silver][[i] 本帖最后由 墨叶 于 2011-10-29 16:38 编辑 [/i]][/color]

更正：

以下为不同棋子数时先拿者的胜负及限定条件。
2  负  <1   （当前一回对方拿的棋子小于2个时成立，即只有开局才负）。
3  负  <2   （当前一回对方拿的棋子小于2个时成立，下同）。
4  胜  取1  （要获胜必须取1个）  
5  负  <3
6  胜  取1
7  胜  取2
8  负  <4
9  胜  取1
10 胜  取2
11 胜  取3,>1
12 胜  取1
13 负  <6
14 胜  取1
15 胜  取2
16 胜  取3,>1
17 胜  取4,>1
18 胜  取1；或者取5
19 胜  取2，
20 胜  取3，>1
21 负  <11

可以证明。

20颗棋子的情况能解决就差不多解决问题了。

回复 #9 meidi9z 的帖子

选择是多，就是在那么多选择中有一个后手必胜的，就必然会先手胜。

试了一遍，好像不大会玩

答案：先拿者必胜，第一次必须拿两枚。

首先，先拿者第一次只能拿1个或者2个，各种情况分析如下：

(先拿者为A，后拿者为B )

1、1(1或者2)、1(此时A只能选择拿1枚)、1(此时B只能选择拿1枚)、1(此时A只能选择拿1枚)……最终B胜。

1、2(1或者2)、1(此时A只能选择拿1枚)…………最终A胜。

2、1(此时B只能选择拿1枚)、1(同上)…………最终A胜

所以，A必胜，第一次拿2枚。

[size=3][color=blue]若增加棋子数，答案为：

当总棋子数为偶数时，先拿者必胜，第一次取的个数：(总棋子数/3) - 1 取整

当总棋子数为奇数时，先拿者必胜，第一次取的个数：(总个数/3) - 2 取整(棋子数≥9)[/color][/size]

[color=Red][b][size=3]以上蓝色字的答案有待验证……[/size][/b][/color]

[color=Silver][[i] 本帖最后由 Garnet 于 2011-12-8 20:55 编辑 [/i]][/color]

回复 #26 Garnet 的帖子

1、1(1或者2)、1(此时A只能选择拿1枚)、1(此时B只能选择拿1枚)、1(此时A只能选择拿1枚)……最终B胜。

1、2(1或者2)、1(此时A只能选择拿1枚)…………最终A胜。


明显错误，倒数第二步乙可以拿2。。。。

度娘了一下，这里有加强版的。。

[url]http://www.aoshu.com/e/20090626/4b8bcbc79c57a.shtml[/url]