五千年(敝帚自珍)

主题:【原创】从两个经典智力趣题谈起(一) -- 丁坎

共:💬102 🌺203
全看分页树展 · 主题 跟帖
家园 二进制和三进制?

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 帖 引用 (帖内工具实现)
全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河