博弈、策略类趣题(长期更新)

Oct 7, 2015

版权声明:本文为博主原创,未经作者许可谢绝转载。
如有任何疑问或者建议,请联系 xiangchen.cs@gmail.com

海盗分金

5 个海盗抢得 100 枚金币,他们按抽签的顺序依次提方案:首先由 1 号提出分配方案,然后 5 人表决,超过半数同意方案才被通过,否则他将被扔入大海喂鲨鱼,依此类推。求问 1 号的最佳策略

如果只剩 4 号 和 5 号,4 号的提案一定不会得到 5 号的支持。故而 3 号提出“100, 0, 0”的方案就可以获得 4 号的支持。故而 2 号提出“98, 0, 1, 1”的方案就可以获得 4 号和 5 号的支持。故而 1 号提出“97, 0, 1, 2, 0”就可以获得 3 号和 4 号的支持。

公共知识

公共知识是指,所有参与人知道,所有参与人知道所有参与人知道,所有参与人知道所有参与人知道所有参与人知道……的知识。

村庄里的大屠杀

一个村庄有一个风俗:当老婆知道自己的老公出轨时可以在夜里杀掉自己的老公。这个村庄一共有 100 对夫妻,每一个女人都知道村庄里的其他所有男人出轨,但是由于互相谈论时,都不会告诉这个出轨男人的老婆,所以每一个女人知道其他所有的男人出轨,唯独不知道自己的男人出轨。村庄里有一个老太婆,某天说了一句话:“这个村庄里至少有一个男人出轨。”之后会发生什么?

如果村庄里只有一个男人出轨,那么他的老婆因为知道其他所有男人多不出轨,可以推断出自己的老公出轨,第一晚就会杀死自己的老公。
如果村庄里有两个男人出轨,那么他们的老婆第一晚因为证据不足,不会杀死她们的老公。但是当第一晚没有发生任何事情时,可以推断出自己的老公出轨。因此第二晚会同时杀死自己的老公。
依此类推。前 99 个夜晚,什么都不会发生。第 100 晚,所有的女人都把自己的丈夫杀死了。

额头上的数字

教授有两个学生 A 和 B,他们诚实又聪明。教授选了一对连续的正整数分别贴在他们头上,A、B 可以看见对方的数字,但看不到自己头上的数字。教授问:现在你知道自己头上的数字是多少?就这样轮流不断的问,一段时间之后,一个学生回答“我知道了”。

两军问题

A、B 两只军队与 C 军队进行战争。A、B 只有同时进攻才能战胜 C,A、B 也仅在确认对方出兵时才会出兵。但是 A 与 B 商定进攻时间的通信过程不能保证百分之百送达。之后会发生什么?

A 通知 B 进行进攻,只有收到 B 的反馈才能确认 B 会进攻。B 只有收到 A 的第二轮反馈才能确认 A 收到了 B 的信息才会进攻。……这个过程永远无法停止,因此 A、B 永远无法确认对方会出兵。

5 囚徒与 100 绿豆

5 个囚犯,分别按 1-5 号,在装有 100 颗绿豆的麻袋里抓绿豆,规定每人至少抓一颗,而抓得最多和最少的人将被处死,而且,他们之间不能交流,但在抓的时候,可以摸出剩下的豆子数。问他们中谁的存活几率最大?100 颗不必都分完。若有重复的情况,则也算最大或最小,一并处死。囚犯的原则是先求保命,再去多杀人。