Brain teaser

9个球，重量为1,2,3,...,9，外表一样，但是我可以区分，你却不能。
有一个天平，问至少我称给你看几次，你可以区分得出这9个球？
（copyright:多年前一个哥们问我的）
至于一般情况（n个球）是怎么回事我还没搞清楚。

发信站: BBS 未名空间站 (Thu Jan 4 17:12:12 2007)

there are several solution with 4 times

but I only have one with 3

the key is to maximize the utility of the 3rd time by taking the advantage
of the fact that the scale has two sides.

First I show you

1+2+3+4+5<7+9

then you know it is one of the following three ordered sets

a: (1,2,3,4,5),(7,9).(6,8)
b: (1,2,3,4,5),(8,9),(6,7)
c: (1,2,3,4,6),(8,9, (5,7)

next I show you

1+2+3+7<6+8

since 1,2,3,7, are the smallest in (1,2,3,4,5), (7,9) and no other selection
could produce such an inequality, then you know we are in case (a) and know
the ball weight 7 and 9 now.

and now before you eyes, you know the left balls are ordered as
(1,2,3),(4,5),(6,8)
then I show you
1+4+6<3+9
since 1,4,6 are the smallest in each set, and 3 is the largest in (1,2,3)
then you know which is which~

I hope I made no error :)

My way of sorting them in 3 times.

1. a+b+c+d+e=f+i
You then sort them into 3 groups. (a,b,c,d,e) is (1,2,3,4,5); (f,i) & (g,h)
are (6,9) or (7,8)

2. a+b+f=d+e
Then you know (a,b) is (1,2), c is 3, (d,e) is (4,5), f is 6, (g,h) is (7,8)
and i is 9.

3. a+d+g=c+i
Then you got it.