|
It's tempting to think that every problem can be solved by
following some direct path to the solution (such as setting
up an equation and solving it). But often that's not the
case - or the direct path is far from obvious. For example:
Q: Find the three smallest two-digit numbers that have an odd
number of factors.
A: Suppose we systematically start examining all the two-digit numbers,
and write down all their prime factors, and their factors:
Number Prime Factors Factors
------ ------------- ----------------------
11 11 1, 11
12 2, 2, 3 1, 2, 3, 4, 6, 12
13 13 1, 13
14 2, 7 1,
15 3, 5 1, 3, 5, 15
16 2, 2, 2, 2 1, 2, 4, 8, 16
So we've found one! What you might do now is look at the prime
factors for the numbers 1-11, and see if you can spot something that's
different about the prime factors for 16.
Or, you can just keep extending the table until you find three numbers
with an odd number of factors. By the time you find the third, I'll
bet you'll be able to spot the pattern. Then the fun part is trying
to explain _why_ that pattern leads to that result.
If you're going to systematically explore
a space of possible solutions, it's important to have some way
of keeping track of what you've done, so you don't (1) forget to
try some of the possibilities,
or (2) keep trying the same things over and over.
In the example above, we used a table. Sometimes we need
to get a little more creative:
Q: Suppose we have 9 coins, and we know that one is heavier than
the others, and we'd like to find it with as few weighings as
possible (using a balance scale).
A: We can divide the coins into three groups: (1,2,3), (4,5,6), (7,8,9).
Next, we can weigh the first two groups against each other. Three
possible things can happen: They can balance each other, or the first
can be heavier, or the second can be heavier. We would represent this
in a flow chart as
[Divide coins into three groups]
|
|
v
[Weigh first group against second group]
|
______________|______________________
| | |
| | |
| balance? | (1,2,3) | (4,5,6)
| | heavier? | heavier?
| | |
v v v
Now, depending on which of these happened, we will have to do
something different. If the first two groups balanced, we know that
the heavier coin is in the third group. So then we weigh two coins
from that group. Again, three things can happen: The first can be
heavier, the second can be heavier, or they can balance:
[Divide coins into three groups]
|
|
v
[Weigh first group against second group]
|
______________|______________________
| | |
| | |
| balance? | (1,2,3) | (2,3,4)
| | heavier? | heavier?
| | |
v v v
[weigh 7, 8]
|
___|_________________________
| | |
| | |
| balance? | 6 | 7
| | heavier? | heavier?
| | |
v v v
If they balance, we know that the last ball is the heaviest, so we're
done! If either is heavier, we know that it's the ball we're looking
for, so we're also done.
[Divide coins into three groups]
|
|
v
[Weigh first group against second group]
|
______________|______________________
| | |
| | |
| balance? | (1,2,3) | (2,3,4)
| | heavier? | heavier?
| | |
v v v
[weigh 7, 8]
|
___|_________________________
| | |
| | |
| balance? | 6 | 7
| | heavier? | heavier?
| | |
v v v
<9> <6> <7>
Now we need to do something similar for the possibilities that we
haven't left open. I won't complete it, because it wouldn't add a lot
to what's been said, but this is the main idea behind a flow chart.
You do some kind of test, and depending on what happened, you go to a
subsequent test, until you've asked enough questions to find out what
you want to know.
|