## Chapter 7Notes for 25 August

Notes also available as PDF.

### 7.2 Draw a diagram, follow dependencies

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.

1. The Ford finished seven seconds before the Chevy.
2. The Pontiac finished six seconds after the Buick.
3. The Dodge finished eight seconds after the Buick.
4. The Chevy finished two seconds before the Pontiac.

In what order did the cars finish the race?

#### 7.2.1 Understanding the problem

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

1. F is seven units to the right of C,
2. P is six units to the left of B,
3. D is eight units to the left of B, and
4. C is two units to the right of P.

#### 7.2.2 Devise a plan

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

#### 7.2.3 Carry out the plan

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.

#### 7.2.4 Looking back

• 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.
• Following dependencies often is called “working backwards.”
• 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.

### 7.3 Look for a pattern

• Incredibly important at many levels.
• Mathematics generally is about characterizing patterns.
• Immediately useful for
• extending from provided data, and
• continuing relationships found when considering problems.

#### 7.3.1 Example: What is the last digit of {7}^{100}

The initial problem is straight-forward; there appears to be little more to understand. One useful relationship is that there are at most 9 possible finial digits. (Zero is not possible.)

With so few possible digits, a good initial plan is forming a table:

 Number Last digit {7}^{1} 7 {7}^{2} 9 {7}^{3} 3 {7}^{4} 1 {7}^{5} 7 {7}^{6} 9 \mathop{\mathop{⋮}} \mathop{\mathop{⋮}}

We certainly don’t want to extend this to {7}^{100}. However, note that the last digit of {7}^{4} is 1. Then 7 ⋅ 1 = 7 begins the pattern anew.

To check, we could guess that the last digit of {7}^{8} is 1. Continuing the table confirms the guess.

So {7}^{i} has the last digit 1 for all i that are multiples of four. And thus the last digit of {7}^{100} is 1.

### 7.4 Patterns and representative special cases

• A special case is quite literally a case set aside as special.
• A representative special case is a special case that accurately represents the general case.
• Consider teaching a property over all cases by illustrating with a specific case.
• The specific case must not depend on which case is used\mathop{\mathop{…}}
• Will use text’s example: sums of rows of Pascal’s triangle

#### 7.4.1 Sums over Pascal’s triangle

• A wonderful source of examples and relationships
• Related to polynomials, probability distributions, and even fractals.

Written in rather boring table form, each entry is the sum of the entry directly above and above to the left:

 # 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 = \mathbf{0} + 1 4 = 1 + 3 6 = 3 + 3 4 = 3 + 1 1 = 1 + \mathbf{0}

##### Problem: What is the sum of the 20th row? The 200th?

Understanding the problem:

• How is the triangle formed?
• Each entry is the sum of the two above.
• Can we continue this pattern? Yes.
• Do we want to write 200 rows? No.
• What else can we do?

Plan:

• Form the sums.
• Look for a pattern.
• Reason about all cases given a representative case.

The result:

 # sum 0 1 1 1 1 1 2 2 1 2 1 4 3 1 3 3 1 8 4 1 4 6 4 1 16

A guess:

• Each row’s sum is twice the previous row’s sum.
• Starting from the “zeroth” row as 1, the nth row is {2}^{n}.
• The next few rows check.

Consider a specific case, forming the fourth row:

 # sum 3 1 3 3 1 8 4 1 = \mathbf{0} + 1 4 = 1 + 3 6 = 3 + 3 4 = 3 + 1 1 = 1 + \mathbf{0} 16
• What do we know about the sum of each row?
• It’s the sum of each entry.
• In turn, each entry is the sum of two entries from the previous row.
• So the sum must be the sum of sums of pairs from the previous row, or twice the previous row’s sum.

By looking at a special case but applying only general reasoning, we have proven that each row’s sum is twice the previous row’s sum.

• We used no properties specific to the third or fourth rows.
• We could have chosen (“without loss of generality”) any row and applied the same reasoning.
• Thus the reason applies to all rows.

• {2}^{20} = 1\kern 1.66702pt 048\kern 1.66702pt 576. A megabyte (MiB in correct units, not MB) is {2}^{20} bytes.
• {2}^{200} has 61 digits, none of which are particularly elucidating. For this style of problem, leaving {2}^{200} unevaluated is much better. But, for completeness, the answer is in the notes.

1 606 938 044 258 990 275 541 962 092 341 162 602 522 202 993 782 792 835 301 376

### 7.5 Homework

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.

• Patterns: What is the 87th digit past the decimal point in the expansion of 1∕7?
• Patterns and related patterns: Using the result of {7}^{100} above, what is the last digit of {3}^{100}?
• From problem set 1.3:
• Arithmetic progressions: problem 6 (see the text, esp. around examples 1.8 and 1.9)
• Problem 9, and feel free to criticize the use of “likely” or “probably” here as well.
• Problem 11.
• Problem 20.

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.