出几个烧脑的智力/算法题，顺便聊聊它们背后的数学

[mathzhaoliang]

问题之一：有 12 枚外表一模一样的硬币，其中一枚是假币，其余都是真币。假币的重量与真币不同，但是更重还是更轻不知道。给你一个没有砝码和刻度的天平，最少称几次才能找出假币?

问题之二：有 100 瓶药水和若干只小白鼠，其中一瓶药水是有毒的。正常的药水对小白鼠是无害的，但是有毒的药水则会杀死小白鼠。问最少需要几只小白鼠才能找出有毒的是哪一瓶？

欢迎 v 友们讨论。

[wohenyingyu02]

1. 最少称 2 次。首先拿两个比较，正好有一个是假币，再随便拿一个和其他比，就是最少的情况。
2. 一只。

[mathzhaoliang]

@zhzer 你说的大体意思我懂，但是不是我要的解答。

[Exin]

第一题的最佳解是 三次 ，不是四次。有比二分法更好的解法。
第二题大家都会。

[Exin]

@zhzer 二分如何解出三次的？

[murmur]

第一个题不是一次都不需要么
既然假币和真币的差别只有重量区别 而且是只有天平才能发现的问题
那就是说把这 12 个硬币都花掉不就解决了

[denano]

第一题一开始 3 等分找出重量不一致的那一堆再 2 等分，4 次
第二题就是一开始把 50 瓶药混在一起喂，就是 2 分查找。。

[LadyChunsKite]

https://leetcode.com/problems/poor-pigs/description/

[dingyaguang117]

第一题是 google 埃里克·施密特 面试别人的题，最多 3 次，过程比较复杂

[yukiww233]

2.每瓶药水等分并编号 1-100，用二进制表示占 7 位，7 只老鼠喝对应二进制位为 1 的的药水，死了该位为 1，拼起来就完事

[yukiww233]

1 在面试时候被问过，半天没答上来

[mathzhaoliang]

@SuperNovaSonic
@yukiww233
@Exin
@zhzer

如果是其中两瓶有毒呢？

[ch365]

只要找到假币的话总共称三次，如果还要知道假币轻还是重则要称四次
首先分成三组每组四个，第一次称其中两组。
如果，第一次两组一样重，假币则在第三组的四个中；
这种情况下，第三组的四个中，天平两边各放一个，一样重假币在没称的两个中，不一样重假币在天平上的两个中；
第三次拿一个真币和一个未知币称可以找到假币。
如果，第一次两组不一样重，假设轻的那组标为 0，重的那组标为 1，剩下的真币组标为 2 ；
第二次，天平左右这样放: 001 vs 012 ；
如果一样重，假币在组 0 和组 1 中没放上天平的三个硬币中；
第三次拿组 1 中剩下的两个放上天平；如果一样重，假币是租 0 中剩下的那个，否则假币就是重的那个
如果第二次称，001 的一边较重；那么假币在 001 的 1 或者 012 的 0 之中；两个币第三次称下确定假币。
如果第二次称，012 的一边较重；那么假币在 001 的两个 0 或者 012 的 1 之中；三个币第三次可以确定假币

[mathzhaoliang]

@ch365 如果知道背后的数学的话，就可以设计出正确的方案来。并不很难，三次就知道轻重。光靠自己试的话累死不说还找不到正确的方案。

[SuperNovaSonic]

@denano 第一题是求最好情况，如果一开始三堆上称的那两堆重量一致，直接确认假币在剩下一堆里，所以一共三次就好了，4 次是最差情况下的

[binux]

@mathzhaoliang #29 13 只

[ch365]

@mathzhaoliang 恩，三次就可以知道轻重，假币则在第三组的四个中的情况，后面称重设计有误。

[A3m0n]

我也来补两个，第一题是小白鼠的简单版本：

有一批玻璃杯（产品的优劣程度完全相同），和一幢高 100 层的楼（ 1 层到 100 层，不存在 0 层）。现在要测试这批玻璃杯的耐摔程度，即玻璃杯如果在 n 层下落没碎，在 n+1 层下落碎了，那耐摔程度就是 n。请问：

1：最少牺牲多少个玻璃杯？
2：最少测试几次？
（两个问题相互独立）

还有一题题目比较恶俗，但是解起来还是比较有趣的。我想想有什么不怎么恶俗的表达方式，如果想不到的话，待会上题目。

[MisakaTang]

数学之美番外篇：快排为什么那样快 : http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/
这篇博客我感觉是讲到了背后的数学原理了 可以看一下

[loryyang]

第一题答案是三次，https://gist.github.com/zjucloud/eee320c016e670ddfef111c386ad9b26
直接写的，不确定一定正确：
1：平均分三组,A B C
A vs B
A < B or A > B 看 2.1, A == B 看 2.2

2.1
说明在 A,B 里面，由于 A 和 B 相对等价，我们可以假设 A < B （反过来就把 AB 互换即可）：这样只可能是 A 有一个硬币轻，或者 B 有一个硬币重
A 和 B 都分成 2+1+1，表示为 A1,A3,A4 和 B1,B3,B4
我们从 C 里面取正常的硬币 X，然后 A3 + B1 VS A4 + B4 + X，把 A1 和 B3 留下
三种情况：
<：2.1.3
>：2.1.4
=：2.1.5

2.1.3
A3 + B1 < A4 + B4 + X
说明 A3, B4 有问题，因为之前是 A < B，所以要不是 A 的只可能轻，B 的只可能重, B1, A4 如果有问题，应该是>而不是<
A3 和 B4 都是一个，所以用 3.1.2 解法即可

2.1.4
A3 + B1 > A4 + B4 + X
反转了，说明 B1,A4 可能有问题，B1 是两个，A4 是一个
我们把 B1 拆成 B11 和 B12，然后 B11 + A4 VS X + X:
<:说明 res = A4
>:res=B11
==:res=B12

2.1.5
A3 + B1 == A4 + B4 + X
说明剩下的 A1 和 B3 有问题，和 2.4 类似，拆分 A1 为 A11, A12
然后 A11 + B3 VS X + X
<: res=A11
>: res=B3
==: res=A12

3.1
说明 C 有问题
C 分为 2 + 2：M, N
M 再分 M1, M2，然后 M1 VS M2
如果 M1 != M2 看 3.1.2，否则看 3.1.3

3.1.2 M1 != M2 说明 M1, M2 有一个有问题
取一个正常的 X vs M1，如果不平衡，res=M1 否则 res=M2

3.1.3
说明 N 里面有问题，和 2.3 一样，取一个正常的 X vs N1，如果不平衡，说明 res=N1，否则 res=N2

[mathzhaoliang]

@MisakaTang 那些写数学之美的人 (包括吴军)，都不是数学科班出身的，所以遇到一个好玩的题目和一个好玩一点的解释就大惊小怪一番。其实那篇文章也没写到点子上。