Algorithmic Problem Solving

This chapter is the first of two considering more demanding applications of induction. The motto of Section 6.6 can be summarised as “Do not guess! Calculate.” We put this into practice in this chapter.

Suppose we are given a number of coins, each of the same size and shape. We are told that among them there is at most one “fake” coin, and all the rest are “genuine”. All “genuine” coins have the same weight, whereas a “fake” coin has a different weight than a “genuine” coin.

The problem is how to use a pair of scales optimally in order to find the fake coin, if there is one.

Note the element of vagueness in this problem statement; we do not say what we mean by using the scales “optimally”. This is deliberate. Often, an essential element of problem solving is to clearly identify the problem itself. Our formulation of the problem and its eventual solution illustrates several other aspects of “real” problem solving. Several stages are needed, including some “backtracking” and revision.

7.1 PROBLEM FORMULATION

When we use a pair of scales to compare two weights – an operation that we call a comparison – there are 3 possible outcomes: the scales may tip to the left, they may balance, or they may tip to the right. This means that with n comparisons, there are at most 3ⁿ different outcomes. This gives an upper bound on what can be achieved using a pair of scales.

Now, suppose we are ...