最近在科大的TA房裏流行互問智力題。假假地都叫做準碩士或者準博士，智力題當然也不止是「無聊IQ題」（謎之聲：咁即係有「無聊IQ題」啦！）。今天來三個「天秤找假幣」的經典問題。這類問題可謂老少咸宜，大家不需要甚麼prerequisite就可以理解問題，然後想出答案。
1) 現在有 n 個金幣，已知其中一個是假的，而假的金幣重量與真的金幣不同，但我們不肯定是輕了還是重了。現在給你一個天秤，你每次可以在天秤的兩邊放一些金幣看看哪邊較重，還是兩邊重量一樣。問：
a) 若 n = 5，最少要秤多少次？
b) 若 n = 12，最少要秤多少次？
2) 情況跟第一題一樣，但今次有另外一個已被確定為真的金幣存在。當 n = 5 時，最少要秤多少次？
經過一段時間的思考後，可能你心中會有一個解法。但，你怎能確定你的解法是最少的呢？若你的答案需要多於一次，你難保其他人能想出比你更少次數的解法。
這就是下一篇文章我想說的東西。
5 則留言:
Condition: Only 1 Coin is abnormal but maybe lighter or heavier.
Let
C = unknown condition coin
N = confirmed normal coin
L = coin which is lighter than or equal to normal coin
H = coin which is heavier than or equal to normal coin
V = 天秤
To find 最少要秤多少次, we need to consider the worse/best outcomes of each method for comparison. However, 最少 means best scenario, worse scenario or the Expectation
1a) We have 5C.
Method 1 (1V1)
Round 1
1C V 1C
Two possible outcomes:
(i) 2N, 3C ( Pr(E(i) = 3/5 )
(ii)1L, 1H and 3N (Pr(E(ii) = 2 /5 )
compare (i) and (ii), the worse case is (i) as ( 3C > (1L+1H) )
for (i)
Round 2
2N V 2C
Two possible outcomes:
i-1) 2L or 2H, 3N ( Pr(Ei-1) = 2/3 )
i-2) 4N, 1C (End as we don't need to know it is lighter or heavier)
( Pr(Ei-2) = 1/3 )
For (ii) and i-1), only need 1 more round
1L V 1N or 1H V 1N
Both 2 possible outcomes indicates which is the abnormal coin.
So Method 1 best scenario is weight 2 times, worse scenario is 3 times and expectation =(3/5)(2/3)*(3) + (3/5)(1/3)*(2) + (2/5)*(2)=(6/5)+(2/5)+(4/5)=12/5 = 2.4.
Method 2 (2V2)
Round 1
2C V 2C
Two possible outcomes:
(i) 4N, 1C (end!) (Pr = 1/5)
(ii)2L, 2H and 1N (Pr = 4/5)
For (ii),
Round 2
1H 1N V 1H 1L
Three possible outcomes:
ii-1) 4N, 1L (end, 1L is the answer) (Pr = 1/4)
ii-2) LHS heavier (i.e. RHS lighter) so 1H, 1L and 3N (need 1 more rnd as similar as 1a) (Pr = (3/4)(2/3)= (2/4) )
ii-3) RHS heaver so 4N, 1H (end)
(Pr = (1/4))
So Method 2 best scenario is weight 1 times and worse scenario is 3 times and expectation = (1/5)*(1) + (4/5)(2/4)*(2) + (4/5)(2/4)*(3) = (1/5)+(4/5)+(6/5) = 11/5 = 2.2
For n=5, only these 2 Rational methods.
so Method 2 is the best.
Thanks pop for posting such detailed solution for 1 a).
Actually I want to discuss worst bound of "comparison based sorting" in this series later. Your expectation evaluation reminds me one thing: average analysis that is very common in Algorithm Analysis.
Looking forward to reading your solution for 1 b) and 2.
I posted similar detailed solution for 1b) in MathDB before. So, let others try 1b) and 2).
However, I would like to "claim" a Algorithm/Logic to compare which method is the best for worst scenario.
Define this kind of problem as
L(T, A, N, H, L) where T is total no. of coins, A is no. of abnormal coins and N is no. of confirmed normal coins.
e.g
1a) is L(5, 1, 0, 0, 0)
1b) is L(12,1, 0, 0, 0)
2) is L(6, 1, 1, 0, 0)
[No solution for L(n=2,1,0)]
KU - no. of certainly unit,
RU - no. of relatively uncertainly unit, i.e. Heavier or Lighter
AU - no. of uncertainly unit,
TU - Total uncertainly value
TU = AU + {0,(RU+1)/2 -if RU>0 }
If I know nothing about a coin, uncertainly is 1; if i know it is H or L, then uncertainly reduced half. Game ends when TU <= 1.
Take 1a) as example.
L(5, 1, 0)
Mthd__Rnd___Outcome__KU_RU__AU_TU
______0_______________0___0___5___5
1V1__ 1______"="______ 2___0___3___=3
_____________"<>"______3___2___0___=3/2
2V2__ 1______"="______ 4__ 0___1___=1
=> L(5, 1, 4, 0, 0)
_____________"<>"______1___4___0___=5/2
=> L(5, 1, 1, 2, 2)
For worst scenario comparsion,
1v1 max.(TU) = 3; 2v2 max.(TU) = 2.5
so 2v2 would have the minimum iteration to get the required coin as it provides least uncertainly after round 1.
For 1b)
L(12,1, 0), the initial uncertainly is 12.
There are 6 rational methods for rnd 1 ( A V A , where A =1,2,...,6).
Let 12 = 2A + B, B=12-2A
if rnd 1 outcome "=", TU = B
if rnd 1 outcome "<>", TU = (2A+1)/2
The worst scenario of each method is Max.{ (2A+1)/2, B }
To select the best method = Min.(Max.{ (2A+1)/2, B })
By this algorithm(recursive), we can write program to find the best method for Rnd1, Rnd2 ...till the game end.
==================================
So claim
for L(C=3N, 1, 0),
best method N V N
for L(C=3N+1, 1, 0),
best method rndown(C/3) V rndown (C/3)
for L(C=3N+2, 1, 0),
best method rndup(C/3) V rndup (C/3)
and it would produce the best method in terms of average(expectation).
=========================
It requires more effort to generalize (with detail proof / explanation) to support above alg. is correct.
Last nite, I read the solution from 黃俊偉. However, I find an counterexample to his solution.
for N=13, L(13, 1, 0, 0, 0)
base on above alg. and the result of 1b) and 2), I know N=13, min iter. is 3.
L(13, 1, 0, 0, 0) after Round 1
=>L(13, 1, 5, 4, 4) or L(13, 1, 8, 0,0)
L(13, 1, 5, 4, 4) >= L(12, 1, 4, 4, 4) (Q1b)
L(13, 1, 8, 0, 0) >= L(6, 1, 1, 0, 0) (Q2)
>= means with better information and should have less than or equal to iter.
(remove 1N from L(13-1, 1, 5-1, 4, 4)
(remove 7N from L(13-7, 1, 8-7, 0, 0)
I think his solution missed to consider the situation after rnd 1, it may become Q2 situation.
oh...Carto Wong's solution included to identify the abnormal coins is heavier or lighter. (a little difference to our question)
His conclusion should be correct thru' there are some mistakes.
Sorry for the late reply. I have been busy coding these days.
I think your claim may be provable by using Mathematical Induction. I would try this method to prove it later.
I am not sure where the proof from Carto is. May you point it out?
張貼留言