主题:【原创】从两个经典智力趣题谈起(一) -- 丁坎
1. 对于i个金环,2^(n-1)<=i<2^n, 需要切分n次,方法是2^0, 2^1,……,2^(n-2), i - 2^(n-2)
2. (世界上有重量相等的两颗珍珠吗,哪怕是养殖的?)对于(3^n-3)/2个小球,可以称n次并知道轻重;或是对于(3^n-1)/2个小球,可以称n次但是有可能不知道轻重。方法是:把 0..3^n-1 共 3^n个非负整数用三进制表示,除去全是0,全是1,全是2的3个数,剩下的数字里每一位上分别为0,1,2的数字都有相同个。这样我们把这些小球编号,每个小球有两个号,这两个号的和是3^n-1 (比如如果n=3, 012和210是同一个小球,112和110也是同一个小球,编号中1不变,2变成0,0变成2),编号1和编号2。(在两个编号中选择哪个是编号1的时候注意让所有小球的编号1的第i位上0和2的个数一样多)。这样在称第i次的时候(1<=i<=n),我们把编号1中第i位不是1的小球(共(3^n-3)/3*2个)分成数目相同的两组来称,第i位是0的放在左边,第i位是2的放在右边。如果左边重,记作0,右边重,记作2,一样重,记作1。称n此后得到的数字就是有问题小球的编号,如果是编号1,这个小球比其他小球重。如果是编号2,这个小球比其他小球轻。如果得到的数字全是1,那么有问题的是从来没有称过的小球,但是我们不知道它轻还是重。
本帖一共被 1 帖 引用 (帖内工具实现)
- 相关回复 上下关系8
🙂此处已从切环问题跳出 1 丁坎 字112 2008-08-04 04:13:10
😁为避免拓扑带来的复杂性,可改用(整数长度的)金条问题 衲子 字0 2008-08-04 04:17:26
🙂对 1 王树 字125 2008-08-04 11:35:21
🙂二进制和三进制?
🙂花之 1 丁坎 字86 2008-08-04 03:49:22
🙂我的思路 2 使用尽量中文 字604 2008-08-04 12:22:21
🙂唉 这才是解决问题的方法阿 流云天下 字30 2008-08-04 01:52:29
🙂花等下文 侯登科 字0 2008-08-03 21:22:07