Finding the Heavy Coin by weighing twice

Question

Suppose you have $100$ coins. $96$ of them are heavy and $4$ of them are light. Nothing is known regarding the proportion of their weights. You want to find at least one genuine (heavy) coin. You are allowed to use a weight balance twice. How do you find it?

Assumptions:

Heavy coins all have the same weight; same for the light coins.

The weight balance compares the weight of two sides on the balance instead of giving numerical measurement of weights.

Answer 1

I think this works.

Divide the coins into three groups: $A$ with $33$ coins, $B$ with $33$ coins and $C$ with $34$ coins.

Weigh $A$ and $B$ against each other.

Now if $A$ is heavier than $B$, then $A$ cannot have two or more light coins, as in that case, $A$ would be lighter (or equal to $B$). Now split $A$ into groups of $16$ plus one odd coin. Weigh the groups of $16$ against each other. If they are the same, then any of those coins is heavy. If not, then any of the heavier 16 coins is heavy.

Consider the case when $A$ and $B$ are equal.

The possibilities for $A$, $B$ and $C$ are:

+-----------+------------+-----------+
|  A        |   B        |  C        |
+-----------+------------+-----------+
|  33H      |  33H       |  30H + 4L |
|           |            |           |
|  32H + L  |  32H + L   |  32H + 2L |
|           |            |           |
|  31H + 2L |  31H + 2L  |  34H      |
+-----------+------------+-----------+

Now move one coin from $A$ to $B$ (call the resulting set $B'$) and weigh it against $C$.

If $B' > C$, then the coin you moved from $A$ is a heavy coin.

If $B' = C$, then the coin you moved from $A$ is a light coin and the remaining coins in $A$ are heavy.

If $B' < C$, then all the coins in $C$ are heavy.

Answer 2

If you pay me $95$ of the coins in advance I'll show you how ;-).

Answer 3

To avoid wasting readers' time when posting puzzles, it is useful (and will improve the upvote/downvote ratio) to provide:

1. an indication of the difficulty level. Was this puzzle in a math-is-fun book for children, or is it a generalization of a problem from the final round of a national olympiad? Having schoolchildren attempt a question that (they were not told) is the $n=100$ specialization of a combinatorial lemma from a research paper, is a waste of time. Having mathematicians spend time on (what might look like) a coin weighing puzzle from the literature, but is really an easy task the high school students could solve with some patience, is a waste of resources.

2. the source, if known. This helps those who want to evaluate the difficulty before taking time to attempt a solution, or who would like to look up hints or answers.

3. indicators of whether the problem is correct or solvable as stated. Problems from a book, a competition or a journal are likelier to be correct and unambiguously formulated. Questions invented, circulated and (believed to be) solved among friends or students are more likely to have pitfalls that were missed in setting or solving the problem.

4. clear definitions. In this case, coin weighing problems involve at least two very different interpretations of "use a weight balance". Weighing can mean comparison or numerical measurement and what is possible is completely different in those settings. Not specifying which is meant can waste the time of users who try to solve the problem in the wrong interpretation.

Answer 4

[Edit] As pointed out by longway, there's a hole in this.

My assumptions:

• Your heavy coins all have the same weight; same for the light coins.

• The weight balance compares the weight of two sides on the balance instead of giving numerical measurement of weights.

Method: Divide the 100 coins into 2 groups A and B, each comprises 49 coins. The remaining 2 coins are labelled C and D.

1. Weight A and B.

1.1 A > B (which also handles symmetrically B > A)

Divide A into 24 + 24 + 1 coins, and weigh 24 vs 24.

1.1.1 If the two sides are equal, all of them are genuine.

1.1.2 Otherwise the heavier side contains all genuine coins.

1.2 A = B

Divide A into 24 + 25 coins, add C to the 24 side, and weigh 25 vs 25. Call the side containing C the C-side.

1.2.1 If the C side is heavier, then C is genuine.

1.2.2 If the C side is equal to the other side, then C side minus C are all genuine.

1.2.3 If the C side is lighter, then the other side contains all genuine coins.

Explanation: Divide the 100 coins into 2 groups A and B, each of 49 coins, and label the remaining 2 coins as C and D.

1. Weight A and B.

1.1 A > B, it means that B has more fake coins than A. Clearly this means that A has either 0 or 1 fake coins.

Divide A into 24 + 24 + 1 coin, and weigh 24 coins against the other 24 coins.

1.1.1 If they are equal, then they must all be genuine since there's at most one fake coin.

1.1.2 If they aren't equal, the heavier side contains all genuine coins.

The case where B > A is symmetric.

1.2 A = B, it means that A and B have same number of fake coins. This number could be 1 or 2.

Divide A into 24 + 25 coins, and add C to the 24 portion, and weigh these 25 coins against the other 25.

• If A and B both have 1 fake coin only, that means both C and D are fake.

• If A and B both have 2 fake coins, that means both C and D are genuine.

That means

• if A has 1 fake coin, then the C side is

  • equal to the other side when C-side minus C are all genuine coins, and the other side contains one fake coin.
  • lighter than the other side when C-side contains the other fake coin as well. In this case the other side contains genuine coins.

• if A has 2 fake coins, then the C side is

  • lighter than the other side when both fake coins are on the C-side. In this case the other side contains genuine coins.
  • heavier than the other side when some fake coins are on the other side. In this case, C must be genuine anyway since A has 2 fake coins.

So

• if the C side is heavier, then C is genuine.
• if the C side is equal to the other side, then C side minus C are all genuine coins.
• if the C side is lighter, then the other side contains all genuine coins.

Answer 5

Update: It seems that Moron has a valid objection (see the comments) that renders my solution incorrect:

Two sides are equal: You could have 2 heavy and 2 light. Either all light or all heavy is incorrect.

In other words:

Yaser's answer misses one case. Where we get H+L vs H+L giving us equal on the first weighing.

At first, I thought that even if this was the case, one could still find a heavy coin with only one more weighing. Alas, in every weighing scheme I could think of in the context of my solution, there was a situation where one weighing does not give the necessary information to guarantee selecting a heavy coin. Perhaps there's some twisted weighing scheme I didn't think of that would guarantee a correct selection, but I really doubt that (don't take my word for it though.. it's left as an exercise to the reader.)

Moron's solution seems to be a correct one, especially that it is, according to T.., the same as the solution by the original proposer (Shapovalov). I still have to check it out, but it's getting late and I'm quite exhausted. For now, I think it's time for me to get some sleep and to accept the downvotes. Be gentle!

---

Let me elaborate on whuber's answer by putting it in a slightly different form.

Let's randomly choose 5 coins out of the 100. Let's denote this set of coins by . Since there are only 4 light coins, we are absolutely sure that contains at least one heavy coin. Now, the problem is reduced to simply finding one heavy coin in by using the weight balance twice.

Now stop for a moment and see if you can solve the new reduced problem on your own.

Can't figure it out? Well, choose any 4 coins and put 2 on one side of the balance and 2 on the other. Now, what are the possible outcomes?

• The two sides are equal. This means that the 4 coins we put on the balance are either all light or all heavy (Update: This is not true. See the update at the beginning). In this case, pick any coin from the balance and compare it with the one we left out. If one is heavier, it would be trivial to select it as a heavy coin. If both are equal, then all of the coins in our initial were actually heavy, so just select any!
• One side is heavier. This implies that at least one of the 2 coins on this "heavier" side is a heavy coin. Take these 2 coins and compare them with each other. Now selecting a heavy coin is trivial (if they are of equal weight, then they are both heavy, so just select one!)

Whuber's answer/hint (look in the comments) put me on the right track to this solution, so don't forget to vote his answer up!

Answer 6

Pick any four coins and weigh two against two. If they are imbalanced then at least one of the two coins on the heavier side is heavy and they can now be weighed against each other to identify one or both as heavy. Otherwise replace the two coins on either side of the balance with two other coins. If they are now imbalanced then both coins on the heavier side are heavy, and if they are still balanced then all six coins are heavy.