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.
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.
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.
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.
And the final answers:
{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.
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.