10
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Do you need to identify which of the 9g and 11g coins is which? For example, suppose I weigh 18 of the coins across 9 weighings, and each time it is the same. Can I then point to the other two coins (which must be 9g and 11g), or do I require a tenth weighing to distinguish between them? $\endgroup$ – ZanyG Jan 2 at 1:13
  • 1
    $\begingroup$ Here is a related question: Finding both fake coins in a set of 5 $\endgroup$ – Jaap Scherphuis Jan 2 at 7:49
  • $\begingroup$ semantics... the coins are not all identical, they may be visually identical but two of them are not the same as the other 18 ;-) $\endgroup$ – houninym Jan 3 at 8:44
9
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ At step 1.1, what happens if A123 B456 > B123 A456? Step 1.1.2 isn't very clear on what to do next, and you don't know yet whether A123 is heavy or neutral, A456 is light or neutral, and A789 is heavy light or neutral. $\endgroup$ – JS1 Jan 3 at 7:00
  • $\begingroup$ I would like this to be correct, because that would mean that reality can meet the theoretical lower bound I also proposed, but to be honest this one is hard for me to understand...it might be correct though $\endgroup$ – FIreCase Jan 3 at 12:49
  • $\begingroup$ Yes, I do feel that there should be a less confusing way to go about this. I tried to rely on symmetry to reduce the number of steps and edited step 1.1.2 for clarity, but I do think this should be correct and the theoretical lower bound (although there might be a simpler way to hit the lower bound) $\endgroup$ – Charles Gleason Jan 3 at 20:28
  • $\begingroup$ Why can't the heavy coin be A7 and the light coin be A4? Your explanation ruled out A7 as the heavy coin. $\endgroup$ – JS1 Jan 4 at 0:44
  • 1
    $\begingroup$ I think this is complete and correct now. Good job! A suggestion: when you do the weighing in step 1.1, there is no need to "swap" B456 to the left scale. At this point, all the As and Bs are indistinguishable from each other, so you can simply weigh A123 B123 vs A456 B456. This might make the notation in the later sections easier to understand (because A1 and B1 would be related to each other rather than A1 and B4). (Actually, I'm not sure if it makes the 1.1.1 sections simpler, but it makes the 1.1.2 sections simpler) $\endgroup$ – JS1 Jan 4 at 5:45
8
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Except, in the worst case scenario, your method isn't 7. G1 vs G2, and G3 vs G4 is 2 weighings. C1 vs C2 5 times, is another 5, then potentially C2 vs C3 5 times, to determine that the issues is the last C3 vs C4 which would be a total of 13 weighings. Your most lucky solution is Case 1 (2 to start), then by luck C1>C2 and C2=C3, which would be 4 weighings. The solution is not linear either, so increase the number of coins and you'll need disproportionately more weighings to get the answer. The more coins, the worse it gets. $\endgroup$ – sibaz Jan 3 at 16:17
  • $\begingroup$ @sibaz, it's not C1 vs C2 5 times, it's the group of all C1's vs the group of all C2's once (JS1 should make this clearer in the answer). You don't need to measure those coins in individual pairs. $\endgroup$ – asgallant Jan 3 at 18:48
  • $\begingroup$ Right, that was the approach I first thought of. I'd suggest naming them as per the 2 dimensional array, you're referring to, so A, B, C, D and E groups and coins 1-4 (so coins A1 through A4, B1 through B4, C1 through C4 and so on). In your example you start considering A vs B and C vs D, then 1 vs 2 and 3 vs 4. $\endgroup$ – sibaz Jan 6 at 17:52
4
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ In case 2, I'm not sure how you're getting the 2nd stage down to 2. If c1<c2 then either c1=9 and c2=10 (with c12 being 11) or c1=10 and c2=11 (with c11 being 9) or c1=9 and c2=11 (c11 and c12 are both 10). Checking c1 vs c12 will show c1<c12 in cases A and C, so if C1<C2 and C1<C12 all you know, is that c1 is 9. You still need to identify which of C2 or C12 is 11. $\endgroup$ – sibaz Jan 3 at 16:33
3
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ It is a good start but it is only a lower bound. It doesn't answer the question. $\endgroup$ – Florian F Jan 3 at 22:57
  • $\begingroup$ Shouldn't your formula be: $2 * {n \choose 2} \leq 3^{w-2}*2^2$ because the two inequalites should each divide the possibilities in 2, thus the extra $2^2$ at the end? Also, assuming your formula really is $2 * {n \choose 2} \leq 3^{w}-2$, then if there are only 3 coins, your formula predicts $w = 2$ but it takes 3 weighings even though there are only 6 possibilities. $\endgroup$ – JS1 Jan 4 at 1:06
  • $\begingroup$ Actually, according to this question, you can see that sometimes the coins can be found with only one unequal weighing. $\endgroup$ – JS1 Jan 4 at 1:28
2
$\begingroup$

Answer

11 weighings

Steps

Split the 20 coins in pairs and weigh each pair (10 weighings).

  1. If there is exactly one imbalance $a<b$, then coin $a$ weighs 9 g and coin $b$ weighs 11 g.
  2. If there are two imbalances $a<b$ and $c<d$, then weigh only coins $a$ and >!$c$ (one extra weighing)
    • Case 1: $a<c \implies$ coin $a$ weighs 9 g and coin $d$ weighs 11 g
    • Case 2: $c<a \implies$ coin $c$ weighs 9 g and coin $b$ weighs 11 g

Thus, 10 + 1 = 11 weighings.

Explanation

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$.

|improve this answer|||||
$\endgroup$
2
$\begingroup$

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.

  1. C1, C2, C3, C4, C5 on the left, C6, C7, C8, C9, C10 on the right. Worst case scenario is they're both equal, leaving 130 solutions.
  2. C4, C17, C18, C19, C20 on the left, C6, C7, C11, C12, C13 on the right. Worst case scenario is they're both equal, leaving 44 solutions.
  3. C1, C4, C10, C13, C18 on the left, C1, C4, C10, C13, C18 on the right. Worst case scenario is the left side being heavier, leaving 15 solutions.
  4. C2, C3, C8, C10, C12, C14, C15, C20 on the left, C4, C5, C7, C11, C13, C16, C17, C18 on the right. Worst case scenario is they're both equal, leaving 5 solutions.
  5. C2, C10, C14 on the left, C4, C12, C16 on the right. Worst case scenario is they're both equal, leaving 2 solutions.
  6. C12 on the left, C11 on the right. One solution remains.

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.

|improve this answer|||||
$\endgroup$
1
$\begingroup$

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

  1. Weigh Row1 against Row2
  2. Weigh Row3 against Row4

At this point, you know either:

  • Which row has the heavy coin AND which row has the light coin
  • OR
  • An unknown row has both the heavy coin and the light coin

Next you work on the columns

  1. Weigh Column1 against Column2
  2. Weigh Column3 against Column4
  3. Worst Case Only: If only one of the prior two weighings are unequal, then you need to know whether the difference is heavier, lighter, or both. Weigh Column5 against one of the prior two columns that was equal. If Column5 is heavier, the lighter of the unequal pairing has the light coin. If Column5 is lighter, the heavier of the unequal pairing has the heavy coin. If Column5 is equal, the unequal pairing has both the heavy coin AND the light coin.

At this point, you are in three possible situations:

  • You know both the row and column of the HeavyCoin and LightCoin (you are done)
  • OR
  • You know the row for Heavy and Light, but they are in the same column
  • OR
  • You know the column for Heavy and Light, but they are in the same row

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:

  1. Weigh Coin1 against Coin2 - if one is the heavy coin, you are done
  2. Weight Coin3 against Coin4 - if one is the heavy coin, you are done. If not, you are still done, because Coin5 is the heavy coin.
|improve this answer|||||
$\endgroup$
0
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ "By the law of averages" - so then we're not guaranteed to have identified the two fakes in 10 steps? $\endgroup$ – Jaap Scherphuis Jan 2 at 7:54
  • $\begingroup$ @ Jaap I will present a more detailed form soon. $\endgroup$ – Vassilis Parassidis Jan 3 at 2:44
-1
$\begingroup$

Weigh two random coins. Luckily, one coin is heavier than the other. Could be:

  • 11 g and 10 g
  • 10 g and 9 g
  • 11 g and 9 g

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.

  • If if was the 11 g and 10 g on one side this is impossible.
  • If if was the 10 g and 9 g on one side this is impossible.

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.

|improve this answer|||||
$\endgroup$
  • 5
    $\begingroup$ Aren't questions like this about finding the Big-O time, not the Big-Ω time? You can't assume that you will be so lucky on the first weighing. $\endgroup$ – ZanyG Jan 1 at 23:56
  • $\begingroup$ That's how I interpreted the question (which I think needs clearer wording). $\endgroup$ – ThoughtBox Jan 1 at 23:57
  • $\begingroup$ Looking at related questions, it's always been "what is the maximum number of steps required by the strategy that minimises this maximum number of steps," but yeah, clarification would be nice. $\endgroup$ – ZanyG Jan 2 at 0:03
  • 1
    $\begingroup$ Yes, I guessed that's what he meant. I've written up one interpretation and am working on the "correct" interpretation now. $\endgroup$ – ThoughtBox Jan 2 at 0:05
  • $\begingroup$ Nice spot! I'll amend my answer. $\endgroup$ – ThoughtBox Jan 2 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.