阿里巴巴笔试总结之博弈论 取物品 - Tristan's blog

阿里巴巴笔试总结之博弈论 取物品 - Tristan's blog

先来看一个更常见的取物品的题目：一堆n个物品，甲乙两人轮流取，每次取1至m个，最后取完者胜。
分析：
1.1-m个物品时，甲稳赢（当然要保证俩人都足够聪明，也就是说甲没傻到当有2个物品时，他却只取一个）
2.m+1个物品时，乙稳赢。此时无论甲取多少个(1-m)，剩下的、乙总能够一次性取完
3.m+2个时，甲稳赢。此时甲拿一个，而无论乙拿几个都会输。其实这时候当乙开始拿物品时，它相当于遇到了第二步中甲所面临的情况（也就是当前物品只剩m+1个，无论自己怎么取，对方都会赢）
4.m+3――2m+1个时，甲稳赢。此时甲只要取2――m个，就会让乙面临m+1这种必输的情况
5.2m+2个时，乙稳赢。此时无论甲取多少个（假设为x），2m+2-x都会落在m+2到2m+1这个区间，此时的乙就面临第四步的情况，所以乙稳操胜券。
6.数学归纳法。我们假设k(m+1)个时，乙稳赢，k(m+1)+1――k(m+1)+m时，甲稳赢，则(k+1)(m+1)时，甲取y个，此时乙面临的个数是(k+1)(m+1)-y==k*(m+1)+m+1-y，介于k(m+1)+1――k(m+1)+m之间，根据假设，也就是说此时乙稳赢。同理，可得当个数在(k+1)(m+1)+1――(k+1)(m+1)+m时，甲稳赢。
前序小结
那么肿么才能让甲稳赢呢？如果n%(m+1)==0，那甲你就别想了，你赢不了了；其他情况，恭喜你，甲赢了，甲的策略就是每次取完都给乙剩下k(m+1)个。上面没提n==0的情况，这个很显然也符合，忘掉了。。。
问题
俩聪明鬼A、B在数盒子里的星星，俩人每人一次只能拿23-28个星星，当某一次某人想拿的时候不够这个数了，就算输。
分析
此题目和上面的很类似，只不过区间变了。
1.0-22个时，A肯定输，因为去不了23――28这么多
2.23-27时，A稳赢，因为可以随便一手抓掉。
3.28-50时，A稳赢，此时A只要取28个，B就面临A在第一步时的处境了
4.51-73时，B稳赢，因为不管A抓多少个（当然，必须是在23――28之间），此时剩下的数肯定在23――50之间，也就是说B面临了A在二、三步的情况，所以B稳赢
5.74-101时，A稳赢，分两种情况：74-96时，A先抓23个，此时剩下51-73，B面临A在第四步的情形，所以A稳赢；97-101时，甲取28个，这样剩69――73个，仍是A赢
6.。。。和前序一样数学归纳法，可以证得51*k――51*k+22时，B稳赢，其它情况A稳赢。
总结规律：
根据上面两个例子，我们可以大胆假设，甲、乙取物品，每次只能取a――b之间的数量，一共sum个物品，则甲稳输的情况位于(a+b)*k到(a+b)*k+(a-1）之间
证明
第一步：当a==b时，显然，最简单了，只要求ans = sum/a，看a是否为偶数，偶数就会输，也就是sum/a%2为0时，甲就会输。公式也就变成了2a*k――2a*k+a-1之间，除以a，商为2*k，2*k%2==0，所以满足公式。
第二步:a==1,b==m时，这也就是前言中的情况，带入公式得到(1+m)*k――(1+m)*k+0，也就是前言中推导出来的(1+m)*k时，乙稳赢，所以满足公式。
第三步：假设i――j的时候满足，也就是说当物品个数位于(i+j)*k到(i+j)*k+(i-1)时，乙稳赢，其他情况，甲稳赢。
则当a==i,b==j+1时：
1.0――i-1时，乙稳赢。
2.i――j时，甲稳赢
3.j+1――i+j时，此时甲取j+1个，此时剩下0到i-1个物品，此时乙面临甲在第一步时的败局，所以甲稳赢。
4.同理，数学归纳法，可证。
当a==i+1，b==j时，同理，也可证。
总结论
甲、乙取物品，每次只能取a――b之间的数量，则甲稳输的情况时总物品的数量在(a+b)*k到(a+b)*k+(a-1）之间，其它数量的时候甲稳赢，所以，甲每次需要做的就是取适量的物品，使得乙面对的物品在(a+b)*k到(a+b)*k+(a-1）之间。

Read full article from 阿里巴巴笔试总结之博弈论 取物品 - Tristan's blog