## 2008年3月27日 星期四

### 天秤找假幣（一）

1) 現在有 n 個金幣，已知其中一個是假的，而假的金幣重量與真的金幣不同，但我們不肯定是輕了還是重了。現在給你一個天秤，你每次可以在天秤的兩邊放一些金幣看看哪邊較重，還是兩邊重量一樣。問：

a) 若 n = 5，最少要秤多少次？
b) 若 n = 12，最少要秤多少次？

2) 情況跟第一題一樣，但今次有另外一個已被確定為真的金幣存在。當 n = 5 時，最少要秤多少次？

#### 5 則留言:

Pop 提到...

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.

Marco_Dick 提到...

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.

Pop 提到...

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.

Pop 提到...

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.

Marco_Dick 提到...

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?