镜像策略

黑板写有$1,2,4,8,\cdots,2^{99}$这$100$个数,甲乙两人轮流对黑板上的数进行操作(甲先),每次将其中的$3$个数减$1$.如果某次操作后黑板上出现了负数,就算输,对方获胜.问:甲有获胜的策略吗?如何操作.


分析与解 甲有获胜的策略,只需要第一次操作$1,2^{98},2^{99}$,之后每次都操作乙刚操作的数即可,证明如下.

记这$100$个数分别为$x_i$($i=1,2,\cdots,100$),它们的初值分别为$1,2,4,8,\cdots,2^{99}$,和是$2^{100}-1$.由于\[1+2+\cdots+2^{97}<2^{98}<2^{99},\]因此无论如何操作,结束时$x_{99}$和$x_{100}$必然均非负数(否则对$x_1,x_2,\cdots,x_{98}$的操作次数大于$2^{98}$,而至多操作$2^{98}$次,在$x_1,x_2,\cdots,x_{98}$中就出现负数了).

这样甲操作完第一次之后,除了最后两个数,其他的各个数都是偶数,所以乙操作后甲必然可以执行相同的操作,并且在这样一次“镜像”操作后仍然处于“除了最后两个数,其他的各个数都是偶数”的状态.经过有限次“镜像”操作后,留给乙的必然为$x_i=0$($i=1,2,\cdots,98$)以及$x_{99},x_{100}$,此时乙失败,甲获胜.

 镜像策略的一个经典例子:一个正方形的桌子,甲乙轮流摆棋子(不允许重合),谁先放不下谁输.

此条目发表在解题展示分类目录。将固定链接加入收藏夹。

发表回复