Minimal Weighings of Ten Coins to Identify the Two CounterfeitsDate: 04/18/2010 at 03:19:13 From: ching Subject: weighings Suppose you have a balance scale and 10 similar coins, but 2 of them are fake. The counterfeits have the same weight, but are lighter than the real ones. At least how many weighings on the scale do you need to find the fake coins? I think you need at least three weighings to identify the fake coins. Since the question asks "at least how many ...," you have to consider the best case scenario. First, split the coins into two piles. If you are lucky, you can determine immediately which group of 5 contains the fake coins because it is lighter than the other. Next, get one coin from the pile with all the real coins, setting aside the rest of that pile. Take that coin you know to be real and add it to the pile of five that contains the two fake coins. If you are lucky again, when you split those six coins into two piles and put them on the scale, you can find in the first try which pile of three contains the two fake coins. Set aside all the real coins, add one real coin to the group that contains the fake coins, then separate them into piles of two. If you are lucky for the third time, you will find out which group of two coins is lighter -- and those are the two fake coins. Date: 04/18/2010 at 05:52:23 From: Doctor Jacques Subject: Re: weighings Hi Ching, I think you misunderstood the meaning of "the least number of weighings." If you only consider the best case, there is a solution (involving a lot of luck) in two weighings: * Place one coin on each pan. If you are lucky, one of the coins is counterfeit. * Place two other coins on the balance. If you are still lucky, one of these is also counterfeit. The way I understand the question, you must attempt to find a procedure that works in _all_ cases, i.e., to find a procedure in N weighings that will always allow you to identify the fakes. You are only required to find a lower bound w on the number of steps. In other words, you want to prove that no procedure in fewer than w weighings will give you the solution in all cases. Of course, if you find a procedure in N (>= w) weighings, that would be better still; and the best would be to find a procedure in exactly w weighings, if such a procedure exists. But this may be to hard to find. In this kind of problem, you must compare the number of possible answers to the number of possible experimental outcomes. If the problem can have x different answers, and the procedure can give y different results, you must have y >= x to allow you to discriminate the results. In this case, the number of answers is the number of subsets of two elements in a set of 10, namely C(10,2) = 45. This means that your procedure must give at least 45 possible results. A single weighing can give 3 results: left pan heavier, right pan heavier, or equilibrium. In a procedure with w weighings, the number of results is 3^w: each additional weighing multiplies the number of results by 3. To give at least 45 answers, you must have 3^w >= 45, which means that you must have w >= 4, since 3^4 = 81 > 45 and 3^3 = 27 < 45. This proves that no procedure in fewer than 4 weighings will work in all cases; but it does not prove that there exists an effective procedure in 4 weighings (I don't know if such a procedure exists). Note that there is a solution in a finite number of weighings: you can simply weigh together all the 45 possible pairs of coins. If you want to try to find an effective procedure (not that you are required to do that, but it may be fun), you should try to ensure that, after each weighing, the number of remaining possible answers is at most 3^k, where k is the number of remaining weighings. This must be true for each of the possible outcomes of the previous weighing. Usually, you should try to ensure that each weighing splits the number of remaining possibilities in 3 almost equal parts. Let me illustrate this with an example. Let us try to see if we can start by weighing 3 coins against 3, i.e., we place coins {1,2,3} on the left and coins {4,5,6} on the right. If we have equilibrium, there are two possible cases: case 1: the two bad coins are in the remaining 4 coins not on the scale. This gives C(4,2) = 6 possibilities. case 2: one bad coin is in each pan. There are 3 possibilities for each pan, for a total of 9. To summarize, if we have equilibrium, there are 6 + 9 = 15 remaining answers. If the left pan is heavier, we have also two possible cases: case 1: the two bad coins are in the right pan. This gives C(3,2) = 3 possibilities. case 2: one bad coin is in the right pan, and the other one is mixed in with the remaining coins. There are 3 possibilities for the first coin, and 4 for the second coin, for a total of 12. In this case, we again have 3 + 12 = 15 possibilities. If the left pan is lighter, the result is the same, by symmetry: we also have 15 possibilities. We see that, whatever the outcome of the first weighing, we are left with 15 possibilities, for a total of 45, as it should be. This means that it may be possible to continue the procedure in 3 weighings, since 3^3 > 15. In addition, as we have split the possibilities equally, we may hope that this is the best we can do (although this is not a proof). The next step would be to devise the second weighing in such a way that, for each possible outcome, the number of remaining possibilities is at most 3^2 = 9. Note that the second weighing may depend on the outcome of the first. We may also ask if our choice of 3 + 3 for the first weighing is the only possible choice. If we try to weigh one coin against another, in case of equilibrium, we have the following remaining possibilities: case 1: one bad coin in each pan; this is one possibility. case 2: two bad coins in the remaining eight. This is C(8,2) = 28 possibilities. This gives a total of 29 possible answers in case of equilibrium. As 29 > 3^3, we cannot hope to finish the procedure in 3 steps. On the other hand, if I am not mistaken, each of the other choices (2 + 2, 4 + 4, 5 + 5) leaves a number of possible answers less than 27. However, the choice 3 + 3 splits the answers equally in three groups of 15, which means that the worst case is at most 15, and this is less than for the other choices. This suggests trying 3 + 3 as the first weighing. Since you are not required to do so, I don't know if you want to try to find an effective procedure. But if you do, beware that this may involve a lot of work -- and I'm not sure that such a procedure (in 4 weighings) exists. Please feel free to write back if you require further assistance. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/