资源描述：
《取石子游戏的策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、取石子游戏的策略效实中学黄志琦有n堆石了，各堆石了数为％、七、…、a„,甲乙两人伦流取石了，规则如下：每次只能从不多于K堆的石了屮取，每堆中所取的石了数不多于m,取到全部石了的最后一枚者为胜。问谁冇必胜策略？这个问题的通解没有得到，但如K=1或者n~+8,都是容易处理的。先考虑m—+00且K=1的简单情形，即每次只从一堆中取，所取石子数不限，把ai、a2…，务写成二进制数ai=bnbi2bi3---bis二b21b22b23“・b2s构造矩阵.•••an=bnlbn2btl3---bnS（位数少于S位前面补上若干个0）这个nXs矩阵中每个
2、元素取0或1。bi厂bi2…bisb-zib22…匕1bn2…每取一次石子,b2sbns相当于矩阵某一行实施变换,变换规则是把某个“1”变成“0”，这个“1”左边的数字均不变动，右边的数字允许任意变动（即任意赋于0或1的值），这相当于把某个二进制数变小。谁把矩阵变成0矩阵，谁就赢了。当矩阵每列中都有偶数个“1”，就把这个矩阵称为“好矩阵”。我们来证明：当石子数构造出的矩阵是“好矩阵”时，后収者乙有必胜策略，否则先収者甲有必胜的策略。证：设一开始矩阵为“好矩阵”，那么，甲取了一次以后，必定使某行至少改变了一个数字，这个数字所在的一列“1”的
3、个数就不是偶数了，得到的矩阵就不是“好矩阵”，即好矩阵操作一次后必定变成不是好的矩阵，我们称之为“破坏”了好矩阵，现在轮到乙収，乙只要把甲“破坏”的矩阵重新“修复”为“好矩阵”就可以了。设任意某个不是“好矩阵”的矩阵厂bnbi2…bls=b21b22…b>s••••••••••••虹b“2…btls/因为它必有某一列有奇数个“1”，设使第j列有奇数个1的最小j为jo即bijo,b2jo,…，bnjo中有奇数个1,从中任取一个"1",不妨设bijo=l现在乙就对第一行实施变换，把变成0,対k>j,把沐变成.「1（若b2k?b3k，-,bnk
4、中冇奇数个“1”）bik=Y
5、1-0（若b2k,b3k,-,bnk中有偶数个“1”）这样乙就又把不好的矩阵修£成了“好短阵”o于是甲、乙两人轮流破坏，修复“好矩阵”，因为0矩阵是“好矩阵，所以最示一定是乙把矩阵变成0矩阵而获胜。设一开始的矩阵不是“好矩阵”，先収甲就有必胜策略，他只要把一开始的矩阵修复为“好矩阵”，然后乙破坏，甲修复，最终甲获胜。下而考虑K>1,m—+oo的情形，类似地：把石子数写成二进制数，构造出一个0,1矩阵。若“石子矩阵”中的每一列的和（即列和）为（K+1）的倍数，把这个矩阵称为“好矩阵”。现在规则是：允许对不多于K
6、行的数字进行前述的变换，把矩阵变成0矩阵的人就是赢家。结论同样是：若一开始的矩阵为“好矩阵”，则后取者乙必胜；若一开始的矩阵不是好矩阵，则先取者甲有必胜策略。由于每一次操作示，至多有K行被变换，那么每一列的“1”的个数至多增加或减少了K个，若要使操作一次后的矩阵仍是好矩阵（即每一列“1”的个数仍是K+1的倍数），那么每一列1的个数都不能改变。这说明，所有数的和经操作示不变。这实际上不可能，因为操作一次后石子总数一定会减少。所以，操作一次一定会破坏“好矩阵”。只要再证明，任意被破坏的好矩阵都一定能经一次操作后修复。设某个不是好矩阵的0、1矩
7、阵門血•・・几，祥j。是使第j列的和不是K+1的倍数的b21b22…b2s最小j,设笫j°列的元素和除以K+1的余数为ro,从笫jo列任収讥个“1”，不妨设blj0=b2j0=—=brojo=l,现对这to行实施变换,把bljO,b2JO,—,brOjo均变成0,对k>jo,lWiWr。把b“均变为1，再考虑第j°+l,j°+2,…，s列的和，设/是使列和不是K+1倍数的最小列数，设第ji列和除以K+1的余数为rb不妨设biji=b2ji=—=briji=l（若oWto,这更加显然的,若口>1*0,则对后面几彳亍进彳亍调换）,把biji,
8、b2ji,—bnj!均变成0,对K>ji,1WiWo,把血均变成1,再考虑第ji+l,ji+2,-,s列的列和,设第一个使列和不是K+1倍数的列数为J2,设第j2列和除以K+1的余数为1*2,不妨设blj2=b2J2=—br2j2=l（若I*2WI*1或i*2这是显然的,若r2>r）fir2>r0,则对■后儿行进行调换），把bij2,b2j2—br2j2都变成0,然后对k>j2,lWiWc把bik全部变成1,……这样以左向右地调整每一列的列和，使矩阵成为好矩阵0,且变换的行数至多有K行，所以一次操作总能将非好矩阵修复为好矩阵，从而前面所述
9、的必胜策略仍行得通。最后是m为任意正整数，k二1的情形设各堆石子数ai,a2,…，an除以m+1的余数依次为rbr2,…，“・有以下的判定法则:若石了数为（门，r2,-Tn）,K=1令m——+
