求【取火柴】一类问题的解的算法例1:2. 取火柴游戏的规则如下:一堆火柴有N根,A、B两人轮流取出。每人每次可以取1 根

1个回答

  • 第一题比较简单,可以推广到有n根火柴每人可取1到m根

    若n % ( m + 1 ) == 1则先取必败,否则必胜,这个比较好证明

    很简单可以证明当火柴数为1时先取必败,然后火柴数为m + 1时,无论先取的人怎样取,假定取x个,那么第二个人取m - x个,即可只剩一个留给对方。这样一直下来,如果用D( x ) = 1表示当留有x个火柴时先取必败,那么

    D( 1 ) = 1

    D( m + 2 ) = 1

    D( 2m + 3 ) = 1

    ........

    在这道题的情况就是

    D( 1 ) = 1

    D( 4 ) = 1

    D( 7 ) = 1

    .........

    所以刚开始这些情况是必败的,换言之,如果刚开始不是这种情况,则先取的人可以取n % ( m + 1 ) - 1个(注意n % ( m + 1 ) == 0的情况,这是应该是取m个),就可以转化成上述令对手必败的情况。

    第二题比较麻烦

    我这里正好有一个别人写的

    只有一堆时,无论有多少,先取者都可以一次性全部取走,所以必胜。

    (1,1)时,显然先取者必败。

    (1,2)时,先取者必胜,他可以在2那一堆中取1个,于是变成(1,1),但这成为上一种情况了,于是接下来取的人必败,亦即先取者必胜。

    (1,3)时,先取者必胜。他可以在3那一堆中取2个,于是变成(1,1)。

    (2,2)时,先取者必败。他在任何一堆中取1个,对方随即在另一堆中取1个,即变成(1,1);如果他取走一堆中的全部石子,对方即取走另一堆中的全部石子。

    (2,3)时,先取者必胜。他可以在3那一堆中取1个,于是变成(2,2)。

    (3,3)时,先取者必败。他取走任一堆中的1,2或3个,就变成了以上讨论过的情形。

    (1,1,1)时,先取者必胜。他取走任一堆,就变成了(1,1)。

    (1,1,2)时,先取者必胜。他取走2那一堆,就变成了(1,1)。

    (1,1,3)时,先取者必胜。他取走3那一堆,就变成了(1,1)。

    (1,2,2)时,先取者必胜。他取走1那一堆,就变成了(2,2)。

    (1,2,3)时,先取者必败。分析如下:

    他先取1那一堆,则变为(2,3),由上面的分析,对手必胜。

    他从2那一堆中取1个,就变成了(1,1,3),对手可以将3那一堆全部取走,变成了(1,1),于是必胜。

    他将2那一堆全部取走,就变成了(1,3),对手必胜。

    他从3那一堆中取1个,就变成了(1,2,2),对手必胜。

    他从3那一堆中取2个,就变成了(1,2,1),对手必胜。

    他将3那一堆全部取走,就变成了(1,2),对手必胜。

    这些胜负有什么规律呢?我们可以将每堆的数转换成二进制,然后看每一位上所有堆里的1的个数总和:

    必胜情况:(n) (1,2)(1,3)(2,3) (1,1,1)(1,1,2)(1,2,2)

    必败情况: (1,1)(2,2)(3,3) (1,2,3)

    化为二进制:

    必胜情况:

    (n):……(反正每位只要有1肯定只有1个)

    (1,2):1,10

    列成竖式:

    01

    10

    个位上只有1个1,“十位”(因为是二进制所以叫十位不妥,这里为了方便说明暂且使用,下同)上也只有1个1。

    (1,3):1,11

    列成竖式:

    01

    11

    个位上有2个1(1的1个,3的1个),十位上有1个1。

    (2,3):10,11

    个位上有1个1,十位上有2个1。

    (1,1,1):1,1,1

    个位上有3个1。

    (1,1,2):1,1,10

    个位上有2个1,十位上有1个1。

    (1,1,3):1,1,11

    个位上有3个1,十位上有1个1。

    (1,2,2):1,10,10

    个位上有1个1,十位上有2个1。

    必败情况:

    (1,1):1,1

    个位上有2个1。

    (2,2):10,10

    十位上有2个1。

    (3,3):11,11

    个位上有2个1,十位上也有2个1。

    (1,2,3):1,10,11

    个位上有2个1,十位上也有2个1。

    下面分析一下这些情况。

    先看必败情形。容易发现,所有的必败情形,都是所有的数位上都有偶数个1。

    下看必胜情形。我们发现,出现了两种情况:

    1.只有1位上有奇数个1,如(1,3)(2,3)(1,1,1)(1,1,2)(1,2,2)。而先取者取走该位上的1,所有的位上就都变成了偶数个1,而这时后取者变成了先取者。

    2.有若干位上都是奇数个1,如(n)(1,2)(1,1,3)。先取者取(不一定取走哪位)后,所有的位上也都变成了偶数个1。后取者变成了先取者。

    以上两种情况,都是将后取者逼至必败情况从而取胜。

    由以上分析我们可以得到结论:将所有的堆的石子数化为二进制后,如果所有数位上的1的个数都是偶数,那么先取者必败;如果有些位上的1的个数是奇数,先取者能够将所有数位上的1的个数都变为偶数的话,那么先取者必胜。

    好,下面来分析我们的题目。

    3,5,7,19,50化为二进制是:

    000011

    000101

    000111

    010011

    110010

    可见,只有最高位的1是奇数个,其他位上都是偶数个。

    所以只需要将最高位的1取走即可必胜。

    二进制的100000就是10进制的32,所以要将50个石子的那堆取32个,取掉就变成偶数个数目。于是先取者必胜。以后无论对方怎么取,始终保证每一位上的1的个数是偶数即可(一种简单的方法是,他在一堆中取几个,你在另一堆中也取几个就可以)。