数学归纳悖论

蓝眼睛问题

在一个岛上,有n个蓝眼睛的人,m个黄眼睛的人.一日一名游客前来游玩,聊天的时候说:你们中有人和我一样有蓝眼睛.知道自己有蓝眼睛的人会沮丧地紫砂.那么这个岛上的人多长时间后可以知道自己眼睛的颜色呢?

在有人做出回应前,所有人都只会沉思.随着大家又沉默了一个时刻,唯一可以得到的新信息就是大家又沉默了一个时刻.似乎无从下手,先从最简单的情况看看.

若n=1,则唯一的蓝眼睛拥有者会立刻知道自己拥有蓝眼睛,在$t=1$时刻直接紫砂

若n=2,两名蓝眼睛拥有者看到没人在第一时间紫砂,又能看到除自己外仅有以为蓝眼睛拥有者,于是可以肯定自己为蓝眼睛,在$t=2$时刻紫砂.

若n=3,对任意一名蓝眼睛的人来说,如果假设自己是黄眼睛,那么就能看到$t=2$时刻人群中剩下的两个蓝眼睛的人同时紫砂.而这个事件并没有发生,于是在$t=3$时刻推出自己也为蓝眼睛,三个人同时紫砂.

当n>3,可以按照这个假设的方法,对人们沉默的轮数进行递归计算.假设自己是黄眼睛,那么所看见的n-1个蓝眼睛的人应该在n-1时刻同时紫砂.根据观察的事实相反,可以推出所有的蓝眼睛人在第n个时刻一起知道自己眼睛的颜色.

沉默的是本题唯一的可更新信息,比起传统的信息,不如说是一个面对所有人的广播,公开自己的推理结果.在一开始,当不止一个蓝眼睛人时,虽然每个人都知道有蓝眼睛人,但并不知道其他人知不知道有没有蓝眼睛,也不知道其他人知不知道自己知不知道有没有蓝眼睛,很像三体里的猜疑链.而游客的话打破了这个无限的猜疑链,让所有人的信息都同时对对方公开,此后的沉默都不只是单纯的个人推理结果,而是彼此可以再次利用的条件.

某大佬将这两个称为“强共识”和“弱共识”.在游客发言之前,“岛上有蓝眼人”是一个弱共识,或者说沉默共识,但不是一个强共识,或者说公开共识.在游客发言之后,“岛上有蓝眼人”被提升成了一个强共识,或者说公开共识.强共识包含了比弱共识更多的信息,所以当然可以导致更多的后果.

三人猜数

https://www.luogu.com.cn/problem/P5779
题意:三个人头上各有一个正整数,每个人只能看到其他两人头上的数,并且有一人头上的数是另两人头上数的和,三人一言不发猜数,最后第n轮时有一个人知道了自己头上的数m.求所有可能的数字组合.还有一个~~似乎很好推出的~~结论:数最大者最先猜到.

乍一看毫无思绪.~~怎么看都不会做啊.~~三个人之间傻看着,除了沉默,没有产生任何新的信息.就算有这个结论,也只能把确定有m-1个组合,如何验证每个组合的可行性呢?

从最简单的情况入手,假如第一个人看到其他两个人的数相等,由于自己的数不可能是0,就可以推出自己的数为其余二人数的和.即

1
2
3

(2,1,1)->n=1,m=2;
(1,2,1)->n=2,m=2;
(1,1,2)->n=3,m=2;

对于更复杂的情况,由于每个人的数只可能是$a+b,|a-b|$.可以考虑像蓝眼睛问题一样,先假设自己的数是$|a-b|$,如果被证伪,那么自己的数肯定是$a+b$.然后就可以把问题转移到前一个猜数的人,如果在自己为$|a-b|$的条件下,前面的人无法得出结果,那么这个猜测就不可行.于是可以递归处理.

if(p==1){
    if(v2==v3) return 1;
    if(v2>v3) return dfs(v2-v3,v2,v3,2)+2;
    else return dfs(v3-v2,v2,v3,3)+1;
}
if(p==2){
    if(v1==v3) return 2;
    if(v1>v3) return dfs(v1,v1-v3,v3,1)+1;
    else return dfs(v1,v3-v1,v3,3)+2;
}
if(p==3){
    if(v1==v2) return 3;
    if(v2>v1) return dfs(v1,v2,v2-v1,2)+1;
    else return dfs(v1,v2,v1-v2,1)+2;
}

而唯一可以用于判断的量化标准就是沉默的轮数.对于一组数,仅当有人猜出来的轮数与给定的n轮相同,才能成为可行解.

For(i,1,m-1){
    if(p==1)if(dfs(m,i,m-i,1)==n)++T,ans[T].a=m,ans[T].b=i,ans[T].c=m-i;
    if(p==2)if(dfs(i,m,m-i,2)==n)++T,ans[T].a=i,ans[T].b=m,ans[T].c=m-i;
    if(p==3)if(dfs(i,m-i,m,3)==n)++T,ans[T].a=i,ans[T].b=m-i,ans[T].c=m;
}

~~信息真神奇啊~~