主题：【原创】从两个经典智力趣题谈起(一) -- 丁坎
家园 二进制和三进制？ 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 帖 引用 (帖内工具实现)- 复 二进制和三进制？
家园 花之 跟我的思路应该是一样的，但老兄的方法似乎更简洁，希望能再介绍详细些，能有数学证明更好。
- 复 花之
家园 我的思路 每次称，结果只有三种，左边重（0），右边重（2），一样重（1）。这样称n次，最多只会出现3^n个不同的结果。而这些结果中，考虑到
1） 两个互补的数（相加等于3^n-1）实际上对应的是同一个小球；
2） 全是1的数字相当于称来称去，所有参加称的小球重量相等，这与已知（有一个小球重量不等）矛盾
这样能够测出的球的数目不会超过（3^n-1)/2。
那么如果我们能找到一种方法可以达到这个数目，我们就是找到了上确界。
这个方法我没有想到。如我上个帖子里所述，那里面测的是(3^n-3)/2个小球，要想加上第（3^n-1)/2个小球，每次称的时候都要把它放在左边，右边加上一个已知是正确的小球。可是正确的小球在称完第一次以后才能得到，除非改题。
本帖一共被 1 帖 引用 (帖内工具实现)
- 复 二进制和三进制？
家园 唉 这才是解决问题的方法阿 我这种只求结果的无疑落了下乘了
家园 花等下文 家园 理论我不懂，对我来说是这是个益智题，请大家看看我的解答， 第二题
12个球分成ABC3组，每组4个。
第一次A(4)/B(4)
平衡则在C组第二次A(2)/C(2)可以找到C组中的两珍珠第三次即可找到
不平衡则在AB组第二次A组中取走2珠，移动B组中的三颗，A(2)B（3）/C(4)B(1)
如果天平平衡，则是取走两珠中的一个，。选一和真的珍珠比较即可找出
如果天平改变方向，则在B(3)中并可以确定赝品是轻是重，第三次从三个中任选二，即可确定赝品。
如果天平不改变方向则是天平上未移动位置的A（2）和B(1)中的一个，第三次A(2)的两珠分置天平两边，平衡为B(1),不改变方向为未移动的A珠，改变则为移动的A珠。
家园 仿佛有点问题 讨论一番 兄台 这是你的假设
12个球分成ABC3组，每组4个。
第一次A(4)/B(4)
平衡则在C组第二次A(2)/C(2)可以找到C组中的两珍珠第三次即可找到
无论平衡与否 C组中2个珍珠都会在第二轮结束时找到。 问题是 找到了以后怎么办？
且设C组不确定的2个珍珠为C(1") 各放一边,C(1")/C(1") 不管是左边大于右边 还是右边大于左边 你都没办法判断哪边是真的
换个角度 A(1)和C(1")比较 只有当选中的C球为假球时 才能确定假球是轻是重 如果C(1")为真球 则只能找出假球 而不能判断轻重
这题如果知道假球轻重 就是小学奥数题
可是不知道假球轻重 这个就麻烦了
家园 如果要判断轻重，只能用才C（3）/A(3)不平衡可知轻重，第三次 可找出，平衡第三次和真品比较也可知轻重
家园 第二次应该A(3)/C(3)吧 。。。
第一次A(4)/B(4)
平衡则在C组第二次A(2)/C(2)。。。
第二次也平衡呢？（1/6的机会）
家园 周易与太玄 周易与太玄
二进制与三进制
二元论和三元论
莫非是楼主要讲的？
家园 我的解答，不知道有没有问题。 第一题比较简单，二进制数而已。分成1，2，4三段。换来换去就成了。
第二题我以前研究过一下，大概是一个递推过程。称三次实际上最多能在13个球中找到赝品，但不能确定知道轻重。少一个球的话就能确定轻重。不需要确定轻重时，基本递推公式是：
Without an extra known good "golden" ball:
1次: 0个球 Special case
2次: 4个球 = 3^0+3^1
3次: 13个球 = 3^0+3^1+3^2
4次: 40个球 = 3^0+3^1+3^2+3^3
5次: 121个球 = 3^0+3^1+3^2+3^3+3^4
6次: 364个球 = 3^0+3^1+3^2+3^3+3^4+3^5
n次: = (3^(n-1)-1)+(n-1 times with an extra known "golden" ball)
我想需要确定轻重的话应该是每个数都要少一。
家园 答题的朋友，此两题不在于“鱼”，而在于“渔”之道。 比如，把7换成8，10，2008，等等，你还会做吗？