## Chapter 10Solutions for second week’s assignments

Also available as PDF.

### 10.1 Exercises for Section 1.3

#### 10.1.1 Problem 6: Understanding

The problem begins by stating that “[t]oday is your first day driving a city bus.” At the end, the question posed is “[h]ow old is the bus driver?” The other information is irrelevant, and the result is your age. (You need not provide your age. The fact that “you” are the bus driver is all that matters.)

#### 10.1.2 Problem 12: Guessing and checking

When playing around with the problem, you may realize that if each of the three parts has the same sum, then each must equal 1∕3 of the total sum. The sum {\mathop{\mathop{∑ }}\nolimits }_{i=1}^{12}i = 12(12 + 1)∕2 = 6 ⋅ 13, so we can guess that three equal parts each will total 6 ⋅ 13∕3 = 2 ⋅ 13 = 26.

Now the problem becomes positioning lines such that the totals are 26. The smaller numbers (e.g. 1, 2) need combined with some of the larger numbers (e.g. 11, 12) to total 26. So we can guess that one of the lines will be nearly horizontal across the top. First try a line that separates the top four numbers, so 11 + 12 + 1 + 2 = 26.

Now the other line cannot intersect the first inside the clock or else the clock will be divided into four parts. My first guess was to anchor one end of the new line where the previous line ran under 2. That would cut a pie-like slice and only include numbers on the opposite side. The closest adding the facing side can come to 26 is 10 + 9 + 8 = 27, so clearly that was not correct. If we chop off the 8, that leaves 10 + 9 = 19 and needs 7 more to match 26. So run the right-hand side down, no longer cutting out a pie-like slice but including some numbers from both sides. Then we can include 3 + 4 = 7.

So far, my guesses separated 11 + 12 + 1 + 2 = 26 and 10 + 9 + 3 + 4 = 26. With the remaining numbers, 5 + 6 + 7 + 8 = 26, so the problem is solved.

In hindsight, however, I see my previous guess was being far too fancy. Note that each slightly diagonal slice adds to 13. That is, 12 + 1 = 13, 11 + 2 = 13, and so on down to 7 + 6 = 13. So we need only combine consecutive slices to create the necessary three regions.

#### 10.1.3 Problem 31: Listing

here most of the problem lies in figuring out an appropriate representation. Then starting to make lists show the way to an answer.

If we were to list all combinations of “black” and “white”, that would be 1.4 × 1{0}^{11} combinations. So this list likely is not what I meant by mentioning listing.

A shorter method is to list all combinations of two socks, or BB, BW, WW. The order does not matter in the end. In the BW case we do not have two socks of the same color, so the result cannot be two.

Now the combinations of three socks are BBB, BBW, BWW, WWW. In each of these we have two socks of the same color. So if we pull out three socks, we are guaranteed to have two matching socks. Since two did not work, the smallest number of socks you can pull without looking to have two of the same sock is three.

Another way to view the problem is by ticking off marks in the following for each sock drawn:

 Black White

Once you have a tick mark in both, the next mark must land in an occupied slot. So the longest sequence of marks without a duplicate is checking off one and then the other, or two marks. After two, you must mark an occupied slot.

This is a consequence of the pigeonhole principle. When there are more pigeons than holes, there must be at least two pigeons in one hole. You can use the same principle to prove that there must be two people in the Tri-cities area with the same number of hairs on their heads.

#### 10.1.4 Problem 35: Listing

The simplest solution is to start listing numbers. The text’s example of 28 shows you will not need to list more than 28 numbers. And because 1 has no factor other than itself, we can skip the first obvious entry.

 2 ≠1 3 ≠1 4 ≠1 + 2 = 3 5 ≠1 \mathbf{6} \mathbf{= 1 + 2 + 3}

We could construct the list without the prime numbers 2, 3, 5, etc. A prime number has only itself and 1 as factors, so we know that they cannot be perfect numbers.

Aside: What would the entry for 1 be? One has no factors other than itself. You would sum over , the empty set. There is no single definition. In the context of this problem, we could define that sum to be zero. That would be consistent with the rest of the problem and perfectly ok. But it’s not a completely standard definition.

Dealing with vacuous cases like the sum of entries of is tricky, but there is a general rule of thumb. Often the vacuous definition needs to be the identity of the operation. Here, zero is the identity element for addititon because x + 0 = 0 for all x. So it’s a safe guess that the sum of the entries in the empty set could be defined to zero.

Another side: No one knows if there are infinitely many perfect numbers, or if there are any odd perfect numbers.

#### 10.1.5 Problem 28: Following dependencies

Let {M}_{1} be the initial amount, {M}_{2} be the amount after buying the book, {M}_{3} be the about after the train ticket, {M}_{4} be the amount after lunch, then {M}_{5} be the final about after the bazaar. Translating the problem into a sequence of equations,

\eqalignno{ {M}_{2} & = {M}_{1} - 10, & & \cr {M}_{3} & = {M}_{2}∕2, & & \cr {M}_{4} & = {M}_{3} - 4, & & \cr {M}_{5} & = {M}_{4}∕2,\text{ and} & & \cr {M}_{5} & = 8. & & }

The only fully resolved data we have is {M}_{5} = 8, so we start there. First {M}_{5} = 8 = {M}_{4}∕2, so {M}_{4} = 16. Then 16 = {M}_{3} - 4 and {M}_{3} = 20. Next, 20 = {M}_{2}∕2 so {M}_{2} = 40. Finally, 40 = {M}_{1} - 10 and \mathbf{{M}_{1} = 50}.

#### 10.1.6 Problem 57: Following dependencies

This is an exercise in translating the words into mathematical relations and then working through the dependencies.

Translate each statement into an equation

\eqalignno{ {x}_{2} & = 3{x}_{1}, & & \cr {x}_{3} & = {x}_{2} + {3\over 4}{x}_{2}, & & \cr {x}_{4} & = {x}_{3}∕7, & & \cr {x}_{5} & = {x}_{4} -{1\over 3}{x}_{4}, & & \cr {x}_{6} & = {x}_{5}^{2}, & & \cr {x}_{7} & = {x}_{6} - 52, & & \cr {x}_{8} & = \sqrt{{x}_{7}}, & & \cr {x}_{9} & = {x}_{8} + 8, & & \cr {x}_{10} & = {x}_{9}∕10,\text{ and} & & \cr {x}_{10} & = 2. & & }

Following these backwards shows that

\eqalignno{ {x}_{9} & = 20, & & \cr {x}_{8} & = 12, & & \cr {x}_{7} & = 144, & & \cr {x}_{6} & = 196, & & \cr {x}_{5} & = 14, & & \cr {x}_{4} & = 21, & & \cr {x}_{3} & = 21 ⋅ 7\text{(note the next step divides by 7, so don’t expand)}, & & \cr {x}_{2} & = 84,\text{and} & & \cr \mathbf{{x}_{1}} &\mathbf{= 28}. & & }

#### 10.1.7 Problem 40: Bisection and guessing a range

See the write-up below.

#### 10.1.8 Problem 52: Think about bisection

With eight coins, split them into two groups of four. One will be lighter. Split the lighter group of four into two groups of two. Again, one is lighter. Now the lighter group of two splits into two single coins. The lighter of the two coins is fake.

For the trick of two weighings, we first consider weighing two groups of three coins. If the groups are equal, we are left with the two remaining coins. Those two can be separated in one more weighing. If the groups of three are unequal, split the lighter one into three groups of one. Compare two of those single coins. If they are of the same weight, the left-over coin must be fake. Otherwise the lighter coin is the fake. Any path here requires only two weighings. This is an example trisection, separating the problem into three groups at each level.

#### 10.1.9 Problem 56

A rotated square with each vertex located at the midpoint of the given square’s sides will separate the kitties.

#### 10.1.10 Problem 61: Look for a pattern

Calculating 1∕7 to a few places shows 1∕7 = 0.14285714285714\mathrel{⋯}\kern 1.66702pt The expansion appears to repeat in groups of six. Because 100 = 16 ⋅ 6 + 4, we expect that the 100th digit after the decimal point is 8.

### 10.2 Making change

How many ways can you make change for 60 cents using pennies, nickles, dimes, and quarters. Either take great care in forming a long list, or look for a relationship using smaller problems.

A hint for a long list: Do you need to move pennies one at a time?

A hint for a relationship: Consider the old example of 20 cents using pennies, nickles and dimes. How many ways are there to change 20 cents using only pennies and nickles? How many ways to change 20 cents minus one dime using all the coins? The relationship makes constructing a table much easier.

This is a classical problem used in discrete mathematics and introductory computer science classes, although often starting with a dollar to make tabling less practical.

There are 73 ways.

There are at most two quarters, at most six dimes, at most 12 nickles, and at most 60 pennies per line of a table with the following heading:

 Pennies Nickles Dimes Quarters total

To generate the table, start with two quarters and then shift amounts over as in other problems. You use the conserved quantity, the total amount, to guide your next choice.

Another method for solving this problem is to set up recurrence relationships and build a slightly different and much, much shorter table.

Consider making change for an amount N. And consider four different ways for making such change:

\eqalignno{ {A}_{N} &\text{ with only pennies,} & & \cr {B}_{N} &\text{ with nickles and pennies,} & & \cr {C}_{N} &\text{ with dimes, nickles, and pennies, and} & & \cr {D}_{N} &\text{ with quarters, dimes, nickes, and pennies.} & & }

Say we start at N and the full collection of possible coins. Then either the change contains a quarter or it does not. If it does contain with a quarter, then we change the remaining N - 25 in the same way, possibly with more quarters. If not, then we change N no quarters. So

\eqalignno{ {D}_{N} & = {C}_{N} + {D}_{N-25}. & & \cr & & }

Similarly,

\eqalignno{ {C}_{N} & = {B}_{N} + {C}_{N-10},\text{ and} & & \cr {B}_{N} & = {A}_{N} + {B}_{N-5}. & & }

We can begin constructing a table of values by N starting from the extreme case N = 0. There is only one way of making no change at all, so {A}_{0} = {B}_{0} = {C}_{0} = {D}_{0} = 1. There also is only one way of making change with pennies, so {A}_{N} = 1 for all N. And the relations above show we need only rows where N is a multiple of five and provide formulas for every entry.

The table is as follows:

 N {A}_{N} {B}_{N} {C}_{N} {D}_{N} 0 1 1 1 1 5 1 2 2 2 10 1 3 4 4 15 1 4 6 6 20 1 5 9 9 25 1 6 12 13 30 1 7 16 18 35 1 8 20 24 40 1 9 25 31 45 1 10 30 39 50 1 11 36 49 55 1 12 42 60 60 1 13 49 73 = 49 + 24

### 10.3 Writing out problems

#### 10.3.1 Section 1.2, problem 9

##### Understanding the problem

We need to extend the sequence of interior regions to find the number of regions when there are seven and eight points. We have the first six entries of the sequence.

##### Devise a plan

Given the first six entries, we can form a successive difference table to extrapolate the sequence.

##### Carry out the plan

The table follows:

 points regions {Δ}^{(1)} {Δ}^{(2)} {Δ}^{(3)} {Δ}^{(4)} 1 1 2 2 1 3 4 2 1 4 8 4 2 1 5 16 8 4 2 1 6 31 15 7 3 1 7 57 26 11 4 1 8 99 42 16 5 1

##### Examine the solution

Computing R(7) = {1\over 24}({7}^{4} - 6 ⋅ {7}^{3} + 23 ⋅ {7}^{2} - 18 ⋅ 7 + 24) = 57 and R(8) = {1\over 24}({8}^{4} - 6 ⋅ {8}^{3} + 23 ⋅ {8}^{2} - 18 ⋅ 8 + 24) = 99 confirms the table’s results. Also note that the table needed four columns to the right of the sequence to find the constant increment. This matches the degree, four, of the polynomial.

#### 10.3.2 Section 1.2, problem 49

##### Understanding the problem

We need to inductively determine the formula for N(n), the nth nonagonal number. We have the following formulas:

\eqalignno{ H(n) & = {n(4n - 2)\over 2} , & & \cr Hp(n) & = {n(5n - 3)\over 2} ,\text{ and} & & \cr O(n) & = {n(6n - 4)\over 2} , & & }

for the hexagonal, heptagonal, and octagonal numbers.

##### Devise a plan

The plan is to look for a pattern in the formulas for H(n), Hp(n), and O(n). That lets us predict N(n).

##### Carry out the plan

All the formulas provided are of the form

 {n(an + b)\over 2} ,

so we examine patterns in a and b.

The values of a are 4, 5, and 6. This suggests the next will be 7. And the values of b are -2, -3, and -4, suggesting to continue the pattern with -5. So we expect that the formula is

 N(n) = {n(7n - 5)\over 2} .

##### Examine the solution

To check, we verify that N(6) = 111. Indeed, N(6) = 6 ⋅ (42 - 5)∕2 = 3 ⋅ 37 = 111, supporting the guess. While not a proof, this is a enough evidence to elevate the guess for N(n) to a conjecture.

#### 10.3.3 Section 1.3, problem 40

##### Understanding the problem

We are looking for a year. That year is 76 more than the birth year of one of the authors and is also a perfect square. The final answer is that year, x, minus 76.

Exploring the problem, we realize that the birth year in question must be within 76 years of publication of the text. The text was published in 2003. To stick to round numbers for estimation, we look for years between 1900 and 2100.

##### Devise a plan

Look for an integer between 1900 and 2100 that is a perfect square. Knowing that \sqrt{ 1900} > 43 and \sqrt{ 2100} < 46, we search the region 44 ≤ i ≤ 45. Bisection here is overkill; there only are two choices after limiting the choices as above.

##### Carry out the plan

 i {i}^{2} {i}^{2} - 76 45 2025 1949 44 1936 1860

So the result is that Hornsby was born in 1949, because 1860 is more than 76 years before 2003.

##### Examine the solution

Bisection here was unnecessary. Had we rounded outwards, though, and assumed only 43 ≤ i ≤ 46, then bisection would have delivered the result in the first step.

### 10.4 Computing with numbers

#### 10.4.1 Extra digits from 1∕7

Compute 1∕7. Write down the number exactly as displayed. Then subtract what you have written from the calculator’s or program’s result. For a calculator, divide one by seven and then subtract off what you see without storing the result elsewhere. For a spreadsheet or other interface, divide one by seven. Then compute 1∕7 - .14\mathrel{⋯}\kern 1.66702pt for whatever was displayed. What is the result? What did you expect? What result did others find?

With a computer using typical arithmetic, we may see 1∕7 computed to be 0.142857142857143. Subtracting that off gives - 1.38777878078145 × 1{0}^{-16}, not zero! Some computers (notably 32-bit Intel-like processors, although not under recent versions of Windows) may show a different result; they store intermediate results to extra precision.

With a calculator, you typically will see one or two non-zero digits. An 8-digit calculator might display 0.1428571. Subtracting that off may show any of 0, 4, 42, or 43 depending on how the calculator rounded and how many extra digits were kept. Most calculators keep a few extra digits past what is displayed.

#### 10.4.2 Binary or decimal?

Enter .1 into whatever device you use. Add .1 to it. Repeat eight more times, for a total of 10 ⋅ .1. Subtract 1. What is the result? What did you expect? What result did others find?

Using a calculator, you probably see zero, exactly what you expect from 10 ⋅ .1 - 1. Most hand-held calculators work with decimal arithmetic directly.

With most computers, you see - 1.11022302462516 × 1{0}^{-16}. This is because .1 cannot be represented exactly in binary. The fraction 1∕10 when converted to binary and computed does not terminate, just as 1∕3 or 1∕7 do not terminate in decimal.

Some systems run decimal arithmetic in software and also will produce zero. However, not all systems that show zero actually have zero stored as the result. Some spreadsheet software is guilty of “cosmetic rounding”. They will display the result as zero but actually carry the binary version; what you see most certainly may not be what you get.