Extra idea: Extend the table by one column to have a total. Check along the
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
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
Within a group, push change across the row.
No number means a zero.
total cents = 20
2*10 = 20
10+2*5 = 20
10+5+5*1 = 20
10+10*1 = 20
4*5 = 20
3*5+5*1 = 20
2*5+10*1 = 20
1*5+15*1 = 20
20*1 = 1
Remember: The “real” answer has one extra penny, so add 1 to the penny
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
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
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
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.