Fog Creek Software
Discussion Board




PROVE THIS IF U CAN

general solution to the classic weighing problem


in general if you know either the coin is heavier or lighter you can find the coin out in n weighings among  3^n coins (at the maximum). (note: if the number of coins falls between 3^(n-1) and 3^n you would still require n weighings)

however if you just know its a counterfeit one i.e you do not know if its heavier or lighter you can find out the countefeit coin in n weighings among (3^n - 3)/2 coins. (note: if the number of coins falls between (3^(n-1)-3)/2 and (3^n - 3)/2 you would still require n weighings)


can anyone prove either of the above mathematically ..if so please mail me the solution.

Abyss
Wednesday, June 15, 2005

Ok let me prove the first One.
Its through decision tree
Let you have 3^n coins.
At root you start and divide the Coins in three equal pairs (initially the it is multiple of 3).
Now weighting any two of them and deciding will localize our poblem to the 3^(n-1) coins only. Doing the same process reapeatingly  to the leave level we need only n comparision.

Deepak Pant
Thursday, June 16, 2005

The proof for the first one was relatively easy and has been suggested by deepak.

how about the second one?

Abyss
Thursday, June 16, 2005

*  Recent Topics

*  Fog Creek Home