121 coins and a balance

Question

Inspired by this puzzle...

You have $121$ apparently identical gold coins. At most one of these is fake, and weighs a different amount than a genuine coin.

In front of you is balance with two pans. In your pocket you have a single coin which you know is genuine.

What is the minimum number of weighings it takes to find the fake (if there is one), and determine whether it is heavier or lighter than the others?

Hint:

Use your first weighing to reduce this to a similar problem, but with fewer coins.

Answer 1

Lemma. Given a set $A$ of coins that may be too heavy, a set $B$ of coins that may be too light. Assume $A\cap B=\emptyset$ and exactly one of the coins is a fake. If $|A|+|B|=3^k$, then the fake coin can be determined in $k$ weighings.

Proof. If $k=0$, there is nothing to be shown. Assume the lemma is true for soem $k$; we shall show that it also holds for $k+1$: Partition $A$ into three nearly equal-sized sets $A_1,A_2,A_3$ (that is, $\lfloor\frac {|A|}3\rfloor\le |A_i|\le \lceil\frac {|A|}3\rceil\le 3^k$). Since only two possible sizes are possible, at least two of the $A_i$ have the same size. Without loss of generality, $|A_1|=|A_2|$. Now we can partition $B$ into sets $B_1,B_2,B_3$ with $|B_i|=3^k-|A_i|$ Put the coins from $A_1\cup B_2$ into the left pan, $B_1\cup A_2$ into the right pan. Ignore the coins in $A_3\cup B_3$. Note that both pans contain the same number of coins. Now if the left pan goes down, we know that the fake coin is $\in A_1\cup B_1$; if the right pan goes down, the fake coin is $\in A_2\cup B_2$; if the pans weigh the same, the fake coin is $\in A_3\cup B_3$.At any rate, the induction hypothesis applies. $_\square$

Proposition. Given a known good coin and $\frac{3^k-1}2$ coins among which there may be exactly one too heavy or too light fake coin or no fake coin at all. It is possible to determine which coin is fake and in which way, or that there is no fake coin, in $k$ weightings.

Proof. Again induction. For $k=0$, there is nothing to be shown. Assume the proposition holds for $k$; we shall show that it also holds for $k+1$: Put the known good coin and $\frac{3^k-1}2$ coins into the left pan, $\frac{3^k+1}2$ into the right pan, and leave the remaing $\frac{3^k-1}{2}$ coins aside. If the left pan goes down, we have $\frac{3^k-1}2$ coins that may be too heavy, $\frac{3^k+1}2$ that may be too light, and the rest is known good. By the lemma, we can finish with $k$ more weighings. The case with the right pan going down is similar: we have $\frac{3^k+1}2$ coins that may be too heavy, $\frac{3^k-1}2$ that may be too light, and the rest is known good. Finally, if both pans weigh the same, we are left with the $\frac{3^k-1}2$ unused coins among which there may be a fake coin or not. By induction hypothesis, this can be solved with $k$ weighings. $_\square$

Remark. Since it is clar that it takes at least $k$ weighings to distinguish among $3^k$ possible outcomes, the result of the proposition is best possible.

Corollary. The puzzle with $121$ coins can be solved in $5$ weighings.

Answer 2

6 uses of the scale.

NOTE: I had another answer with 8 uses, but left it in since it was its own answer.

Take one coin away and split the rest into $3$ groups of $40$. Call them $A$, $B$, $C$. In your first two uses of the scale, you will weigh $A$ vs $B$ and $B$ vs $C$.

There are 7 possible results:

1. $A<B$ and $B=C$ - There is a light coin in $A$
2. $A>B$ and $B=C$ - There is a heavy coin in $A$
3. $A<B$ and $B>C$ - There is a heavy coin in $B$
4. $A>B$ and $B<C$ - There is a light coin in $B$
5. $A=B$ and $B<C$ - There is a heavy coin in $C$
6. $A=B$ and $B>C$ - There is a light coin in $C$
7. $A=B$ and $B=C$ - The coin set aside is the only unknown coin

After this is complete, you will know not only which $40$ coins has the faulty coin, but you will also know if it is lighter or heavier. If they are all the same, you can use the scale once more with the coin set aside to figure out if it is bad or good.

WLOG, lets assume you have $40$ with a single known heavy coin. Add $41$ known good coins to make $81$. Now, repeat the following:

• Split into three equal groups
• Weigh two of the groups
• You will know which of the three groups contains the coin

Until you are left with a single coin.

Since it took you 2 uses of the scale to get to $81$, here is how it breaks down:

3. $81$ coins becomes $27$
4. $27$ coins becomes $9$
5. $9$ coins becomes $3$
6. $3$ coins becomes $1$

So, you can do this in $6$ uses of the scale!

Answer 3

It is known that we can solve the corresponding problem with 13 coins in three weighings. As the coins are broken into three groups each time and we have about nine times more coins, our target should be five. We can follow the logic of the linked solution. We split the coins into groups that are weighed $n$ times. The group weighed $n$ times has ${5 \choose n}2^{n-1}$ coins in it because we can choose the times a coin is on the balance in $5 \choose n$ ways and we can choose the sides it goes on in $2^n$ ways but we need to distinguish heavy from light which divides by $2$. This lets us handle $5+20+40+40+16=121$ coins. The good coin goes on the right each time. Number the single weighing coins $1-5$ and put each one on the left in turn. Twenty coins are each weighed twice. Number them $1$ to $20$. These will be weighed $$1,2,9,20\quad 10,11,12,19\\1,3,4,16\quad 2,15,17,18\\3,5,6,12\quad 4,9,13,14\\5,7,8,18\quad 6,17,19,20\\7,9,10,14\quad 8,13,15,16$$ Note that these always put four coins on each side. There are $40$ coins weighed $3$ times each, number them $1$ to $40$ We will weigh them $$1,2,3,13,15,16,17,18,20,24,30,39 \quad 4,14,19,21,22,23,29,31,32,37,38,40\\ 1,2,4,5,6,7,17,19,20,23,28,34 \quad 3,8,18,21,22,24,25,26,2733,35,36\\ 1,3,4,5,6,8,9,10,11,27,32,38 \quad 2,7,12,25,26,28,29,30,31,37,39,40\\ 5,7,8,9,10,12,13,14,15,31,36 \quad 6,11,16,21,23,24,29,30,3233,34,35\\ 9,11,12,13,14,16,17,18,19,26,35,40 \quad 10,15,20,25,27,2833,34,36,37,38,39$$ there will be $12$ coins on each side.

For the coins that are on the pan four times we can weigh $$ \begin {array} {c c}1,2,6,7,8,17,21,24,25,28,30,33,36,39& 3,4,5,18,19,20,22,23,26,27,29,31,32,34,36,37,38,40\\ 1,3,7,9,10,14,15,16,25,29,32,33,36,38 & 2,4,5,6,8,11,12,13,26,27,28,30,31,34,35,37,39,40\\ 1,4,6,9,11,15,17,18,22,23,24,33,37,40 & 2,3,5,7,8,10,12,13,14,16,19,20,21,34,35,36,38,39\\ 1,5,8,9,12,1417,19,2325,26,30,31,32 & 2,3,4,6,7,10,11,13,15,16,18,20,21,22,24,27,28,29\\9,13,16,17,20,22,25,27,31,33,34,38,39,40 & 10,11,12,14,15,18,19,21,23,24,26,28,29,32,35,36,37 \end {array} $$

We will have $14$ coins on the left and $18$ coins on the right. We can fix that imbalance with the ones that are on all five times. There, we weigh $$3,4,5,6,8,10,11,13,15,16\quad 1,2,7,9,12,14\\2,4,5,6,8,9,11,12,14,15\quad 1,3,7,10,13,16\\2,3,5,6,7,9,11,13,14,16\quad 1,4,8,10,12,15\\2,3,4,6,7,9,10,12,13,15\quad 1,5,8,11,14,16\\2,3,4,5,7,8,10,12,14,16\quad 1,6,9,11,13,15$$ This has $10$ coins on the left and $6$ on the right. This results in $41$ coins on each side of the balance each time.

Given the results, the number of imbalances tells us the number of times the fake coin was on the scale. The pattern of imbalances tells us which coin is fake and whether it is heavy or light.

Answer 4

The answer is $8$ uses of the scale.

First Weighing

Take one coin away and make $4$ groups of $30$. Pick any two of these groups and weight them. If scale balances, then they are all good coins. If the scale tips, then you know there is at least one bad coin in those $60$ and the other $61$ are good. Either way, you have eliminated at least $60$ coins in one weighing leaving you with either $60$ or $61$ coins.

Second Weighing

WLOG, we will assume you have $61$ coins. Take one away and split into $4$ groups of $15$. Again, pick any two and weigh them. You will be able to eliminate at least $30$ more coins in this way.

Third Weighing

You now have $30$ coins, plus one set aside, plus one in your pocket. The one set aside may or may not have been ruled out as a possible bad coin. Lets say that we still don't know, so that you have $31$ coins. Add your coin from your pocket to make $32$ and divide into $4$ groups of $8$. Weigh two groups, and you will be able to eliminate $16$, leaving you with at most $16$ coins.

Forth Weighing

Split into $4$ groups of $4$. Eliminate $8$ by weighing two of the groups.

Fifth Weighing

Split into $4$ groups of $2$. Eliminate $4$ by weighing two of the groups.

Sixth Weighing

Weigh $2$ of the $4$ remaining coins. $2$ will be eliminated.

Seventh and Eighth Weighings

Weigh the last $2$ coins. If the scale balances, you are done and all coins are equal. If the scale tips, then use your last attempt to see which one is the bad one by comparing one of them to a known good coin. You now have only $4$ coins left. Take $3$ of the coins and one from the pile of known good coins. Weigh 2 on each side.

Answer 5

I need 5 weighings.

Where appropriate I'll assume that the scale will tip to one side and not the other, but because of simmetry it will be an equivalent reasoning for the other side. I will signal those places with (X)

Weighing #1

41 coins on one plate, 40 coins on the other plus the known one. Leave 40 coins out

If it balances the fake is int the 40 left out, go to #E-2. If not go to #D-2.

Weighing #E-2

We know that the fake is in the remaining 40 coins or does not exist.

Of the 40 candidates, put 14 on one plate, 13 on the other plus 1 of the known good ones. Leave 13 out.

If it balances go to #EE-3, if not go to #ED-3

Weighing #EE-3

The fake one if present is in the 13 untouched coins.

We put 5 on one plate, 4 on the other plus 1 known good. Leave 4 out.

If it balances go to #EEE-4. If not there are 5 of one weight and 4 of the other. Go to #EED-4.

Weighing #EEE-4

The fake, if present is in the untouched 4 coins.

We put 2 on one plate, 1 on the other plus 1 known good. Leave 1 out.

If it balances go to #EEEE-5, if not go to #EEED-5.

Weighing #EEEE-5

The fake, if present is in the last untouched coin.

We put that single coin on one plate, a known good on the other.

If it balances no fake, if not, that one is the fake.

Weighing #EEED-5

Assume the scale will go to the left (X). Then the fake one is either one of the 2 left, heavier, or the other one, lighter.

We put 1 heavier coin on one plate, the other heavier coin on the other plate.

If it balances the fake is the lighter one. If not, the fake is the one that goes down.

Weighing #EED-4

5 coins are of one weight, 4 of the other. Assume that the 5 are heavier (X).

We put 2 heavier and 2 lighter on the left plate, 1 heavier, 1 ligther and 2 knwon ones on the other. Leave 2 heavier and 1 lighter out.

If it balances the fake is one of the 2 heavier and 1 lighter left out. If it goes to the right, the fake has changed plate, so is one of the 2 lighter plus 1 heavier that moved. If it goes to the left, the fake did not move, so it is one of the 2 heavier plust 1 lighter that did not move.

Go to #EEDD-5.

Weighing #EEDD-5

There are 2 candidates of one weight and 1 of the other. Assume that the 2 are heavier (X).

Put 1 of the heavier one plate and the other in the other plate.

If they balance, the fake one is the other one. If not, the fake is the one that goes down.

Weighing #ED-3

14 coins are of one weight, 13 of the other. Assume that the 14 are heavier (X).

Put 5 heavier plus 5 lighter on the left plate, 4 heavier plus 4 lighter plus 2 known good on the other. Leave 5 heavier and 4 lighter out.

If they balance the fake is in the left out, and there are 5 heavier and 4 lighter. Go to #EDD-4. If it goes to the left, the fake is in one that did not move, that is one of the 5 heavier plus 4 lighter. If it goes to the right, the fake is in one that moved, that is one of the 5 lighter plust 4 heavier.

Go to #EED-4

Weighing #D-2

41 coins are of one weight, 41 of the other.

Put 13 heavier plus 14 lighter on the left plate, 14 lighter plus 13 heavier on the right plate. Leave 14 heavier and 13 lighter out.

If it balances then the fake one is in the left out, 14 heavier and 13 lighter. If it goes to the left, the fake was unmoved, so it is one of the 13 heavier plus 14 lighter. If it goes to the right, the fake was moved, so it is one of the 14 lighter plus 13 heavier.

Go to #ED-3

---

And that's it!!! I think that I covered all cases, if not, let me know and I'll review.

Explanation

The trick to solve this kind of puzzles is to think on the avaliable information, that is the possible outcomes of the weighings versus the possible solutions at each step.

A single weighing can go 3 different ways, left, right or balanced, so 5 weighings can go $3^5 = 243$ ways. The possible solutions of the problem are 121 heavier coins plus 121 lighter coins plus 1 no-fake equals 243. That means that with less than 5 weighing it is impossible to do, with 5 it might be possible.

Then, for each step, check that the possible solutions are never more than the possible outcomes. The possible solutions are on each step are the powers of 3: 243, 81, 27, 9 and 3.

For example, Weight #ED-3, there are 14 of one weight and 13 of the other. Those add up to 27 solutions, just right! We must separate 3 groups of 9 solutions each, so we leave 9 coins out, we change plates on 9 coins, and leave 9 coins unmoved. Then the next step will have 9 solutions in every case and all will go smoothly to the next step.

Answer 6

If there is at most 1 fake coin:

8 weighings

Set aside 1 coin. Put 60 on each side of the scale. If they balance, weigh the set-aside vs your coin.

If they don't balance, take 30 from the heavier side and exchange them with 30 from the lighter side (keeping them separate from the 30 on each side that stay). If the balance changes, you know the odd coin is among those 30. Otherwise, it's among the 30 that don't move.

Take off the groups of 30 that are the same, switch 15 coins. Take off the groups of 15 that don't balance. Add 1 genuine coin to each side. Continue this pattern: switch 8, switch 4, switch 2, switch 1.

If you are left with 2 coins that aren't balanced, weigh your coin against 1 of them. If they balance, the other one is fake. If they don't balance, you know the difference.

Answer 7

Another approach, much simpler to describe than my other, which also takes five weighings. Weigh 41 coins against 40+the known good. Assume they do not balance, and say the 41 go down. Mark those 41 H for possibly heavy and the 40 from the other side L for possibly light. Weigh 14 H+13 L against 14 H + 13 L, leaving 13 H + 14 L off the balance. If one side is heavy, which we will assume, you are left with the 14 H from that side and the 13 L from the other. If it balances, you are left with 14 L + 13 H and it should be clear what to do. Erase the markings on the coins now known to be good. Now weigh 5 H + 4 L each side and you will come down to 5 H + 4 L (or 5 L + 4 H). Weigh 2 H + 1 L each side and finally 1 H each side.

If the first weighing balances, you have 40 coins left that might be fake. Weigh 14 vs 13+known good. If it doesn't balance, you are at the 14 H + 13 L stage above. If it does, you are at 13 unknown + 1 good of the Wikipedia article I referenced previously, or you can weigh 5 vs 4+1 good. If it balances, you are down to 4 and can weigh 2 vs 1+1 good. If it balances again you are down to the bad coin and just weigh it against a known good to find heavy or light.

Answer 8

This is exactly the twelve-coins-and-a-scale problem with the following variations:

• There are now 120 coins instead of 12.
• There is a 121st coin plus a 122nd coin that you know is genuine.
• It's possible that none of the coins weigh a different amount at all.

As I explained in my solution to the twelve-coins problem and its generalization, it's possible to devise a fixed weighing schedule. The schema in those previous two linked solutions generalizes to any number of weighings, and the limit for five weighings is 120 coins, without using the LLLLL, RRRRR, or ===== cases. (See the first link for a description of the L, R, and = notation.)

---

Devise a weighing schedule for 120 of your 121 coins, by assigning different combinations of weighings to each coin so that:

• There are always 40 coins on each pan in a single weighing.
• Each coin is placed on a different combination of pans, and for each coin, if you were to reverse the pans that it were placed into, it wouldn't coincide with the schedule another coin. For example, if you decide to give one coin a schedule of L==RL [i.e. left on first weighing, right on fourth, left on fifth, leaving it off on the others], you couldn't give R==LR to another coin.
• You don't place any coin on the same pan for all five weighings.

The reason for the second requirement is so that if a coin is light or heavy, it will always produce a different result from any other coin being light or heavy. Whatever schedule you assign to a coin, it will tip to that schedule if the coin is heavy, and tip the opposite way if the coin is light.

This allows you to use 240 of the 243 possible outcomes.

Now, given that you have your 122nd coin, you can place the 121st coin on the left side, and your known 122nd coin on the right side for every weighing, so there are now 41 coins in each pan. This uses up the three remaining outcomes as follows:

• If the scale tips to the right or left for all five weighings, this means that the 121st coin is either light or heavy respectively.
• If the scale balances for all five weighings, this means that all the coins are in fact genuine.

Answer 9

Take 4 groups as A=40, B=40, C=40, D=1. Compare A & B , keeping aside C & D.
CASE 1-1 : If equal, then the fake is in C or D.
Compare A & C. If equal, then fake is D (Compare with any one coin to know whether it is heavier or lighter) else A is-less-than C or A is-more-than C, so we know whether fake is heavier or lighter, and we only have 40 coins to analyse.
CASE 1-2 : If not equal, then fake is in A or B. Without loss of generality, let A is-less-than B (Process is same if A is-more-than C). Compare A & C. If equal, then fake is in B & is heavier, else fake is in A & is lighter. We only have 40 coins to analyse.

With 2 weightings, we know which 40 coins have the fake and whether it is heavier or lighter. Without loss of generality, assume it is lighter.

Now take 4 groups as A=13, B=13, C=13, D=1. Compare A & B.
CASE 2-1 : If equal, then fake is in C or D, so compare A & C, to know which has the fake.
CASE 2-2 : If not equal, then fake is in A or B, so compare A & C, to know which has the fake.
If both weightings as equal, then fake is D.

With 2 more weightings, we have only 13 coins remaining.

Now take the groups as A=4, B=4, C=4, D=1. With 2 more weightings, we will have only 4 coins remaining, or we would have found D as the fake.

Now take the groups as A=1, B=1, C=1, D=1. With 2 more weightings, we will know the fake coin.

So we require only 2+2+2+2=8 weightings in maximum, unless we find the fake coin quicker.

Can we do better than 8 ?
We have to get enough information for finding the fake coin in 121 possibilities & 1 bit of information for finding whether that fake coin is heavier or lighter. Combined, we have 121*2=242 possibilities. Every weighing gives 1 ternary bit of information. So minimum information required is 5 ternary bits of information (3*3*3*3*3=243) or 5 ternary weightings. We can do better than 8, but we can not do better than 5. Many answers already have this minimum.

Answer 10

You need 5 tests

Number the coins with the following trinary (base 3) numbers: $\{0< x< 3^5 | \text{ first non-zero digit is 1 and the number of zero digits is even}\}\cup\{0< x< 3^5 | \text{ first non-zero digit is 2 and the number of zero digits is odd }\}$.
Following are the first few of them: $00001, 00010, 00021, 00022, 00100, 00111, 00112, 00121, 00122, 00201, 00202, 00210, 00220, ...$
That means there is no coin numbered $00002, 00011, 00012, 00020, 00101, 00102, 00110, 00120, 00200, 00211, 00212, 00221, 00222, ...$
Fill the scale five times and put the real coin on the side where one coin is missing.
The first time put all the coins with a 1 as the first digit on the left side and all coins with a 2 as the first digit on the right side.
The second time do the same but look at the second digit. And so on.

Write down the result of each test: Write down a 0 if the scale is balanced; write down a 1 if the left side is heavier and a 2 if the right side is heavier.
If the result is 00000 then there is no fake coin.
If there is a coin with the resulting number that coin is heavier then the other coins.
If there is no coin with the resulting number then replace all 1s with 2s and all 2s with 1s and the coin with that number is lighter then the other coins.

Example 1:

That means the scale will tilt to the right during the first and the fifth test and left during the second and third test and will be levelled during the fourth test.
The resulting number will be 2(first test->right), 1(second test->left), 1(third test->left), 0(fourth test->levelled), 2(fifth test->right)
Concatenation of these numbers give 21102 = the number of the heavier coin.

Example 2:

That means the scale will tilt to the right during the second and the third test and left during the fifth test and will be levelled during the first and the fourth test.
The resulting number will be 0(first test->levelled), 2(second test->right), 2(third test->right), 0(fourth test->levelled), 1(fifth test->left)
There is no coin numbered 02201.
That means we have to switch the 1s and 2s and the coin 01102 is the lighter coin.

Why does this works:

Each coin has an individual sequence of placements on the scale.
The coding is chosen in a way that for heavier coins that coding is the results of the tests.
For lighter coins you would have to write down the numbers of the upwards sides of the tests and that is simulated by switching the 1s and 2s at the end.

For an exhaustive proof you would need to proof that both sides of the scale have the same number of coins, but that is omitted here.
This method can be extended to the same question with $364$ coins and $6$ tests or general $\frac{3^n-1}{2}$ coins and $n$ tests.

Answer 11

I can do this in TWO Weightings.

A weighing is the measure of a complete group. It is a mark in the notebook, as a trial. So when you put 60 coins on one side of the scale, you did not do 60 trials, but one. Though, if you count every movement of the coin as a measure, this approach also wins.

So here is my approach:

1. Put half of the coins in one side of the scale, and half in the other, keeping the "known good" separate (not on scale). We will call the left side A and the right side B. If scale is even, there is no fake coin.
2. Remove one coin from both sides simultaneously and place both of those coins into a temporary pool, C. If there were any coins in C from a previous draw, discard them such that there are only ever two.
3. As soon as the scale evens out, you know one of the two coins just removed in TEMPORARY PILE C was the fake one. Let's call the two coins in C now C1 and C2. Complete the removal of coins from both trays, which completes the FIRST MEASURE
4. Put C1 on the left (from group "A"), and put Known Good on the right (from group "B"). If they balance, C2 is the fake, otherwise C1 is the fake. SECOND MEASURE

Tadaa! If anyone wants to argue that my approach is invalid because there are multiple measurements, I disagree. You only record and reload the scale twice. Think about it: My method also means you touch the least number of coins total out of any approach. If N is number of coins, my approach is around O(2N+2.5). So even if you count every change of coin in and out of scale as a measure, this approach still has the least.

EDIT: See my first comment, doing the inverse wherein you start with no coins and slowly add to either side until the tip, then do step #4 above is quicker and much more efficient. That, on average is O(.5N+2.5) touches, where N is number of unknown coins.