每日一题[1001]必胜策略

甲乙两人在沙滩上玩鹅卵石游戏,现有$15$块鹅卵石,甲乙两人轮流从石堆中拿出鹅卵石,每次每人拿的石块数只能是$1,2$或$3$,直到鹅卵石全部拿完游戏结束.如果当游戏结束时,总共拿到奇数个鹅卵石的人获胜,请问是否有必胜策略.


cover

分析与解 设共有$n$块鹅卵石,先考虑简单情形.

当$n=4$时,先手拿$3$块,必然能拿到奇数块鹅卵石;后手必然能拿到奇数块鹅卵石.

当$n=5$时,先手拿$1$块,必然能拿到偶数块鹅卵石;后手必然能拿到奇数块鹅卵石.

当$n=6$时,先手若拿$1$块,就转化成了$n=5$时的后手,必然能拿到偶数块鹅卵石;先手若拿$2$块,就转化成了$n=4$时的后手,必然能拿到奇数块鹅卵石;此时后手没有任何保证拿到奇数块鹅卵石或偶数块鹅卵石的策略(任人宰割).

当$n=7$时,先手若拿$1$块,就转化成了$n=6$的后手,任人宰割;先手若拿$2$块,就转化成了$n=5$时的后手,必然能拿到奇数块鹅卵石;先手若拿$3$块,就转化成了$n=4$时的后手,必然能拿到偶数块鹅卵石;此时后手任人宰割;

依次类推,可得下表.
因此先手有必胜策略,先拿$2$块.

 限定石块数为奇数,则当$n=4k+3$或$n=8k+1$时,先手必胜.必得的意思是不管对方怎么拿,我一定有办法得到这样的结果.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表评论