Coin weighting problems.

[Guv]

Years ago, mathematicians fooled around with various coin weighing problems. Perhaps you folks might like to have a try at solving some of them.

The basic idea is that true and counterfeit coins can only be distinguished due to a difference in weight. All true coins have the same weight. All counterfeit coins have the same weight. In none of the problems do you have a true coin available for comparison purposes.

Here are three problems.

First problem.

You are given 12 coins, one of which is counterfeit, and a balance scale. In three weighings, determine which coin is counterfeit and determine whether it is lighter or heavier than the true coins.

Second problem.

An emperor has 15 kings who pay tribute in coins of the realm. There is a ceremony in which each king places a pile of coins in front of the emperor. One year, a spy tells the emperor that one of the kings is going to pay him in counterfeit coins. Before he can identify the culprit king, he is killed by an arrow from an unknown source.

Using a scale which will give the exact weight of any number of coins put on it, the emperor intends to start weighing one coin from each king's tribute. To identify the counterfeit pile of tribute, the weight of a true coin, and the weight of a counterfeit, he figures to use the scale at most 15 times. If lucky, he will use it only 3 times.

A court mathematician tells him the following.Your plan might be the fastest method, but in theory you can always solve the problem in three weighings, assuming there are enough coins in each pile of tribute, and it looks to me as though there are enough coins for the solution I have in mind.Can you think of the mathematician's solution to this problem?

Third problem.

Several years later: Same emperor with 15 kings paying tribute. This time the emperor is told that 5 of the fifteen kings are crooks paying in counterfeit coins. This time the mathematician says.You should start weighing one coin from each pile. I do not think there are enough coins in each pile of tribute to solve the problem in 3 weighings, but in theory it could be done with really big piles of coins. In practice, no non-mathematician would consider the solution I have in mind., but we mathematicians enjoy thinking about cute theoretical solutions to such problems.What did the mathematician have in mind?

[paulw]

Come on then - you've got me hooked...

Spill the beans.

P.

[Guv]

12 coin solution starts with weighing four versus four. You have to be able to distinguish the 12 coins, perhaps by pasting a piece of paper on each and assigning letters A-L or numbers 1-12 to the coins.

If scales balance, the counterfeit is one of the remaining four, and the 8 which were weighed are true coins usable in the next weighing. Weigh 3 of the four suspect coins versus 3 true coins. If they balance, the last coin is counterfeit and the third weighing is used to determine whether it is light or heavy. If the three suspect coins do not balance, you know whether the counterfeit is light or heavy. Now weigh one suspect versus another. If they do not balance, the second weighing tells you which one is counterfeit. If they balance the third suspect is the counterfeit, and second weighing tells you whether it is light or heavy.
If 4 versus 4 in first weighing do not balance, it gets tuff. One of the eight coins weighed is the counterfeit, and the remaining four are know to be true coins. Record which 4 were on the light side and which were on the heavy side. For the second weighing: Leave three of the possibly heavy coins on the scale; Remove three of the possibly light coins, replacing them with true coins; Reverse the remaining two coins. There are 3 possibilities for the second weighing. The scales balance, indicating that the suspect is one of the three light coins removed from the scales. Weigh one suspect versus another. If one is light, it is the counterfeit, otherwise the third suspect is the counterfeit. The heavy side is still heavier, indicating that the suspect is one of the three heavy coins which were on the heavy side twice. Weigh one suspect versus another. If one is heavy, it is the counterfeit, otherwise the third suspect is the counterfeit. The heavy side is now lighter, indicating that the suspect is one of the two coins switched after the first weighing. Weigh one suspect versus a true coin. If it does not balance, it is the counterfeit and this weighing tells you whether it is light or heavy. If it balances, the other suspect is the counterfeit. Determine light or heavy by what happened in first two weighings.Enough for this post. Will post solutions to the 15 pile problems later.

[Guv]

Solution to 15 piles of coin, with one pile containing counterfeits starts with the following two weighings. Weigh 120 coins: One from first pile, 2 from second, 3 from third, ... and 15 from the 15th. Weigh another 120 coins: One from 15th pile, 2 from 14th pile, ... and 15 from the first pile.If you designate the weight of a good coin as G, and the weight of a counterfeit as (G + D), these two weighing provide the following equations.FirstWeight = 120 * G + K * D, where pile K contains counterfeits.
SecondWeight = 120 * G + (16 - K) * DIf the two weights are equal, the middle pile (K = 8) contains counterfeits. Use third weighing to determine weight of a true coin (weigh a coin from any pile other than the 8th). Knowing both G and K, you can solve either equation for D, and determine the weight of a counterfeit coin.

If the two weights are not equal, you know that the 8th pile contains true coins. Use third weighing to determine the weight of a true coin. Knowing G, you have two equations in two unknowns (D & K). Solve them to determine the unknowns.

Note that D might be negative (counterfeit is lighter) or positive (counterfeit is heavier).

Solution to 15 piles with 5 containing counterfeits will be posted later.

[honeybee]

Solution to the first problem:

(I am assuming that counterfeit coins weigh less than the good ones.)

The solution is to divide the 12 coins in groups of 3 coins each. You now have 4 such groups, let's call them Group1, Group2, Group3 and Group4.

Now on the scale, weigh Group1 and Group2 (Weight1).

If both Group1 and Group2 are equal in weight, it means Group1 and Group2 both contain good coins. Now weigh Group3 and Group4(Weight2). One of these groups contains the fake coin. Let's say Group3 contains the counterfeit. So Group3 will weigh less than Group4.

Now Group3 contains the counterfeit. Out of the three coins (let's say Coin1, Coin2 and Coin3) in this group, take two coins and weigh them. Let's say Coin1 weighs less than Coin2. So Coin1 is the counterfeit. In the opposite case of Coin2 weighing less, Coin2 would be the counterfeit coin. And if both Coin1 and Coin2 have the same weight, it's the Coin3 which is counterfeit.

Apply the same logic for the possibility of the counterfeit coin being in any of the groups. I think this solution will work only if you know for sure that the counterfeit weighs less than the real one (or more than the real one).


Solution to the second problem

Assuming that you know for sure if the counterfeit weighs less/more than the real coins, you can solve this in one weighing itself.

Let's call the coin bags as Bag1 (From the first king paying tribute), Bag2, Bag3, Bag4 and so on up to Bag15. Now take 1 coin from Bag1, 2 coins from Bag2, 3 coins from Bag3 and so on till you take 15 coins from Bag15. Now you have 120 coins. Weigh them all at the same time on the weight. Compare the weight taken to that of the equal number of good coins. The difference will give you the number of coins that are counterfeit. Also this number corresponds to the bag number and you can identify the king. For e.g. the weight of 120 good coins is 120gm. If the actual weight of the 120 coins taken from the bags is 110gm, you are short by 10gm. This value means Bag10 contains counterfeit coins, so King no. 10 is the culprit.


Solution to the third problem:

Not much of a mathetician myself, and also pretty sure that I have got some of the basic assumptions wrong, so I shall not try to solve this one, although it must be on the lines of the second problem. I would like to see the right solutions to them ...



That was my last night's work, all ruined now. :(

I am eager to know the solution to the last problem, and by the way, Guv your assumption that it is not known whether the counterfeits weigh more or less than the good ones provides a beautiful twist to the simple problems that I knew.

[Guv]

Solution to 15 piles of coins, with 5 piles containing counterfeits: Remember that the mathematician said the solution was impractical, but cute from the warped point of view of a theoretical mathematician. Assume G is weight of a good coin and (G + D) is weight of a counterfeit. Choose a coin and assume that it is a true coin (odds are 2 to 1 in your favor). If it happens to be a counterfeit, you will discover your bad guess later and recalculate. Weigh the assumed true coin and one coin from each pile. FirstWeight = G (Might be G + D). SecondWeight = 15 * G + 5 * DSolve for D: D = (SecondWeight - 15 * FirstWeight) / 5. If FirstWeight was a good coin, result is: [ (15 * G + 5 * D) - 15 * G ] / 5 = D If FirstWeight was (G + D), result is: [ (15 * G + 5 * D ) - 15 * (G + D) ] / 5 = -2 * DFor the third weighing, take one coin from 1st pile, 2 from 2nd pile, 4 from 3rd, 8 from 4th, ... 2^14 from the 15th. This is where it gets really impractical, and the emperor decides to start over by weighing one coin from each pile. ThirdWeight = 32767* G + K * D, where K is some integer.Solve for K. If you have a correct value for both G and D, you will calculate a correct value for K. Express K as a binary number. It should have exactly 5 one bits. For example, if the 1st, 3rd, 6th, 9th, and 10th piles contained counterfeits, then K (805) = 1 + 4 + 32 + 256 + 512, which converts to 1100100101. Note that counting from the right, the 1st, 3rd, 6th, 9th, and 10th bits are one. The positions of the one bits correspond to pile numbers.

If your values for G and D are incorrect, your binary number will have more than 5 one bits, and/or might not be an integer. You will then know that your value of D has the wrong sign and its absolute value is twice what it should be. You know enough to calculate the correct value of D, the correct value of G, and the correct value of K. Convert correct value of K to binary and voila (there you are)!

[Guv]

In the balance scale problem (see previous posts): If you have a true coin for use in the first weighing, you can solve the problem with 13 coins (instead of 12).

[honeybee]

That's really cute!!

Guv, I declare you as the Chief Mathematician in my court.

The problem is I don't have a court...

That was really what you had promised it to be, a warped mathematician's mind!

I didn't try the last one, but enjoyed going through the solution.