Chapter 8
Notes for 27 August

8.1 Review: Pólya’s problem-solving 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…).

• Understand the problem
  • Determine what data you have and what quantities you need.
  • Try rephrasing the problem in words and in symbols.
  • Look for relationships: symmetries, which items are fully determined by others, etc.
• Divise a plan
  • Remember previous similar problems and extend the pattern.
  • Use relationships to help select possible plans.
  • Make plans as specific as possible.
• Carry out the plan
  • Pay attention to details.
• Examine the solution
  • Check your solution, either directly or against relationships.
  • Consider related (and future) problems.

Previous tactics:

• Making lists or tables:
  • Good for systematic searching or counting.
  • Requires care in forming the tables.
• Guessing:
  • Good for discovering or extending relationships.
  • Rarely a complete plan on its own, but great for starting.
• Dependencies, or working backwards:
  • Essentially, find the starting point and then exhaust all the rules or formulas that apply. (Breadth-first)
  • Or try following one piece of data through all possible rules, then backtrack. (Depth-first)

Today, a few more tactics:

• “Trial and error”, but a bit more systematically and quickly through bisection.
• Using simpler sub-problems to find patterns.

8.2 Effective trial and error by bisection

Remember:

Geometric sequence

Sequence of numbers defined by a starting number and a constant multiplier. The second number is generated by multiplying by the constant, the third by multiplying again, and so on.

Consider the sequence where 3 is the starting number and two is the constant.

Which term in the sequence is 768?

8.2.1 Understanding the problem

• What do we have?
  • Definition of a specific geometric sequence, 3 ⋅ {2}^{n-1}.
• What do we need?
  • A specific term equal to 768.

8.2.2 Forming plans

• Baring use of logarithms, what is one possible plan?
  • Extend the table until it reaches 768.
• A list would work, but could be long.
  • Guess how long.
    • What is {2}^{10}? 1024. What is 3 ⋅ {2}^{10}? 3072.
• Now we have more information.
  • So we know the third term is smaller, 12 < 768, and the eleventh term is larger, 3072 > 768.
• Consider filling in only some entries of the list. Which to try next?
• Try going half-way, a new plan.

8.2.3 Carrying out the new plan

• Half-way is the seventh term, 3 ⋅ {2}^{6} = 192.
• Now what do we know?
  • That 768 must be after the seventh term and before the eleventh.
• Half-way again is the ninth term, \mathbf{3 ⋅ {2}^{8} = 768}.

8.2.4 Looking back

• Calculated three additional terms (12, 7, 9) rather than six (4, 5, 6, 7, 8, 9).
• When considering finding an entry by a list, look for an ordering relationship.
  • Each entry no smaller or larger than the previous. (How does that differ from always being larger/smaller?)
  • Or if you’re looking for a property, try to order the list so that all those after a point have (or don’t have) that property.
• Use the ordering to reduce work (and errors).
  • Calculate a few entries spaced far apart.
  • Find entries that bracket your search target. So you know your target is between a and b, or in (a,b).
  • Then look half-way to form a new bracket. The new bracket will be one of \left (a,(a + b)∕2\right ) or \left ((a + b)∕2,b\right ). Remember to round consistently.

8.3 Simpler sub-problems for finding patterns

What is the units digit of {7}^{100}?

• Relatively straight forward, so try examples to gain a feel for the problem.

• Want a quick plan for generating examples.
  • Bisection doesn’t apply. We know which entry we want, and the digits go up and down.
  • What relationship can we use?
  • While generating 2401, only needed the product of 7 with the prior last digit.
• But now we have 1 as the last digit. A few more lines, and we see the pattern. The 1 begins a pattern.
• What is the pattern?
  • The table breaks into groups of four lines.
  • The all repeat 7, 9, 3, 1.
• Restate what we have more abstractly. For each i, we know that
  • the last digit of {7}^{4i} = 1,
  • the last digit of {7}^{4i+1} = 7,
  • the last digit of {7}^{4i+2} = 9, and
  • the last digit of {7}^{4i+3} = 3.
• Where does {7}^{100} fall?
  • {7}^{100} = {7}^{4⋅25}, so its last digit is 1.

Looking back:

• On the technical side, we only needed to track the last digit.
  • This will return when we break apart numbers in Chapters 4-6.
• There were no simple phases corresponding to the principles, but all applied.
• New facts and new patterns let us understand more of the problem.
• Each led to new plans and new phrasings.

8.4 Other sources for tactics and examples

• The Math 202 notes. The notes currently are at

  http://jriedy.users.sonic.net/math202-f08/ .

• Pólya’s books. In particular, the majority of How to Solve It consists of a compendium of ideas and techniques.

8.5 Next time: Reading graphs and charts

Recommended reading: Anything by Edward Tufte. The “Ask E.T.” section of his personal site (http://www.edwardtufte.com) has examples of excellent and poor graphics.

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

• Describe not only the result but also your approach in the following.
• From problem set 1.3:
  • Problem 28 for following dependencies
  • Problem 40 both for bisection and guessing a reasonable range
  • Problem 52, think of bisection
  • Problem 56, think about lines and the shapes you can form
  • Problem 61, look for a pattern
• How many ways can you make change for 60 cents using pennies, nickles, dimes, and quarters. Either take great care in forming a long list, or look for a relationship using smaller problems.

  A hint for a long list: Do you need to move pennies one at a time?

  A hint for a relationship: Consider the old example of 20 cents using pennies, nickles and dimes. How many ways are there to change 20 cents using only pennies and nickles? How many ways to change 20 cents minus one dime using all the coins? The relationship makes constructing a table much easier.

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.