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

引子

好几年前跟朋友吃饭的时候惯例闲聊,我提了一道题,昵称“羊宝宝”的大佬立刻指出答案以及求解思路。我立刻茅塞顿开,联想起了自己大学的课程,灵感迸发,一番酣畅的讨论,仿佛回到了学校。

后来跟当时在场的另一朋友聊起此事(上一篇里提到过开坑说明),而这么久过去也没写。一个既有趣,又引人思考的话题,可不能浪费了。

题目

这道题有各种版本,我第一次知道的版本是这样的:

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

如果搜索国王 毒酒,则可以找到各种变种,例如酒桶增多了、毒发时间变长了等。且住,先不看那些,来思考一下上面的“50桶版本”

问题初解

当时我是在面试的时候被问到这道题,“自然而然”是按程序员的思路去看待问题——“嗯,这是要找到一个时间、空间开销最优的算法”,典型的应试思维。当时过了几分钟,我就放弃了,当然更多原因是面试得很差。

不过这个题目一直在我脑子里转悠,我想找到解法

先简单粗暴地来,50人一人试一桶(49人也可以, 1小时全没中毒那就是最后一桶有毒),1小时可解。那么,最快最少的答案,必然是大于等于1小时且小于50人,那么必然得喝下不同桶的混合酒,于是剩下的问题是怎么安排策略。

策略必须满足的条件:

  1. 输入$x$人($x < 50$),每人喝下混合的酒,等待1小时后获取“死亡结果”
  2. 通过最终结果能唯一确定毒酒

所以就变成了怎么安排混合方式的问题,先来朴素的解法

朴素的解法

统统只需要1小时

1. 排成一条线

将50个点依次放到X坐标轴上,那么按50桶酒从1到50的编号,列出其在X轴上的坐标是:

1
2
3
4
5
6
7
8
9
0
1
2
3
4
...省略
47
48
49

其中取值为0的无须测试,X轴上有49个值,所以需要49人:哪一个挂掉了,就表示相应的酒有毒;都没挂掉,则是坐标原点0所代表的第一桶酒有毒。这也是前面的简单粗暴解法的答案,明显不满足要求,那么更进一步

2. 摆一个方阵

将50个点依次放到XY平面的第一象限,但这可以有很多种摆法。设摆成a行、b列,则需要满足条件: $ab \ge 50$ 且 $a,b$ 均是正整数,目标是使得 $a + b$ 尽量小。不用想就知道当 $a = b$ 的时候满足条件,又因为 $a,b$ 都是正整数,所以 $a = 7, b = 8 $ 即可。故而令 $y \in [0, 7]$ ,是当前最优解

那么按50桶酒从1到50的编号,列出其在XY平面上的坐标是:

点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(0,0)
(0,1)
(0,2)
(0,3)
(0,4)
(0,5)
(0,6)
(0,7)
(1,0)
(1,1)
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
(1,7)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(2,5)
(2,6)
(2,7)
(3,0)
(3,1)
(3,2)
(3,3)
(3,4)
(3,5)
(3,6)
(3,7)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)
(4,5)
(4,6)
(4,7)
(5,0)
(5,1)
(5,2)
(5,3)
(5,4)
(5,5)
(5,6)
(5,7)
(6,0)
(6,1)

同上,取值为0则无需测试,那么X轴上有6个值,Y轴上7个值,所以需要13个人。

到这里一下子少牺牲一波倒霉蛋,可喜可贺。上面这段50行坐标似乎好有道理,但这个摆好的难道不是8行7列,那为什么是 $6 + 7 = 13$ , 需要13人?取值为0无需测试是什么含义?

在X坐标轴上 $x = 0$ 无需测试,很容易理解,49人没死,那就是没人喝的有毒呗,那XY坐标平面是怎么操作的?

莫慌,我们把这么个酒桶阵画出来,为了方便用markdown语法表述,将酒桶阵顺时针旋转了90°,如下表格:

来两拨人,分别记作X队、Y队。如此,X队每人按上面的表格喝一行,Y队每人按上面的表格喝一列。例如X队1号就喝编号9,10,11,12,13,14,15,16 这8桶的酒, Y队1号2,10,18,26,34,42,50这7桶的酒

最终结果:

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

嗯,能完美地唯一确定毒酒编号!

想到这一步,立刻觉得事情有眉目了,如果扩展到XYZ三维空间中,摆成a行b列c层,应该能进一步减少人数要求

3. 堆成一摞

将50个点放进XYZ空间直角坐标系的第一卦限(类比二维平面,三维空间的有 $2^3 = 8$ 个”象限”,所以中文译名就用卦限了。正所谓“两仪四象八卦”),也就是前面提到的a层b行c列

需要满足条件: $a \times b \times c \ge 50$ 且 $a,b,c$ 均是正整数,目标是使得 $a + b + c$ 尽量小

同理,得到XYZ空间直角坐标系中酒桶编号排列如下:

点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(0,0,0)
(0,0,1)
(0,0,2)
(0,0,3)
(0,1,0)
(0,1,1)
(0,1,2)
(0,1,3)
(0,2,0)
(0,2,1)
(0,2,2)
(0,2,3)
(0,3,0)
(0,3,1)
(0,3,2)
(0,3,3)
(1,0,0)
(1,0,1)
(1,0,2)
(1,0,3)
(1,1,0)
(1,1,1)
(1,1,2)
(1,1,3)
(1,2,0)
(1,2,1)
(1,2,2)
(1,2,3)
(1,3,0)
(1,3,1)
(1,3,2)
(1,3,3)
(2,0,0)
(2,0,1)
(2,0,2)
(2,0,3)
(2,1,0)
(2,1,1)
(2,1,2)
(2,1,3)
(2,2,0)
(2,2,1)
(2,2,2)
(2,2,3)
(2,3,0)
(2,3,1)
(2,3,2)
(2,3,3)
(3,0,0)
(3,0,1)

依然去掉0值,X,Y,Z的取值都有三种,也就是X,Y,Z三个小队都派出3人,因此需要9人

这里我就不画排列表格了,这可是一个 $4 \times 4 \times 4$ 的未填满的立方体:如果把X的取值作为层高的话,那它就是4行4列4层的一摞酒桶,有3层填满而第4层只有两个桶。对照上面完整的“XYZ坐标-编号”,能轻易地从最终结果唯一确定毒酒编号

4. 朴素解法的终点

4.1 从问题到数学

9人就是最终解了吗?如果你想到了放进三维空间这一步,给出答案 $9$ 而不是 $4\times3=12$ ,已经很厉害了,我觉得这是通过常识能做到的极限。毕竟谁也想象不出三维以上的空间是啥样、怎么摆,对吧?

虽然隐隐约约感觉将50个酒桶丢进更高维空间里去,几维空间就派出几队人,这能进一步减少所需人数,但这个方向的终点到底是多少呢?能做到的极限是多少呢?

常识不好使了很正常,赶紧回想一下数学归纳法吧,中学数学老师会比较欣慰的

设维度为正整数 $n$ , 那么已知:

  1. $n = 1$ 时, $50^1 = \boxed{50}$ , 需要1队人。合计 $(50 - 1)$ 人
  2. $n = 2$ 时, $8^2 > 8 \times (8 - 1) > \boxed{50} > 7^2$ , 需要2队人。合计 $(8 - 1) + (7 - 1)$ 人
  3. $n = 3$ 时, $4^3 > \boxed{50} > 4^2 \times (4 - 1)$ , 需要3队人。合计 $(4 - 1) + (4 - 1) + (4 - 1)$ 人

接着推测:

$n = 4$ 时, $3^4 > 3^3 \times (3 - 1) > \boxed{50} > 2^4 $, 需要4队人。合计 $(3 - 1) + (3 - 1) + (3 - 1) + (2 - 1)$ 人

看起来好规整,这个合计人数看起来也很有规律,先试着固定它猜测一下

那么当 $n$ 为某一常数时,设 $x$ 为满足要求 $x^n \ge 50$ 的最小正整数,是否可以有推论:

  1. 若 $x^n \ge \boxed{50} > x^{n-1} \times (x - 1)$ , 所求解为 $(x - 1) \times n$ 人
  2. 若 $x^n > x^{n-1} \times (x - 1) \ge \boxed{50}$ , 所求解为 $(x - 1) \times (n - 1) + (x - 2)$ 人

看起来好复杂,但若把 $n$ 当做变量, $x$ 也从正整数扩展到正实数范围内,那么可知 $x=\sqrt[n]{50}$ ,上面的公式可以大胆简化为:

所需人数等于 $n(\sqrt[n]{50} - 1)$

又由于最终人数必须整数,所以向上取整

所需人数等于 $\lceil{n(\sqrt[n]{50} - 1)}\rceil$

接着验算下 $n = 1,2,3$ 的情况,发现居然都是对的。我们先假装公式是正确的吧!

简单地画个图可以发现随着 $n \to +\infty $ ,所需人数的确是不断减少的。如果数学分析的知识还在,不难发现:

$\lim_{n \to +\infty}\,{n(\sqrt[n]{50} - 1)} = ln\,50 \approx 3.91202$

对其向上取整:

$\lceil{3.91202}\rceil = 4$

4.2 从数学回到问题

队伍数量越多,所需总人数越少没毛病。等于4,提交答案?

不行的,这个推测出来的公式是有现实含义的,$n$对应着n队人,$(\sqrt[n]{50} - 1)$ 对应着平均各队派出的人数

回到题目, 确定 $n \in {\displaystyle \mathbb {Z} ^{+}}$ (即 $n$ 为正整数)且 $(\sqrt[n]{50} - 1) \ge 1$, 不然平均每队派人数不到1人,肯定是出现了空队伍,这毫无意义

随着 $n$ 递增, $\sqrt[n]{50}$ 在逐渐减小且无限趋近于 $1$

令 $(\sqrt[n]{50} - 1) = 1$ , 求出满足上述条件的最大的 $n$

计算得到 $n$ 的合适取值就在 $log_2\,50 \approx 5.64386$ 附近了

那么n取5或者6的时候就是最优解了,列一下底数x:

  1. $n = 5, x = \sqrt[5]{50} \approx 2.18672, \lceil{x}\rceil = 3$

  2. $n = 6, x = \sqrt[6]{50} \approx 1.91938, \lceil{x}\rceil = 2$

实际使用中 $n = 5$ 的情况是严重不可取,因为 $3^5 = 243$ 太大了,把50个酒桶放进去会有非常多的浪费, 其结果就是需要人数肯定不止是6人

生成对应的5维坐标清单如下:

点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(0,0,0,0,0)
(0,0,0,0,1)
(0,0,0,0,2)
(0,0,0,1,0)
(0,0,0,1,1)
(0,0,0,1,2)
(0,0,0,2,0)
(0,0,0,2,1)
(0,0,0,2,2)
(0,0,1,0,0)
(0,0,1,0,1)
(0,0,1,0,2)
(0,0,1,1,0)
(0,0,1,1,1)
(0,0,1,1,2)
(0,0,1,2,0)
(0,0,1,2,1)
(0,0,1,2,2)
(0,0,2,0,0)
(0,0,2,0,1)
(0,0,2,0,2)
(0,0,2,1,0)
(0,0,2,1,1)
(0,0,2,1,2)
(0,0,2,2,0)
(0,0,2,2,1)
(0,0,2,2,2)
(0,1,0,0,0)
(0,1,0,0,1)
(0,1,0,0,2)
(0,1,0,1,0)
(0,1,0,1,1)
(0,1,0,1,2)
(0,1,0,2,0)
(0,1,0,2,1)
(0,1,0,2,2)
(0,1,1,0,0)
(0,1,1,0,1)
(0,1,1,0,2)
(0,1,1,1,0)
(0,1,1,1,1)
(0,1,1,1,2)
(0,1,1,2,0)
(0,1,1,2,1)
(0,1,1,2,2)
(0,1,2,0,0)
(0,1,2,0,1)
(0,1,2,0,2)
(0,1,2,1,0)
(0,1,2,1,1)

不难发现,$3^5$ 的5维空间中空余的位置太多,非常浪费。其第一个维度取值都是0,直接退化成了4维空间,而所需人数也的确是 $0 + 1 + 2 + 2 + 2 = 7$ ,第一队完全就是吃空饷的

那么,$2^6$ 的6维空间似乎比较合理了,出6队,每队都出1人就刚好6人

到了这里,你应该也发现了,上面一大堆所做的事情是:

  1. 通过某种方式生成一串 $(a_1, a_2,…, a_n)$ ,用n队人来表示另一串数字——也就是酒桶编号

  2. 对每个酒桶编号都有唯一一组 $(a_1, a_2,…, a_n)$ 序列,它们的取值分别代表第几队第几号得来喝这桶酒。如果是第0号,该队无需派人

  3. 每个队出人的最大编号,刚好是 $\sqrt[n]{50}$ 向上取整后减去1

这听起来怎么特别耳熟呢,程序员思维已经急不可耐了:

从程序员角度去理解,也就是把0~49这50个数字,分别用 $\lceil{\sqrt[n]{50}}\rceil$ 进制去转换:

  1. 当 $n=1$ 时$\lceil{\sqrt[1]{50}}\rceil=50$, 用的是50进制
  2. 当 $n=2$ 时$\lceil{\sqrt[2]{50}}\rceil=8$, 用的是8进制
  3. 当 $n=3$ 时$\lceil{\sqrt[3]{50}}\rceil=4$, 用的是4进制
  4. 当 $n=4$ 时$\lceil{\sqrt[4]{50}}\rceil=3$, 用的是3进制
  5. 当 $n=5$ 时$\lceil{\sqrt[5]{50}}\rceil=3$, 还是3进制, 它也的确退化成了 $n=4$ 的情况
  6. 当 $n=6$ 时$\lceil{\sqrt[6]{50}}\rceil=2$, 用的是2进制, 是我们推测出的最优解6人

转换到相应的进制后,左侧高位可能是没有数字的空位
这些左边高位为空的就用0去填充对齐,最终解读编码结果:

  1. 从高位向低位依次计数,有几位就需要几个队伍
  2. 每个队伍对应的那一列有几种非0的值,那一队就需要派出几人
  3. 最终对每个队伍派出的人数求和,就是总人数

很好,这很程序员,很二进制!

程序员的解法

1. 代码和输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int wineCnt = 50; // 酒桶数
int radix = 2; // 二进制
int dimCnt = (int) Math.ceil(Math.log(50) / Math.log(radix)); // 位数(派出几队人)
String fmtStr = "%" + dimCnt + "s";
IntStream.range(0, wineCnt)
.mapToObj(idx -> Integer.toUnsignedString(idx, radix))
.map(s -> String.format(fmtStr, s))
.map(s -> s.replace(' ', '0'))
.map(s -> charsToVector(s.toCharArray()))
.forEach(System.out::println);
/**
* 把char数组以逗号作分隔符拼接, 首尾包上括号, 按字符串返回
* 省略具体实现
*/
String charToVector(char[] chars) {...}

直接上列表:

点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(0,0,0,0,0,0)
(0,0,0,0,0,1)
(0,0,0,0,1,0)
(0,0,0,0,1,1)
(0,0,0,1,0,0)
(0,0,0,1,0,1)
(0,0,0,1,1,0)
(0,0,0,1,1,1)
(0,0,1,0,0,0)
(0,0,1,0,0,1)
(0,0,1,0,1,0)
(0,0,1,0,1,1)
(0,0,1,1,0,0)
(0,0,1,1,0,1)
(0,0,1,1,1,0)
(0,0,1,1,1,1)
(0,1,0,0,0,0)
(0,1,0,0,0,1)
(0,1,0,0,1,0)
(0,1,0,0,1,1)
(0,1,0,1,0,0)
(0,1,0,1,0,1)
(0,1,0,1,1,0)
(0,1,0,1,1,1)
(0,1,1,0,0,0)
(0,1,1,0,0,1)
(0,1,1,0,1,0)
(0,1,1,0,1,1)
(0,1,1,1,0,0)
(0,1,1,1,0,1)
(0,1,1,1,1,0)
(0,1,1,1,1,1)
(1,0,0,0,0,0)
(1,0,0,0,0,1)
(1,0,0,0,1,0)
(1,0,0,0,1,1)
(1,0,0,1,0,0)
(1,0,0,1,0,1)
(1,0,0,1,1,0)
(1,0,0,1,1,1)
(1,0,1,0,0,0)
(1,0,1,0,0,1)
(1,0,1,0,1,0)
(1,0,1,0,1,1)
(1,0,1,1,0,0)
(1,0,1,1,0,1)
(1,0,1,1,1,0)
(1,0,1,1,1,1)
(1,1,0,0,0,0)
(1,1,0,0,0,1)

前面已经说了,这是派出6个队伍,每队至多1人,没有空间浪费,也符合我们未经证明的计算公式,很好很好

2. 程序员总结

到这一步,面试官应该无话可说了,可惜当时我没想到这里来。像个程序员一般地总结一下:碰到题不要慌,编号啊编码之类的事情,多想想二进制祖宗😂

这就是毫无异议的最优解了,这就完事了?

是的,在前面被“羊宝宝”大佬启发之前,在搜索网上相关问题之前,我是这么以为的

直到我膝盖中了一箭

问题的延伸

国王、毒酒问题的诸多变种版本里,有一种是这样的:

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

诸多人推广(互相抄袭)、转发的答案是两人

什么?!两人就能搞定?肯定有什么是之前没想到的!

仔细看下两种问题之间的区别,不难发现……

欲知后事如何,且听下回分解