用数学思考01-国王与毒酒(2)

上回说到“国王与毒酒”问题的变种版本,机智如你肯定已经搜索了一番知晓了答案,或者更知晓了这篇要讲什么。毕竟,tag 已经说明了一切嘛。

1. 500桶的解

所给出的2人解答里是这么说的:

将500桶酒分作23行23列,囚犯A每隔一小时喝一行,囚犯B每隔一小时喝一列。最后分别根据A、B死亡的时间点即可反查出毒酒所在的行和列,行列交叉处就是毒酒所在。

2. 50桶和500桶的区别

补充回忆,再次分别贴一遍500桶版本的问题:

50桶酒,其中有1桶有毒,人喝下去1小时后见效。而国王可以随意命令士兵/死囚去试毒,求最少多少人且最快多久分辨出有毒的酒

500桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

仔细观察,不难发现其区别有:

  1. 酒桶从50增加到了500
  2. 毒酒见效时间从1小时增加到了23-24小时
  3. 可接受时间从1倍见效时间增加到了2倍见效时间
  4. 只问了最少要多少囚犯,并未附加“同时最快”的约束条件

让我们来分析下:

首先,第4条非常关键,否则这只是50桶版本问题的简单推广而已。答题一定要看清题对不对?

然后,结合第3条似乎一下子多了非常多了可选策略,比如后面会详细说明的“作妖策略”。

最后,也是最有趣的第2条。粗看似乎只是告诉你生效时间变长了,但仔细一看,它既明确告诉了你“在48小时内一个囚犯保证可以尝试很多次”,又隐藏了“每次尝试最小间隔1小时”这个约束。

答案里说每1小时喝一次,其原因也是因为毒酒的见效时间是个23~24小时之间的未知值,如果间隔时间小于1小时将无法区分两次验毒行为

这个非常容易想明白,让我举个例子好了:

想象一下,你打开手电正对着一堵墙照过去,出现直径1米的圆形光斑,从光斑到你的手电是一个直径1米高度未知的圆锥,顶点是你。

那么在旁边再紧挨着摆下一个同样的圆锥,使得两个光斑外切。
两个圆锥顶点之间的距离不就刚好是半径乘以2么?

如果出现光斑重叠,那就无法分辨“这一块到底是谁的手电照亮的”,在题目里也就是无法分清“这次死亡到底是喝哪一行/列造成的”。

题目里的23~24小时,前后相差1小时,即 $\Delta t = 1h$ ,就等效于上面例子里的这种1米大光斑。

那么这个时候我就可以发散一下了,假设使用的是光斑大小近乎为零的激光手电呢?那么发射这边是不是可以互相之间站得无限接近?会有什么神奇效果?

3. 疯狂的试酒者

简化思考,以50桶版本为例来进行思考实验,我们只需要一个试酒者就能搞定问题:

  1. 令毒酒非常精确地在1小时后生效,计时手段也非常精确;
  2. 令试酒者有超人般的能力,能无限快地喝酒;
  3. 令其他我还没想到的干扰都不复存在;

设酒桶编号是从0开始到49结束。

令试酒者按酒桶编号每隔 $\Delta t$ 时间就喝一次酒,从 $0$ 时刻点开始喝,喝满50次。其实按前面的经验解,49次就行了

那么当 $ 1h + \Delta t \times n $ 时刻试酒者死亡,即可判断编号为 $n$ 的酒有毒。

这种策略仅需要1人,消耗的时间是 $\ T_{cost} \in [1h, 1h + 49 \Delta t] $

当 $\Delta t$ 足够小,无限趋近于0,我们甚至可以宣称只要1人1小时就解决了问题!

那么,是不是我们其他的求解策略都可以用类似的“作妖”来替换呢?

当然可以!

等等,再想想,这些是不是说明有什么通用的规律呢?

答案是:

问题的统一

在此之前,回过头去看下前面所有的策略、解答。

1. 50桶几队几人

在50桶版本的所有解答里,都一再表达了一个概念:“几个队、各个队伍几个人”,比如“某队有几种非0的取值情况,所以需要几人”。

  1. 1个队,需要有 $[1, 49]$ 这49种非0取值,所以要49人
  2. 2个队,X队有 $[1, 6]$ 6种非0取值、Y队有 $ [1, 7] $ 7种非0取值,所以要 $ 6 + 7 = 13 $ 人
  3. 3个人,X、Y、Z三队均有 $[1, 3]$ 3种非0取值,所以要 $3 + 3 + 3 = 9$ 人

等等

其实这都是可以给出通用解释的,因为这件事情的本质在于:

  1. 我们用了几队人,就相当于把“50中可能中的哪一种”这1件$ \frac{1}{50} $ 概率的事情给拆分成了几件
  2. 这几个队各自去确定“事实是x种可能中的哪一种”
  3. 向我们表达每个分拆事件的结果,汇总后得出原$ \frac{1}{50} $ 概率事件的结果

以前面的两队13人求解策略为例来讲解,再贴一下之前的表格,把0号也补上:

相应的结果判定方法:

  1. 全员存活,编号1的酒有毒
  2. 13人中仅有1人死亡,则相应的那桶酒有毒。例如仅X6死亡意味着编号49的酒有毒
  3. 13人中有2人死亡,则这两人同时喝到的酒有毒。例如X6和Y1死亡代表编号50的酒有毒

在这套策略中:

  1. 我们将“50桶酒那一桶有毒”这件 $ \frac{1}{50} $ 概率的事情拆分给了X、Y两个队伍
  2. X队需要给出“7组混合酒里哪一组有毒”这件 $ \frac{1}{7}$ 概率事件的确定答案
  3. Y队需要给出“8组混合酒里哪一组有毒”这件 $ \frac{1}{8}$ 概率事件的确定答案

当我们去查看结果的时候,只能从“发现某队的尸体”上得出“该队有喝到毒酒”这种信息,但无法确定死者死于哪一组混合酒。相当于之前我们分派给X、Y队的测试任务,未能给出足够的信息,无法得出最终的结果。

对X的7种混合酒、Y队的8种混合酒,我们使用的办法是:

  1. X队派6人,能反映 [“无人死亡”, “1号死亡”, … “6号死亡]这7种可能的事件结果

  2. Y队派7人,能反映 [“无人死亡”, “1号死亡”, … “7号死亡]这8种可能的事件结果

上篇的策略里我们选定的是每队取0值的不用派人,是因为只要该队其他人没死,就等同于取0值所代表的事件发生了。

以X队为例,因为确定只有一瓶毒酒,所以对X队来说7组混合酒必然有一组有毒,即$\frac{1}{7}$ 概率,派6人即可试出。也就是 $ 1 = \frac{1}{7} \times \boxed{6} + \frac{1}{7}$

这样:

  1. X队就能给出$ \frac{1}{7}$ 概率事件的确定答案;

  2. Y队就能给出$ \frac{1}{8}$ 概率事件的确定答案;

  3. 合起来给出$ \frac{1}{50}$ 概率事件的确定答案;

2. 500桶的2人和“超人”试酒者

在500桶版本里,虽然只需要2人,但由于时间更加宽裕,每人所能给出的可能性更高——可以通过“死在哪一刻”来表达多种可能性:

囚犯A、B均每隔1小时喝一行/列,共23行23列,意味着他们的死亡时间都是 $ \frac{1}{23}$ 概率的事件;

合起来给出$ \frac{1}{500}$ 概率事件的确定答案;

每小时喝1次,喝23次,跟一队的23人每人喝一行/列,其实是等价的,都是给出了 $ \frac{1}{23}$ 概率事件确定答案

在我们对50桶酒的作妖解法里,只需要1个人,也就是1个队。但它也提供了50种可能性。我们以喝满50次为例:

1个队1个人,可以死在[ $1h$, $1h + \Delta t$, $1h + 2 \Delta t$, … ,$1h + 49 \Delta t$] 这50种可能的时刻点

它依然成功地给出$ \frac{1}{50}$ 概率事件的确定答案,跟派50人跟酒桶一一对应一齐喝,是等价的。500桶的2人、作妖解法的“超人”试酒者,无非是在时空维度上展开,来表述 概率事件确定答案

总结一下就是:

  1. $ \frac{1}{P_0} $ 概率的事件拆分成 $n$ 件概率事件,它们的概率分别是 $ \frac{1}{P_1}, \frac{1}{P_2}, \frac{1}{P_3}, … \frac{1}{P_n} $

  2. 用某种求和的方法汇总这 $n$ 件概率事件,表示这 $n$ 件概率事件各自处在某一系列特定结果时,等价(确定)原来的$ \frac{1}{P_0} $ 概率的事件处在某一特定结果

现在的问题就是,这种求和方法是什么?

前面朴素解法:

在二维平面里的 $ a \times b \ge 50$

三维空间里的$ a \times b \times c \ge 50$

等等

其实前后已经对应上了,完全可以可以归纳出 $ P_1 \times P_2 \times … P_n \ge P_0$ 就是我们所求的“求和方法”。

很好,从问题到数学,从数学回到问题,都能圆上了,两个乃至更多版本的“国王毒酒”问题也都统一了。但这就是我们想要的通法通则了吗?我们找到的明明就是个乘法!

另一方面也应该明显感觉到了,可能性越多,发生的概率也就越低的事件,确定其发生,要做的测试越复杂。如果有一种理论能解释、度量、计算这种特性,那它才是我们想要的通法通则。

其实到这一步,已经离主题一步之遥了

前面讲过我曾向“羊宝宝”大佬提过50桶版本的题,大佬沉思片刻就给出答案6,再问理由,回答的是:

毒酒以 $ \frac{1}{50} $ 的概率出现,信息量是 $log_2\,50$,即6比特,所以要6人

我当即恍然大悟,这也就是上一篇提过的事情。我回问道,你们还开了《信息论》这门课不成?大佬答“自己随便看的”。

总是从学校出来后才觉得书本里的知识好用

是的,国王与毒酒的问题用信息论来解释是普适的。本篇最终就是要讲这个。

某乎上500桶版本的众多回答里有一条就提到过,应该是同道中人。不过并没有更进一步的描述,旁的人看来应该也不太明白吧

3. 信息的度量

信息论是什么?简单讲它是一门研究对信息进行量化、传输、存储的理论。这里我们需要它“对不确定性进行度量”的能力。

信息论是我大学学过的一门课,隐约只记得香农、Huffman编码、信息熵

更具体的可以自行搜索了。一般日常所见,直接感触到它的应该是压缩文件了。有的文件可以压缩得很小,而有的压缩前后几乎差别不大,信息论已经指明了这里面的原因。

比如两张同样分辨率的图片,一张是全部黑色像素点,一张是美食。分别zip压缩两张图片,得到的压缩包的体积相差极大

信息熵,用简单的话来解释,信息的可能性越多,预测该信息的值所涉及到不确定度的量 也就越大。这个量度就叫“信息熵”。

当年给这个量度取名 信息熵 除了唬人,也是有道理的。越随机也越无序,热力学的熵和信息论的熵在这点上相通了。

找不到课本,拉出维基。当取自有限样本时,信息熵的公式:

其中 $P(x_i)$ 是 $x_i$ 事件发生的概率,$I(x_i)$ 是 $x_i$ 事件的自信息(self-information),其计算方法是:

在这里 $b$ 是对数计算的底数,一般用$2, e, 10$

  1. $b=2$时,信息熵的单位是bit
  2. $b=e$时,信息熵的单位是nat
  3. $b=10$时,信息熵的单位是Hart

这里有两个概念,信息熵自信息:

  1. 度量“概率空间中单一事件或者离散随机变量的值”相关信息量的量度,叫做自信息:$ I(x_i) = -log_b{P(x_i)}$。它有单位,单位跟计算底数相关。
  2. 自信息的期望值,就是信息熵。

期望值的计算应该不必讲述了吧

这两个量,分别是对整体情况和特定情况的度量。一系列事件中,发生概率越低的情况发生了,这情况本身的自信息也就越大

信息被从信息源传递到接收者,当且仅当接收者无法预知内容,信息才得以传递,否则信息量为0。换而言之,100%确定的事情发生了,其自信息是0。

学以致用

了解了两个概念及其算式,现在开始用起来

1. 再试题目

以我们50桶酒的题目为例:

  1. $ \frac{49}{50} $ 的概率是无毒酒,其自信息是 $ -log_2{\frac{49}{50}} $ bit
  2. $ \frac{1}{50} $ 的概率是有毒酒,其自信息是 $ -log_2{\frac{1}{50}} $ bit

计算期望,就得到了信息熵。但我们解题需要的是“找到毒酒”,也就是预测 $ \frac{1}{50} $ 概率的事件。

只有当我们通过测试、观测所能获取的信息量大于等于某个阈值时,“确定毒酒是第几号”这件事情才能被我们确认,相当于我们收到了“毒酒是第X号”这条消息。否则就是信息不足,无法判定。

而这个阈值就是$ \frac{1}{50} $ 概率事件的自信息 $ -log_2{\frac{1}{50}} \approx 5.64386$ bit

  1. 观测一个人“是死是活”,生死几率各半。通过其结果所以我们可以得到的自信息是 $ -log_2{\frac{1}{2}} = 1$ bit

    那么我们需要的人数是: $ \frac{-log_2{\frac{1}{50}}}{-log_2{\frac{1}{2}}} \approx 5.64386$

    向上取整就是6人,也就是我们需要观测6个人分别“是死是活”,获取总计6bit的信息,足以100%预测毒酒所在。

  2. 作妖解法里,是观测一个人“死在第1小时零几分钟”,共50种可能性。通过其结果,我们得到的自信息是 $ -log_2{\frac{1}{50}} $ bit

    那么我们需要的人数是: $ \frac{-log_2{\frac{1}{50}}}{-log_2{\frac{1}{50}}} = 1$

    也就是只需要1人,观测这个人死在哪一刻,获取足够的信息100%预测毒酒所在

  3. 500桶版本的题目里,是观测 一个囚犯“死在第T小时零几小时” $ T \in [23,24] $ , 按题目48小时内囚犯可以尝试24次,有24种可能性。通过其结果,我们得到的自信息是 $ -log_2{\frac{1}{24}} $ bit

    那么我们需要的人数是: $ \frac{-log_2{\frac{1}{500}}}{-log_2{\frac{1}{24}}} \approx 1.95548$

    向上取整就是2人,分别观测这2人死在哪一刻,获取足够的信息100%预测毒酒所在

这也是前面所说的“分成 $n$ 件概率事件,观测后汇总求和”的本质。至于拆成怎样的概率事件,就需要读题了。

是不是觉得说破之后,这种题目一下子非常简单?

2. 实际与理论

本次“国王毒酒”从朴素解法的具体实践,到推广问题,尝试找到普适规律,再到引入可描述、概括普适规律的理论,最后又从理论回过头指导解题方案。

这是一套完整的流程,也是数学的特点所在:来自现实、超脱现实、指导现实

而我们知道理论上可行,但到具体实现还有一段距离,这就是应用的范畴了。

本篇小结

1. 数学是什么

历来自然科学的发展进步,离不开数学工具的发展。因为人类的常识实在是太过渺小不堪了,比如:

完全无法想象三维以上的空间,天体的引力对空间的拉伸影响,只能想象成沙发上有个铅球。

数学最擅长做的,就是基于已知结论进行推而广之:证明现有公式定理,在推广集里依然为真,再推导出更多规律。以此来对人类常识之外的东西进行研究,给现有的研究指出方向。

然而正如我前面感叹的,总是从学校出来后才觉得书本里的知识好用。以前上课的时候很难有直观的理解“这有什么用”——数学不光是那堆完全看不懂的符号听不懂的定义,它一定不是思考游戏,更不是试卷上的证明题计算题。

它是一种思考的方式、套路,归纳分析问题的理论,实践解决问题的工具。

2. 用数学思考

回到现实,我们在工作生活里,面对这样那样的实际问题,如果能找到合适的数学理论工具,就能简化流程,少走很多弯路。

例如编程中对多个条件进行if else 判断,如果漏写所有情况,程序很可能就会跑出未定义的行为,而且还极难定位。但如果数学知识还在,简单画一画就能列清楚。

也不一定非得是针对编程工作,比如所谓“最优停止理论”,或者叫秘书问题(Secretary problem):

要聘请一名秘书,有 n 个应聘者。每次面试一人,面试后就要及时决定是否聘他,如果当时决定不聘他,他便不会回来。面试后总能清楚了解应聘者的合适程度,并能和之前的每个人做比较。问什么样的策略,才使最佳人选被选中的概率最大

答案是最优截断值趋近于 $ \frac{n}{e}$,最佳人选被选中的概率为 $ \frac{1}{e} \approx 0.367879$。这个问题类似名称有很多很多:

比如:把“秘书”替换成“对象”,“应聘者”替换成“相亲者”,就变成相亲问题了呗。不过现实里可不是题目里假设的那么单纯、绝对,比如舔狗啦、备胎啦之类的

比如:换成手游里初始送了30次10连抽,抽到第几次“见好就收”。等等

是不是非常有意思?

我觉得很有意思!这也是开坑这个系列的本意所在

本篇到此结束,不知下一篇是什么题目,什么时候会写……

参考资料和工具

  1. Wikipedia
  2. Mathematica
  3. Java