【每日一道智力题】之轮流取石子(简单的尼姆博弈）

朱雀 2024-04-26 11:04 6阅读 0赞

### 题目： ###

> **一共有N颗石子（或者其他乱七八糟的东西），每次最多取M颗最少取1颗，A，B轮流取，谁最后会获胜？（假设他们每次都取最优解）。**

### 解答： ###

#### 结论： ####

假如A先取，N<M，A获胜；

N>M，若N能被（M + 1）整除时，A失败；

若N不能被（M + 1）整除时，A获胜；

假如B先取，（同上）；

#### 分析：（以A先手为例） ####

N<M时，A一次拿完（不可能给B留机会，前提就是每次取最优），不会给B留机会；

N>M时，A要想赢，必须要在自己倒数第二次取完的时候还剩下（M + 1）颗石子（此时A和B还可以再取一次就可以分出胜负游戏就结束了），这样不论B取几颗，A都获胜！但是要怎样才能控制最后一轮的石子数量？

##### 分两种情况分析， #####

1.  N不能被（M + 1）整除，A先拿走n颗石子就可以使得剩下的石子数量是（M + 1）的整数倍，那么下一次B拿走任意k颗石子时，A就拿走（M + 1）- k颗石子。这样不论B怎么拿A总能控制剩下的石子数量是（M + 1）的整数倍，那么最后一轮一定剩下（M + 1）颗石子；

1.  N能被（M + 1）整除，A就认输吧。。。**（B除非傻才会让A赢）**无论A怎么拿，B可以控制石子数量（即当B拿完后总能使剩下的石子数量是（M + 1）的整数倍)，在最后一轮之前B拿完后还剩（M + 1）颗，A拿多少颗都是输。

实际上，这就仅仅是运用了小学数学：**余数永远比除数小这个特点**

###### 分析完了之后，我们就拿长安大学ACM的一道题来练练手吧！ ######

#### 问题描述： ####

> 学校会每周来检查一次宿舍，一般情况大多宿舍都是轮流安排值日。但是在1205宿舍，Alex想玩点「新花样」，他对Bob说：咱们来玩一个游戏吧，输了那个人去值日。  
> 游戏规则是这样的：一开始有n个石子，Alex和Bob两个人轮流取石子，每次至少取一个至多取m个。取到最后一个石子的人获胜，也就是最后不能取的那个人输。  
> 假设两个人都非常聪明，每次做出的都是最优选择。最开始Alex先取，问哪个人最终能获胜。  
> 输入  
> 输入第一行为一个整数T，表示一共有T组数据。 接下来有T行，每行有两个整数n(1 ≤ n ≤ 109)和m(1 ≤ m ≤ 109)，中间用一个空格隔开。  
> 输出  
> 对于每组数据输出游戏最终获胜者的名字。  
> 样例输入  
>   
> 3 7 3 5 4   
> 样例输出  
> Alex Bob  
>   
>

下面我们就用c语言来实现这个代码：

#include<stdio.h>
    int main()
    {
        int T=0;
        int n,m;
        scanf("%d",&T);
        int i=0;
        for(i=0;i<T;i++)
        {
            scanf("%d %d",&n,&m);
            if(m>n||n%(m+1)!=0)
            {
                printf("Alex\n");
            }
            else
            {
            
                    printf("Bob\n");
            }
        }
     }

结果：

![30bb882392a5a84853c1b092082c3c5e.png][]

#### 总结： ####

今天我们通过一道题目，大概的了解了简单的尼姆博弈，但是这个博弈到底是什么，怎么使用，我将会在明天的每日一题中进行深入讲解！这就是今天的每日一道智力题，如果对大佬们有帮助的话，麻烦帮忙点赞＋关注哦😛！您的支持是我创造的动力！谢谢大佬们！😉

[30bb882392a5a84853c1b092082c3c5e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/89aef2191f7e432d8250942be1ec2a54.png