猜帽问题

¿

Posted by ShanLunjiaJian's Blog on December 13, 2021

太阳爆了英才,然后被小学奥数题干爆了。拉了。

一类经典问题,从 不知道 进行推理。

从一个笑话开始。三个绝顶聪明的人走进酒吧,招待问,都来一杯啤酒?

第一个人说,我不知道。

第二个人说,我也不知道。

第三个人说,是的。

这个笑话的意思大概是,第一个人说不知道,说明她肯定想要啤酒,不然她就会说不是都要啤酒了。第二个人也是一样的,所以第三个人知道大家都要啤酒。

于是我们知道,不知道 这样的回答也是有信息量的,它表示可能的情况不止一种。


最经典的版本是,有三个绝顶聪明的人A,B,C和五顶帽子,其中三顶是红的而两顶是蓝的。每个人戴了一顶帽子,每个人只能看到别人的帽子,不能看到自己的,目标是猜出自己的帽子是什么颜色。

现在三个人依次发表看法。

A说,我不知道我的帽子是什么颜色。

B说,我也不知道。

C说,我知道了。问C的帽子分别是什么颜色?

不知道 表示可能的情况不止一种,也就是说当时的情况不是唯一确定的情况。

强行讨论一下。最简单直接的做法是,考虑所有可能的情况。它们是 红红红,红红蓝,红蓝红,蓝红红,蓝蓝红,蓝红蓝,红蓝蓝,一共七种。

A不知道,说明

  • 如果她看到 ~红红,那么有 红红红 和 蓝红红 两种情况,所以啥事没有。

  • 如果她看到 ~红蓝,那么有 红红蓝 和 蓝红蓝 两种情况,所以啥事没有。蓝红是一样的。

  • 如果她看到 ~蓝蓝,那么只有 红蓝蓝 一种情况,所以她不可能看到 蓝蓝。

还剩下六种情况,也就是 红红红,红红蓝,红蓝红,蓝红红,蓝蓝红,蓝红蓝。

B不知道,说明

  • 如果她看到 红~红,那么有 红红红 和 红蓝红 两种情况,所以啥事没有。

  • 如果她看到 红~蓝,那么只有 红红蓝 一种情况,所以她不可能看到 红蓝。

  • 如果她看到 蓝~蓝,那么只有 蓝红蓝 一种情况,所以她不可能看到 蓝蓝。

还剩下四种情况,也就是 红红红,红蓝红,蓝红红,蓝蓝红。于是C的帽子必然是红色。

这只适用于可能的情况很少的时候,或者如果可以用计算工具,可能可以支持更大的情况数。


来看一个别的问题。

小学奥数题

有三个人A,B,C,每个人头上贴了一个正整数(也就是说不能是\(0\))。现在大家都知道有两个人头上的数字和等于第三个人头上的。

A说,我不知道我的数字是什么。

B说,我也不知道。

C说,我也不知道。

A说,我还是不知道。

B说,我也不知道。

C说,我知道了,我的是\(144\)。问另外两个人头上分别是什么?

这个问题情况数很多,不得不用计算机来做了。有没有什么手动方法?

有是有的,但是非常惊悚。我们先来介绍一下方法。

每个人只需要考虑自己的数是另两个人的和还是差。

如果最后是某个人X猜出来了,那么我们考虑所有前面有人猜出来的情况,它们都不是真实情况。

而X能猜出来,说明X头上的数是和或者是差的情况已经确定不可能了,而这个不可能是因为前面的人没有猜出来,导致一些情况不可能了。所以我们可以从前面推得当前这个人。

注意到人与人信息是不对等的,但是随着游戏的进行,每个人掌握的信息量都在增加。于是我们可以只考虑前面两个人,而不需要考虑前面所有人。

考虑使用三个数的比来表示一个情况。

第一轮,A猜出来的情况只可能是\(b=c\)这样的,因为此时\(b-c=0\),而我们要求是正整数。这是\(2:1:1\)。

A没猜出来而B猜出来了。显然首先可以是\(1:2:1\)。

不是\(2:1:1\) 这件事说明如果B看到\(2:?:1\)的话,她不能是差,那么我们知道B必然是和,也就是\(2:3:1\)。

AB都没猜出来而C猜出来了。显然首先可以是\(1:1:2\)。

不是\(2:1:1\) 这件事说明如果C看到\(2:1:?\)的话,她不能是差,那么我们知道C必然是和,也就是\(2:1:3\)。

不是\(1:2:1\) 这件事说明如果C看到\(1:2:?\)的话,她不能是差,那么我们知道C必然是和,也就是\(1:2:3\)。

不是\(2:3:1\) 这件事说明如果C看到\(2:3:?\)的话,她不能是差,那么我们知道C必然是和,也就是\(2:3:5\)。

你可以发现什么规律?

我们用\(a:b:c\rightarrow d:e:f\)表示上面的推理过程。

第二轮。

A :

\[\begin{aligned} 1:2:1 &\rightarrow 3:2:1\\ 2:3:1 &\rightarrow 4:3:1\\ 1:1:2 &\rightarrow 3:1:2\\ 2:1:3 &\rightarrow 4:1:3\\ 1:2:3 &\rightarrow 5:2:3\\ 2:3:5 &\rightarrow 8:3:5\\ \end{aligned}\]

为什么没有\(2:1:1\)了?因为那个在第一轮就会被猜出来。实际上这相当于是有一个第零轮,它的存在就是用来表示题目给出的不合法的情况。

B :

\[\begin{aligned} 1:1:2 &\rightarrow 1:3:2\\ 2:1:3 &\rightarrow 2:5:3\\ 1:2:3 &\rightarrow 1:4:3\\ 2:3:5 &\rightarrow 2:7:5\\ 3:2:1 &\rightarrow 3:4:1\\ 4:3:1 &\rightarrow 4:5:1\\ 3:1:2 &\rightarrow 3:5:2\\ 4:1:3 &\rightarrow 4:7:3\\ 5:2:3 &\rightarrow 5:8:3\\ 8:3:5 &\rightarrow 8:13:5\\ \end{aligned}\]

C :

\[\begin{aligned} 3:2:1 &\rightarrow 3:2:5\\ 4:3:1 &\rightarrow 4:3:7\\ 3:1:2 &\rightarrow 3:1:4\\ 4:1:3 &\rightarrow 4:1:5\\ 5:2:3 &\rightarrow 5:2:7\\ 8:3:5 &\rightarrow 8:3:11\\ 1:3:2 &\rightarrow 1:3:4\\ 2:5:3 &\rightarrow 2:5:7\\ 1:4:3 &\rightarrow 1:4:5\\ 2:7:5 &\rightarrow 2:7:9\\ 3:4:1 &\rightarrow 3:4:7\\ 4:5:1 &\rightarrow 4:5:9\\ 3:5:2 &\rightarrow 3:5:8\\ 4:7:3 &\rightarrow 4:7:11\\ 5:8:3 &\rightarrow 5:8:13\\ 8:13:5 &\rightarrow 8:13:21\\ \end{aligned}\]

一共有这么多解,也就是说形成这样比例的初始情况就会在对应的轮被对应的人猜中。

不过这里限制了第三个数是\(144=2^4\times 3^2\),所以只有\(3:1:4,1:3:4,2:7:9,4:5:9,3:5:8\)五个情况是有可能的。它们分别对应\((36,108,144),(108,36,144),(32,112,144),(64,80,144),(54,90,144)\)。


你可能发现了一些有趣的结论。比如归纳可以发现,最先猜出来的一定是那个和,并且这个方案数满足斐波那契数列的递推式,但是它的边界不太一样。

下面我们讨论若干引申问题。

给一个情况,它是否可以被猜出来?如果可以,如何判断它在第几轮被猜出来?

这需要我们反着搞回去。首先给三个数约掉\(\gcd\)。

考虑一定是那个和猜出来的,不妨认为她是C。她能猜出来,是刚才AB没猜出来给了她足够的信息,设三个数分别是\(a,b,a+b\),那么AB猜不出来告诉C,不可能是\(a,b,\vert a-b\vert\),也就是说这两个人里面有一个可以把这个东西猜出来。显然这个人应该是\(a,b\)中更大的,因为和会先猜出来。

我们可以用这个算出猜了多少次,于是就知道猜了多少轮了。具体一点,我们写一个\(f(a,b,a+b)\),分别表示ABC三个人。

  • 如果\(a=b=1\),返回\(1\)。

  • 如果\(a>b\),返回\(2+f(b,a-b,a)\)

  • 如果\(a<b\),返回\(1+f(b-a,a,b)\)

看起来很像辗转相除,这个是不是也能做到1\(\log\)?

我们把那个和的位置扔掉。你发现完全一致(

于是我们也知道,任何情况都可以被猜出来。

下一个问题。如果是别的限制,甚至同时有别的人数,会发生什么?比如我们知道两个数之和是另一个数的二倍?

不知道。可能方法是普适的吧。