Knowledge and Uncertainty

You run the mint for a small kingdom and the Queen has requested 44 coins for her trip abroad (she is a modest ruler). Everything is in place when, on the eve of your delivery, thieves break into the mint.

In the morning, you find the Queen's coins along with a note:

These pretty coins shine in the light.
But so does a fake and just as bright.
Did I gaze at them then take my leave,
Or replace one with a forgery?

If you can't read old English, here's a translation: it's possible that one of the coins is a forgery.

To help to figure it out, you're given a scale and a reference coin that's guaranteed to be real.

How many times do you need to use the scale to find out the truth?

Find the Counterfeit Coin

                           

Remember — in this puzzle there are 44 coins, and either one of them is counterfeit, or all of them are real.

If one of the coins is counterfeit, it can either be heavier or lighter than the others.

For example, one of the possibilities is "coin 33 is the counterfeit and weighs less than a genuine coin." Another possibility is "all the coins are real."

How many possibilities are there?

Find the Counterfeit Coin

                           

There are nine possible answers that we need to narrow down.

We can give each of them a label so that, for example,

  • "coin 33 is the counterfeit and is lighter than a real coin" 3\rightarrow \textcolor{#3D99F6}{\textbf{3}^-} and
  • "all the coins are real" A.\rightarrow \textcolor{#69047E}{\textbf{A}}.

If each of these outcomes is equally likely, what is the probability of A?\textcolor{#69047E}{\textbf{A}}?

Find the Counterfeit Coin

                           

It might be tempting to start our weighing by putting half the coins on one side and the other half on the other:

Suppose we do this and find that the left side is heavier. Which hypotheses might still be true?

Remember that these were the nine hypotheses originally:

Find the Counterfeit Coin

                           

This picture shows us which hypotheses would remain after each of the possible outcomes:

It seems that there aren't an equal number of hypotheses left standing in each case.

Find the Counterfeit Coin

                           

Was this a good weighing scheme to pick first?

We can judge it by quantifying how many hypotheses are still possible, on average, after we get the answer. We'd like to make that number as low as possible because we need to try to eliminate possibilities using as few questions as possible.

Find the average number of hypotheses left, given that

  • 19\frac19 of the time you're left with 11 hypothesis and
  • 89\frac89 of the time you're left with 44 hypotheses.

Find the Counterfeit Coin

                           

Suppose you're about to put a group of coins on the left side of a scale, and another group on the other side. One possibility is that the left side will be heavier than the right.

How many possible outcomes are there for this weighing in total?

Find the Counterfeit Coin

                           

What makes for an informative weighing in general?

When you weigh two things against each other, you're really asking, "How do the weights of these two objects compare?" There are three possible answers:

  1. the left is heavier than the right,
  2. the right is heavier than the left, or
  3. both sides weigh the same.

This was the insight from our last quiz:

The most informative questions are the ones whose answer we are the most uncertain about.

The first weighing we considered did not obey this principle, since there was one thing we could be fairly confident about — both sides would not weigh the same. That's why that weighing was not maximally informative.

We'd have the most uncertainty if all three possible answers were equally likely, instead.

How many hypotheses would be left if we asked such a maximally informative question?

Find the Counterfeit Coin

                           

Our original weighing left behind more hypotheses on average than a maximally informative question would have ((i.e. about 3.673.67 rather than just 3).3).

This is why we're looking for a weighing that splits the hypotheses into three groups of equal size.

Which of these weighings would do that?

Find the Counterfeit Coin

                           

Let's see why this weighing worked:

If we leave off coin 4,4, there are now more ways for the two sides to balance — either there are no counterfeit coins, or coin 44 is the counterfeit and it's heavy or light.

If the left side is heavier, then that means that either coin 11 or 22 is counterfeit and heavier, or else coin 33 is counterfeit and it's lighter. This way, the scale partitions the hypotheses into three equal-sized groups:

Find the Counterfeit Coin

                           

Suppose we make this measurement and find that the left side is heavier, leaving these three possibilities:

Which of these should be our second weighing?

Find the Counterfeit Coin

                           

When we did this weighing, both sides balanced!

Which coin is the counterfeit? And is it heavy or light?

Find the Counterfeit Coin

                           

Well done, you found the counterfeit coin!

The solution turned out not to be arbitrary at all. All we had to use was our insight:

The most informative questions are the ones whose answer we are most uncertain about.

Find the Counterfeit Coin

                           

In fact, this insight is enough to answer a much harder version of the puzzle.

Suppose that you have 1313 coins that you must investigate and, as before, one real coin and a scale to help you. Can you figure out the least number of weighings to find the counterfeit coin (if there is one) and know whether it is heavy or light?

You can try to answer this question yourself with what we've learned, or you can wait until we revisit this problem in Chapter 2.

Find the Counterfeit Coin

                           
×

Problem Loading...

Note Loading...

Set Loading...