Newsgroups: rec.puzzles From: hoey@aic.nrl.navy.mil (Dan Hoey) Date: 30 Sep 1994 15:10:24 GMT Subject: Re: An interesting riddle posit...@Starbase.NeoSoft.COM (Jonathan Haas) writes: > You have twenty-nine thousand, five hundred twenty-three coins. > One is counterfeit and is either lighter or heavier than the others. > Using only *ten* weighings on a balance scale, determine which > is counterfeit, and whether it is lighter or heavier. I don't know why he didn't bother to mention this is a FAQ problem. The archive solution, while elegant, isn't too explicit about the actual working of the process, though. Also, the archive answer ends up with a lot of cases of putting unnecessary coins on the scales. eua...@eua.ericsson.se (Goran Wicklund) tried to answer the problem explicitly, but he got it a little wrong in the details, so that his method will sometimes require eleven weighings instead of ten. In particular, if the first eight weighings test equal, he will eliminate (9837+9837)+6561+2187+729+243+81+27+9 = 29511 coins, leaving 12. Then as he says ``three weighings left = the original problem!'' But after 8 weighings he doesn't have three weighings left, only two. The following is an explicit explanation with all the gory details, derived using the archive solution, of just how the coins may be weighed. You may prefer to skip to the ObPuzzle at the end. The first step, given W weighings to measure the odd coin among (3^W-3)/2 unknown coins, is first to weigh (3^W-3)/6 coins against (3^W-3)/6 others. Here we will have 9841 coins on each pan. If they test equal, we will have 9841 suspect coins left and continue; if not we will skip to the If the first weighing tests equal, we repeatedly test 3^(W-1) of the suspect coins against the same number of known good coins, as long as they test equal. Table 1: Continue as long as balance tests equal. SETUP : TEST : RESULT Weighing Number of: Number of :Number of Number of number suspect : suspect coins :suspect coins suspect coins coins : to weigh :left if equal if unequal : : 2 9841 : 6561 : 3280 6561 3 3280 : 2187 : 1093 2187 4 1093 : 729 : 364 729 5 364 : 243 : 121 243 6 121 : 81 : 40 81 7 40 : 27 : 13 27 8 13 : 9 : 4 9 9 4 : 3 : 1 3 10 1 : 1 :won't happen 1 The reason we can measure 13 coins in the last three weighings is that we have a supply of good coins to weigh them against, so when inequality occurs we know whether the bad coin is heavy or light. Goran outlined how to identify the bad coin out of 3^(W-1), using W-1 weighings. If the first weighing tests unequal, then we have 9841 coins in the light set L and 9841 coins in the heavy set H, together with a set of known good coins. In general, we have (3^W-1)/2 in each set to solve in W weighings. Our procedure is on each weighing to put (3^(W-1)-1)/2 coins from H and 3^(W-1) coins from L in the left pan, and (3^(W-1)-1)/2 coins from L and 3^(W-1) good coins in the right pan. If they test equal, we have completely eliminated L, and have only the other 3^(W-1) other coins from H to test, as above. If the left pan tests light, then we have the 3^(W-1) right-pan coins L in the left pan to test, as above. If the left pan tests heavy, then we have the (3^(W-1)-1)/2 left coins from H and the (3^(W-1)-1)/2 right coins from L to test, using this procedure. Table 2: Continue as long as left pan tests heavy. SETUP : TEST : RESULT WeighingSize:Left pan Right pan:Equal: Left Left number of : H L L good: Size Light: Heavy: Size L = H:coins coins coins coins: of H Size of L of L, H : : 2 9841: 3280 6561 3280 6561 : 6561 6561 3280 3 3280: 1093 2187 1093 2187 : 2187 2187 1093 4 1093: 364 729 364 729 : 729 729 364 5 364: 121 243 121 243 : 243 243 121 6 121: 40 81 40 81 : 81 81 40 7 40: 13 27 13 27 : 27 27 13 8 13: 4 9 4 9 : 9 9 4 9 4: 1 3 1 3 : 3 3 1 10 1: 0 1 0 1 : 1 1 won't happen > The different outcomes of 10 weighings are 3^10=59049. This can > point out 59049/2 = 29524.5 i.e. 29524 considering that the false > coin can be lighter or heavier. The problem contains 29523 coins, > i.e. one less than the theoretical maximum. Or put it in other > words, the solution will contain three redundant states (outcome > of weighings). These occur in weighing 10, were, for some of the > possibilities, the result "in balance" can not occur. The theoretical maximum is actually easily seen to be 29524, because any scheme that admits the possibility of always testing equal will, in that case, not determine whether the bad coin is heavy or light. I don't know an obvious way of showing that the odd coin can't be measured from (3^W-1)/2 coins in W weighings. In fact, we know it can be found from Table 1, provided that we have at least 3^(W-1) known good coins. But is that the minimum number of good coins needed? ObPuzzle: What is the minimum number of known good coins needed to find the one odd coin from (3^W-1)/2 suspect coins, and to find whether it is heavy or light, in W weighings on a balance scale? Dan Hoey Hoey@AIC.NRL.Navy.Mil