Thursday, February 28, 2008

Puzzle - Counterfeit Coins

SQL Server Magazine (February 2008) has the following puzzle:

  • This puzzle is from Clifford Jensen. Suppose you have 10 stacks of coins, with 10 coins in each stack. One stack consists of 10 counterfeit coins and the other 9 stacks each consist of 10 legitimate coins. Each legitimate coin weighs exactly 1 gram. Each counterfeit coin weighs exactly 0.9 grams. You have a digital scale that’s graduated in tenths of grams. Using the scale to take only one reading, determine which stack has the 10 counterfeit coins. You can weigh any number of coins from any number of stacks, but must you weigh them all together (i.e., you can take only one reading from the scale).

It is obvious that the solution has to be one in which coins of all 10 stacks are used in some way. In order to distinguish one stack from another, we need to take different number of coins from different stacks. So one solution is

  1. Label the 10 stacks (arbitrarily) from 1 to 10
  2. Take n coins from stack n, where n = 1, 2, …, 10. Put them on the scale and take a reading.
  3. Focus only on the single decimal digit. If it is 9, then the counterfeit stack is stack number 1; 8: stack 2; 7: stack 3; 6: stack 4; 5: stack 5; 4: stack 6; 3: stack 7; 2: stack 8; 1: stack 9. So, if we let j be the decimal digit from the reading, then the stack with all counterfeit coins is stack number (10 - j).

No comments: