You are given 20 identical coins. 18 of those coins have a weight of 10g each, 1 coin has 9g and 1 coin has 11g. You are given a traditional balance scale with two pans (no reading).
What is the minimal number of weighings required to guarantee finding the 9g and the 11g coins?
This can be done in
6 steps. This is the theoretical minimum, since there are ~5.4 trits of randomness here.
Steps
Separate the coins into A1-A9, B1-B9, and C1,C2.
Step 1 Weigh the As against the Bs.
Step 1.1 If equal, one of the three groups must contain both the heavy and the light ball. Swap A4-A6 with B4-B6 and remove A7-A9 and B7-B9 from the scale. Weigh A1-A3 and B4-B6 against B1-B3 and A4-A6.
Step 1.1.1 If still equal, the heavy and light are in a group of at most 3 together. Next weigh A1,B2,A4,B5,A7,B8 against B1,A2,B4,A5,B7,A8. This is a pairwise comparison: Since only one coin from each group is removed, if the heavy and light coins are not in C1 and C2 then there must be at least one heavy or light coin on the scales. Since the pairs from the groups of 3 are on opposite sides, the heavy and light coin cannot balance each other.
Step 1.1.1.1 If these are equal, then C1 and C2 are the heavy and light coin. Weigh them once to determine which is heavy and which light, for a total of 4 steps
Step 1.1.1.2 One of the groups is heavier than the other. WLOG, assume it is A1,B2,A4,B5,A7,B8. This means the heavier coin is A1,B2,B3,A4,B5,B6,A7,B8, or B9. Which of the 9 can be determined in 2 weighings (weigh 3 against 3 and then 1 against 1). If it is one of the Bs, the lighter coin is immediately obvious as the one in the same group of 3. If it is an A, the two As in the same group have to be weighed against each other. This is a worst case of 3 + 2 + 1 = 6 weighings.
Step 1.1.2 One of the two groups is heavier than the other. WLOG, assume A1-A3 + B4-B6 are heavier than B1-B3 + A4-A6. This means that within the group of 12, there must be at least a heavy or a light coin. Weigh A1-A3 against B4-B6.
Step 1.1.2.1 If A1-A3 weigh the same as B4-B6, then the light coin is one of B1-B3 and A4-A6. Weigh these against each other. Whichever is lighter contains the lighter coin. If that is B1-B3, then B7-B9 must contain the heavier coin. If it is A4-A6, the heavier coin will be in A7-A9. In any case, identifying the correct coin in each group of three takes only one weighing, for a total of 3 + 1 + 1 + 1 = 6 weighings
Step 1.1.2.2 If they are different, than the heavier group contains the heavier coin. One more weighing identifies the correct option among the 3, and the remaining 6 of that letter must contain the lighter coin for 2 more weighings. 3 + 1 + 2 = 6 weighings total
Step 1.2 WLOG, assume the As are heavier. Weigh C1 and C2 against A1 and A2.
Step 1.2.1 If equal, C1 and C2 are eliminated and the 9 (technically 7 but it doesn't matter) As contain the heavy coin and the 9 Bs contain the light. 2 weighings each for a total of 2 + 2 + 2 = 6 weighings
Step 1.2.2 If C1 and C2 are heavier, C1 and C2 contain the heavy and the Bs contain the light. 2 + 1 + 2 = 5 weighings
Step 1.2.3 If C1 and C2 are lighter, weigh C1 and C2 against B1 and B2.
Step 1.2.3.1 If equal, C1 and C2 are eliminated and the heavy must be A1 or A2 with the light in the Bs. 3 + 1 + 2 = 6 weighings
Step 1.2.3.2 If C1 and C2 are lighter, the light must be C1 or C2 and the heavy is in the As. 3 + 1 + 2 = 6 weighings
Step 1.2.3.3 If C1 and C2 are heavier, the heavy is A1 or A2 and the light is B1 or B2. 3 + 1 + 1 = 5 weighings
In each case, 6 or fewer comparisons are made.
I think it can be done in:
7 weighings
Method:
Divide the coins into five groups of four, call these G1..G5.
Weigh G1 vs G2, and G3 vs G4.
Case 1: G1 = G2, G3 = G4
This means the fake coins are in the same G group. Within each group, mark the coins as C1..C4. That is, C1 will denote the first coins of each group (5 coins total), C2 the second coins of each group, etc. It will take 3 weighings to figure out which C has the heavy and which C has the light, without knowing which G group had both fakes.
Weigh C1 vs C2 (5 coins vs 5 coins).
- If C1 = C2, then C3 and C4 have the fakes, so weigh them against each other to determine which has the heavy and which has the light.
- If C1 > C2, then weigh C2 vs C3.
-- If C2 = C3, then C1 is heavy and C4 is light.
-- If C2 < C3, then C2 is light, and weighing C1 vs C3 will determine which of C1, C3, C4 is heavy.
-- If C2 > C3, then C1 is heavy and C3 is light.
Now that we know which C was heavy and which was light, and have used 5 weighings, we need to find out which group contained the two fake coins in 2 weighings.
Suppose C1 was heavy. C1 has one coin from each of 5 groups. Call these H1..H5.
Weigh H1 H2 vs H3 H4.
- If equal, H5 is the heavy coin, and group 5 had the fakes.
- If H1 H2 > H3 H4, then weigh H1 vs H2 to find the heavy coin and thus the group with the fakes. This gives the light coin because we now know both which group had the fakes and which coin within the group was light.
Case 2: G1 > G2, G3 = G4 (and equivalent permutations)
We know G3 and G4 have regular coins.
Weigh G3 vs G5:
- If G3 = G5, then G1 has the heavy, G2 has the light
- If G3 > G5, then G1 has the heavy, G5 has the light
- If G3 < G5, then G5 has the heavy, G2 has the light
So far we have used 3 weighings, and we know which G group has the heavy coin and which G group has the light coin. It will take two weighings to find the heavy coin in its group and two weighings to find the light coin in its group.
For example, suppose G1 (a group of 4 coins) has the heavy coin. Weigh two against two, then take the two on the heavy side and weigh them against each other, with the heavier being the heavy coin.
Case 3: G1 > G2, G3 > G4 (and equivalent permutations)
Weigh G2 vs G3.
- If G2 = G3, then G1 has the heavy and G4 has the light.
- If G2 < G3, then G3 has the heavy and G2 has the light.
- G2 > G3 is impossible.
Similar to case 2, we used 3 weighings to identify the heavy and light groups. We do the same thing as in case 2 to find the coins within each group: 2 weighings to find the heavy and 2 to find the light.
This can be done in
at most 8 weighings
Steps
Let C1, C2, ... C20 be designations for both the coins themselves and their weights. So, for example, C1=C2 means that the weight of the first coin is equal to the weight of the second coin.
Step 1. Split the coins in 10 pairs C1+C11, C2+C12, up to C10+C20. Weigh the pairs against each other (C1+C11 vs. C2+C12, C3+C13 vs. C4+C14 etc.), 5 weighings in total.
Step 2. There can be 3 different cases:
Case 2.1. All 5 weighings show the equal result. That means that both Cn and C(n+10) (for some n in 1...10) are "fake" coins (9+11), and there is exactly one "fake" coin in C1 to C10. The 1 of 10 "fake" coin (if we don't know if it's heavier or lighter than "real" one) can be found in 3 weighings (see below), and if we found it, we can say that the coin whose number is 10 + number of the found coin is also "fake" (and we know which of them is heavier, and which is lighter - e.g. if we found that C8 is lighter (9 g), then C18 is necessarily heavier (11 g), etc.).
Case 2.2. Exactly 1 weighing is unequal, e.g. C1+C11 < C2+C12. This can happen only in one case, namely 10+9 < 10+11. To find the "fake" coins, we need at most 2 weighings, e.g. C1 vs C2 (if C1< C2, then either C1=9g or C2=11g, else C1=C2=10g) and C1 vs C12 (to know the rest).
Case 2.3. There are 2 weighings with unequal result, e.g. C1+C11 < C2+C12 and C3+C13 < C4+C14. This can be happen when 10+9 < 10+10 and 10+10 < 10+11. To find the "fake" coins, we need at most 3 weighings: firstly, weigh C1+C11 vs C3+C13, the lighter part will contain the 9g coin (e.g. if C1+C11 < C3+C13, then either C1 or C11 will be 9g, so 1 additional weighing (2nd one)). The 11g coin will be in the part which was heavier that the heavier part of 1st weighing (e.g. in our case we know that C1+C11< C3+C13< C4+C14, so either of C4 or C14 is 11g coin, so 1 more weighing to find it (3rd one)).
And now, here comes the solution to the problem "how to find 1 fake coins out of 10 in 3 weighings" (labeled C1 to C10, as in the our case).
Firstly, weigh C1+C2+C3+C4 vs C5+C6+C7+C8. If the scales are equal, then either C9 or C10 is fake (9 or 11-gram), you need 2 more weighings to compare both of them with a known-real (10-gram) one (we now know that all of C1-C8 are real, so just use one of them).
Secondly, if the scale are unequal (let's assume that C1+C2+C3+C4 < C5+C6+C7+C8, without loss of generality - if the C1+C2+C3+C4 is in fact heavier, we can make the all the following steps just substituting "<" for ">" and "lighter" for "heavier", and vice versa), weigh C1+C2+C5 vs. C3+C4+C6.
If C1+C2+C5 < C3+C4+C6, then either of C1 of C2 are fake and lighter, or C6 is fake and heavier (since C3 and C4 cannot be heavier, and C5 cannot be lighter). Compare C1 and C2 to know the result.
If C1+C2+C5 > C3+C4+C6, compare C3 and C4 for the very same reason (in this case, either one of C3 and C4 is lighter, or C5 is heavier).
Finally, if C1+C2+C5=C3+C4+C6, then either of C7 and C8 is fake (and heavier). Compare them to know.
It should be at least 6, because of 2*(n 2) <= 3^w-2 if n=20 and w is the minimum number of weighings. (Binominal in the first brackets)
Reasoning:
The information gathered by measurements on the scale should be more or equal than the number of possibilities how we can choose two fake items out of n, doubled, because the two are not the same weight, so after w weighings we can point at a coin pair with certainty. There is 3^w results on a balanced scale after w weighings, there should be at least two inequalities.
11 weighings
Split the 20 coins in pairs and weigh each pair (10 weighings).
Thus, 10 + 1 = 11 weighings.
In step 2, weighing just $a$ and $c$ is sufficient to understand the maximum of $b$ and $d$. Since there are exactly two imbalances to get to this step, it is understood that if the 9 g coin is in one set, then the greater of the other set is the 11 g coin. Note that one may also choose to compare only $b$ and $d$; $b<d$ implies $d$ weighs 11 g and $a$ weighs 9 g, and so on for $d<b$.
The answer is
six weighings.
Unfortunately, this answer is neither elegant nor easy to explain since I found it via brute force. It's pretty disappointing to solve a puzzle this way, but I don't think anyone explained a correct answer yet (at least before I was sniped by Charles Gleason!).
The General Approach
Consider the case of 9 coins with one heavier than the rest. The optimal solution here is two weighings. First set 3 coins on the left and 3 on the right. If they're equal, the heavy coin is in the remaining three. If they're not equal, the heavy coin is on the heavier side. Weigh two of the coins in the "heavy" set of three coins. If one is heavier, that's your answer. If they're equal, the remaining coin is your answer.
The principle to take away here is that your best bet is to try and separate the coins into three roughly equal groups based on the outcome of each weighing. This way, no matter what the outcome is, you've reduced the number of possible solutions to about a third. Regardless of the result of the weighing, you go from looking at one of nine coins to one of three coins.
The only difference between this toy problem and the one asked by ThomasL is the number of possible solutions. There being two odd coins makes no difference. We have \begin{equation} \frac{20!}{18!*1!*1!}=380 \end{equation} combinations. At each step, we try to cut this number down to a third its original value. Since 3^6 exceeds 380, we should theoretically be able to do this in 6 steps, and find that it's achievable in reality as well.
The first step is simple. Take any five coins and weigh them against any remaining five coins. No matter which coins are weighed, if the scale is balanced you have 130 remaining possibilities, if the left side is heavier you have 125 remaining possibilities, and if the right side is heavier you have 125 remaining possibilities. Do your best to repeat this procedure five more times and you will identify the heavier and the lighter coin without fail every single time.
The Nitty Gritty
I first solved for the worst-case scenario. Of the three outcomes that can occur when you place coins upon the scale (left heavier, right heavier, both equal), I reasoned that the worst-case would be the one that leaves the most solutions open.
There are probably better ways to do that. I hoped that if I solved for the worst-case scenario, the other scenarios with fewer remaining solutions would be trivial. I am not sure if that is the case. Perhaps there are situations where a case with fewer remaining solutions actually takes more steps to solve due to the solutions being tricky to separate.
Regardless, I went ahead and brute forced it. After finding an optimal weighing at each step so as to split the solutions among the three outcomes, I looked at the optimal next step for each outcome. Do this until 1 solution remains, which takes six steps no matter what.
Full brute force solution and calculator tool for looking at solution splits can be found here, with sloppy-but-reproducible python code here.
With the assumption that you can distinguish the coins by either marking them or retrieving them in the reverse order by stacking them on the scale, then worst case is seven weighings:
Arrange the coins into a grid of 4 rows and 5 columns
At this point, you know either:
Next you work on the columns
At this point, you are in three possible situations:
The latter two situations are actually the same. You have either four pairs or five pairs of coins. Within each pair, if one is the heavy coin, the other is the light coin. So, worst case, you need to find the heavy coin from a set of five coins. Separate out the potential heavies (while keeping track of the pairs). Regardless of four or five coins, the worst case is two more weighings:
You make four stacks of 5 coins each. You put one stack on one side and one on the other side. You have two possibilities. a) They balance the scale. b) They do not balance the scale. If the scale is balanced then you have the smallest number of steps. If the scale is not balanced, we have the following combinations 9[10-11-10]. Remove the stack with the 9 and set it aside. Then try the combinations 11[10-10]. If the scale is not balanced remove the stack that contains the 11. Now, from the stacks that contain 9 and 11, from each stack put one coin at a time on each side of the scale. If they balance the scale, then put one more coin on each side. If the scale does not balance, remove both coins and set them aside separately. Now put three coins on each side; the scale will show imbalance. On the side which contains the heavier or lighter coin, put the coin which caused the imbalance in the second case. From the very bottom of that stack, take a coin and transfer it to the other side of the scale, which will balance the scale. If by adding the second coin the scale is still balanced, by adding the third coin the scale must show an imbalance. If it does, repeat the previous process. If the scale is still balanced when a fourth coin is added, then the remaining coins are the 9 and 11 g coins. Remove a coin from the four-coin stack, placing it on the other side of the balance. Add the 9 and 11 g coins the three-coin stack. This balances the scale. But balancing the scale four times in a row is an extreme case and in this extreme case five steps are required. So we need 4+4=8 or 4+5=9 steps to balance the scale.
Weigh two random coins. Luckily, one coin is heavier than the other. Could be:
Take both coins (just weighed) and put them on same side (keeping track of the heavier coin) and weigh them against another two coins. You get lucky and both sides weigh the same.
The only option is for the 11 g and 9 g to be on the same side.
The heavier coin that you kept track of is 11 g. The other is 9 g.
Therefore, 2 (lucky) weighings is the ideal case.
