## Chapter 10Solutions for second week’s assignments

Also available as PDF.

Note: These are my approaches to these problems. There are many ways to tackle each.

### 10.1 Patterns: The 87th digit past the decimal in 1/7?

What are the digits of 1∕7? A computer or calculator computes something like 0.142857142857143. We start to see a pattern: 142857 is repeated. The chunk has length six, so digit 6i + 1 will be 1, 6i + 2 will be 4, and so on. Digit 87 = 6 ⋅ 14 + 3, so we expect the 87th digit will be 2.

We could prove this in a few ways if desired. One would be to carry out long division for seven steps. On the seventh, we would see the same problem as the initial problem, namely 1.0∕7. The same problem with the same data must have the same solution, and thus the pattern must repeat.

### 10.2 Patterns: Units digit of \mathbf{{3}^{100}}

The quick solution is to note that 3 appears in the “orbit” of {7}^{100} directly before 1, because 7 × 3 = 21. So in a sense which we will formalize later, 3 is the inverse of 7 with respect to the units digit. We need merely to count backwards in the table generated by powers of 7.

The more direct approach is to note that powers of 3 give a final digit sequence of 3, 9, 7, and 1 repeating after the 1. The sequence works in chunks of four, and we see that the entry for 100 = 4 ⋅ 25 + 4 is 1.

### 10.3 Problem set 1.3

#### 10.3.1 Arithmetic progressions: Problem 6

Part a. The number of increments by seven is (86 - 2)∕7 = 12. To check, form 2 + 12 ⋅ 7 and verify it is 86.

Part b. One method is to re-apply Gauss’s technique (using inductive reasoning). There are 13 entries in the sequence, 2 and then 12 increments by 7. Pairing these up, we have 6 added terms of the form 2 + 86 = 9 + 79 = 72 + 16 = 65 + 23 = 58 + 30 = 51 + 37 = 88 and one remaining term of 44. So the result is 6 ⋅ 88 + 44 = 572.

Note that the paired terms added to 88, while the lone term was 88∕2 = 44. Playing with the form above 6 ⋅ 88 + (1∕2)88 = 88 ⋅ (12 + 1)∕2, recalling the n(n + 1)∕2 form for the sum from 1 to n.

Another method is to work with the summation form directly to find

\eqalignno{ {\mathop{∑ }}_{i=0}^{12}(2 + 7i) & = 13 ⋅ 2 + 7{\mathop{∑ }}_{i=0}^{12}i & & \cr & = 26 + 7 ⋅{12(12 + 1)\over 2} & & \cr & = 572. & & }

Part c. There is a slight trick to this. Often it is more obvious to start with the zeroth term as I have above. Then the form of the ith term is 2 + 7i, showing the initial term directly. However, many people prefer counting from one. To convert the form, substitute n - 1 for i and see that 2 + 7(n - 1) = -5 + 7n is the form of the nth form.

Part d. One method of computing the sum again is to emulate Gauss’s trick with the observation from Part a. We expect the sum to be the number of terms, n, times the first plus the last, 2 + (-5 + 7n) = -3 + 7n, divided by two. So the sum is n(7n - 3)∕2.

Another method is to work with summation form,

\eqalignno{ {\mathop{∑ }}_{i=0}^{n}(2 + 7i) & = (n + 1) ⋅ 2 + 7{\mathop{∑ }}_{i=0}^{n}i & & \cr & = 2(n + 1) + 7 ⋅{n(n + 1)\over 2} . & & }

With sufficient algebra, this does simplify to the other form.

#### 10.3.2 Problem 9

Part a. Personally, I’d point out that in their limited imagination, the writers likely intend 16 to be the next number.

Part b.

 n {2}^{n} {n}^{2} - n + 2 {n}^{3} - 5{n}^{2} + 10n - 4 1 2 2 2 2 4 4 4 3 8 8 8 4 16 14 20

Part c. There are many, many functions that could generate 2, 4, and 8. One needs more information to decide on which function.

And the wording of the first problem uses “likely.” To me, “likely” infers some probability, but there is none.

Better wording would ask for the reason why the student believes the sequence extends to their guesses.

#### 10.3.3 Problem 11

Following the hint, consider rearranging B B R R to B R B R. That requires one swap in the middle. The number of swaps cannot be fewer, so this is the minimum number.

Now rearrange B B B R R R to B R B R B R. Two swaps move the left-most R into position, B R B B R R. The first two letters are correct, and the rest match the previous problem. No fewer swaps could have moved an R into the second-left-most position; there must be at least one swap for each position moved. So we know the fewest swaps beyond the first case is two, for a minimum total of three.

At this point, it’s reasonable to guess that the number of swaps is either {2}^{\text{#B}-1} - 1 or {\mathop{\mathop{∑ }}\nolimits }_{i=1}^{\text{#B}-1}i. Either fits the data so far. However, at each stage we moved one R into place and then reduced to a known subproblem. This adds moves, so the summation seems the most likely.

To verify that {\mathop{\mathop{∑ }}\nolimits }_{i=1}^{\text{#B}-1}i = 4 * (4 + 1)∕2 = 10 swaps suffices, use the following:

 Start with: B B B B B R R R R R 4 swaps later: B R B B B B R R R R 3 swaps later: B R B R B B B R R R 2 swaps later: B R B R B R B B R R 1 swap later: B R B R B R B R B R Total number of swaps: 10

To support that this is the minimum, we rely on inductive reasoning. At each stage, we add the minimum number of necessary swaps to the subproblem, which in turn is solved minimally. To formalize this, we could apply mathematical induction.

#### 10.3.4 Problem 20

Part a. The sums are 12, 24, 48, and 64. One pattern is that the sum is four times the repeated quantity on the anti-diagonal. Another is to note that the repeated quantity is one larger than the upper-left corner and one smaller than the lower-right corner.

So adding along “opposite” anti-diagonals is like adding the same number entries from the main anti-diagonal. So given a block of the form

 k - 1 k k k + 1

we can add the two far anti-diagonals to get (k - 1) + (k + 1) = 2k. Along with the main diagonal, the total sum is (k - 1) + (k + 1) + k + k = 4k.

Part b. The sums are 54, 108, and 144.

Part c. The blocks follow a similar pattern as the previous part:

 k - 2 k - 1 k k - 1 k k + 1 k k + 1 k + 2

Again, add along “opposite” anti-diagonals to match + 2 and - 2, + 1 and - 1. So the sum must be 9k.

Part d. In each case, the sum is the number of squares times the element repeated along the main anti-diagonal. If the square is side-length n and the main anti-diagonal holds k, the sum is {n}^{2}k.

### 10.4 Problem set 1.4

#### 10.4.1 Reducing possibilities: Problem 7

Part a. Writing out the conditions that are easy to express gives

\eqalignno{ x & = 2k + 1\text{ for some $k$}, & & \cr x & > 1, & & \cr x & < 100, & & \cr x & > 20, & & \cr x & < 5 ⋅ 7 = 35,\text{ and} & & \cr x & = 5i\text{ for some $i$}. & & }

Combining the first and last, we know x is an odd multiple of five, or x = 5(2j + 1) for some j. The inequalities reduce to 20 < x < 35. The only possibility in this range is x = 25, and the digits here add to seven.

Part b. Again, translating the conditions and rewriting them to be positive rather than negated (so “not even” becomes “odd”) gives

\eqalignno{ x & = 2k + 1\text{ for some $k$}, & & \cr x & = 11i\text{ for some $i$}, & & \cr x & > 20, & & \cr x & = 3j\text{ for some $j$},\text{ and} & & \cr x & < 79. & & }

An odd multiple of three and nine can be expressed by composing the requirements, so x = 3 ⋅ 11 ⋅ (2p + 1) = 33(2p + 1) for some integer p. The bounds here are not redundant, so 20 < x < 79. The only multiples of 33 in this region are 33 and 66. Both have digits whose sums are even (divisible by two). So there are two possible results.

Part c. Translating this is not quite as useful, giving

\eqalignno{ x & = 2k\text{ for some $k$}, & & \cr x & = 3{j}_{1} + {i}_{1}\text{ for some $j$ and $i≠0$}, & & \cr x & = 4{j}_{1} + {i}_{1}\text{ for some $j$ and $i≠0$}, & & \cr x & ≤ 81,\text{ and} & & \cr x & ≥ 64. & & }

One observation helps: An even number not divisible by four has only one factor of 2. So the first and third requirements become

\eqalignno{ x & = 2 ⋅ (2p + 1)\text{ for some $p$}. & & }

So we are looking for even numbers in 64 ≤ x ≤ 80 with only one factor of two and that are not multiples of three. This reduces to looking for an odd z = x∕2 in 32 ≤ x ≤ 40 that is not a multiple of three.

The odd non-multiples of three in this range are 35 and 37. So z is either 35 or 37, and x is either 70 or 74.

#### 10.4.2 Logic puzzle: Problem 9

The problem assumes neither bigamy nor marriage to immediate relations is allowed, which is reasonable in the US. The true (T) and false (F) values are subscripted by a number if they are a direct implication of that rule. The forth rule was useless.

 Kitty Sarah Josie Anne David F{}_{3} F{}_{5} T F Will F{}_{3} T{}_{5} F{}_{1} F{}_{5} Floyd F{}_{3} F{}_{5} F{}_{2} T Gus T{}_{3} F{}_{3} F{}_{3} F{}_{3}

#### 10.4.3 Pigeonholes: Problem 12

Part a. To fill 365 days and guarantee one is repeated, you need 366 people. As an amazing aside, though, with only 23 people the chance of two sharing a birthday is over 50%!

Part b. The result here is twice 365 plus one, or 731.

#### 10.4.4 Pigeonholes: Problem 13

There are only ten units digits possible, zero through nine. If one digit is repeated, the difference between the two numbers with the same units digit must have units digit zero and be divisible by ten. With eleven numbers, we must have two with the same units digit.

#### 10.4.5 Pigeonholes: Problem 14

Part a. Note there are six ways single-digit numbers (or the units digit) can add to ten, 1 + 9, 2 + 8, 3 + 7, 4 + 6, and 5 + 5. If we use those as pigeonholes for the units digit, then we know one of those holes must be filled twice with seven numbers. Now within the holes we have another set of holes with one hole for each digit. If both holes are filled, then the sum is divisible by ten. If only one hole is filled, then the numbers share a units digit and their difference is divisible by ten.

Part b. With six numbers, we can fill each hole once. Any consecutive sequence of six numbers suffice, e.g. 1, 2, 3, 4, 5, 6.

### 10.5 Inductive or deductive?

• It has rained for the past week. It will rain tomorrow.

This is inductive because it is based solely on repeated observations.

• All men are mortal. Socrates is a man. Therefore, Socrates is mortal.

Deductive reasoning begins with premises and draws a conclusion as in this example.

• Satellite-based network access does not function through heavy rain. It is raining heavily. I cannot upload the notes right now.

Again, this example sets up data and rules from which it draws a conclusion. This is deductive reasoning.

• The next number after 3, 8, 13, 18, and 23 is 28.

This could fall either way, depending on how you decide on the next number. If you assume this is an arithmetic sequence and calculate the next term, this could be considered deductive reasoning. Recognizing an arithmetic sequence without further information is inductive in itself. If you just look and see a pattern, the process is completely inductive.

Often the initial phase of problem solving, understanding the problem, is an exercise in reasoning inductively.