免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] Nim游戏

本帖最后由 hbghlyj 于 2019-8-8 19:01 编辑

某桃园有n(n∈N)棵桃树,每棵桃树所结桃子个数恰好构成n元自然数组
($a_1,a_2,....a_n$).桃园里有甲、乙两名采摘工人准备举行一场特别的采桃子比赛:假设每位采摘工均清楚每棵桃树上桃子的个数,采摘过程中,采摘工每次可任选-棵桃树并从该桃树上采下若干(至少采1个)桃子,规定采到最后一个桃子的人获胜.假设n=63且每棵桃树所结桃子个数构成数组(1,2,3,..63),每名采摘工每轮采一次.若按甲、乙顺序轮流采摘.证明: 采摘工人乙有必胜策略
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

TOP

本帖最后由 hbghlyj 于 2019-8-10 10:23 编辑

Nim游戏:有n堆石子,每堆石子的个数分别为$a_1,a_2…a_n$.甲乙两人进行取石子的游戏,甲先开始轮流操作,规定每人每次可以选定其中一堆石子,然后在此堆石子中取若干块石子,每次不能不取.能不取.取到最后一块石子者为胜,在什么情况下,甲有必胜策略?
解:将$a_1,a_2…a_n$都表示为二进制${a_i} = \overline {{b_{ik}}{b_{ik - 1}} \cdots {b_{i1}}{b_{i0}}} $,其中$b_{ij}=0,1$,为了位数统一,允许某些$b_{ik}=0.$令$c_j=a_{1j}+a_{2j}+…+a_{nj},0\leq{}j\leq{}k,$即$c_j$为这个数第j位数字之和.我们以下证明:当且仅当所有$c_j$不全为偶数时,甲有必胜策略.
证明:当$c_j$不全为偶数时,不妨设$c_{r_1},c_{r_2},…,c_{r_t}$是其中全部奇数且$r_1>r_2>…>r_t.$由于$c_{r_1}\geq{}1$,必有一个$a_s$使得$b_{{sr_1}}=1$,取$d=\overline{d_kd_{k-1}…d_1d_0}$,其中当$j\not=r_1,…,r_t$时,$d_j=d_{sj}$;当j=$r_1,…,r_t$时,$d_j=1-b_{sj}$
,由于$b_{{sr_1}}=1>0=d_{r_1}$,故$a_s$$>$d,所以甲可以从第s堆中取出$a_s$-d块石子.这样第s堆还剩下d块石子.由d的定义,取完以后$c_j$全变为偶数.
轮到乙取时,$c_j$全变为偶数,假设他在第t堆中取,无论他取多少,都会将$a_i$中的某个$b_{ij}=1$变为$b_{ij}$=0(如果所有的1都不变,则这堆石子没有减少,但是我们规定不能不取)这样相对应的$c_j$变为$c_j-1$,由偶数变成了奇数。
我们将所有$c_j,j=1,2,\cdots,k$都是偶数的状态称为理想状态。综上所述,如果开始不是理想状态,则甲总是可以通过一次操作将之变为理想状态。另一方面,当乙面对理想状态进行操作时,他必然会破坏理想状态。也就是说甲每次取完后肯定是理想状态,乙每次取完后都不是理想状态。而获胜时,所有的$b_{ij}$=0,当然所有的$c_j$=0,也就是说获胜的一方取完后应该是理想状态,加之石子总数不断减少,必然会有人获胜。因此这样进行下去,甲必然获胜。

TOP

看不到3楼图片

TOP

回复 4# realnumber 刚看到,已改成文字.
顺便测试了一下新下载的Word2Tex.总体效果不错,只是以下几处需要微调:
1.下标的下标。比如$b_{r_1}$会弄成$b_{r1}$
2.上划线。比如$\overline{hbghlyj}$会弄成$\bar{hbghlyj}$
如果看到其他转换错误,请立即告诉我

TOP

回复 1# hbghlyj
你的问题似乎我都不会。太深奥了。

TOP

返回列表 回复 发帖