题目引入
题目:除数博弈——LeetCode第132场周赛第一题
5024.除数博弈
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
示例 1：
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
提示：
1 <= N <= 1000
我的题解
class Solution {
public:
// void getCount(int N, vector<int> &resVec, int count) {
// if (N == 1) {
// resVec.push_back(count);
// } else {
// for (int i = N - 1; i > 0; i--) {
// if (N % i == 0) {
// count++;
// getCount(N - i, resVec, count);
// }
// }
// }
// }
bool divisorGame(int N) {
int m = 0;
if (N == 1) {
return false;
}
for (int i = N - 1; i > 0; i--) {
if (N % i == 0) {
m = i;
}
}
if (N % (m + 1) == 0) {
return true;
} else {
return false;
}
}
// vector<int> resVec;
// int count = 0;
// getCount(N, resVec, count);
// for (int i : resVec) {
// if (i % 2) {
// return true;
// } else {
// return false;
// }
// }
// return false;
// }
};
简单分析
- 这道题一开始我想的是递归，然后开始步步受挫，其实对题目一开始了解的也有问题
- 简单来说，什么叫两个人头脑清醒，就是必须有办法让爱丽丝必胜，而不是有一种能赢得就行
- 想通这一点后，赫然发现这不就是小学奥数题轮流取东西吗，可惜因为它把名字改了改没想到是那个题目
- 这在数学里涉及的就是著名的巴什博奕(Bash Game)，本博文将会推导一下公式的产生和嵌入这道题的思考
参考文章
数学时间
一个公式
- 假设有1堆含n个石子，两个人轮流从这堆物品中取物，规定每次至少取1个，最多取m个。取走最后石子的人获胜
- 此时n%(m+1)==0. 先取者必败，即最后石子是被后取的人取走的
推导过程
-
首先我们之所以能预测这个看起来大家都随便取石子的游戏谁能赢，因为虽然每个人拿的石子数不固定，但是两个人拿的石子数的和确实可控的，我们可以保证两个人的石子数之和一定是m + 1
-
A B 1 m 2 m - 1 3 m - 2 ... ... m 1 -
因此只要能被m + 1整除就会导致后手赢
-
这类题其实我觉得还是要见多识广吧，见过就会懂，不然这道题的前提就是大家都懂这个游戏套路，可总感觉怪怪的
在数学&博弈中的扩展
倒推思想
- 如果深究这个问题，本质上其实也是个倒推的过程。我们需要的是从最后结果——最后一个石头被取走为结果，一步步往上推，要求每一步都在必胜状态
一个经典的倒推问题（强盗分金）
- 强盗分金问题可以说是最经典的问题了，它特别就特别在它的答案会出乎每个第一次看到这道题的人
问题描述
曾经有这样一道问题十分流行：有五个强盗抢得100枚金币，他们决定：(1)抽签决定各人的号码(1，2，3，4，5)；(2)由1号提出分配方案，然后5人表决，如果方案超过半数同意就被通过，否则他将被扔进大海喂鲨鱼；(3)1号死后，依次类推，直到找到一个被同意的方案。假定每个强盗都是经济学假设的“理性人”，都能很理智地判断得失、作出选择，那么，1号要如何分配得到最大的利益？
答案
公认的标准答案是：(97，0，1，2，0)或(97，0，1，0，2)。
分析
这个答案可能会大大出乎人的意料，似乎1号承担着很大的风险，却能够获得如此大的利益？并不是这5个强盗在决策的过程中失去了理性，而是在博弈中存在策略依存性的决策问题，即某一博弈方的策略不仅取决于自己，还与其他博弈方的策略相关，不能只从个人的角度，而是要从其他博弈方的角度同时来考虑这个问题。
根据条件可以知道，这个博弈是一个完全信息和完美信息的动态博弈，每个强盗都可以得知之前其他强盗所做的决策，同时也可以推想出其他强盗所能采取的策略和相应的收益。在这个博弈中，博弈的特点之一：博弈次序起到了很关键的作用。可以用严格下策反复消去法来解决这个博弈问题：从5号开始，如果只剩4号和自己，无论如何他也可以获得100个金币。而对4号：只有支持3号或3号以前的人才能保证自己不被扔进海里。3号知道在这个决策点上4号的选择，就会提出(100，0，0)的分配方案，因为他知道4号为了保命会投赞成票。2号推知到3号的方案，就会提出(98，0，l，1)的方案，即放弃3号，而给予4号和5号各1枚金币。由于该方案对于4号和5号来说比在3号分配时更为有利，他们会投赞成票。2号可以拿走98枚金币。但是，l号同样可以推出2号的方案，l号并将提出(97，0，1，2，0)或(97，0，1，0，2)的方案，即放弃2号，而给3号1枚金币，同时给4号或5号2枚金币。由于l号的这一方案对于3号和4号(或5号)来说，相比2号分配时更优，他们将投l号的赞成票，再加上1号自己的票，1号的方案可获通过，这无疑是1号能够获取最大收益的策略了。但从一方面考虑，对1号最有利的情况导致了其他4人利益的损失，在分配上是不公平的，这就是因为个人利己的理性选择并不能保证人们的处境得到改善，虽然这里得到了一个均衡，但是却并非有效率的选择。
这与古诺寡头模型的拓展——斯塔克博格模型很相似，虽然号数在后的强盗可以知道号数在前的强盗的决策，看似拥有更多的信息，但是由于号数在前的强盗可以推出号数在后的强盗的策略，反而更能制定出有针对性的策略，使得号数在后的强盗别无选择，形成了“先手优势”。
当然，上面的推论还有部分不严谨的地方，对于4号来说，除了支持3号以外，还可以选择提出（0，100）的方案，因为完全理性的假定，既然可以得到所有钱，5号可以选择不杀死4号（5号没有杀死其他人的偏好）。正是由于这个原因，3号在采取策略的时候，就应该选择风险上策，要考虑到其他博弈方出现不确定的决策，选择一个并非最优但是风险较小的策略，例如（99，1，0），显然因为海盗们都是理智的，会考虑不应把希望寄托于4号的随机选择上，所以最终1号的决策只能是（97，0，1，0，2）。如果不考虑1号与2号的决策，仅仅从3号开始分配来考虑，4号就可能会因为这样的一个威胁而多获得一个金币的利益，对于3号来说，必须要考虑这个威胁带来的后果。动态博弈中存在威胁的“可信性”的问题，如果是基于完全理性的角度，3号应该相信这个威胁，但是如果5号有杀死4号的偏好，那么只要4号珍惜生命，他的威胁就是不可信的。举个例子，2号完全可以对3、4、5号假称基于l号所提出的任何分配方案，他一定会再多加上一个金币给他们，那么对于3、4、5而言，就需要考虑2号的信用，如果基于完全理性，显然2号所说的这个合作必然不会实现。联系现实生活，双方和多方的合作就需要有足够的保证使得参与者互相信任，才能使合作最终实现，这就需要法律和信用体系的完善和实现了。
而在现实生活中，还要考虑到有一类“非理性”的行为。按照1号的分配方式，3号和5号的确能获得比其他策略更多的利益，基于“理性人”假设，他们没有改变自己选择的动机，但是倘若他们认为1号独得了大部分的金币并对此表示不满，甚至愿意放弃自己的利益来对1号进行惩罚，那么结果又不同了。这类“非理性”行为正是依据人所推崇的“以直报怨”原则，事实上这种看似非理性的行为却更能促进福利，虽然它不能挽回损失，但是它能够给背叛方给予足够的惩戒，有效防止新的伤害。如果这个分金问题变为了重复博弈，而把扔下海换为其他惩罚措施，这种“非理性”的行为就有了意义，通过夺取他人利益来谋取自己更多利益的行为将受到约束，各博弈方选择的策略更有了新的变化，从短期看“非理性”的行为将转换为一种能够保障长期利益的策略。
综上，博弈是一种策略互动的过程，每个博弈方的策略存在相互依存的关系，在不同的情况下策略都在不断变化，根据先后顺序和博弈次数的不同，博弈的结果也会发生一定的改变，想要在博弈中得到理想的结果，必须要考虑得更为全面，要考虑到各博弈方所能采取的策略、收益、偏好、效用等，根据各博弈方和自己的实际信息随情况改变策略。
后记
- 拿石子问题是在小学奥数题上就见过了，之后这类题好想也算在智力题里面，有见过这样的面试题
- 强盗分金问题是我在《沙漠圣贤》里第一次见到，当时第一次看到就很着迷，自己推了很长时间，还是很有趣的。顺便一提，《沙漠圣贤》写的是真不错，可惜作者作死，非要搞民族问题。。。
网友评论