Chapter 7
Notes for 25 August

Notes also available as PDF.

7.1 Review

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?

Is this enough information?

Try rephrasing the problem.

7.2.2 Devise a plan

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

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

7.3 Look for a pattern

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

7.4.1 Sums over Pascal’s triangle

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

#
01
11 1
21 2 1
31 3 3 1
41 = \mathbf{0} + 14 = 1 + 36 = 3 + 34 = 3 + 11 = 1 + \mathbf{0}

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

Understanding the problem:

Plan:

The result:

# sum
01 1
111 2
2121 4
31331 8
414641 16

A guess:

Consider a specific case, forming the fourth row:

# sum
31 3 3 1 8
41 = \mathbf{0} + 14 = 1 + 36 = 3 + 34 = 3 + 11 = 1 + \mathbf{0} 16

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.

And the final answers:

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.

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.