10
$\begingroup$

There are 16 coins, 3 of which are slightly heavier or lighter than the others. The counterfeit coins have the same weight but it is not known whether they are heavier or lighter than the genuine ones.

Using a balance scale, what is the minimum number of weighings in order to determine whether the counterfeit coins are heavier or lighter?

Notes:

  • All the coins look identical.
  • The genuine coins have the same weight.
  • You can compare any number of coins on the balance scale.
$\endgroup$
1
  • 10
    $\begingroup$ This is a question asked at puzzleup.com/2020. It is clearly against the competition rules to ask for outside help. Shame on you, helloworldx. $\endgroup$ – Boluc Papuccuoglu Dec 17 '20 at 8:30
15
$\begingroup$

This is my first answer on the puzzling stack exchange and I'm really not used to explaining things like this so it's probably going to be rather convoluted. I'll probably come back and edit it later when I can figure out how to make this clearer.

Solution for a maximum of 4 weightings:

First divide the coins into 4 equally sized piles.

There are now 3 possible fake coin placements:

Pile #1 Pile #2 Pile #3 Pile #4
# of fake coins 3 0 0 0

or

Pile #1 Pile #2 Pile #3 Pile #4
# of fake coins 2 1 0 0

or

Pile #1 Pile #2 Pile #3 Pile #4
# of fake coins 1 1 1 0

But of course, you don’t know which scenario you’re in. For the sake of simplicity I'm going to call any pile with at least one fake coin an "impure" pile and a pile without any fake coins a "pure" pile.


Compare any two piles. If they are equal write down an equal sign (=) on the top of both piles, if they are different write down which side is heavier and which side is lighter (perhaps by using ≥ and ≤ signs). Now take the other two piles and compare them. As with the first comparison, write down whether the piles are heavier, lighter or the same. It might be useful to write down the results of different comparisons with differently colored markers to make it easier to track which pile was compared to which other pile because we'll need this information.

Strictly speaking you could just keep track of these things using a piece of paper or even in your head, but I think physically marking relevant information on the top of each pile makes it less likely you'll mess up.


Regardless, you will find that there was either a difference during both comparisons or both piles weighed the same during one comparaison and there was a difference during the comparison of the other 2 piles.

If there was a difference in both comparisons:

You must be in the 1,2,0,0 scenario:

One comparison was between piles with 1 fake coin and 0 fake coins. The other was between piles with 2 fake coins and 0 fake coins.

Now compare two piles with the same sign.

If they have the same weight:

You’ve found the two piles containing no fake coins. Simply compare one of the pure piles to one of the impure piles you’ll know whether the fake coins are lighter or heavier.

If they have different weights:

You’ve found the piles containing 1 fake coin and 2 fake coins. By the process of elimination, the other two piles must have no fake coins. Simply compare one of the “pure” piles to one of the “impure” piles you’ll know whether the fake coins are lighter or heavier.

If one of the comparisons resulted in the piles being the same weight and the other two piles different weights:

Then we cannot know what scenario we’re in right away. Fear not. Take one pile out of the pair that had the same weight. Now divide that pile into two numerically equal parts and compare the two newly created sub piles to each other.

If they have the same weight:

Then that pile must have no fake coins in it. The same must be true for the other equal pile. You are either in scenario 3,0,0,0 or scenario 1,2,0,0. Compare one of the equal piles to one of the unequal piles.

If they weigh the same:

You're in scenario 3,0,0,0 and you've just found the third "pure" pile. Simply read what's written on the impure pile and you'll know whether the fake coins are heavier or lighter.

If they don't weigh the same:

You can't know whether you're in scenario 3,0,0,0 or scenario 1,2,0,0 but it doesn't matter. You're definitely comparing a pile with no fake coins to a pile with fake coins so simply check whether the impure pile is lighter or heavier and you'll know your answer.

If they don't weigh the same:

You're in scenario 1,1,1,0. And you've found two of the impure piles (both piles with an equal sign). Now compare one of the impure piles to one of the unknown piles.

If they weigh the same:

You've just found the third "impure" pile. By the process of elimination the last untested pile is the pure pile and you can simply read what's written on it to know whether the normal coins are heavier or lighter than the fake coins and consequently whether the fake coins are lighter or heavier.

If they don't weigh the same:

You've just found the "pure" pile. Read what's written on it and you'll know whether the normal coins are heavier or lighter than the fake coins and consequently whether the fake coins are lighter or heavier.

$\endgroup$
1
  • 5
    $\begingroup$ Wonderful first answer! I think all of this makes sense (will have to re-read to make sure). The nested quotes make it much easier to understand your strategy. $\endgroup$ – bobble Dec 16 '20 at 20:04

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