All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Classic counterfeit coin problem (Posted on 2005-06-04)
In the famous "The Odd Coin" problem you are given twelve coins, exactly one of which is lighter or heavier than the other coins. You are to determine the counterfeit coin, and whether it is lighter or heavier than the other coins, in just three weighings with a balance.

Can you solve this problem with the additional restriction that you must decide what coins go on each pan for all three weighings before any weighing takes place?

Submitted by McWorter
Solution: (Hide)
One way to place the coins on the pans of the balance for the three weighings is to think of the numbers from 1 to 12 in the balanced ternary number system: base 3, digits 0, 1, and -1. Thus 2 has representation with units digit -1 and 3's digit 1 because 2=3-1. The number 7 has representation with units digit 1, 3's digit -1, and 9's digit 1 because 7=9-3+1.

We arbitrarily decide that when the left pan goes down it corresponds to the digit 1, when the right pan goes down, that corresponds to the digit -1, and when the pans balance, that corresponds to the digit 0. We also choose that the first weighing produces the units digit, the second weighing produces the 3's digit, and the last weighing produces the 9's digit.

Now we place the coins on the pans for each weighing as if they are all potentially heavy. So, since 1=1+0*3+0*9, we place 1 on the left pan in the first weighing, and on neither pan in the second and third weighings. Since 2=-1+1*3+0*9, we place coin 2 on the right pan in the first weighing, the left pan in the second weighing, and on neither pan in the third weighing. Continuing in this way, we determine where each of the twelve coins go.

Unfortunately, not all pans end up with exactly four coins. To remedy this problem we re-place coins 1, 6, 9, 11, and 12 as if they are potentially light coins. This requires special interpretation of the the outcome of the three weighings for these five coins, which we elaborate below. The final result of assigning coins to pans for the three weighings is below.

 left pan right pan neither pan first weighing 4,7,10,11 1,2,5,8 3,6,9,12 second weighing 2,3,4,6 5,7,11,12 1,8,9,10 third weighing 5,7,8,10 6,9,11,12 1,2,3,4

Now we can quickly determine the counterfeit coin. For example, if the weighing goes left pan down, right pan up, balance, then the counterfeit coin is 1+1*3+0*9=4 (recall that left pan down, equivalently, right pan up, is interpreted as caused by a heavy coin) and it is a heavy coin because 4 is positive. If the weighing goes left pan down, left pan down, left pan up, then the counterfeit coin is 1+1*3+(-1)*9=-5 meaning the counterfeit coin is 5 and it is light. If the weighing goes left pan down, left pan up, right pan up, then the founterfeit coin is 1+(-1)*3+(-1)*9=-11. Hence the counterfeit coin is 11, but because 11 is one of the special-handling coins, we report 11 is heavy instead of light (examination of the table confirms this).

 Subject Author Date re(6): Another way to answer it McWorter 2005-06-10 22:10:56 re(5): Another way to answer it Ken Haley 2005-06-10 04:39:39 re(4): Another way to answer it McWorter 2005-06-07 15:45:50 re(3): Another way to answer it Ken Haley 2005-06-07 06:08:50 re(2): Another way to answer it McWorter 2005-06-05 22:35:18 re: Another way to answer it Charlie 2005-06-05 17:43:52 Another way to answer it Jennifer 2005-06-05 11:36:10 re(2): Answer Ken Haley 2005-06-04 23:07:43 re: Answer Tristan 2005-06-04 23:04:11 re(2): No Subject TomM 2005-06-04 16:49:51 re: No Subject Sam 2005-06-04 16:29:40 No Subject jasper 2005-06-04 16:08:16 Answer Ken Haley 2005-06-04 16:01:20

 Search: Search body:
Forums (0)