# 囚犯测试毒药

### 1、囚犯测试毒酒的问题

$N$瓶酒，其中有$K$瓶酒为毒药。问至少需要多少名囚犯，才能在$T$轮试酒中找出所有的毒酒。

### 2、数学背景

A familiar example of group testing involves a string of light bulbs connected in series, where exactly one of the bulbs is known to be broken. The objective is to find the broken bulb using the smallest number of tests (where a test is when some of the bulbs are connected to a power supply). A simple approach is to test each bulb individually. However, when there are a large number of bulbs it would be much more efficient to pool the bulbs into groups. For example, by connecting the first half of the bulbs at once, it can be determined which half the broken bulb is in, ruling out half of the bulbs in just one test.

### 4、$K=1$ 单瓶毒酒情况

$N$瓶酒从 0 开始编号，并用$T+1$进制表示，每瓶酒的编号的位数不超过$M=\lceil\log_{T+1}N\rceil$

### 5、单轮两瓶毒酒的情况

In a matrix that is d-separable, the Boolean sum of every d columns is unique.

A $t\times n$ matrix $M$ is d-separable if and only if $\forall S_{1}\neq S_{2}\subseteq [n]$ where $|S_{1}|,|S_{2}|\leq d$, such that $\bigcup _{j\in S_{1}}M_{j}\neq \bigcup _{i\in S_{2}}M_{i}$

Maximal number of binary vectors of length n such that the unions (or bitwise ORs) of any 2 distinct vectors are all distinct.

#### 5.2、小范围内求解

10:22, 11:31, 12:46, 13:55, 14:63, 15:72, 16:91, 17:113, 18:145, 19:182, 20:230, 21:281, 22:359, 23:449, 24:571, 25:690, 26:892, 27:1078

### 6、两轮两瓶毒酒的情况

Q. E. D.

##### 类似文章：

600 个人站一排，每次随机杀掉一个奇数位的人，几号最安全？