Counterfeit Coin Challenge
Date: 05/12/2007 at 09:36:36 From: John Subject: Coin Challenge with 2 Light Counterfeits You are presented with a set of 13 suspect coins. Of these, it is known that the number of counterfeit coins is either 0 or 2. All of the counterfeit coins, if any, are known to have come from a single batch of light coins. You must identify the counterfeit coins, if any, after 4 weighings or fewer.
Date: 05/12/2007 at 13:23:59 From: Doctor Vogler Subject: Re: Coin Challenge with 2 Light Counterfeits Hi John, Thanks for writing to Dr. Math. The trick with these coins-on-a-balance problems is that the balance only distinguishes three different cases: (1) both sides weigh the same (2) the left side is heavier than the right (3) the right side is heavier than the left That means that one weighing on the balance can only tell apart three different scenarios. Two weighings can only tell apart 3^2 = 9 different scenarios. With n weighings, you can tell apart 3^n different scenarios. In your case, there are 13-choose-2 or 78 different ways that the 2 light coins could be hidden among the 13 coins, and one way that they are all identical, giving a total of 79 scenarios. That's pretty close to the optimum 81 scenarios you can distinguish with 4 weighings, so you don't have a lot of wiggle room. Your job is to figure out how to arrange coins on the two balance trays in order to divide those 79 scenarios as evenly as possible into three cases: (1) at most 27 scenarios where both sides weigh the same (2) at most 27 scenarios where the left is heavier (3) at most 27 scenarios where the right is heavier Then for each of those results, you need to decide how to arrange coins on the two balance trays in order to divide the at-most-27 scenarios into three more cases: (1) at most 9 scenarios where both sides weigh the same (2) at most 9 scenarios where the left is heavier (3) at most 9 scenarios where the right is heavier and so on. Does that make sense? If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 05/12/2007 at 14:52:36 From: John Subject: Coin Challenge with 2 Light Counterfeits You weigh: 1 2 3 4 5 6 against 7 8 9 10 11 12 Result #1: The balance remains in the middle. So Coin 13 is not a light coin You weigh: 1 2 3 against 4 5 6 Result #2: The balance tips to the left. 1 2 3 are normal and either 4 5 or 6 is light You weigh: 7 8 9 against 10 11 12 Result #3: The balance tips to the left. 7 8 9 are normal, second light coin is 10 11 or 12 ...too many options left open, first weigh needs to narrow more down.
Date: 05/12/2007 at 18:01:18 From: Doctor Vogler Subject: Re: Coin Challenge with 2 Light Counterfeits Hi John, Let's see if I can help you with that first weighing. You probably already noticed that you have to put some number (say n) of coins in the left side (and we might as well label these coins 1, 2, ... n), and the same number of coins in the right side (n+1, n+2, ... 2n). If the balance is level, that means that either (a) there is no light coin at all, (b) both light coins are in the 13-2n that we didn't weigh, or (c) one light coin is in each side of the balance. Of our original 79 scenarios, there is 1 for (a), (13-2n)*(13-2n-1)/2 for (b), and n^2 for (c), so the balance is level in 1 + (13-2n)(13-2n-1)/2 + n^2 scenarios. If the balance tips to the right, so the right side is heavier, then that means that either (a) there is one light coin in the left side and one unweighed, or (b) both light coins are in the left side. Of the original 79 scenarios, there are n(13-2n) for (a) and n(n-1)/2 for (b), so the balance tips to the right in n(13-2n) + n(n-1)/2 scenarios. Similarly, the balance tips to the left in n(13-2n) + n(n-1)/2 scenarios. You want to choose n so that all three of those numbers are less than or equal to 27. By the way, you should double-check your arithmetic to make sure that [1 + (13-2n)(13-2n-1)/2 + n^2] + 2*[n(13-2n) + n(n-1)/2] is exactly 79 no matter what n is. If not, then you didn't count where all of the scenarios go. Remember that every possibility will either leave the balance level or tip it one way. So how many do you think you should weigh first? And why? - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.