不知读者是否见过下面这个逻辑谜题?

一个家庭有 $n$ 个孩子。有一天这些孩子们出门玩,父亲叮嘱他们不要玩泥巴。但是这些孩子很淘气,还是去玩了泥巴,其中 $k$ ($1 \leq k \leq n$)个孩子弄脏了自己的脸。孩子们只能看到别人的脸,看不到自己的脸。回到家后,父亲对他们所有人同时说:「你们中至少有一个人的脸上有泥巴。」然后不断对他们所有人同时提问:「你们脸上有泥巴吗?」孩子们同时回答「有」「没有」或者「不知道」。假设这些孩子都非常聪明,他们的回答会是怎样的?

如果读者以前没见过这个问题,不妨现在先暂停 5 分钟思考一下。

答案是:在前 $k-1$ 次询问时,所有孩子都回答「不知道」。在第 $k$ 次询问时,所有 $k$ 个脸上有泥巴的孩子都将回答「有」,其他孩子仍回答「不知道」。第 $k+1$ 次询问时,脸上有泥的孩子回答「有」,其他孩子回答「没有」。

我们对 $k$ 使用归纳法证明如下:

  1. $k=1$ 时,那个脸上有泥巴的孩子可以看到所有其他孩子脸上都没有泥巴,根据父亲一开始说的话,他必定能推知自己脸上有泥巴,因此在第一次询问时他就将回答「知道」。
  2. $k>1$ 时,若只有 $l<k$ 个孩子脸上有泥巴,那么根据归纳假设,在第 $l$ 轮时所有脸上有泥巴的孩子已经被找出了,事实并非如此,从而每个孩子都知道脸上有泥巴的孩子数为 $k$,而任一脸上有泥巴的孩子只看到有 $k-1$ 个孩子脸上有泥,那么他将知道自己脸上也有泥。从而这些孩子将齐声回答「有」,其他孩子仍无法推断,故继续回答「不知道」。

好的,到目前为止,我们似乎已经解决了这个问题。但是仔细思考则不然:

  • 「这些孩子都很聪明」:这个假设也太强了!难道我的推理能力还不如这些孩子吗?或者换句话说,这个假设到底意味着什么?
  • 隐含了很多假设:孩子们都听懂并理解了父亲的宣言。如果一个孩子一个恍惚没听到别人的回答,或者眼神不好没看到别人脸上的泥,那我们的推理全部无效了!
  • 如果 $k>1$,那么父亲似乎只是宣称了一个大家都知道的事实(每个人都能看到至少一人脸上有泥),那这个宣言有什么用呢?如果父亲不在所有人面前宣称,而是私下给每个孩子说一遍,又会有什么区别?

除此之外,更重要的似乎是,我们能否推广这道题?我们似乎进入了一个全新的领域:我们在对知道与否这件事进行推理。硬用脑袋想似乎很麻烦(试试文末的思考题!),我们能否找出一个好的工具来解决这样的问题?

这些问题,我们下期分解~

思考题

有 S、P、C 三人玩游戏。C 从 1~10 之间任选两数字 $a,b$,把和告诉 S,把积告诉 P。

S:「我不知道 $a,b$。」

P:「我不知道 $a,b$。」

S:「我不知道 $a,b$。」

P:「我不知道 $a,b$。」

S:「我知道 $a,b$ 了。」

请你求出 $a,b$ 分别是哪两个数字(注意多解情况)。