想起来一道经典题

lewiss

12个外表一样小球。其中一个和其他的重量不一样，不知是轻了还是重了。如何用没有砝码的天平称3次把它找出来。
3 P" s% t5 a5 \5 x+ q# f3 P5 A当时想了两天才想出答案。。
- s1 k4 j  j" O0 v4 G. N今天又想了一下，24个小球要多少次呢？
  `) h( n8 l4 Y0 L36个呢？

scarletmood

3分法？

lewiss

原帖由 scarletmood 于 2007-12-11 23:54 发表
0 X" |, T. _- A1 ^1 l; B3分法？

第一步，后面有点复杂

kolinsky

lz
! P8 ~/ G$ e% }: r怎么搞定的？我要4次…………

lewiss

原帖由 kolinsky 于 2007-12-12 12:24 发表
lz
怎么搞定的？我要4次…………

数学系的，肯定能想出来
* q2 h  h4 g9 T! v. e6 {6 V' R0 G  B这么早说答案，没意思。。

kolinsky

悄给我，我计算最少4次

kolinsky

妈的，收回我说的话，当是多发一帖多赚一个聚元

lewiss

看来是没人会做了$NO$ $NO$ $NO$

kolinsky

答案我知道啊……哈哈哈，不告诉你……
; I( w1 ?6 ^. |4 h3 P* N当然要准做记号才有正确答案啦，要不也要4次才可以的。

# _+ ]5 f% W! \' l( Y  i6 C能做记号的情况下：
24个球4次，36个球也是4次

% E2 P  M7 o" m[ 本帖最后由 kolinsky 于 2007-12-29 19:14 编辑 ]

kolinsky

再加点难度吧。
* s; v% w0 R' H6 o) J8 o9 H1 E! x题设不变，在能给小球做记号的情况下请证明：

% i2 {! a# b$ s1 N任给小球数量n>=4，当 4×3^(m-1) < n <= 4*3^m 则至少要2＋m次才能把小球称出来。

lewiss

原帖由 kolinsky 于 2007-12-29 19:30 发表
再加点难度吧。
题设不变，在能给小球做记号的情况下请证明：

任给小球数量n>=4，当 4×3^(m-1) < n  

6 o% X. w3 I, [2 ]! O哇！这个强！

solvas

12个小球称3次好像不用做记号的吧$考虑$ $考虑$

solvas

$汗$ 搞错了

回首又见你

$考虑$ $考虑$

sofl

本题的解法很多  我列举一种吧  大家参考下，我称呼重量不同的为假球
2 s, L. ~) D" H7 [分组4  4  4个  
+ ]0 ^. p- Z( f1 E7 h+ s$ g一。拿如果4=4 则不同的球在最后4个里面 我给编号 9 10 11 12 ，前面的
       1。2 。1任意拿三个1 2 3号球和9 10 11号称 如果 1 2 3=9 10 11 则12是假的
1 s5 l8 v6 k: Q( s, n! e       1。2。2如果1 2 3〉9 10 11则假的在9 10 11里面并且假的轻
7 h  |- V/ r/ ]+ ]7 H0 z' v       1 。2。3拿9和10称  9〈10 则9假，9〉10则10假  9=10则11假
       1。3   （1 2 3〈9 10 11的情况类似）
$ I( d0 E8 y2 d4 ~- K1 L二。如果前面4 4不等 我们把重的编号1 2 3 4  即1 2 3 4〉5 6 7 8......................式（1）
/ W/ s+ t! c+ \. j+ ^       2。1   拿1 7 9 和 5 6 2称
       2。1。1如果1 7 9=5 6 2 .....................式（2）
                  则假的在3 4 8里面，根据式（1）知假的重，拿其中2个再称一次就知道哪个是假的了
9 P( |. `  X4 h& l       2。1。2如果1 7 9〉5 6 2....................式（3）
                   这里用下数学推理假设法：假设2是假的，根据式（1），假的重  根据式（3）假的轻  矛盾2不可能为假
                                                       假设7是假的，根据式（1），假的轻  根据式（3）假的重  矛盾7不可能为假
' g" x; u% x+ u: h% j: @! |# t4 w                   所以假的只能在1  5 6里面
+ O  k. {( R* T' A: P! ^: v- A       2。1。3 拿5和6称  如果5=6，1为假的  
                                  如果5〉6说明假的在5 6里面 根据式（1）假的轻 6为假
                                  如果5〈6说明假的在5 6里面 根据式（1）假的轻 5为假
       2。2。1如果1 7 9〈5 6 2....................式（4）
                                                        假设5 6里有假，根据式（1），假的轻，根据式（4）假的重 矛盾 5 6不可能为假
                   所以假的只能在 1 7 2里面  拿1 2称
- W( V; U+ A1 @. L) n                                  如果1=2，7为假
                                  如果1〉2，根据式（1），假的重  所以1为假
4 Y' Y* z8 X6 L& ^: F" s                                  如果1〈2，根据式（1），假的重  所以2为假

& i' m* j" X, p( }; M" D7 s所有情况分析完毕  本题还有其他多种称法  主要是第二次称怎么选择:)

jutree

原帖由 sofl 于 2008-1-6 03:34 发表
+ M' t$ ?9 q# z* s9 B: o) j7 g: M" W本题的解法很多  我列举一种吧  大家参考下，我称呼重量不同的为假球
6 J6 v4 d6 ?1 w' m分组4  4  4个  
一。拿如果4=4 则不同的球在最后4个里面 我给编号 9 10 11 12 ，前面的
! V9 X9 {) M- i+ z" r7 ^1 l       1。2 。1任意拿三个1 2 3号球和9 10 11号 ...

) \  W; K* }& E7 x3 z5 t& ~ls好有耐心~~~$x8$

lewiss

原帖由 kolinsky 于 2007-12-29 19:30 发表
3 [: l5 O% i. o  T* Y$ r# u6 |再加点难度吧。
. t) l5 a  _, l5 a题设不变，在能给小球做记号的情况下请证明：

任给小球数量n>=4，当 4×3^(m-1) < n  

" L5 m+ w5 v! r' U8 n给个证明吧。。。

kolinsky

:( :( 最近要证明的东西太多了，你们先想想，我也是写的一个猜想，我觉得应该是能证出来的……
- P% ]/ _& X0 a: S5 _' |证明我也没有写过啊……

+ s8 H+ F; Q! U. o& y方法基本上都透露了，实在不行用归纳法证就可以了……

黯然消魂

原帖由 sofl 于 2008-1-6 03:34 发表
2 |8 Q7 O5 ?) C& Z& g3 \本题的解法很多  我列举一种吧  大家参考下，我称呼重量不同的为假球
. G2 V9 P' l9 u分组4  4  4个  
) h) U/ m0 x; y9 [8 W0 u) D+ p8 m一。拿如果4=4 则不同的球在最后4个里面 我给编号 9 10 11 12 ，前面的
       1。2 。1任意拿三个1 2 3号球和9 10 11号称 如 ...

看这个已经晕了

黯然消魂

做出来了，2种做法。

24个球 4步也做出来了，
, G% q4 N' x9 c3 H& L6 f36个球需要5步，， 4步是怎么做的—？

herzgut

n次二分法
12个球3步
- c: X2 j9 ~, d: K0 C% S24个球4步
8 P0 V1 R0 L1 Q36个球5步

黯然消魂

1 如果1 7 9=5 6 2 .....................式（2）
- u) a1 N% W0 {+ F! U4 @5 \0 ?   则假的在3 4 8里面，根据式（1）知假的重，拿其中2个再称一次就知道哪个是假的了


根据式（1）知假的重              不一定，可能是3或4 重，也可能是8轻啊？
不过这种分法作为第2步，3步也能得到正解的