老鼠喝药问题
问题：
有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
分析：
直接贴知乎回答吧
Q1：为什么10个白鼠能分辨1000瓶液体？
（先假设老鼠喝毒药之后立刻死，而不是一周后，稍后解释原因）我们让第一只老鼠喝掉前500瓶液体，如果它死了，那么毒药就在前500瓶里。
下面，将存在毒药的500瓶一分为二，再拿一只老鼠来试验：我们再次精确把毒药限制在250瓶中。
继续下去，每次取一半做实验，我们将依次精确到125瓶（第三只），精确到62/(或)63瓶（第四只），31/32瓶（第五只），15/16瓶（第六只），7/8瓶（第七只），3/4瓶（第八只），1/2（第九只，这次可能一举就确认，如果恰好出现在只有1瓶的那个分块中，饶过一只可怜的小白鼠，否则就需要再实验一次决定），1瓶（第十只）。
Q2：上面这个假设没有考虑到“只能观察一次”这个前提，即不允许我们每次实验一下，观察并排除一半，再循环实验。用什么方式让这种分辨在一次观察中就解决呢？
（考虑 3 只老鼠，8(2^3) 瓶液体的情况）我们让第一只老鼠喝掉1，2，3，4前四瓶；第二只喝掉1，2，5，6瓶；第三只老鼠喝掉2，4，6，8瓶。
一周后，假设发生：第一只老鼠死了：毒药在前4瓶（1,2,3,4）；第二只老鼠活着：毒药在（3,4）；第三只老鼠死了：第4瓶。Q3：推广到更多毒药要老鼠怎么喝呢？
如题设，1000瓶的情况，我们让每只老鼠都喝掉一半，即500瓶。第一只喝掉前500瓶；第二只每隔250瓶喝接下来的250瓶，即1~250, 501~750；第三只每隔125瓶喝125瓶，即1~125, 251~375, 501~625, 751~875；第四只每隔62瓶喝63瓶（或每隔63瓶喝62瓶）；直到第十只，每隔1瓶喝一瓶，即都喝奇数（或偶数）瓶。
比如只有第1, 2, 3, 4, 5, 6, 7, 8, 9只死亡的情况（除了第10只其他都死了），我们能依次精确到毒药存在于以下范围的瓶子中，1-500, 1-250, 1-125, 1-63, 1-32, 1-16, 1-8, 1-4, 1-2, 2。得出第2瓶是毒药的结果。Q4：这和二进制的解法有什么区别？
没区别。二进制解法中，第一只老鼠，即负责个位的那个老鼠，就是每隔1瓶就喝一个：因为二进制逢 2 归 0；第 3 只老鼠，即负责百位的老鼠，每隔 2^(3-1) = 4 瓶喝 4 个：二进制百位隔 4 个保持一样；第 n 只老鼠，即负责从各位数第 n 位的老鼠，每隔 2^(n-1) 瓶喝 2^(n-1) 个。其实和上述用逻辑的方式喝法没有区别。作者：dark blue链接：https://www.zhihu.com/question/19676641/answer/127149488
来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解释一下二进制的方法：将瓶子编号为0~1023（10个老鼠可以分辨1024瓶药水），转换为2进制，老鼠标号为1~10号，对每一瓶药水，如果所在的位为1，就要喝。
比如：00 0000 0001 第一个老鼠喝，所以第一个老鼠是负责第一位的，即每隔一瓶喝一瓶。
00 0000 0010 和00 0000 0011第二个老鼠要喝，即每隔两瓶喝两个。
……
第10只老鼠喝的是10 0000 0000~11 1111 1111的药水，即后一半。
可以看到，与Q3是一样的，不过顺序相反了。
出栈顺序问题
首先想到的就是著名的 卡特兰数 :
$C_n=\frac{1}{n+1}\cdot \begin{pmatrix} 2n \ n \ \end{pmatrix}=\frac{(2n)!}{(n+1)!\cdot n!}$
它的应用很广：
- $C_n$表示长度2n的dyck word的个数。Dyck word是一个有n个X和n*个Y组成的字串，且所有的前缀字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
- 将上例的X换成左括号，Y换成右括号，$C_n$表示所有包含n组括号的合法运算式的个数：
((())) ()(()) ()()() (())() (()())
- $C_n$表示有n个节点组成不同构二叉树的方案数。下图中，n等于3，圆形表示节点，月牙形表示什么都没有。
- $C_n$表示有2n+1个节点组成不同构满二叉树（full binary tree）的方案数。下图中，n等于3，圆形表示内部节点，月牙形表示外部节点。本质同上。
- $C_n$表示所有在n × n格点中不越过对角线的单调路径的个数。一个单调路径从格点左下角出发，在格点右上角结束，每一步均为向上或向右。计算这种路径的个数等价于计算Dyck word的个数：X代表“向右”，Y代表“向上”。下图为n = 4的情况：
- $C_n$表示对{1, …, n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, …, n),其中S（w）递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。
