[数学故事]火柴游戏

  一个最普通的火柴游戏就是两人一起玩,先置若干支火柴於桌上,两人轮流取,每次所取的数目可先作一些限制,规定取走最后一根火柴者获胜。 

  规则一:若限制每次所取的火柴数目最少一根,最多三根,则如何玩才可致胜? 

  例如:桌面上有 n=15 根火柴,甲、乙两人轮流取,甲先取,则甲应如何取才能致胜? 

  为了要取得最后一根,甲必须最后留下零根火柴给乙,故在最后一步之前的轮取中,甲不能留下1根或2根或3根,否则乙就可以全部取走而获胜。如果留下4根,则乙不能全取,则不管乙取几根(1或2或3),甲必能取得所有剩下的火柴而赢了游戏。同理,若桌上留有8根火柴让乙去取,则无论乙如何取,甲都可使这一次轮取后留下4根火柴,最后也一定是甲获胜。由上之分析可知,甲只要使得桌面上的火柴数为 4、8、12、16... 等让乙去取,则甲必稳操胜券。因此若原先桌面上的火柴数为15,则甲应取3根。(∵15-3=12)若原先桌面上的火柴数为18呢?则甲应先取2根(∵18-2=16)。 

  规则二:限制每次所取的火柴数目为1至4根,则又如何致胜? 

  原则:若甲先取,则甲每次取时,须留5的倍数的火柴给乙去取。 

  通则:有n支火柴,每次可取1至k支,则甲每次取后所留的火柴数目必须为k+1之倍数。 

  规则三:限制每次所取的火柴数目不是连续的数,而是一些不连续的数,如1、3、7,则又该如何玩法? 

  分析:1、3、7均为奇数,由於目标为0,而0为偶数,所以先取者甲,须使桌上的火柴数为偶数,因为乙在偶数的火柴数中,不可能再取去1、3、7根火柴后获得0,但假使如此也不能保证甲必赢,因为甲对於火柴数的奇或偶,也是无法依照己意来控制的。因为〔偶-奇=奇,奇-奇=偶〕,所以每次取后,桌上的火柴数奇偶相反。若开始时是奇数,如17,甲先取,则不论甲取多少(1或3或7),剩下的便是偶数,乙随后又把偶数变成奇数,甲又把奇数回覆到偶数,最后甲是注定为赢家;反之,若开始时为偶数,则甲注定会输。 

  通则:开局是奇数,先取者必胜;反之,若开局为偶数,则先取者会输。 

  规则四:限制每次所取的火柴数是1或4(一个奇数,一个偶数)。 

  分析:如前规则二,若甲先取,则甲每次取时留5的倍数的火柴给乙去取,则甲必胜。此外,若甲留给乙取的火柴数为5之倍数加2时,甲也可赢得游戏,因为玩的时候可以控制每轮所取的火柴数为5(若乙取1,甲则取4;若乙取4,则甲取1),最后剩下2根,那时乙只能取1,甲便可取得最后一根而获胜。 

  通则:若甲先取,则甲每次取时所留火柴数为5之倍数或5的倍数加2。
时间: 06-19

[数学故事]火柴游戏的相关文章

【贪心】取火柴游戏

[贪心]取火柴游戏 题目描述 输入k及k个整数n1,n2,…,nk,表示有k堆火柴棒,第i堆火柴棒的根数为ni:接着便是你和计算机取火柴棒的对弈游戏.取的规则如下:每次可以从一堆中取走若干根火柴,也可以一堆全部取走,但不允许跨堆取,也不允许不取. 谁取走最后一根火柴为胜利者. 例如:k=2,n1=n2=2,A代表你,P代表计算机,若决定A先取: A:(2,2)→(1,2)    {从一堆中取一根} P:(1,2)→(1,1)    {从另一堆中取一根} A:(1,1)→(1,0) P:(1,0)

【博弈论】取火柴游戏

取火柴游戏 时间限制: 1 Sec  内存限制: 128 MB 题目描述 输入k及k个整数n1,n2,…,nk,表示有k堆火柴棒,第i堆火柴棒的根数为ni:接着便是你和计算机取火柴棒的对弈游戏.取的规则如下:每次可以从一堆中取走若干根火柴,也可以一堆全部取走,但不允许跨堆取,也不允许不取. 谁取走最后一根火柴为胜利者. 例如:k=2,n1=n2=2,A代表你,P代表计算机,若决定A先取: A:(2,2)→(1,2)    {从一堆中取一根} P:(1,2)→(1,1)    {从另一堆中取一根}

智力火柴游戏Android源码项目

该游戏源码是一个智力火柴游戏源码,游戏分为难.中.易三种模式,通过对火柴的移动来实现等式分成立,具有极好的市场价值和参考意义. 源码下载: http://code.662p.com/view/9741.html <ignore_js_op> 菜单界面 <ignore_js_op> 关卡界面   详细说明:http://android.662p.com/thread-6086-1-1.html

数学故事

发信人: ukim (我没有理想), 信区: Mathematics 标 题: Heroes in My Heart ( 序 ) 发信站: 北大未名站 (2002年04月06日14:23:24 星期六), 转信 --------------------------------- To Music For the Encouragement and Smiles She Gave Me --------------------------------- 序 废话几句. 多年以前,我有一个很宏伟的计

[数学故事]有趣的位置几何

有一种只研究图形各部分位置的相对次序,而不考虑他们尺寸大小的新几何学,叫做拓扑学.有时人们也称它是橡皮膜上的几何学.因为橡皮膜上的图形,随着橡皮膜的拉动,其长度.曲直.面积等等都将发生变化,但也有一些图形的性质保持不变.例如点变化后还是点,线变化后依旧是线:相交的图形决不因橡皮的拉伸和弯曲而变得不相交!拓扑学正是研究诸如此类,使图形在橡皮膜上保持不变的性质.在这种几何中,扭曲和拉长(但不包括撕开和接合)称为拓扑变换.图形在拓扑变换下保持不变的性质,称为图形的拓扑性质. 三角形和圆使两种截然不同的

P1247 取火柴游戏

题目描述 输入k及k个整数n1,n2,…,nk,表示有k堆火柴棒,第i堆火柴棒的根数为ni:接着便是你和计算机取火柴棒的对弈游戏.取的规则如下:每次可以从一堆中取走若干根火柴,也可以一堆全部取走,但不允许跨堆取,也不允许不取. 谁取走最后一根火柴为胜利者. 例如:k=2,n1=n2=2,A代表你,P代表计算机,若决定A先取: A:(2,2)→(1,2) {从一堆中取一根} P:(1,2)→(1,1) {从另一堆中取一根} A:(1,1)→(1,0) P:(1,0)→ (0,0) {P胜利} 如果

P1247 取火柴游戏 (奇异局势)

题目链接 题目描述 输入k及k个整数n1,n2,…,nk,表示有k堆火柴棒,第i堆火柴棒的根数为ni:接着便是你和计算机取火柴棒的对弈游戏.取的规则如下:每次可以从一堆中取走若干根火柴,也可以一堆全部取走,但不允许跨堆取,也不允许不取. 谁取走最后一根火柴为胜利者. 编一个程序,在给出初始状态之后,判断是先取必胜还是先取必败,如果是先取必胜,请输出第一次该如何取.如果是先取必败,则输出“lose”. 输入格式 第一行,一个正整数k 第二行,k个整数n1,n2,…,nk 输出格式 如果是先取必胜,

[数学故事]围剿兔子村

独眼狼王把瘸腿狐狸从象鼻子底下救了出来. 瘸腿狐狸抹着眼泪说:“要不是狼老弟来救我,我早就粉身碎骨了!” 独眼狼王拍着狐狸的肩膀说:“像狐狸老兄这样足智多谋的动物,世界上也不多见.今后咱俩合作,我有勇,你有谋,天 下无敌!哈哈.” 瘸腿狐狸说:“咱俩先弄点吃的,填饱肚子要紧.” “对!”独眼狼王说:“树林东头有一个兔子村,住有5家,共有15只兔子.” 瘸腿狐狸一听这么多兔子,眼睛一亮,问:“这么说每家都有3只兔子喽?” 独眼狼王摇摇头说:“不,不.每家的兔子数都不一样,至于每家有多少只兔子,我可

BZOJ2828 : 火柴游戏

设$f[i][j][k]$表示考虑了前$i$个数字,增加了$j$根火柴,删掉了$k$根火柴是否可能,用bitset加速DP. 然后设$g[i][j]$表示增加了$i$根火柴,删掉了$j$根火柴的最小代价,枚举移动次数进行更新. 决策满足单调性,故可以分治求解. 设$m=14n$,则时间复杂度为$O(\frac{nm^2}{64}+m^2\log m)$. #include<cstdio> #include<bitset> using namespace std; const int