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