引入
故事一《黑暗森林》
公理:
- 生存是文明的第一需要。
- 文明不断增长和扩张,但宇宙中的物质总量保持不变。
推理过程:
不妨假设A先发现B。
由于公理1,两方为了保证自己的生存,必须先判断对方善意恶意,“善意文明并不能预先把别的文明也想成善意的”。
(1)若A选择与B交流,则由于上述的相互判断,猜疑链形成,同时A暴露己方存在。若AB实力相当,则猜疑链后B对A构成实际威胁;若B落后于A,则技术爆炸(可能由A的交流引发)可能使B在相对较短的时间内对A形成威胁。
(2)若A选择隐蔽,则B在技术爆炸后仍会发现A,猜疑链发生,A的存在暴露,转化为第一种情况。
由公理1和猜疑链性质,得出结论:若文明A发现文明B,A只能对B施以打击。
“总结起来,一、让你知道我的存在;二、让你存在下去,对我来说都是危险的,都违反第一条公理。”
这里运用了两种技巧,一是从不失本质的最小情况出发,二是在有限次猜疑时合理总结并代入验证。
故事二 《有一腿》
老板有两个秘书,都跟老板有一腿,但每个秘书都只知道自己这一腿。
显然,“至少有一个人和老板有一腿”这件事儿,两个秘书各自心知肚明,但她们却不清楚对方知不知道这个事儿。所以俩人虽然心怀鬼胎,但表面终归是相安无事。
突然有一天,老板酒后抽风,当着两个秘书的面说:“你们俩啊,至少有一个人跟我有一腿。”
现在,每个秘书都会得到一个全新的推理思路:“如果另外一个人跟老板是清白的,那她就一定知道我跟老板有一腿。”
不怕话多,就怕嘴贱。一句酒后戏言,改变了整个信息结构——“至少有一个人跟老板有一腿”这个事儿,以前只是秘书A、B分别知道;现在她们确信对方也知道了——「共有知识」变成了「共同知识」。
故事三《岛民自杀案件》
有一个与世隔离的小岛,上面住着一百个红眼岛民,他们信奉一个残忍的宗教。
这个宗教只有一条教规所有人不能知道自己眼睛的颜色,知道的就要去岛中心上吊自杀。当然,除了一位大祭司,他知道所有人(包括自己)的眼睛颜色,所以她自杀了,但是没死,于是就成大祭司了。
有一个探险家去了之后,大祭司告诉了他这个岛上的真相,探险家表示很OK,没有和岛民合影。
但是探险家家其实是个腹黑仔,他离开时就说了一句话:
我的天啊,你们中居然有人是红色的眼睛。
大祭司没文化,觉得没啥~探险家坐船回去了。
但是神奇的事情发生了,$1-99$天没人自杀,$100$天后,$100$个红眼岛民集体到岛中央的广场自杀。大祭司于是傻眼了。
假设岛上只有红蓝两色眼睛的人,那么次日蓝色眼睛的人也会集体自杀。
题目讲解
贪吃蛇
简单题,推理过程
聪明的学生
好题,首先我们得明白为什么他能猜到自己头上的数字,
从简单构造开始,2 1 1
此时第一个人(化名小A)肯定不是第二个(化名小B)和第三个(化名小C)的差,
因为所有人头上的数都是正整数,所以此时不可能是差而是和。
我们发现是小A最先猜出,那么是不是 总是头上贴着最大的那个数的人最先猜出自己头上的数呢?
由于在差为零时可以猜出,如果不是头上数字最大者,显然是有差为正数的情况。
那么对于三元组 $(x+y, x, y)$,$x+y$ 是如何猜到自己不是 $|x-y|$ 的呢?
假设自己的数字不是最大的(即为其他两人数字之差),而在这种情况下,数字最大的那个人在他理论上能够猜出的那一步却没有猜出来。
因为我们知道这三个人都非常聪明,所以在这种情况下就只有一种可能了:自己是其他两数之和。
这可以用递归解决,终止条件就是小A的数等于小B的数。
为了便于转移,设$f(x,y,t)$表示目前第$t$个人头上的数字最大(为表示方便,$A$对应$t=0$,$B$对应$t=1$,$C$对应$t=2$)其后一个人的数字是$x$,前一个人的数字是$y$时能猜出自己数字的步数。 可以知道,如果$x>y$,那么$f(x,y,t)=f(y,x-y,t 的下一位)+2$;
反之,则$f(x,y,t)=f(y-x,x,t的前一位)+1$。($+2$和$+1$的对应关系不要搞反啦,一个是转一圈回来,一个是直接顺着下一步就到啦)