Notes for 22 August

Principles are not a recipe, but they are a way to cook.

- Understand the problem
- Rephrase it, play with examples, sketch it, determine your goals

- Divise a plan
- Covered two search-based plans, guessing and tabling

- Carry out the plan
- Requires attention to detail

- Examine the solution
- Check your result, generalize, try different problems

- Good for finding a solution satisfying a relationship or emulating an example.
- While rephrasing the problem, look for relationships to guide the guesses.
- If stuck, try related or simpler examples.
- Looking back at the problem can help you target guesses better on similar future problems.
- Examples:
- Number games
- Getting started on just about any problem. Guessing helps find examples while understanding the problem.

- Good for listing problems and some counting problems.
- Find the number of ways to make change given certain coins.

- Can be good for satisfying relationships when guesses run dry.
- Search through the space of answers methodically.
- Ensures you won’t miss anything.
- Takes attention to detail in the plan of making the table.
- The simpler the plan, the fewer mistakes in execution.
- Examples:
- Logic tables
- Counting ways to make a particular sum
- (Amusingly, this is a computationally difficult problem. There is no known method that is fundamentally better than listing the possibilities.)

Problem 11 in set 1.2:

When Anita made a purchase she gave the clerk a dollar and received 21 cents in change. Complete this table to show what Anita’s change could have been.

# dimes | # nickles | # pennies |

2 | 0 | 1 |

- Why does the list start with one penny?
- Only way to make any change ending in 1.

- Can you use that to simplify the problem?
- Use 20 cents rather than 21, then add 1 to the last column.

Removing extraneous details can help simplify a table-making method.

- What now? Decide on a systematic method for filling in the table.
- Methods for making methods:
- Find a rule each row of the table must satisfy.
- A conserved quantity is good, here the total amount.

- Find rules relating the columns.
- How many nickles per dime? Pennies per…?

- Decide on a transformation style from one row to the next.
- Try to push from one side to the other.
- Will need to back-track sometimes.

- Look for groups to separate the table, possibly nested.
- How many dimes can be used? Each number determines a group.
- Within each dime group, how many nickels?
- Defines a recursive function, may recall from Math 131.

- Sometimes careful construction leads to a direct solution.
- Not this time, at least not without some number theory. (See linear Diophantine equations and how to solve them.)

- Find a rule each row of the table must satisfy.
- Extra idea: Extend the table by one column to have a total. Check along the
way.
- The goal of self-checks is not only to find errors earlier but also to help locate the error.
- Designing good checks is an art in itself, but can help with the table design.
- An aphorism from computer programming:

Everyone knows that debugging is twice as hard as writing a program in the first place. So if you’re as clever as you can be when you write it, how will you ever debug it? – Brian Kernighan (C, Unix, awk, …)

Ideal end results:

- One dime becomes two nickels, one nickel becomes five pennies
- Each dime quantity defines a group. Each nickel quantity defines a (fairly trivial) group.
- Within a group, push change across the row.

No number means a zero.

# dimes | # nickles | # pennies | total cents = 20 |

2 | 2*10 = 20 | ||

1 | 2 | 10+2*5 = 20 | |

1 | 1 | 5 | 10+5+5*1 = 20 |

1 | 10 | 10+10*1 = 20 | |

4 | 4*5 = 20 | ||

3 | 5 | 3*5+5*1 = 20 | |

2 | 10 | 2*5+10*1 = 20 | |

1 | 15 | 1*5+15*1 = 20 | |

20 | 20*1 = 1 | ||

Remember: The “real” answer has one extra penny, so add 1 to the penny column.

- One example is bisection.
- Works when there is a natural order in the result values.
- Example last time was finding a term in an increasing sequence.

- Pick a place to check the result value.
- Consider an increasing sequence like the example in the last session:
- If it’s too small, pick a second larger place. Let’s call it A.
- If still too small, repeat. Replace the old staring point A.

- If too large, pick a second smaller place.
- If still too large… Same idea.

- Once you find a bracketing point,
B, consider a point
half-way between A
and B.
- If the half-way point is too small, replace A and repeat.
- If it’s too large, replace B and repeat.

- If it’s too small, pick a second larger place. Let’s call it A.

Talk about a coincidence, although clearly the example has no relationship to actual car models. Example 1.5 from the text, but done a little differently.

Example 1.5: Draw a diagram

In a stock car race the firist five finishers in some order were a Ford, a Pontiac, a Chevy, a Buick, and a Dodge.

- The Ford finished seven seconds before the Chevy.
- The Pontiac finished six seconds after the Buick.
- The Dodge finished eight seconds after the Buick.
- The Chevy finished two seconds before the Pontiac.

In what order did the cars finish the race?

What information do we have?

- Make of five different finishers.
- Only one dimension is involved: time.
- Four statements relating their finishing times.
- Four relative time relationships.
- The Buick is mentioned most often, but every make is mentioned at least once and no relationships are obviously repeated.

Is this enough information?

- Five cars, four relationships, one dimension.
- Consider: (car)-(car)-(car)-(car)-(car). Four relationships.
- Could be exactly enough information.

Try rephrasing the problem.

- Place five points (F, P, C, B, and D) on a line such that
- F is seven units to the right of C,
- P is six units to the left of B,
- D is eight units to the left of B, and
- C is two units to the right of P.

- All distances are relative. We need a starting point.
- Pick one. B volunteers by appearing twice.
- Apply all relationships with B on the right.
- Then we will have two new cars placed. Use all relationships with those on the right.
- Repeat until finished or stuck.
- If stuck with this method, is there any solution?
- No. All times are relative. There would be at least two groups of cars with no relationships between the groups.

Now we get to draw. Sorry, but I’m just using tables.

Using relationship 2 and 3,

P(6) | -(5) | -(4) | -(3) | -(2) | -(1) | B | ||

D(8) | -(7) | -(6) | -(5) | -(4) | -(3) | -(2) | -(1) | B |

Simplifying the presentation:

D | - | P | - | - | - | - | - | B |

- Now we have D and P available for resolving the rules.
- Only one appears on the right of a rule, P in rule 4.

Place C
by rule 4:

D | - | P | -(1) | C(2) | - | - | - | B |

Now C is available,
so place F
by rule 1:

D | - | P | - | C | -(1) | -(2) | -(3) | B(4) | -(5) | -(6) | F(7) |

Or without the counts:

D | - | P | - | C | - | - | - | B | - | - | F |

So the final finishing order is F, then B, then C, then P, and then D.

- How can we check this result?
- Did we place all the cars? Yes.
- Did we use all the statements? Yes, so there can be no inconsistency.

- What helped with executing the plan?
- The way the statements were written let us build a concrete plan.
- We could follow the chain of cars.

- Variations on the problem:
- Would three statements be enough?
- No. One car would be left out of the relationships. Counting to determine if a problem is soluble will return.

- Would more statements guarantee a solution?
- No. Not if the statements are inconsistent.
- No. Some cars may not be related to others.

- If the statements were consistent and not repeated, how many would we
need to guarantee a solution exists?
- The total number of consistent relationships possible is a counting problem in itself. The result is every way to choose two cars from five, “5 choose 2” = 5!/(2!(5-2)!) = 10, where 5! is “5 factorial” or 5*4*3*2*1.
- The minimum number of relationships is 4 (from above), the maximum is 10.
- There’s a kind of order here from a threshold. If a solution is guaranteed by K consistent relationships, it also is guaranteed by K + 1.
- You could search for counter-examples from 5 to 9, or you could use the order here to bisect.

- Would three statements be enough?

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

Write out (briefly) your approach to each problem.

- Problem set 1.2:
- Problem 13, for making a list.
- Problem 18, for drawing a diagram.
- Problem 20, somewhat combining all of the above. Hints: Try techniques on a smaller problem. Find a numerical property about the number of edges exposed. And consider two limiting cases to govern how many possibilities exist.

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.