Pure Theory


Sunday, September 16, 2012

Golden Bag with False Golden Coin Problem

You are given 10 bags of gold coins. Nine bags contain coins that each weigh 10 grams. One bag contains all false coins that weigh one gram less. You must identify this bag in just one weighing. You have a digital balance that reports the weight of what is placed on it.

1st, The very native solution came to my mind is like: take 10 pieces from each bag, and we use binary search to find the false coins. First, we have five ten coins on each side, we will find the one which is lighter, then we choose the lighter one, repeat the previous action, until we have only one which is lighter than the other. This will take lg(10), 

2nd, This solution come from the "Solution."
1) Find an empty bag (labeled "E")
2) Place 1 coin from bag 1 into E
3) Place 2 coins from bag 2 into E
10) Place 9 coins from bag 9 into E
11) Place 10 coins from bag 10 into E
12) Weigh bag E on your digital scale

If all coins were 10 grams, the bag would weight 550 grams. Thus, 550 − weight will tell you how many coins are too light. Since this number of coins correlates to the bag from which the coins came, you now know which bag contains the light coins.
This is a pretty smart solution.