Chapter 7
Notes for 25 August

7.1 Problem solving principles

• So far we’ve covered problem solving by recognizing and playing with patterns.
• Pattern matching is one part of mathematical “common sense” and a valuable way to start on a problem.
• Recognizing patterns is only one approach to problem solving.
• Mathematicial George Pólya spent much of his life considering how mathematicians and others approach problems.
• His problem solving principles are a good general description.

7.1.1 Pólya’s principles

These are principles and not a recipe or a plan. Use these to form a problem-solving plan. (Problem solving itself is a problem…).

The principles are very well explained in Pólya’s light book, How to Solve It. He later goes into much depth in his two part series on Mathematics and Plausable Reasoning (volume 1, volume 2).

• Understand the problem
• Divise a plan
  • Text provides ideas, and we will cover a few.
• Carry out the plan
• Examine the solution

7.1.2 Understand the problem

• Goals in understanding: Find the data you have and the solution you need.
• Often helps to rephrase a few ways.
  • In English (or whatever is appropriate)
  • With mathematical notation
• Determine what may be relevant.
• Sketch the problem graphically, with numbers, with physical items… Whatever works for you on this problem.
• Decide if the problem may have a reasonable solution.
• Example: Problem of the seven coins.

7.1.3 Divise a plan

• Goal: Decide on an approach to the problem.
  • The first plan is your initial plan.
  • You may need to toss it aside and form a new one...
  • Often useful to approach a problem with a few plans at once.
• Taxonomy of plans in the text.
• Plans apply inside and in conjunction with other plans.
• Few problems fall to a single technique.
• Being excessively clever is not a plan.
• Most “cleverness” comes from experience and practice.

• When I think about the strategy, I consider what I want to write about it. A major goal of mathematics is communicating ideas well.
• To communicate a plan to others, you need all the understanding and precision necessary to carry out the plan.

7.1.4 Carry out the plan

• Details depend on the plan…
• May work, may not work.
• Dead-ends are common when approaching new styles of problems.
• Moving through the plan requires attention to detail.
  • Mathematicians and scientists grow to loath +/- signs.
  • Eventually, you learn which details can be “fixed” later.

7.1.5 Examine your solution

• Very, very important.
• Check your results somehow, possibly by varying the problem a little.
• Trying a different solution technique also can check your problem.
  • Re-trying the same technique often does not help. People often make the same mistakes.
• Try to generalize a little.
• Interpret your results by writing sentences. Often provides a check in itself, or leads to an alternate route.
  • Common in mathematics: First publication of a result is long and hairy. Interested people being interpreting it, and a short or more direct proof is found.
  • Erd\H{o}s and the “book proof”.

7.2 Making a lists and tables

• Lists are useful for
  • counting items, and
  • systematically searching possibilities.
• Planning includes deciding how to construct the list.
  • The method must be systematic and easy.
  • Will get plenty of practice when building logic tables.
• Careful planning helps to construct a smaller list.
  • Relationships found from understanding and guessing can help.
• We will talk about bisection, working with a list but not forming all of it, next time (“trial and error”).

7.2.1 Example of a table

How many ways can you form 21 cents from dimes, nickles, and pennies?

While thinking of the problem, note that the last 1 cent does not change the number of ways to form the total. There always will be one penny involved. We should just drop that one penny.

Plan: Form a table. Then the plan becomes how to form the table.

We can start with an extreme solution and modifiy it one row at a time. In the table, we push change from left (higher) to right, while checking the total.

So there are nine ways of forming 21 cents from dimes, nickles, and quarters.

7.3 Searching by guessing

• Guessing, a good start to just about every problem. Helps to:
  • find examples,
  • discover relationships,
  • gain a feel for the problem,
  • or just find the answer.
• Guessing randomly is of little use.
• Use relationships gleaned from understanding the problem to prune your guesses.
• Sometimes the relationships are as easy as “smaller inputs yield smaller results.”

7.3.1 Example for guessing and checking

Complete the following triangle such that the numbers in the vertices are equal to the sum of the variables adjacent to them. Assume all the variables are positive integers.

• When considering the problem, look for relationships that can guide your guesses.
• Because a, b, and c are positive, we know the sum of any two is greater than either. That is, 16 = a + b > a, and 16 = a + b > b.
• The initial plan becomes to pick numbers less than the ones shown.
• Try a guess, and notice that you only need to pick one number. The rest are completely determined.
• So you can start with a and guess from numbers less than 11.

Now look back and consider some new relationships:

• 16 + 11 + 15 = 2(6 + 5 + 10).
• Try other numbers in the vertices, see if this relationship holds.
• For which numbers does this problem have a solution when a, b, and c all are positive integers?
  • What are the smallest numbers?
  • What property must the sum of the numbers have?

7.4 Understanding dependencies, or ”working backward”

• “Working backward” is short-hand for following the chain of dependencies in a problem.
• Useful when it looks like there’s no where to start, but there are definite known points along the way.
• The plan:
  • Start with what you know.
  • Derive every quantity you can from that data.
  • Repeat.

7.4.1 Example for following dependencies

Example 2 from the text:

First, rephrase the problem mathematically. Let {M}_{n} be his total starting in week n. We want {M}_{1}. From the problem,

As written, {M}_{2} depends on {M}_{1} and so on. But we only have the last total, {M}_{4}.

So our plan:

• Rearrange dependencies to start from what we have and lead to what we want.

Thus,

Substituting {M}_{4} = 224,

Looking back:

• Alternate approach: We could have algebraically substituted {M}_{2} and {M}_{3} into the expression for {M}_{4} and solved.
• End result is the same, but with less algebra.

7.5 Next time: more techniques

7.6 Homework

Practice is absolutely critical in this class.

Groups are fine, turn in your own work. Homework is due in or before class on Mondays.

• Exercises for 1.3
  • Understanding the problem: Problem 6
  • Guessing and checking: problem 12
  • Listing: problems 31, 35
  • Dependencies and diagramming: 28, 57

Note that you may email homework. However, I don’t use Microsoft^TM products (e.g. Word), and software packages are notoriously finicky about translating mathematics.

If you’re typing it (which I advise just for practice in whatever tools you use), you likely want to turn in a printout. If you do want to email your submission, please produce a PDF or PostScript document.