| |
BGonline.org Forums
Two-counterfeit puzzle -- SOLUTION
Posted By: Nack Ballard In Response To: Another coiins problem (Nack Ballard)
Date: Friday, 8 March 2019, at 4:56 a.m.
Bob Koca posed:
You have 6 coins. 4 weigh exactly the same and the other two are slightly off. They might both be heavy or both be light, or one could be light with other being heavy. The amount they are off by might be the same or different.
What is the fewest number of weighings using a balance scale that could conclusively determine the 2 coins that are off in weight?
The possibility that the two counterfeits might be different shades of light and/or heavy adds complexity. For example, one coin can be heavier than another, yet they might both be light.The answer is five weighs, though one might also say that it is slightly more than four. That is, I'm fairly certain that no four-weigh solution exists, though it is possible to come very close.
Below, between the dotted lines, is my solution in shorthand. Weighs are denoted by descriptive numbers. The first weigh is "One," the second is "Two," etc.
Coins are numbered 1, 2, 3, 4, 5, 6, and "v" stands for versus (or the balance point of the scale). Equals (=) means the scale is balanced. Greater than (>) means the left side is heavy, and less than (<) means the left side is light.
Designations are in the form of coin number followed by "H" for Heavy, "L" for Light, or "c" for counterfeit (when it is H or L but we don't yet know which). When more than one coin is listed, there is sometimes a symbol in between (= or > or <). For example, "1c=2c" means that 1 and 2 weigh the same (equally heavy or equally light); "2H3c" means that 2 is heavy and 3 is a counterfeit (that might be heavy or light); "3L4L" means that 3 and 4 are both light; "3L<4L" means that 3 is light and 4 is even lighter.
Before the first weigh, any of twenty-one answer pairs are possible: 1c2c, 1c3c, 1c4c... through 5c6c. With each weigh, some pairs can be logically eliminated. After weighs Two and Three below, counterfeit pairs that are still "alive" are helpfully listed on the right in parentheses, so that you can see what is left (or you can choose to ignore it). When the fourth weigh is finished (or in one instance sooner), the sole remaining counterfeit pair appears in square brackets.
------------------------------------------------------------------------------------------------- SOLUTION One 1 v 2
Two 3 v 4One 1 v 2
Two 3 v 4Case A: 1 = 2 and 3 = 4:................................... (1c=2c, 3c=4c, 5c6c)
..Three 1 v 3
........1 = 3: then [5c6c] (Done in three.)................ (5c6c)
........1 > 3: then Four 1 v 5: if 1 = 5, then [3L=4L]..... (1H=2H 3L=4L)
................................if 1 > 5, then [1H=2H]
...................................1 < 5 is impossible........1 < 3: then Four 1 v 5: if 1 = 5, then [3H=4H]..... (1L=2L 3H=4H)
................................if 1 < 5, then [1L=2L]
...................................1 > 5...impossible
Case B: 1 > 2 and 3 > 4.................................... (1H3H 1H4L 2L3H 2L4L)..Three 1 v 5 and Four 3 v 5
........1 = 5 and 3 = 5, then [2L4L]
........1 = 5 and 3 > 5, then [2L3H]
........1 > 5 and 3 = 5, then [1H4L]
........1 > 5 and 3 > 5, then [1H3H] 1 < 5 or 3 < 5 is impossible
Case C: 1 = 2 and 3 > 4.................................... (3c>4c 3H5c 3H6c 4L5c 4L6c)..Three 1 v 3
........1 = 3: then Four 1 v 5: if 1 = 5 then [4L6c]....... (4L5c 4L6c)
................................if 1 > 5 then [4L5c]
................................if 1 > 5 then [4L5c]........1 > 3: then Four 4 v 5:....4 = 5 impossible........ (3L>4L)
...................................4 > 5 impossible
................................if 4 < 5 then [3L>4L]........1 < 3: then Four 4 v 5: if 4 = 5 then [3H6c]....... (3H>4H 3H5c 3H6c)
................................if 4 > 5 then [3H>4H 3H5L]
................................if 4 < 5 then [3H5H]------------------------------------------------------------------------------------------------- EXPLANATION One 1 v 2
Two 3 v 4Weigh One is coin 1 versus coin 2, and the result might be 1 = 2, or 1 > 2, or 1 < 2. In the same vein, weigh Two might be 3 = 4, 3 > 4 or 3 < 4. Over two weighs, that seems to generate three times three equals nine outcomes. Actually, though, there are only three distinct outcomes:
Case A: Both weighs are balanced (=).
Case B: Both weighs are unbalanced (> or <).
Case C: One weigh is balanced and the other is unbalanced.Other cases are symmetric. (If this isn't evident to you, ask me and I'll explain further.)
Case A: 1 = 2 and 3 = 4
This outcome indicates either:
(a) 1, 2, 3 and 4 are all neutral. Or
(b) Either 1 and 2 (from weigh One) or 3 and 4 (weigh Two) are equal-weight counterfeits.To find out which, our third weigh is: Three 1 v 3.
If 1 = 3, then all four coins are the same weight (subcase "a"). They cannot be all heavy or all light (because that would be four counterfeits instead of two), so they must all be neutral. By process of elimination, the counterfeits are 5 and 6 (and we don't need to bother with a fourth weigh).
If 1 v 3 does not balance, then 1 2 are either two neutrals or two equal-weight counterfeits. This also means that 5 and 6 are neutral. So, for the fourth weigh we can pit one those neutrals (5 or 6) against any of 1, 2, 3 or 4. Arbitrarily, I chose 1 v 5. If this does NOT balance, then 1 2 is the counterfeit pair. If it DOES balance, then 1 and 2 are neutrals, which means that 3 4 is the counterfeit pair.
Case B: 1 > 2 and 3 > 4
When one coin weighs more than another, it means that at least one of the two is counterfeit. There cannot be more than two counterfeits total; therefore, either 1 or 2 is counterfeit and either 3 or 4 is counterfeit. This also tells us that 5 and 6 are neutral coins.
All that is left to do is to weigh one coin from each pair heads up against a neutral. I chose: Three 1 v 5 and Four 3 v 5.
If 1 is heavy or light, it is the counterfeit; otherwise, 2 is the counterfeit. Parallel logic applies to the 3 4 pair.
Case C: 1 = 2 and 3 > 4
Coin 3 and/or 4 is a counterfeit. With that in mind, 1 and 2 can't be equal counterfeits (as there aren't three counterfeits). Thus 1 and 2 are both neutral, and either 5 or 6 is neutral. This leaves five possibilities:
3c>4c..3H5c..3H6c..4L5c..4L6c There are at least three heads-up possibilities (not counting symmetrical ones) that work for the third weigh. The one that comes closest to solving in four weighs is 1 or 2 (neutral) v 3 or 4 (symmetric). I chose Three 1 v 3.
If 1 = 3, the remaining pairs with a 3 are eliminated, and thus only 4L5c and 4L6c remains. For the fourth weigh, 1 or 2 (neutral) v 5 or 6 breaks the tie.
If 1 > 3, the pairs without 3 are eliminated, and 3H5c and 3H6c are ejected as well, because 3H is not lighter than a neutral coin. Only 3c>4c remains, clarified to 3L>4L. No fourth weigh is necessary.
If 1 < 3, this is the only problematic branch. The two pairs without the 3 still go away, but all three of 3c>4c, 3H5c and 3H6c are still standing. For the fourth weigh, 4 v 5 does not quite succeed in a three-way diversification. If 4 = 5 then 3H6c is alone (good), and if 4 < 5 then 3c>4c is clarified to 3c>4L and is alone (good). However, if 4 > 5, then a clarification to 3H5H works and a clarification to 3H>4H works.
It is solely in that sub-branch where a dual answer exists after the fourth weigh. (The tie is easily broken, of course, in a fifth weigh by any neutral versus 4 or 5.)
Close call! Obviously, solving in five weighs is trivial, and there are many other approaches work, too. Even solving 7 coins in five weighs is comfortable, and it might even be possible with 8 coins (I came very close without much effort).
Unless a four-weigh solution actually exists for six coins (which I doubt), I prefer to pose the problem this way:You have six coins. Four weigh 1 ounce each. The other two are counterfeits, each off by one gram. The counterfeits might both be heavy or both be light, or one of each. How can you conclusively identify the counterfeits in just four weighs? (Or "What is the fewest...")
Under these modified conditions, the solution outlined above works in four weighs, because 3 > 4 can be neither 3H>4H (heavier and heavy) nor 3L>4L (light and lighter); it can only be 3H4L.
Nack
| |
BGonline.org Forums is maintained by Stick with WebBBS 5.12.