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

[mathzhaoliang]

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

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

欢迎 v 友们讨论。

[lookforsex]

问题一用二分法？

[mathzhaoliang]

@lookforsex 什么是二分法？

[murmur]

我记得第二个题的漏洞不是小白鼠喂水会被撑死么

[Rizio]

第二题，一只？让它一直喝到死。

[SuperNovaSonic]

转换成二进制去看这个问题就简单了

[mathzhaoliang]

@Rizio 应该加上限制，喝药 24 小时以后毒药就会发作。要求 24 小时内找出毒药。

[binxin]

@lookforsex
至少第一轮不能两等分，需要三等分。

[meefly]

第一题四次，不知道能不能更少

[binux]

@mathzhaoliang #5 24 小时以后才发作，24 小时内无论如何都找不出来。。

[chwhsen]

一般说到背后的数学时，第一步就是把具体的数量抽象成`n`个

[feiyuanqiu]

把 12 枚硬币按四个一组分成三组，找到重量与其他两组不一致的一组，同时能知道假币相对真币轻还是重（ 2 次）；将包含假币那组四个硬币按两个分成两组，找到假币那组（ 1 次）；比较假币组两枚硬币重量，找到假币（ 1 次）。需要称 4 次

[mathzhaoliang]

@chwhsen "一般说到背后的数学时，第一步就是把具体的数量抽象成 n 个"。有时候一上来就讨论一般的情形会把问题复杂化。很多数学定理是先对特殊情形加以证明，然后推广到一般的。

@Rizio
@mathzhaoliang
@binux
我也觉得这个原表述不好，应该直接告诉读者无歧义的规则，我觉得应该表述为 "规则允许每次可以将若干瓶药水搭配起来给某一只小白鼠喝下，且每只小白鼠只能被使用一次"。

[Myprincess]

我出一个:
例子:615+X^2=2^Y 求 X 与 Y 的值
Z+X^2=2^Y
Z 在什么情况下本题无解.

[rabbbit]

第二题不考虑撑死 1 个,考虑撑死 7 个,貌似在哪看过...

[chwhsen]

@mathzhaoliang 的确是这样的

[dnhzm]

第一个 4 次，先分成 3 份，比较两次，得到重量有差别的那份，然后再拿基准的硬币与那份比较。
第二个是 7 只老鼠，因为是 2 的 7 次方＞ 100，每个药按二进制编码，然后按位数等于 1 的投喂药。看死了几只就知道落在哪位为 1，然后就求出来了。
很久之前看过

[zhzer]

第一题二分，三次
第二题二进制分桶，七次

此贴完结

[Voichesapete]

@murmur 没说剂量。如果有毒的那瓶喝一滴也会死呢 2333

[Nimrod]

第一个三次 之前貌似做过这个题
第二个 DP

[stevenbipt]

第一个先四个一组分三个看哪一组和另外两组有差异，然后在把有差异的一组取三个对比，如果有一个与另外两个有差异则那个是假币，如果没有差距则没有对比的那一张是假币，一共需要两次称重。