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. ```