常见思维题二
轮流拿石子
问题:一共有N颗石子(或者其他乱七八糟的东西),每次最多取M颗最少取1颗,A,B轮流取,谁最后会获胜?(假设他们每次都取最优解)。
答案:简单的巴什博奕:https://www.cnblogs.com/StrayWolf/p/5396427.html
问题:有若干堆石子,每堆石子的数量是有限的,二个人依次从这些石子堆中拿取任意的石子,至少一个(不能不取),最后一个拿光石子的人胜利。
答案:较复杂的尼姆博弈:https://blog.csdn.net/BBHHTT/article/details/80199541
蚂蚁走树枝
放N只蚂蚁在一条长度为M树枝上,蚂蚁与蚂蚁之间碰到就各自往反方向走,问总距离或者时间。
答案:这个其实就一个诀窍:蚂蚁相碰就往反方向走,可以直接看做没有发生任何事:大家都相当于独立的
A蚂蚁与B蚂蚁相碰后你可以看做没有发生这次碰撞,这样无论是求时间还是距离都很简单了。
海盗分金币
5个海盗抢到了100枚金币,每一颗都一样的大小和价值。
他们决定这么分:
抽签决定自己的号码(1,2,3,4,5)
首先,由1号提出分配方案,然后大家5人进行表决,当半数以上的人同意时( 不包括半数,这是重点),按照他的提案进行分配,否则将被扔入大海喂鲨鱼。
如果1号死后,再由2号提出分配方案,然后大家4人进行表决,当且仅当半超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。
依次类推……
假设每一位海盗都足够聪明,并且利益至上,能多分一枚金币绝不少分,那么1号海盗该怎么分金币才能使自己分到最多的金币呢?
答案
从后向前推,如果1至3号强盗都喂了鲨鱼,只剩4号和5号的话,5号一定投反对票让4号喂鲨鱼,以独吞全部金币。所以,4号惟有支持3号才能保命。
3号知道这一点,就会提出“100,0,0”的分配方案,对4号、5号一毛不拔而将全部金币归为已有,因为他知道4号一无所获但还是会投赞成票,再加上自己一票,他的方案即可通过。
不过,2号推知3号的方案,就会提出“98,0,1,1”的方案,即放弃3号,而给予4号和5号各一枚金币。由于该方案对于4号和5号来说比在3号分配时更为有利,他们将支持他而不希望他出局而由3号来分配。这样,2号将拿走98枚金币。
同样,2号的方案也会被1号所洞悉,1号并将提出(97,0,1,2,0)或(97,0,1,0,2)的方案,即放弃2号,而给3号一枚金币,同时给4号(或5号)2枚金币。由于1号的这一方案对于3号和4号(或5号)来说,相比2号分配时更优,他们将投1号的赞成票,再加上1号自己的票,1号的方案可获通过,97枚金币可轻松落入囊中。这无疑是1号能够获取最大收益的方案了!答案是:1号强盗分给3号1枚金币,分给4号或5号强盗2枚,自己独得97枚。分配方案可写成(97,0,1,2,0)或(97,0,1,0,2)。
此题还有变种: 就是只需要一半人同意即可,不需要一半人以上同意方案就可以通过,在其他条件不变的情况下,1号该怎么分配才能获得最多的金币?
答案:类似的推理过程
4号:4号提出的方案的时候肯定是最终方案,因为不管5号同意不同意都能通过,所以4号5号不必担心自己被投入大海。那此时5号获得的金币为0,4号获得的金币为100。
5号:因为4号提方案的时候 ,自己获取的金币为0 。所以只要4号之前的人分配给自己的金币大于0就同意该方案。
4号:如果3号提的方案一定能获得通过(原因:3号给5号的金币大于0, 5号就同意 因此就能通过),那自己获得的金币就为0,所以只要2号让自己获得的金币大于0就会同意。
3号:因为到了自己提方案的时候可以给5号一金币,自己的方案就能通过,但考虑到2号提方案的时候给4号一个金币,2号的方案就会通过,那自己获得的金币就为0。所以只要1号让自己获得的金币大于0就会同意。
2号:因为到了自己提方案的时候只要给4号一金币,就能获得通过,根本就不用顾及3 号 5号同意不同意,所以不管1号怎么提都不会同意。
1号:2号肯定不会同意。但只要给3号一块金币,5号一块金币(因为5号如果不同意,那么4号分配的时候,他什么都拿不到)就能获得通过。
所以答案是 98,0,1,0,1。
类似的问题也可用类似的推理,并不难
三个火枪手
彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好,十发八中;乙枪法次之,十发六中;丙枪法最差,十发四中。如果三人同时开枪,并且每人每轮只发一枪;那么枪战后,谁活下来的机会大一些?
答案
一般人认为甲的枪法好,活下来的可能性大一些。但合乎推理的结论是,枪法最糟糕的丙活下来的几率最大。
那么我们先来分析一下各个枪手的策略。
如同田忌赛马一般,枪手甲一定要对枪手乙先开枪。因为乙对甲的威胁要比丙对甲的威胁更大,甲应该首先干掉乙,这是甲的最佳策略。
同样的道理,枪手乙的最佳策略是第一枪瞄准甲。乙一旦将甲干掉,乙和丙进行对决,乙胜算的概率自然大很多。
枪手丙的最佳策略也是先对甲开枪。乙的枪法毕竟比甲差一些,丙先把甲干掉再与乙进行对决,丙的存活概率还是要高一些。
我们根据分析来计算一下三个枪手在上述情况下的存活几率:
第一轮:甲射乙,乙射甲,丙射甲。
- 甲的活率为24%(40% X 60%)
- 乙的活率为20%(100% - 80%)
- 丙的活率为100%(无人射丙)。
由于丙100%存活率,因此根据上轮甲乙存活的情况来计算三人第二轮的存活几率:
情况1:甲活乙死(24% X 80% = 19.2%)
甲射丙,丙射甲:甲的活率为60%,丙的活率为20%。
情况2:乙活甲死(20% X 76% = 15.2%)
乙射丙,丙射乙:乙的活率为60%,丙的活率为40%。
情况3:甲乙同活(24% X 20% = 4.8%)
重复第一轮。
情况4:甲乙同死(76% X 80% = 60.8%)
枪战结束。
据此来计算三人活率:
- 甲的活率为(19.2% X 60%) + (4.8% X 24%) = 12.672%
- 乙的活率为(15.2% X 60%) + (4.8% X 20%) = 10.08%
- 丙的活率为(19.2% X 20%) + (15.2% X 40%) + (4.8% X 100%) + (60.8% X 100%) = 75.52%
通过对两轮枪战的详细概率计算,我们发现枪法最差的丙存活的几率最大,枪法较好的甲和乙的存活几率却远低于丙的存活几率。
来自:https://www.zhihu.com/question/288093713/answer/482192781
囚犯拿豆子
有5个囚犯被***,他们请求上诉,于是法官愿意给他们一个机会。
犯人抽签分好顺序,按序每人从100粒豆子中随意抓取,最多可以全抓,最少可以不抓,可以和别人抓的一样多。
最终,抓的最多的和最少的要被处死。
- 他们都是非常聪明且自私的人。
- 他们的原则是先求保命。如果不能保命,就拉人陪葬。
- 100颗不必都分完。
- 若有重复的情况,则也算最大或最小,一并处死(中间重复不算)。
假设每个犯人都足够聪明,但每个犯人并不知道其他犯人足够聪明。那么,谁活下来的可能性最大?
答案
不存在“谁活下来的可能性比较大”的问题。实际情况是5个人都要死。答案看起来很扯淡,但推理分析后却发现十分符合逻辑。
根据题意,一号知道有五个人抓豆子,为保性命,他只要让豆子在20颗以内就可以了。但是他足够聪明的话他一定拿20颗,因为无论多拿一颗:2,3,4号的人一定会拿20颗最后死的人就会是最多的1号和最少的5号 还是少拿一颗:2,3,4号拿20个后,5号选择也拿20个拉上1234号垫背。(下面会说为什么多拿少拿也只会相差一颗)
2号是知道1号抓了几颗豆子(20)的。那么,对于2号来说,只有2种选择:与1号一样多,或者不一样多。我们就从这里入手。
情况一,假如2号选择与1号的豆子数不一样多,也就是说2号选择比1号多或者比1号少。
我们先要证明,如果2号选择比1号多或者比1号少,那么他一定会选择比1号只多1颗或者只少1颗。
要证明这个并不算太难。因为每个囚犯的第一选择是先求保命,要保命就要尽量使自己的豆子数既不是最多也不是最少。当2号决定选择比1号多的时候,他已经可以保证自己不是最少,为了尽量使自己不是最多,当然比1号多出来的数量越小越好。因为这个数量如果与一号相差大于1的话,那么3号就有机会抓到的居中数,相差越大,二号成为最多的可能性也就越大。反之,当2号决定选择比1号少的时候,也是同样的道理,他会选择只比1号少1颗。既然2号只会会选择比1号多1颗或者比1号少1颗,那么1、2号的豆子数一定是2个连续的自然数,和一定是2n+1(其中1个人是n,另1人是n+1)。
轮到3号的时候,他可以从剩下的豆子数知道1、2号的数量和,也就不难计算出n的值。而3号也只有2个选择:n颗或者n+1颗。为什么呢?这与上面的证明是一样的道理,保命原则,取最接近的数量,这里不再赘述。
不过,3号选择的时候会有一个特殊情况,在这一情况下,他一定会选择较小的n,而不是较大的n+1。这一特殊情况就是,当3号知道自己选择了n后(已保证自己不是最多),剩下的豆子数由于数量有限,4、5号中一定有人比n要少,这样自己一定可以活下来。计算的话就是 [100-(3n+1)]/2<=n ,不难算出,在这个特殊情况下,n>=20。也就是说,当1、2号选择了20或21颗的时候,3号只要选择20颗,就可以保证自己活下来。
这样一来剩下的豆子只剩39颗,4、5号至少有一人少于20颗的(这个人当然是后选的5号),这样死的将是5号和1、2号中选21颗的那个人。当然,1号、2号肯定不会有人选择21这一“倒霉”的数字(因为他们都是聪明人),这样的话,上述“特殊情况(即3号选择n)”就不会发生了。
综上所述,2345这四个人不难从剩下的豆子数知道前面几个人的数量总和,也就不难进而计算出n的值,而这样一来他们也只有n或者n+1这两种选择。最后的5号也是不难算出n的。在前4个人只选择了2个数字(n和n+1)的情况下,5号已是必死无疑,这时,根据“死也要拉几个垫背”的条件,5号会选择n或n+1,选择5个人一起完蛋。
情况二,如果2号选择了与1号不一样多的话,最终结果是5个人一起死,那么2号只有选择与1号一样多了。
那么1、2号的和就是2n,而3号如果选择n+1或者n -1的话,就又回到第一点的情况去了(前3个人的和是3m+1或3m+2),于是3号也只能选择n ,当然,4号还是只能选n,最后的结果仍旧是5个人一起完蛋。
“最后处死抓的最多和最少的囚犯”严格执行这句话的话,除非有人舍己为人,死二留三。但这是足够聪明且自私的囚犯,所以这五个聪明人的下场是全死,这道题只不过是找了一个处死所有人的借口罢了. . . . . .
变种问题:如果每个囚犯都知道其他囚犯足够聪明,事情会怎么发展?
答案:
这样的情况下囚犯一也会像我们一样推导出前面的结论,那么根据自私的规定,他会直接拿完100个,大家一起完蛋(反正结局已定)
学生猜生日
这种题目笔试中出现的次数比较多,用排除法比较好解决
小明和小强都是张老师的学生,张老师的生日是M月N日,
2人都知道张老师的生日是下列10组中的一天,张老师把M值告诉了小明,
把N值告诉了小强,张老师问他们知道他的生日是那一天吗?
3月4日 3月5日 3月8日
6月4日 6月7日
9月1日 9月5日
12月1日 12月2日 12月8日
小明说:如果我不知道的话,小强肯定也不知道.
小强说:本来我也不知道,但是现在我知道了.
小明说:哦,那我也知道了.
请根据以上对话推断出张老师的生日是哪一天?
答案
排除法:
1.小明肯定小强不知道是哪天,排除所有月份里有单独日的月份:6月和12月<因为如果小强的M是2或者7的话,小强就知道了,所以把6月7日与12月2日排除>,所以小明拿到的是3或者9
2.小强本来不知道,所以小强拿到的不是2或者7,但是小强现在知道了,说明把6月与12月排除后,小强拿到的是1,4,8中的一个<这里小强肯定没拿到5,否则他不会知道是哪天的>
3.小明现在也知道了,说明小明拿到的不是3,否则他不会知道是3月4日还是3月8日的,所以小明拿到的是9才能唯一确定生日
综上,答案是9月1日
小明和小强是赵老师的学生,张老师的生日是M月N日,张老师
把M值告诉小明,N值告诉小强
给他们六个选项
3月1日 3月3日 7月3日 7月5日
9月1日 11月7日
小明说:我猜不出来
小强说:本来我也猜不出来,但是现在我知道了
问:张老师生日多少
答案:3月1日
答案
排除法:
1.小明说猜不出来,说明小明拿到的不是单独出现的9或者11,说明老师生日只能是3月或者7月
2.小强原本不知道,说明小强拿到的不是单独出现的5或者7,说明老是生日是1日或3日
3.小强现在知道了,说明小强拿到的是1,因为如果拿到的是3,那么小强就不知道是3月3日还是7月3日了
综上,老师生日是3月1日
参考文章: