## 2008年4月15日 星期二

### 天秤找假幣（三）

#### 3 則留言:

Pop 提到...

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.

Marco_Dick 提到...

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.

Pop 提到...

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.

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?