五千年(敝帚自珍)

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

共:💬102 🌺203
分页树展主题 · 全看首页 上页
/ 7
下页 末页
    • 家园 二进制和三进制?

      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珠。

    • 家园 周易与太玄

      周易与太玄

      二进制与三进制

      二元论和三元论

      莫非是楼主要讲的?

    • 家园 我的解答,不知道有没有问题。

      第一题比较简单,二进制数而已。分成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,等等,你还会做吗?

分页树展主题 · 全看首页 上页
/ 7
下页 末页


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

Copyright © cchere 西西河