有趣算法题

25 Sep 2014

有100个球,甲乙两人轮流取,每次必须且只能取1到5个,最后一个取球的输。若甲先取,有无必胜策略?

分析

如果总球数为1,第一个就是最后一个必输。

如果总球数为2,3,4,5,6,甲取1,2,3,4,5个,乙只能取剩下的一个,存在必胜策略。

如果总数为7,无论甲如何取(1,2,3,4,5),乙只要取(5,4,3,2,1)就可以留一个给甲,存在乙必胜策略。

结论

如果总个数满足:

sum = 6*n + 1

不管甲每次取几个(x),乙在甲取后只要取(6-x)个,就可以两人总共都取n次,最后剩一个给甲(先手)。

面对6n+1的境地就是必输境地,甲先手取,就要构造6n+1境地给乙。

回到题目中,甲的必胜策略为:

第1次取3个,留97给乙(97 = 6*16 + 1);

第2次至17次,乙取过之后x个,甲取6-x个;

最后剩1个,刚好到乙的顺序取球。

总结

甲乙总共各取17次,第1次甲取3个,中间16次,每次甲乙共取6个,最后1次乙取最后一个: 100 = 3 + 16 * 6 + 1