Identifying counterfeits with a digital scale.

[Guv]

Another thread mentioned a problem involving 12 balls and a balance scale.

There are some interesting problems using a digital scale that provides exact weights.

The following two are theoretical problems, not practical ones. In practice, it would be better to use more weighings.

There are 15 piles of coins, 14 of which contain genuine coins, all of the same weight. The 15th pile contains counterfeit coins, all of the same weight, but different from the weight of a genuine coin. Each pile contains as many coins as you would like. You have a digital scale which provides the exact weight of any objects put on it. Using the scale three times, determine which pile contains the counterfeit coins.

Similar problem with 15 piles: 5 contain counterfeits and 10 contain true genuine coins. In three weighings determine the counterfeit and genuine piles.

The weight of neither a genuine nor a counterfeit coin is known.

[WorkHorse]

Ok, I'm not very good at this, but I'll have a shot. I don't need many coins--16 from a pile at most.

I weigh 1 coin from pile 1. For now, I'll assume that is the genuine weight value. Then for each pile n, I weigh n number of coins from each pile (1 from pile 1, 2 from pile 2, 3 from pile 3, etc.) Next I weigh n+1 coins (2 from pile 1, 3 from pile 2, etc.)

Now I calculate expected value for Weigh2 & 3 using assumed genuine weight value (weight of 1 coin from pile 1). Then I calculate the difference between the expected values and the actual values. I subtract the difference for Weigh2 from the difference for Weigh1. Now I take the difference for Weigh2 and divide by that value. This give me a close estimate of the counterfeit pile. I round it to the nearest tenth. If it is 8.5, then pile 1 is the counterfeit pile. Otherwise, the rounded value is the counterfeit pile. I've attached an Excel sheet that does that calculations. You have to enter the weights. The gray areas are the values you don't know. You can enter a value nest to TestCount and it will try that many calculations. It will let you know if there is an error. (It is only acurate to 11 decimal places.)

I think my checking value of 1 coin is clumsy. There should be a better way (I think). The second problem is hard using this method, which leads me to believe there is an easier way to do this that would also solve problem 2 (probably increasing the number coin weighed exponentially, I'm guessing). :)

[Guv]

WorkHorse: You seem to have a good basic idea of how to solve the first problem. I did not analyze your solution, but it seems to be workable.

Another approach is as follows.

Weigh the total of 1 from pile 1, 2 from pile 2, et cetera.
Weigh the total of 1 from pile 15, 2 from pile 14, et cetera.

If the weights are the same, pile 8 (the middle pile has counterfeit coins). 8 coins from that pile were included in both weighings.

If the weights are different, pile 8 has genuine coins. Weigh one of them to determine the weight of a genuine coin. Given this value, you can calculate what the weighings would be if all coins were genuine.

The first two weighings provide two equations which can be solved for two unknowns.

Assign an unknown (say Dx) to the difference between the weight of a good coin and the weight of a bad coin. The other unknown is the pile number containing the counterfeit coins.

Solving the two equations is a bit of work, but not conceptually difficult.

The solution to the second problem is trickier. It requires picking a coin, weighing it, and assuming that it is a genuine coin (Same initial start as your solution to the first problem). Then weigh the total of one coin from each pile, giving the following equation.

Weight2 = 15 * GenuineWeight + 5 * Dx, solve for Dx (which might be incorrect)

Then weigh the total of 1 from pile 1, 2 from pile 2, 4 from pile 4, 8 from pile 8, 2n from pile n. This of course is neat theoretically, but stupid from a practical point of view.

You can calculate the expected weight if all coins were genuine. The difference betwen this value and the actual weight is some number. Divide that number by Dx, and express the value in binary. The one bits correspond to the pile numbers of counterfeit coins.

If some impossible result occurs, the coin you assumed was genuine (the first weighing) was actually a counterfeit. Redo the calculations using this new data.

This method would work for almost any problem of this type. An exception would be 2n piles with n containing counterfeits. You could identify two sets of n piles, but would not know which set contained counterfeit coins.

[WorkHorse]

Good stuff.

1) Can you explain this for problem 1: With my formula, when coin 1 is the couterfiet coin, the calucaltion is always 8.5. Why? I would have expected 7.5 (the average of the number of coins.) In summary, what I did was weigh one coin for the genuine value. I weigh n+1 coins and then n+2 coins. I subtract the difference between the actual values and the values that would result if all coins were genuine. The difference between the two weights is the constant difference between genuine and counterfieet (I think). So, take that difference and divide by the larger amount (Weigh2), we get the pile that has the counterfiet. But if the first coin we weighed is wrong, we get what you call "some impossible result". But the value is always 8.5 when the coin from pile 1 (the guess of a genuine coin) is in fact counterfiet. Why?

This is like Enum and vb constants: spread the possible values out over max values so that you can add them together and know what combination of values were selected.

2) Do you think this can be solved with only two weighs? I have a hunch that it can. I think average weights between two mesurement would give enough to indicate counterfiet values (you wouldn't know the actuall genuine & counterfiet weights, but you could tell which ones don't match). How about a new challenge to do this with two weighs (think it can be done?) :confused:

[Guv]

Workhorse: As posted earlier, your approach is basically correct. The three weighings you describe will lead to the correct solution. I checked it out using MathCad, which is a very handy application. It is for those who cannot afford Mathematica.

There are three fundamental unknowns in this problem, which involves 15 piles of coins, with one pile containing counterfeits. The weight of a genuine coin The weight of a counterfeit coin n, the number of the pile containing counterfeits.Each use of the scale can provide an equation. Three equations in 3 unknowns can provide a solution. Two equations cannot, except in the special case of pile 8 containing counterfeits (see below). In the special case, you can determine that pile 8 contains counterfeits using only two weighings, knowing neither the weight of a genuine nor the weight of a counterfeit.

I looked at your Excel Spread sheet for about 10 minutes, and do not understand it well enough to know how it functions. Perhaps if I spent some more time with it, it would become clear. Hence, I cannot answer questions about your results. Using your method, some algebra can provide the solution, and seems easier than the spreadsheet.

Using your technique, the following formulae apply.Weight1 = Good (assumed)

Weight2 = 120 * Good + n * Delta

Weight3 = 120 * Good + (n + 1) * Delta

Bad = Good + Delta, or Good = Bad - Delta

In the above, n is the number of the bad pile. Good and Bad are the weight of a genuine and of a counterfeit coin, respectively.

Delta = Weight3 - Weight2, even if Weight1 is the weight of a counterfeit coin.

n = (Weight2 - 120*Good) / Delta

Bad = Good + DeltaIf you substitute Weight1 for Good in the last two formulae, you expect to get reasonable results. If the results are not reasonable, you know that Weight1 is the Weight of a counterfeit coin. However, you know that the calculated value of Delta is correct, and can calculate the weight of a Good coin for substitution.

My solution was to weigh 1 from pile 1, 2 from pile 2, 3 from pile 3, et cetera (Same as your second weighing). Then weigh 1 from pile 15, 2 from pile 14, 3 from pile 13, et cetera. If the first two weights are the same, pile 8 contains counterfeits. If the two weights are different, pile 8 contains genuine coins. For the third weighing, weigh a genuine coin. The formulae are as follows.Weight1 = 120 * Good + n * Delta

Weight2 = 120 * Good + (n - 1) * Delta

Weight3 = Good

Bad = Good + Delta, or Good = Bad - Delta

In the above, n is the number of the bad pile. Good and Bad are the weight of a genuine and of a counterfeit coin, respectively.

Delta = Weight1 - Weight2Knowing Delta and the weight of a genuine coin, you can easily determine n and the weight of a counterfeit coin.