98 Unit 3 Problem solving: basic skills
3.6 Solving problems by searching
Some problems may not always be resolved by
using direct methods of calculation.
Sometimes, problems do not have a single
solution, but many, and we need to find one
that represents a maximum or minimum (for
example the least cost or shortest time for a
journey). In these cases we need to have a
systematic method of evaluating the data to
come up with all (or at least the most likely)
possibilities. This is called a ‘search’. Once
again, with this type of question, it is
important to have a way of checking that the
final answer is correct.
Here is an example of a problem that
requires a search.Amir is helping with a charity collection and
has gathered envelopes containing coins
from a number of donors. He notes that all
the envelopes contain exactly three items but
some of them contain one, two or three
buttons instead of coins. All the coins have
denominations of 1¢, 5¢, 10¢, 25¢ or 50¢.
What is the smallest amount of money
that is not possible in one of the envelopes?Activity
Commentary
The easiest way to approach this question is to
list the possibilities in a systematic order. We
know envelopes can contain 0, 1, 2 or 3 coins.
The possibilities with one coin (and two
buttons) are: 1¢, 5¢, 10¢, 25¢ or 50¢.
That was the easy part. With two coins (and
one button), we need to be a little more
careful. First consider that the first coin is 1¢,
then look at all the possibilities for the second.We can then continue with the first coin as a
5¢ in the same manner (we do not need to
consider repeats). The possibilities are:
1¢ + 1¢, 1¢ + 5¢, 1¢ + 10¢, 1¢ + 25¢, 1¢ +
50¢, then
5¢ + 5¢, 5¢ + 10¢, 5¢ + 25¢, 5¢ + 50¢,
10¢ + 10¢, 10¢ + 25¢, 10¢ + 50¢,
25¢ + 25¢, 25¢ + 50¢, and
50¢ + 50¢.Listing all the totals, we have: 2¢, 6¢, 11¢, 26¢,
51¢, 10¢, 15¢, 30¢, 55¢, 20¢, 35¢, 60¢, 50¢,
75¢ and $1.
Finally, we need to list all the possibilities
with three coins. This is slightly more difficult.
However, we only need to go on until we have
found an impossible amount (you may already
have spotted it). The possibilities are:
1¢ + 1¢ + 1¢, 1¢ + 1¢ + 5¢ etc.
1¢ + 5¢ + 5¢ etc.You should have spotted by now that we have
not seen the value 4¢ and that all further sums
of three coins (anything including a 5¢ or above)
will be more than 4¢. So 4¢ is the answer.
This was actually a trivial example used for
the purposes of illustration. There is an
alternative way to solve this, which also
involves a search. This is to look at 1¢, 2¢, 3¢,
etc. and see whether we can make the amount
up from one, two or three coins. In this case it
would have led to a very fast solution, but if
the first impossible value had been, for
example, 41¢, this second method would have
taken a very long time and we might have
been unsure that we checked every possible
sum carefully.
The method described above is called an
‘exhaustive search’, where every possible