第一張圖是有五個金幣，有一個是假（但不知是輕了還是重了），沒有已給定的真幣時，其中一個需要三次才能確保找出假幣的方法。這也是我在「天秤找假幣（一）」問的問題1(a)。
第二張圖是有五個金幣，有一個是假（但不知是輕了還是重了），有一個給定的真幣時，需要兩次能確保找出假幣的方法。這也是我在「天秤找假幣（一）」問的問題2。
在兩張圖，一開始時我們都不能確定哪一枚金幣是假，亦不能知道假幣是輕了還是重了。所以一開始時有10個可能性：1較輕、1較重、2較輕、2較重、3較輕、3較重、4較輕、4較重、5較輕、5較重。而在兩個樹形圖的最低部分，都有10個黃色格，表示這10個可能性。
因為我們是用天秤的，所以每次只有三個可能的結果：左邊較輕、左邊較重或兩邊等重，亦即是說在上面的樹形圖中，每個格最多只有三個在下方與它相連的格。若樹形圖只有一層，則最多只能有31=3個黃色格；若樹形圖有兩層，則最多有32=9個黃色格；若樹形圖有三層，則最多有33=27個黃色格。
因為兩個情況下我們都會有最少10個黃色格（對應剛說明的10個可能性），所以樹形圖最少有三層，亦代表最少秤三次才能找出假幣，並判斷它比真幣重了還是輕了。
但我們的問題並不需要判斷假幣是重了還是輕了。所以當遇到上圖的藍色格時，我們已經知道哪個金幣是假，即使不知道它是重了還是輕了，我們也完成了任務。因此在第二張圖，我們最多只需秤兩次。
在上次的問題1(b)，我們最少會有12個藍色格，因此樹形圖最少有三層，亦代表最少要秤三次才能找出假幣。若我們要求找出假幣是輕了還是重了，則我們要有最少24個黃色格，也是最少三層的樹形圖也能做到這點，而上一次我們已說了用三次秤的方法，大家有興趣不妨根據那個方法畫畫相對的樹形圖。
但在問題1(a)，我們可能可以有5個藍色格，那樣兩層的樹形圖是可行的。為甚麼我宣稱秤兩次是不可能呢？這需要用到另一個技巧：backward induction。
在問題1(a)，我們一開始只可能有兩種放法：1 vs 2 或 1,2 vs 3,4（這裏指每邊放一個金幣或每邊放兩個金幣；其他的放法不會給我們帶來任何information）。
若使用 1 vs 2 而兩邊等重時，則我們所遇的問題變成：「有三個幣，其中一個是假（不知輕重），而有兩個確定為真的金幣」。這時我們可以考慮的秤的方法並不多，只有 3 vs 4、1 vs 3、 1,3 vs 4,5 、 1,3 vs 2,4。易証使用四種方法均不能只秤一次就保証判斷到假幣。
若使用 1,2 vs 3,4而兩邊並非等重時，1、2、3、4都有可能是假幣，根據我剛剛介紹的「樹形圖分析」，只少要多秤兩次，即要解決整個問題需要秤三次。
3 則留言:
wow macro,you spend so much effort.
share some results.
The keys:
1)f(H+L<=3^k) = k
2)T(i)= 2, 5, 13, ...
f is the function to returns the min iter. k for remaining H suspected heavier coins and L suspected lighter coins.
sketch the proof:
i) f(H+L=1) =0
ii) f(H+L=2) =1
iii)f(H+L=3^k)=k (induction)
iv) f is "monotonic increasing"
[0<= f(n+1)- f(n) <= 1]
The min. iter. can be reduced by 1 when no. of coins n of system is belongs to T(i).
combine f and T, with some more arguments, we can setup the general solution.
Hi, pop.
For i), trivial. For ii), I guess you mean there is at least one reference coin, right? But I am not sure how iii) and iv) is going (although iv) sounds obvious...).
Also, when n=13, the min. iterations required is 3. I am not sure what 13 means in f, it means H, L, or H+L? But it sounds that all these will make f returns 3.
ii) macro, u r right as assume the situation happens only when weighted some coins and unbalanced.
iii)
n=3^0 - true
n=3^1 - true, can show it easy.
assume n=3^k true
then for n=3^(k+1)
separate the n coins into 3 parts each 3^k to weight
a) if either H or L is less than 3^k, say L, then weight
3^k (H) v 3^k (H) and remains(H) + L = 3^k
so if balance or not, it returns to 3^k unsure coins problem, thus (1+k)iter.
b) if neither H nor L is less than 3^k, then we need to massage the H and L such that
(H1 + L1) v (H1 + L1) and remains (H2+L2)
H1+L1 = 3^k, so if unbalance, say LHS heavier, pick LHS (H1) and RHS(L1) and returns to 3^k unsure coins problem. ....
iv)0 <= f(n+1)-f(n) <=1
assume f(n+1)-f(n)>1
say f(n)= x,
for f(n+1), put aside 1 unsure coins first, then for remaining n coins we have f(n)=x
finally, f(n+1) <= 1 + x iter.
contradiction.
so f( H+L<=3^k ) = k
2) there is a typos in previous post, T(i) = 2, 5, 14...
Define g(n) is the required iter for system with n coins.
In yr questions
1a) n = 5, g(5)=3
1b) n = 12, g(12)=3
2) n = 5 plus 1 reference g(5,1)=2
it is not diff. to show g is also "monotonic increasing"
ok, T(i) is the no. of coins n for the system(like your question 2, n=5) at round 0 such that add 1 more reference coin can reduced the iter. (no relation to f)
n=2, if no reference coin, no solution. if add 1 reference coin then need 1 iter. to find the unknown.
n=3, we know it requires 2 iter.
so what max. value of n such that the required iter. is still 2?
The answer is n =4
(1 v 1) + 2 = 4
reasons:
if 1 v 1 unbalanced, then by f(2<3)=1, need 1 more iter.
if 1 v 1 balanced, then we have reference coin for remains 2 unknown, so need 1 more iter.
To be continued...
張貼留言