说明问题 识别毒酒方法1 视为一个有约束的最优化问题进行求解 1 模型的进一步讨论 3方法2 使用编码的方法 1 结论2 具体方法3一个瑕疵和改进的方法4如果再考虑所需时间最少怎么办5 本方法所能支持的数量上限 欢迎提供更多的方法

0.说明

本文是鸡年新年计划的内容之一：每周学习一个数学模型，写一篇总结，记录自己学到的东西和遇到的问题。这些文章并不是相关模型的全面介绍，也不是从最基础的开始，所以不一定适合数学模型的beginner，但都是些很实际的技术，希望能帮到你。这个问题可以使用多种方法（或模型）解决，本文给出了使用最优化模型和二维编码的方法，但彼此之间的效率差距很大，如果你还知道其他解决方法，欢迎你给我留言！我会不定期更新。

1. 问题 ：识别毒酒

请诸位为乌有国王出个主意：有500桶酒，其中1桶是毒酒；毒酒喝下去会在之后的第23-24小时内读法身亡；48小时后要举行酒会；国王决定用囚犯来试酒。 不介意囚犯死多少，只要求用最少的囚犯来测试出哪一桶是毒酒，问最少需要多少囚犯才能保证找出毒酒？

2. 方法1： 视为一个有约束的最优化问题进行求解

添加一个假设：毒酒经充分稀释后仍然致命。 最容易想到的当然是n分法，既高数上的二分法的扩展，以下以三分法为例说明：

将500桶编号，每桶取一杯，将500杯平均分成三组，1-166号倒到一个大杯子里（记为A）、167-333杯（共167杯）倒到一个大杯子里（记为B）、剩下的167杯倒到一个大杯子（记为C），让两个囚犯随便喝两杯（比如A和B），23-24小时后根据囚徒的死亡情况就可以判断毒酒在哪一组。

然后将毒酒所在的组平分为3组，再次安排2个囚犯试喝就可以，……，如此几次就可以得知哪桶酒是毒酒。

需要说明的是，分三组，但并不需要3个囚徒试喝，只需要2个即可，如上例，若A死掉则毒酒在A组；B死掉则在B组；都没死则毒酒在C组。

以上是3分法的情况，对于n分法，识别毒酒就是求在满足(n-1)^m>=500的前提下(n-1)*m的最小值；另外一个约束条件是48小时，所以，最多只能尝试两轮，所以m最多取2

全部模型如下：

max(n−1)ms.t.(n−1) m ≥500m≤2m,n为整数  关于求解，由于500相对较小，因此，符合条件的m和n并不多，可以逐一尝试。 一个参考答案如下：

需要最多43个囚犯，使用22分法，分两轮： 500-22*22=16，所以第一轮需要22人； 如果第一轮都活着，毒酒就在剩余的16里，第二轮需要16人； 如果第一轮死1个，那么他喝过的22桶，再用21人去喝，即可确定毒酒在哪一桶。

2.1 模型的进一步讨论

如果不考虑m，则所需囚犯数量即为n-1，n越小则所需的人数越少，所需时间越多，n=2时需要9*24小时。那么，n是否可以为1？

实际上，如果n=1，则上述模型就失效了。但n=1实际上是更简单的情况，就是让一个囚犯，先试喝第1桶，24小时之后如果没事就试喝第2桶，……，以此类推，直至死亡就找到了毒酒。

3方法2： 使用编码的方法

3.1 结论

先说结论：使用该方法，只需要2个囚犯，具体方法如下（为了方便，假设喝了毒酒之后将在第24个小时时段内毒发身亡）

3.2 具体方法

酒从1-500编号，按照21桶一组平均分开，也就是说，1～21桶是第一组，22～42桶是第2组，…… ，最后一组是第24组，是484-500桶（16桶，注意最后一行有4个0）。如下图： 第一个囚犯喝0时刻喝第1组的酒，既第一行的酒，1时刻喝第2组的酒，……23时刻喝484～500的酒（最后一行）；

第二个囚犯0时刻喝每一组的第1桶酒，既第1列的酒，标号1、22、43、……484的酒，1时刻喝每一组的第2桶酒，既第2列的酒，标号2、23、44、……485的酒，……，20时刻喝每一组的第21瓶酒，既第21列的酒，既标号21、42、……、483的酒。

最晚在宴会开始前，两人都会死亡，根据两人死的时间就可以推出是哪一桶酒有毒。比如，第一个人死于次日10至11时之间，则其是第一天的11时服的毒酒，属于上图的232至252号，第二个人死于次日8至9时，则其是第一天9时服的毒酒，是上图中的第10列，二者的交叉点是241号，说明第241桶为毒酒。

根据死亡时间确定喝酒时刻的方法是：如果该人死于次日的第 i-1至 i 时，则其喝下毒酒的时刻是第一天的 i 时。 如果死于第一天的23至24时，则为0时喝的酒；死于24至次日1时的是头天1时喝的酒。

上述方法的实质是对1到500这500个数字进行编码，本文采取的是用两个下标进行编码：行和列，另外，从数制的角度来看，本文的方法使用的是24进制；这似乎是由毒发间隔来确定的。

3.3一个瑕疵和改进的方法

上述方法有一个瑕疵：题目告知的毒发时段是23至24时，如果理解为两个小时，则上述方法存在时段重叠问题，会导致无法判断喝酒时间。

解决方法是间隔两个小时喝一次酒，那么，要在两天内完成测试，必须在24时内完成试喝，每个人试喝的组数不能超过12组，所以分组方法如下图 此时带来的问题是：由于有42行，所以，之前的由一个囚犯按照行进行试喝的方法无法进行。那么，我们需要4个囚犯按照行进行试喝吗？

不需要，实际上，我们只需要增加一个囚犯即可，既，让一个囚犯按照“页”试喝，具体如下：

第一个：0时刻喝每一页的第1组的酒，既每一页第1行的酒，既1至12号、145至156号、289至300号、433至444号；2时刻喝每一页的第2组的酒，既每一页第2行的酒，……22时刻喝每一页的第12组的酒，既每一页第12行的酒，

第二个囚犯0时刻喝每一页的第1列，既上图的第1列的所有酒，标号1、13、25、……、493的酒，2时刻喝每一页的第2列，既第2列的酒，……，22时刻喝每一页的第12列的所有酒，既第21列的酒，既标号12、24、……、492的酒。

第三个囚犯0时刻喝第一页的所有酒，既1至144号，2时刻喝第二页的所有酒，既145至288号，4时刻喝第三页的所有酒，289至432号，6时刻喝剩余的。

同样根据三个人的死亡时间可以确定毒酒的编号。 大家也可以结合下图理解上述方法：

3.4如果再考虑所需时间最少怎么办？

如果不仅要所需囚犯最少，也要所需时间最少，则上述500桶可以分成8行8列8页，如下图： 采取相同的方法，最晚可以在次日14:00时找到毒酒。

3.5 本方法所能支持的数量上限

如果毒发时间是在服毒后的第24个小时内，而不是23至24时，则两个囚犯所能检测的最大数量为24*24=576桶，超过这个数字则两个囚犯就不够了；

同样的假设下，三个囚犯所能检测的最大数量为24^3=13824桶；

n个囚犯所能检测的最大数量为24^n

4. 欢迎提供更多的方法

显然，第二种方法更好，也更惊艳，欢迎大家提供更多的思路和方法。