Hence N " p2 ˆ 3qm " 2 ˆ p3mq, so N is a multiple of 2; and N " 3 ˆ p2mq, so N is a multiple of 3.

If an integer N is divisible by 2, then we can write N " 2k for some integer k. If N is also divisible by 3, then 3 divides exactly into 2k. But HCFp2, 3q " 1, so the 3 must go exactly into the second factor k, so k " 3m for some integer m, and N " 6m is divisible by 6.

Note: It is crucial that HCFp2, 3q " 1. (E.g. 12 is divisible by 6 and by 4; but 12 is not divisible by 6 ˆ 4.)

### 52.

53. (a) This exploits the fact that

$$(11^k - 1) = (11 - 1)(11^{k-1} + 11^{k-2} + \dots + 11 + 1),$$

and so is divisible by p11 ´ 1q – a fact which is obvious if we introduce a new digit X in base 11 to stand for "ten", and then notice that

$$11 - 1 = X\_{\text{base }11}, \ 11^2 - 1 = XX\_{\text{base }11}, \ 11^3 - 1 = XXX\_{\text{base }11}, \ \text{etc.}$$

For example:

$$\begin{aligned} \textbf{12.345}\_{\textbf{base}\ 11} &= \begin{array}{c} \textbf{1}\times 11^4 + \textbf{2}\times 11^3 + \textbf{3}\times 11^2 + \textbf{4}\times 11 + \textbf{5} \\ &= \begin{bmatrix} \textbf{1}\times (11^4 - 1) + \textbf{2}\times (11^3 - 1) + \textbf{3}\times (11^2 - 1) + \textbf{4}\times (11 - 1) \end{bmatrix} \\ &+ \begin{bmatrix} \textbf{1} + \textbf{2} + \textbf{3} + \textbf{4} + \textbf{5} \end{bmatrix} \\ &= \begin{bmatrix} \textbf{a}\text{ sum of terms, each of which is a multiple of ten} \end{bmatrix} \\ &+ \begin{bmatrix} \textbf{the sum of the digits of } \textbf{"12 345"} \end{bmatrix} \end{aligned}$$

If the LHS is divided by ten, the remainder from the first bracket on the RHS is zero, so the overall remainder is the same as the remainder from dividing the digit sum by ten.

54.

$$\begin{array}{ccccccccc}1 & + & 2 & + & 3 & + & \cdots & + & n\\n & + & n-1 & + & n-2 & + & \cdots & + & 1\end{array}$$

and observe that each of the n vertically aligned columns adds to n+1. Hence

$$T\_n = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.$$

If we do the same geometrically, then we can combine two "staircases"

of dots (one of which is inverted) into an n by n ` 1 array of dots (either with n columns and n ` 1 dots in each column, or with n ` 1 columns and n dots in each column).

Note: The n th triangular number is defined by the "formula"

$$T\_n = 1 + 2 + 3 + \dots + n.$$

But this "formula" has serious limitations: in particular, there is no way to calculate T100 without first calculating T1, then T2, then T3, . . . all the way up to T99. Hence it is just a "recurrence relation", which tells us how to find Tn once we know Tn´1 (just "add n").

The formula

$$T\_n = \frac{n(n+1)}{2}$$

derived in part (b) is much more useful, in that it allows us to work out the value of Tn as soon as we know the value of n. This is what we call a "closed formula". (The language may seem strange, but it refers to the fact that the calculation is direct, and that the formula involves a small, fixed number of operations – whereas using the recurrence requires more and more work as n gets larger.)

(c) Note: There are two reasons why these questions are worth asking. The first is that whenever we focus attention on certain special classes of objects, it is always good practice to consider whether the notions we have defined are completely separate, and to try to identify any overlaps. The second reason is less obvious, but can be surprisingly fruitful: sometimes two ideas may be interesting, yet have nothing to do with each other; but at other times, the two ideas may not only be interesting in their own right, but may "combine" in a way that gives rise to surprising subtleties. Here two of the combinations are routine and uninteresting; but two combinations generate more interesting mathematics than we have a right to expect.

(i) We know that one of the two factors n and n ` 1 in the numerator is odd, and the other is even. If the triangular number

$$T\_n = \frac{n(n+1)}{2}$$

is to be a power of 2, then any odd factor of Tn must be equal to 1, so n ă 3: n " 2 does not give a power of 2. Hence n " 1, and Tn " 1 is the only triangular number which is also a power of 2.

	- ∗ n is odd and one of n, n`1 2 is equal to 1 (so n " 1 and T1 " 1 is not prime), or
	- ∗ n is even and one of n 2 , n ` 1 is equal to 1, so n " 2, and T2 " 3 is the only triangular number which is also prime.

When n is even, we notice that a " n 2 and n ` 1 " 2a ` 1 are integers with no common factors. We want their product to be a square. Because HCFpa, 2a ` 1q " 1, this occurs precisely when both a (" b 2 ) and 2a ` 1 (" c 2 ) are both squares. So we see that solutions correspond to pairs of integers b, c which satisfy the Pell equation c 2 " 2b 2 ` 1. Notice that b " 2, c " 3 is one solution, and that they satisfy the equation c 2 ´ 2b 2 " 1. We have already met

$$a^2 + b^2 = (a + bi)(a - bi)$$

as the norm (or square of the length) of the complex number a ` bi (Problem 25). In a similar way, we can "factorise"

$$c^2 - 2b^2 = (c + b\sqrt{2})(c - b\sqrt{2}).$$

So once we have one solution of the equation c 2 ´2b 2 " 1, we can take powers to get more solutions:

$$[(c + b\sqrt{2})^2][(c - b\sqrt{2})^2] = 1^2 = 1, \quad \text{etc...}$$

Hence, for example,

.

$$(3+2\sqrt{2})^2 = 17+12\sqrt{2}$$

gives rise to the solution b " 12, c " 17 – corresponding to a " 144, n " 288.

Note: If you are not yet familiar with complex numbers, or with the idea of a norm, don't worry. Make a note of it as something that seems to be powerful and is worth learning. It will reappear later.

(iv) The only obvious cube triangular number is the first one – namely T1 " 1. Basic algebra leads quickly to an equation as in part (i):

$$\frac{n(n+1)}{2} = m^3,$$

which is equivalent to

$$\left(2n+1\right)^{2}-1=\left(2m\right)^{3}.$$

So p2mq 3 and p2mq 3 ` 1 are consecutive integers that are both proper powers. Catalan (1814–1894) conjectured in 1844 that 8 " 2 3 and 9 " 3 2 are the only consecutive powers (other than 0 and 1). This simple-sounding conjecture was finally proved only in 2004. It follows that T1 " 1 is the only triangular number that is also a cube.

55.

	- (ii) 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34; 1, 1, 0, 1, 1, 2, 3, 5, 8, 13
	- (iii) mth term of k th sequence of differences " Fm´k
	- (ii) 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024; 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
	- (iii) mth term of k th sequence of differences " 2 m

56.

	- (ii) x n`<sup>1</sup> ´ 1 " px ´ 1qpx <sup>n</sup> ` x n´1 ` ¨ ¨ ¨ ` x ` 1q. When x " 2, the first factor on the RHS px ´ 1q " 1, so

$$2^0 + 2^1 + 2^2 + \dots + 2^n = 2^{n+1} - 1.$$

[Alternatively:

$$\begin{aligned} \left(2^0 + \left(2^0 + 2^1 + 2^2 + \dots + 2^n\right)\right) &= \left\{2^0 + 2^0 \ \left[= 2^1\right]\right\} + \left\{2^1 + 2^2 + \dots + 2^n\right\} \\ &= \left\{2^1 + 2^1 \ \left[= 2^2\right]\right\} + \left\{2^2 + 2^3 + \dots + 2^n\right\} \\ &= \left\{2^2 + 2^2 \ \left[= 2^3\right]\right\} + \left\{2^3 + 2^4 + \dots + 2^n\right\} \\ &= \dots \\ &= \left\{2^n + 2^n\right\} = 2^{n+1}. \end{aligned}$$

(b)(i) 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, . . .

(ii) F0 ` F<sup>1</sup> " F<sup>2</sup> " F<sup>3</sup> ´ F<sup>1</sup> F<sup>0</sup> ` F1 ` F<sup>2</sup> " pF<sup>3</sup> ´ F1q ` F2 " pF3 ` F2q ´ F<sup>1</sup> " F<sup>4</sup> ´ F<sup>1</sup> F<sup>0</sup> ` F1 ` F<sup>2</sup> ` F3 " pF4 ´ F1q ` F<sup>3</sup> " pF<sup>4</sup> ` F3q ´ F1 " F5 ´ F1.

### Claim:

$$F\_0 + F\_1 + F\_2 + \dots + F\_{n-1} = F\_{n+1} - F\_1$$

holds for all n ě 1.

Proof: When n " 1, the LHS " F0 " 0 " 1 ´ 1 " F2 ´ F1 " RHS. We proved the next few case n " 2, n " 3, n " 4 above.

Suppose we have already proved the required relation holds all the way up to the pk ´ 1q th equation:

$$F\_0 + F\_1 + F\_2 + \dots + F\_{k-1} = F\_{k+1} - F\_1 \dots$$

Then the k th equation follows like this:

$$\begin{aligned} \left( \left( F\_0 + F\_1 + F\_2 + \dots + F\_{k-1} \right) + F\_k \right) &= \left( F\_{k+1} - F\_1 \right) + F\_k \\ &= \left( F\_{k+1} + F\_k \right) - F\_1 \\ &= F\_{k+2} - F\_1. \end{aligned}$$

So we have shown

Hence the identity holds for all n ě 1. QED

Alternatively:

$$\begin{aligned} \left(F\_1 + \left(F\_0 + F\_1 + \dots + F\_k\right)\right) &= \left(F\_1 + F\_0 \ \left[= F\_2\right]\right) + \left(F\_1 + F\_2 + \dots + F\_k\right) \\ &= \left(F\_2 + F\_1 \ \left[= F\_3\right]\right) + \left(F\_2 + F\_3 + \dots + F\_k\right) \\ &= \left(F\_3 + F\_2 \ \left[= F\_4\right]\right) + \left(F\_3 + F\_4 + \dots + F\_k\right) \\ &= \dots \\ &= F\_{k+1} + F\_k = F\_{k+2} .\end{aligned}$$

Note: In 56(a)(ii) we appealed directly to the factorisation of x n`<sup>1</sup> ´ 1 as though this were a "known fact" which is easy to prove. And in the "alternative" proof, we repeatedly combined "2<sup>k</sup> + 2<sup>k</sup> " to make 2<sup>k</sup>`1 , inserting dots ". . . " to indicate that this replacement operation is repeated n ` 1 times. Both of these involved thinly veiled applications of the principle of Mathematical Induction, which is addressed in detail in Chapter 6. In 56(b)(ii) we had no way of concealing the use of "proof by Mathematical Induction", which is likely to be lurking whenever we have

and

a proposition, or statement, Ppnq involving the parameter n

we wish to prove the infinite collection of assertions:

"Ppnq is true for every n " 1, 2, 3, . . . ".

The standard way of achieving this apparent miracle of proving infinitely many things at once is:

to check that Pp1q holds (that is, to check that Ppnq is true when n " 1);

then

to suppose that we have checked all of the instances Pp1q, Pp2q, . . . , up to Ppkq for some k ě 1,

and

to show that the next instance Ppk ` 1q must then also be true.

We then conclude that Ppnq is true for all ně 1.

57.

(a)(i) 0, 2, 3, 10, 24, 65, 168, . . .

(ii) Guess:

$$F\_{n-1}F\_{n+1} = F\_n^2 + \left(-1\right)^n F\_1, \text{ for all } n \gg 1.$$

Proof: By part (i), this identity holds for n " 1, 2, 3, 4, 5, 6, 7. Suppose we have checked it as far as the k th instance:

$$F\_{k-1}F\_{k+1} = F\_k^2 + \left(-1\right)^k F\_1 \dots$$

Then the next instance follows, since

$$\begin{aligned} F\_{\{k+1\}-1}F\_{\{k+1\}+1} &=& F\_k F\_{k+2} \\ &=& (F\_{k+1} - F\_{k-1})(F\_k + F\_{k+1}) \\ &=& F\_{k+1}^2 + \{F\_{k+1}F\_k - F\_{k-1}F\_k\} - F\_{k-1}F\_{k+1} \\ &=& F\_{k+1}^2 + (F\_k^2 - F\_{k-1}F\_{k+1}) \\ &=& F\_{k+1}^2 + \{-1\}^{k+1}F\_1. \end{aligned}$$

So we have shown that the identity holds for the first few values of n, and whenever we know it is true up to the k th identity, it also holds for the pk ` 1q th identity. Hence the identity holds for all n ě 1. QED

(b)(i) We suppose that

$$\frac{b}{a} < \frac{d}{c}$$

(if the inequality is reversed, the expression for the area is multiplied by "´1").

The lines x " 0, y " 0, x " a ` c, y " b ` d form a rectangle of area pa ` cqpb ` dq, which surrounds the parallelogram.

To get from this to the area of the parallelogram, we must subtract

$$\text{area}(OABC) = (a+c)(b+d) - 2bc - ab - cd = ad - bc.$$

(ii) 1

(iii) Half of the 2nd parallelogram is equal to half of the 1st – so both have the same area, namely 1.

Half of the 3rd parallelogram is equal to half of the 2nd – so they both have the same area, namely 1.

And so on. Hence the area of the n th parallelogram is equal to

$$|ad - bc| = |F\_{n-1}F\_{n+1} - F\_n^2| = 1.$$

Part (a)(ii) is more precise in that it says that Fn´1Fn`1 ´ F 2 n " p´1q n : this says that the relative positions of the generators pa, bq, pc, dq for successive Fibonacci parallelograms alternate, with first b a ą d c , and then b a ă d c . (In fact the gradient of successive versions of the line OA, or the ratio of successive Fibonacci numbers, converges to the Golden Ratio τ , with successive Fibonacci points A " pFn´1, Fnq alternately above and below the line with equation y " τx.)

58.

$$F\_{n-1}^2 + F\_n^2 = F\_{2n-1}.$$

Note: When part (a) gives rise unexpectedly to "the odd-numbered terms of the Fibonacci sequence", it is almost impossible to believe that this is an accident. Yet the attempt to prove that this "Guess" is correct may well prove elusive – for it is hard to see how to relate the pn ´ 1q th and n th terms to the p2n ´ 1q th term.

One approach is to

"try to prove something stronger than what seems to be required".

Claim: For each n ě 1, both of the following are true:

$$F\_{n-1}^2 + F\_n^2 = F\_{2n-1} \quad \text{and} \quad F\_{n+1}^2 - F\_{n-1}^2 = F\_{2n}.$$

Proof: We have already checked that the first relation holds for n " 1, 2, 3, 4, 5. And it is easy to check that

$$\begin{aligned} F\_{1+1}^2 - F\_{1-1}^2 &= -1 - 0 = 1 = F\_2, \\ F\_{2+1}^2 - F\_{2-1}^2 &= -4 - 1 = 3 = F\_4, \\ F\_{3+1}^2 - F\_{3-1}^2 &= -9 - 1 = 8 = F\_6. \end{aligned}$$

So both identities hold for the first few values of n.

Now suppose we have checked that both relations hold all the way up to the k th pair of relations.

Then simply adding the two relations in the k th pair gives the first relation of the next pair:

$$\begin{aligned} \left(F\_k^2 + F\_{k+1}^2\right) &= \left(F\_{k-1}^2 + F\_k^2\right) + \left(F\_{k+1}^2 - F\_{k-1}^2\right) \\ &= \left(F\_{2k-1} + F\_{2k}\right) \\ &= \quad F\_{2k+1} \end{aligned}$$

To see that the second relation of the next pair also follows, consider

$$\begin{aligned} \begin{array}{rcl} F\_{k+2}^2 - F\_k^2 &=& \left( F\_k + F\_{k+1} \right)^2 - F\_k^2 \\ &=& F\_{k+1}^2 + 2F\_k F\_{k+1} \\ &=& \left( F\_{k+1}^2 - F\_{k-1}^2 \right) + F\_{k-1}^2 + 2F\_k F\_{k+1} \\ &=& F\_{2k} + \left( F\_{k+1} - F\_k \right)^2 + 2F\_k F\_{k+1} \\ &=& F\_{2k} + \left( F\_{k+1}^2 + F\_k^2 \right) \\ &=& F\_{2k} + F\_{2k+1} \\ &=& F\_{2k+2}. \end{array} \end{array}$$

So we have shown

Hence the two identities hold for all n ě 1. QED

#### 59.

	- (ii) Guess: Fn´2Fn`<sup>2</sup> " F 2 <sup>n</sup> ` p´1q n`1 . Proof: By part (i), this identity holds for n " 2, 3, 4, 5, 6. Suppose we have checked it as far as the k th instance:

$$F\_{k-2}F\_{k+2} = F\_k^2 + \left(-1\right)^{k+1}.$$

Then the next instance follows using 57, since

$$\begin{array}{rcl} F\_{\{k+1\}-2}F\_{\{k+1\}+2} & = & F\_{k-1}F\_{k+3} \\ & = & F\_{k-1}(F\_{k+1} + F\_{k+2}) \\ & = & F\_{k-1}F\_{k+1} + F\_{k-1}F\_{k+2} \\ & = & F\_k^2 + (-1)^k + (F\_{k+1} - F\_k)(F\_k + F\_{k+1}) \\ & = & (-1)^k + F\_{k+1}^2 .\end{array}$$

(b)(i) 0, 13, 21, 68, . . .

#### (ii) Guess:

$$F\_{n-3}F\_{n+3} = F\_n^2 + (-1)^{n+3-1}F\_3^2 \dots$$

This suggests that we should reinterpret our previous guesses, and that the "correction terms" on the RHS:

We leave the proof (or otherwise) of this conjecture as an exercise for the reader.

60.

$$(1.1a)(1.1b) = (1 + 0.1)^2ab = (1 + 0.2 + 0.01)ab = 1.21ab.$$

(iii) 0% – notice that

$$\frac{1.1a}{1.1b} = \frac{a}{b}.$$

61. If x is doubled in the expression "x", then the value of the expression doubles. If y is doubled in the expression x ˜ y, then the value of the expression is halved. If z is doubled in the expression x ˜ py ˜ zq, then the bracket is halved, and the expression is doubled.

Replacing "x, y, z" by "d, e, f" we see that, if the value of f is doubled, the value of the bracket pd ˜ pe ˜ fqq is also doubled.

If we now take x " b, y " c, z " pd ˜ pe ˜ fqq, then, when f is doubled, z is doubled, and the value of pb ˜ pc ˜ pd ˜ pe ˜ fqqqq is doubled.

Hence the value of the whole expression

$$a \div (b \div (c \div (d \div (e \div f))))$$

is halved.

62.

(a) The fact that one can add the entries in any order depends on the commutative and associative laws of addition. Expressing the subtotal in the second row as 2p1 ` 2 ` 3 ` 4q uses the distributive law. And expressing the overall sum

$$1 + (1+2+3+4) + 2(1+2+3+4) + 3(1+2+3+4) + 4(1+2+3+4)$$

as p1 ` 2 ` 3 ` 4q 2 uses the distributive law again.

	- (ii) p4`8`12`16q ` p12`8`4q " 4T4 `4T3. Similarly, the k th reverse L-shape has sum

$$k \cdot T\_k + k \cdot T\_{k-1} = \frac{1}{2}k^2(k+1) + \frac{1}{2}k^2(k-1) = k^3.$$

Hence

$$C\_n = 1^3 + 2^3 + 3^3 + \dots + n^3 = \left(1 + 2 + 3 + \dots + n\right)^2 = \frac{1}{4} \cdot n^2 (n+1)^2 \dots$$

#### 63.

(a) The terms are 1 ˆ 2, 2 ˆ 3, 3 ˆ 4, etc,; so the r th term is r (r+1), and the last term is pn ´ 1qppn ´ 1q ` 1q.

The r th term can be expressed as "r 2 ` r", so the sum

$$1 \times 2 + 2 \times 3 + 3 \times 4 + \dots + r(r+1) + \dots + (n-1)n$$

can be expressed as

$$\left(1^2 + 2^2 + 3^2 + \dots + (n-1)^2\right) + \left(1 + 2 + 3 + \dots + (n-1)\right) = S\_{n-1} + T\_{n-1}.$$

(b)(i) ∗ n " 2: 6 " 1 ˆ 2 ˆ 3.

∗ n " 3: 6 ` 18 " 24 " 2 ˆ 3 ˆ 4.

∗ n " 4: 6 ` 18 ` 36 " 60 " 3 ˆ 4 ˆ 5.

Guess: 3pSn´1 ` T<sup>n</sup>´<sup>1</sup>q " pn ´ 1qnpn ` 1q.

Proof: This is true for n " 1, 2, 3, 4.

Suppose we have checked the claim for all values up to

$$3(S\_{k-1} + T\_{k-1}) = (k-1)k(k+1).$$

Then

$$\begin{aligned} 3(S\_k + T\_k) &=& 3([S\_{k-1} + k^2] + [T\_{k-1} + k]) \\ &=& (k-1)k(k+1) + 3k(k+1) \\ &=& k(k+1)(k+2). \end{aligned}$$

Hence our guess is true for all n ě 1.

(ii)

$$S\_n + T\_n = \frac{n(n+1)(n+2)}{3},$$

$$S\_n = \frac{n(n+1)(n+2)}{3} - T\_n = \frac{n(n+1)(2n+1)}{6}$$

.

so

\*\*64.\*\* If one tries to apply the usual algorithms for decimals, then one is likely to get in something of a mass. But if we re-interpret each decimal as a fraction, then  $\frac{1}{2}$  things are much easier.

$$\begin{aligned} \text{(a)} \quad &\frac{5}{9} + \frac{6}{9} = \frac{11}{9} = 1.22222\cdots. \\ \text{(b)} \quad &0.99999\cdots = \frac{9}{9} = 1; \, 1 + \frac{1}{9} = 1.11111\cdots. \\ \text{(c)} \quad &\frac{10}{9} - \frac{2}{9} = \frac{8}{9} = 0.88888\cdots \\ \text{(d)} \quad &\frac{1}{3} \times \frac{2}{3} = \frac{2}{9} = 0.22222\cdots. \\ \text{(e)} \quad &\frac{11}{9} \times \frac{9}{11} = 1. \end{aligned}$$

65.

(a) Such a decimal is by definition equal to the fraction with numerator

$$b\_n b\_{n-1} \cdot \cdots \cdot b\_1 b\_0 b\_{-1} b\_{-2} \cdot \cdots b\_{-k}$$

(an integer with n ` k ` 1 decimal digits) and with and denominator 10k .

(b) If p q is equivalent to a fraction with numerator

$$m = b\_n b\_{n-1} \cdots b\_1 b\_0 \,\_{\text{baso } 10}$$

and denominator 10k , then m has decimal representation

$$b\_n b\_{n-1} \cdots b\_k.b\_{k-1} \cdots b\_1 b\_0.$$

66.

(a) (i) 1 27 ; (ii) 10 27 ; (iii) 19 27 (b) (i) a 9 ; (ii) ab 99 ; (iii) abc 999

67.

(a) 0.166666 ¨ ¨ ¨ (block length 1); 0.833333 ¨ ¨ ¨ (block length 1)

(b) All have block length 6:

.142857142857142857 ¨ ¨ ¨ ; .285714285714285714 ¨ ¨ ¨ ; .428571428571428571 ¨ ¨ ¨ ; .571428571428571428 ¨ ¨ ¨ ; .714285714285714285 ¨ ¨ ¨ ; .857142857142857142 ¨ ¨ ¨ .

Note: The repeating blocks are all cyclically related: e.g. the block for 2 7 is the same as for 1 7 , but starting at "2" instead of at "1".

(c) All have block length 2:

0.090909 ¨ ¨ ¨ ; 0.181818 ¨ ¨ ¨ ; 0.272727 ¨ ¨ ¨ ; 0.363636 ¨ ¨ ¨ ; 0.454545 ¨ ¨ ¨ ; 0.545454 ¨ ¨ ¨ ; 0.636363 ¨ ¨ ¨ ; 0.727272 ¨ ¨ ¨ ; 0.818181 ¨ ¨ ¨ ; 0.909090 ¨ ¨ ¨ .

Note: The repeating blocks are not all cyclically the same, but fall into five pairs:

– 1 11 and 10 11 are cyclically related;

$$- \text{ as are those for } \frac{2}{11} \text{ and } \frac{9}{11};$$

Note: They fall into two families of six, where each family is cyclically related :

1 13 " 0.076923076923076923 ¨ ¨ ¨ , 3 13 " 0.230769230769230769 ¨ ¨ ¨ , 4 13 " 0.307692307692307692 ¨ ¨ ¨ , 9 13 " 0.692307692307692307 ¨ ¨ ¨ , 10 13 " 0.769230769230769230 ¨ ¨ ¨ , 12 13 " 0.923076923076923076 ¨ ¨ ¨ ;

and

$$\begin{array}{l} \frac{2}{13} = 0.153846153846153846\cdots; \\ \frac{5}{13} = 0.384615384615384615\cdots; \\ \frac{6}{13} = 0.461538461538461538\cdots; \\ \frac{7}{13} = 0.538461538461538461\cdots; \\ \frac{8}{13} = 0.615384615384615384\cdots; \\ \frac{11}{13} = 0.846153846153846153\cdots. \end{array}$$

68.

69. Claim Decimal fractions have two decimal representations. All other numbers have exactly one decimal representation.

Proof: Every "decimal fraction" (that is, any fraction which can be written with denominator a power of 10) has two representations – one that terminates and one that ends with an endless string of 9s: if the last non-zero digit of the terminating decimal is k, then the second representation of the same number is obtained by changing the "k" to "k ´ 1" and following it with an endless string of 9s.

Consider an unknown number with two different decimal representations α and β. Since they are "different", α and β must differ in at least one position. Suppose the first, or left-most, position in which they differ is that in the k th decimal place (corresponding to 10´k ), and that the two digits in that position are ak (for α) and bk (for β).

We may suppose that ak ă bk. Then bk " ak ` 1 (otherwise bk ´ ak ą 1, and β ´ α ą 10´k , so α ‰ β).

Moreover, since β is not larger than α, the digits following bk must all be equal to 0, and the digits following ak must all be equal to 9. QED

70. In case (d), A only has to choose a recurring block (such as "55555 ¨ ¨ ¨ ", or "090909 ¨ ¨ ¨ ", or "123123123 ¨ ¨ ¨ ") for his/her positions – no matter where they are. B's control terminates at some stage, after which A's recurring block guarantees that the resulting number is rational.

The other parts all offer a guaranteed strategy for B. Let the positions chosen by B be numbered

$$n\_1, n\_2, n\_3, n\_4, \dots, n\_k, \dots$$

Now exploit the fact that the positive rationals are countable – that is, can be included in a single list. To see this we can use Cantor's (1845–1918) diagonal enumeration

0 1 ; 1 1 ; 1 2 , 2 1 ; 1 3 , 3 1 ; 1 4 , 2 3 , 3 2 , 4 1 ; 1 5 , 5 1 ; 1 6 , 2 5 , 3 4 , 4 3 , 5 2 , 6 1 ; 1 7 , . . . ,

which lists all rationals p q with HCFpp, qq " 1

#### and so on.

All B needs to do is to make sure that the resulting decimal is not the decimal of any number in this list, and s/he can do this by choosing a digit in the n th k position which is different from the digit which the k th rational in the above list has in that position. The resulting real number is then different from every number in the list – and hence must be irrational.

#### 71.

Note: Trying to do this should make it clear how easily we confound "the fourteenth positive integer" with its familiar base 10 representation. It takes time and effort to learn to see "14base 10" as "2 ˆ7", and "21base 10" as 3ˆ7, and hence to spot the common multiple "42base 10". In base 2 the same numbers evoke no such familiar echoes.

72. Let N " pakak´1 ¨ ¨ ¨ a1a0qbase 2.

$$"{a\_0 - a\_1 + a\_2 - a\_3 + \dots \pm a\_k}",$$

is divisible by 3.

#### Proof

$$\begin{aligned} N &= \ (a\_k a\_{k-1} \cdots a\_1 a\_0)\_{\text{basa }2} \\ &= \ 2^k a\_k + 2^{k-1} a\_{k-1} + \cdots + 2a\_1 + a\_0. \end{aligned}$$

For each odd suffix m, increase the coefficient 2m by 1: then

$$2^m + 1 = (2+1)(2^{m-1} - 2^{m-2} + \dots - 2 + 1)$$

has 3 as a factor.

For each even suffix m " 2n, decrease the coefficient by 1: then

$$2^{2n} - 1 = (2^2 - 1)(2^{2n - 2} + 2^{2n - 4} + \dots + 2^2 + 1)!$$

has 3 as a factor.

Hence

$$\begin{aligned} N &= \ 2^k a\_k + 2^{k-1} a\_{k-1} + \dots + 2a\_1 + a\_0 \\ &= \ \text{(multiple of 3)} + (a\_0 - a\_1 + a\_2 - \dots \pm a\_k). \end{aligned}$$

$${"{a\_1 a\_0}" - {"{a\_3} a\_2"}} + {"{a\_5} a\_4" -
\cdots}$$

is divisible by 5.

Proof:

$$\begin{array}{rcl} N &=& \langle a\_k a\_{k-1} \cdots a\_1 a\_0 \rangle\_{\text{base } 2} \\ &=& 2^k a\_k + 2^{k-1} a\_{k-1} + \cdots + 2a\_1 + a\_0 \\ &=& \langle 2a\_1 + a\_0 \rangle + 2^2 (2a\_3 + a\_2) + 2^4 (2a\_5 + a\_4) + \cdots \\ &=& \langle 2^2 + 1 \rangle (2a\_3 + a\_2) + (2^4 - 1)(2a\_5 + a\_4) + \cdots \\ & & \quad + [ (2a\_1 + a\_0) - (2a\_3 + a\_2) + (2a\_5 + a\_4) - \cdots ] \\ &=& \langle \text{a multiple of } 5 \rangle + [ \*a\_1 a\_0 \text{" $ } - \text{"} a\_3 a\_2 \text{"$  } + \text{" $a\_5} a\_4 \text{"$  } - \cdots ]. \end{array}$$

73.

(a) To weigh an object with weight 1, we must have w0 " 1.

To weigh an object with weight 2, we must have w1 " 2. We can then weigh any object of weight 3, but not one of weight 4.

(i) Now assume each positive weight w can be balanced in exactly one way. Then we cannot have w2 " 3, so w2 " 4.

Suppose that, continuing in this way, we have deduced that wi " 2 i for each i " 0, 1, 2, . . . , k.

Then the binary numeral system reveals precisely that every weight w from 0 up to

$$2^{k+1} - 1 = 1 + 2 + 2^2 + \dots + 2^k$$

can be uniquely represented, but 2k`1 cannot. Hence

> wk`<sup>1</sup> " 2 k`1 .

The result follows by induction.

(ii) If the representation of each integer is not unique, then the sequence

$$w\_0, \ w\_1, \ w\_2, \ \dots$$

need not include the powers of 2. For example, it could begin

1, 2, 3, 5, . . .

(b) If each integer w is to be weighed in this way, then w has to be represented in the form

$$w = a\_1 w\_1 + a\_2 w\_2 + a\_3 w\_3 + \cdots$$

where each coefficient ai " 0 (if the weight wi is not used to weigh w), or " 1 (if the weight wi is used to balance w), or " ´1 (if the weight wi is used to supplement w).

If each representation is to be unique, then one can prove as in (a)(i) that the sequence of weights must be the successive powers of 3.

74. Write m in "base 2":

$$m = (a\_{n-1} \cdot \cdots \cdot a\_1 a\_0)\_{\text{base 2}},$$

where each ak " 0 or 1. Then

$$\frac{m}{2^n} = \frac{a\_0}{2^n} + \frac{a\_1}{2^{n-1}} + \dots + \frac{a\_{n-1}}{2}.$$

That is,

$$\frac{m}{2^n} = (0.a\_{n-1} \cdot \cdots \cdot a\_1a\_0)\_{\text{base 2}}.$$

75. We give an example, starting with N " 110 111 001base 2 .

Write N, and pair off the digits, starting at the units digit.

### 1 } 10 } 11 } 10 } 01

The left-most digit stands for 28 , so the square root is at least 24 (and less than 2 5 ). Hence the required square root has five digits (one for each "pair" of digits of N), and starts with a 1.

Root 1 } ? } ? } ? } ?

[We can also see that the final units digit will have to be a "1". But this is not the time to add such information.]

Let x " 10 000, and subtract x 2 " 100 000 000 from N:

$$\begin{array}{r|r|r|r} 1 & 00 & 00 & 00 & 00 \\ \parallel \text{ 10} \parallel \text{ 11} \parallel \text{ 10} \parallel \text{ 01} \end{array}$$

This residue has to be equal to "2xy ` y 2 ". However, as with long division, our immediate interest is in determining the next digit of our "partial square root". If the next digit is a 1 (contributing 23 ), then 2xy ě 2 8 , which would spill over and change the digit we have already determined. Hence the next digit is a 0.

Root 1 } 0 } ? } ? } ?

So we can again let x " 10 000 giving the same remainder, which has to be equal to "2xy ` y 2 ", but this time y ă 2 3 has at most three digits.

The remainder

$$\begin{array}{c|c|c|c|c} \hline 1 & 10 & 11 & 10 & 01 \\ \hline \end{array}$$

is greater than 27 , so y ě 2 2 and the next digit must be a "1".

Root 1 } 0 } 1 } ? } ?

Now let x " 10 100, and subtract x 2 " 110 010 000 from N, leaving

$$\begin{array}{c|c} 10 & 10 \perp 01 \\ \end{array}$$

This residue has to equal 2xy ` y 2 , with x " 10 100. If the next digit in the square root is 1, then 2xy ě 2 <sup>6</sup> ą 101 001 " 2xy ` y 2 . Hence the next digit is 0, and the last digit is then 1.

Hence the required square root is equal to:

```
Root 1 } 0 } 1 } 0 } 1
```
76.

(b)(i) The fact that

n1 " p1 ` 1

says that

"n1 is equal to a multiple of p1 with remainder " 1".

(c)(i) The fact that

$$n\_2 = p\_1 \times p\_2 + 1$$

says that

"n2 is equal to a multiple of p1 with remainder " 1",

and that

"n2 is equal to a multiple of p2 with remainder " 1".

Hence neither p1 nor p2 are factors of n2.

(d) The fact that

nk " p1 ˆ p2 ˆ ¨ ¨ ¨ ˆ pk ` 1

says that

"nk is equal to a multiple of pi with remainder " 1"

for each suffix i, 1 ď i ď k. Hence none of the primes p1, p2, p3, . . . , pk is a factor of nk.

So the smallest prime factor of nk always gives us a new prime pk`1.

(e) If we start with p1 " 2, then n1 " p1 ` 1 " 3, so p<sup>2</sup> " 3. Then n<sup>2</sup> " p<sup>1</sup> ˆ p<sup>2</sup> ` 1 " 7, so p3 " 7. Then n3 " p1 ˆ p2 ˆ p3 ` 1 " 43, so p<sup>4</sup> " 43. Then n<sup>4</sup> " p<sup>1</sup> ˆ p<sup>2</sup> ˆ p<sup>3</sup> ˆ p<sup>4</sup> ` 1 " 1807 " 13 ˆ 139, so p5 " 13.

77.

(a) We write rxs for the "first integer ě x".

(b) The initial "doubling" is an accident of small numbers, which soon turns into "slightly more than doubling".

The observation that should (eventually) jump out at you concerns the ratio e N : πpNq, which seems to be surprisingly close to N ´ 1. This suggests the possible

Conjecture: πpxq " x lnpxq´1 (where lnpxq " loge pxq).

All the evidence suggests that the shapes of reality are mathematical. George Steiner (1929– )

The previous chapter focused on aspects of the arithmetic of pure numbers – mostly without any surrounding context. However, our mathematical experience does not begin with pure numbers. At school level, mathematical concepts, and the reasoning we bring to understanding and using them, have their roots in language. And in real life, every application of mathematics starts out with a situation which is described in words, and which has to be reformulated mathematically before we can begin to calculate, and to draw meaningful mathematical conclusions. Word problems play an important, if limited, role in helping students to appreciate, and to handle the subtleties involved in

> the art of using the mathematics we know to solve problems given in words.

This art of using mathematics involves two distinct – but interacting – processes, which we refer to here as "simplifying" and "recognising structure".

• To identify the mathematical heart of a problem arising in the real world, one may first have to simplify – that is, to side-line details that seem unimportant or irrelevant, and then simplify as much as possible without changing the underlying problem (e.g. by replacing some awkward feature by a different quantity which is easier to measure, or by an approximation which is easier to work with).

This "simplifying" stage is well-illustrated by the tongue-in-cheek title of the classic textbook Consider a spherical cow . . . by John Harte (1985):

Milk production at a dairy farm was low, so [. . . ] a multidisciplinary team of professors was assembled. [. . . After] two weeks of intensive on-site investigation [. . . ] the farmer received the write up, and opened it to read [. . . ] "Consider a spherical cow . . . ".

The point to emphasise here is that the judgements needed when "simplifying" are subtle, depend on an understanding of the particular situation being modelled, and may lead to a model which at first sight seems to be counterintuitive, but which may not be as silly as it seems – and which therefore needs to be explained sensitively to non-mathematicians.

In contrast word problems by-pass the "simplifying" stage, and focus instead on "recognising structure": they present the solver with a problem which is already essentially mathematical, but where the inner structure is contextualised, and is described in words. All the solver has to do is to interpret the verbal description in a way that extracts the structure just beneath the surface, and to translate it into a familiar mathematical form. That is, word problems are designed to develop facility with the process of "recognising structure", while avoiding the complication of expecting students to make modelling judgements of the kind required by the subtler "simplifying" process.

Because word problems focus on the second process of "recognising structure", they tend to incorporate the relevant mathematical structure isomorphically. The underlying structure still needs to be identified and interpreted, but the interpretations are likely to be standard, with no need for imaginative assumptions and simplifications before the structure can be discerned. For example, if a problem in primary school refers to an unknown number of "sweets" to be "shared" between six children, then the collection of "sweets" is isomorphic to a pure number (the number of sweets); and the act of "sharing" is a thinly veiled reference to numerical division.

The story in a word problem may be a purely mathematical problem in disguise. But the art of identifying the correspondence between

the data given in the story line, and

the mathematical entities to which they correspond

and between

the actions in the story line, and

the corresponding mathematical operations on those mathematical entities

is non-trivial, and has to be learned the hard way. The first problem below illustrates the remarkable variety of instances of even the simplest subtraction, or difference.

As in Chapters 1 and 2 the "essence of mathematics" is to be found in the problems themselves. Some discussion of this "essence" is presented in the text between the problems; but most of the relevant observations are either to be found in the solutions (or in the Notes which follow many of the solutions), or are left for readers to extract for themselves.

### 3.1. Twenty problems which embody "3 ´ 1 " 2"

The answer to every one of the questions in Problem 78 is the same – at least, as a 'pure number'. The goal is therefore not to "solve" each problem, but to distinguish between, and to reflect upon, the different ways in which the very simple mathematical structure "3 ´ 1 " 2" turns out to be the relevant "model" in each case.

### Problem 78

4 This question is historically correct. In 1946, in the Soviet Union, when these problems were formulated, Saturday was a working day.

### 3.2. Some classical examples

Problem 79 Katya and her friends stand in a circle in such a way that the two neighbours of each child are of the same gender. If there are five boys in the circle, how many girls are there? 4

Problem 80 How much pure water must be added to a vat containing 10 litres of 60% solution of acid to dilute it into a 20% solution of acid? 4

5 Gorky (now the city of Nizhny Novgorod) lies to the east of Moscow.

 Six years ago the mother was 4 times as old as her daughter.  The team spent half-a-day mowing the larger field. After that the team split: one half continued working on the big field and finished it by evening; the other half worked on the smaller field, and did not finish it that day – but the remaining part was mowed by one mower in one day. How many mowers were there? 4

### 3.3. Speed and acceleration

Problem 84 Jack and Jill went up the hill, and averaged 2 mph on the way up. They then turned round and went straight back down by the same route, this time averaging 4 mph. What was their average speed for the round trip (up and down)? 4

### Problem 85

	- (ii) I cycle for 3 hours round the track of a velodrome, averaging 40 km/h for the first hour, 30 km/h for the second hour, and 20 km/h for the final hour. What is my average speed over the whole 3 hours?
	- ∗ the arithmetic mean

$$\frac{u+v}{2}$$

of two positive quantities u, v, and

∗ the harmonic mean

$$\frac{2}{\frac{1}{u} + \frac{1}{v}}\text{.}$$

(ii) Give a purely algebraic proof of your inequality in (i). 4

Problem 86 A train started from a station and, moving with a constant acceleration, covered a distance of 4 km, finally reaching a speed of 72 km/hour. Find the acceleration of the train, and the time taken for the 4 km. 4

Problem 87 (Average speed of an accelerating car) A typical car (and maybe also a typical train!) does not move with constant acceleration. Starting from a standstill, a car moves through the gears and "accelerates more quickly" in lower gears, when travelling at lower speeds, than it does in higher gears, when travelling at higher speeds. Use this empirical fact to prove that the average speed of a car accelerating from rest is more than half of its final measured speed after the acceleration. 4

### 3.4. Hidden connections

Problem 88 Two old women set out at sunrise and each walked with a constant speed. One went from A to B, and the other went from B to A. They met at noon, and continuing without a stop, they arrived respectively at B at 4 pm and at A at 9 pm. At what time was sunrise on that day? 4 Problem 89 A paddle-steamer takes five days to travel from St Louis to New Orleans, and takes seven days for the return journey. Assuming that the rate of flow of the current is constant, calculate how long it takes for a raft to drift from St Louis to New Orleans. 4

Problem 90 [From Paolo dell'Abbaco's Trattato d'aritmetica] "From here to Florence is 60 miles, and there is one who walks it in 8 days [in one direction], another in five days [in the opposite direction]. It is asked: Departing at the same time, in how many days will they meet?" 4

Problem 91 Notice that in Problem 88 sunrise occurs t " ? 4 ˆ 9 hours before noon, and that ? 4 ˆ 9 is the geometric mean of 4 and 9. Once this is pointed out, can you reformulate your solution to Problem 88 to solve a more general problem? 4

### 3.5. Chapter 3: Comments and solutions

#### 78.

Note: This kind of "geometrical subtraction" is needed in many contexts (such as: proving the general formula

$$\frac{1}{2}(\text{base} \times \text{height})$$

for the area of a triangle, or showing that the area of the parallelogram spanned by the origin and vectors pa, bq, pc, dq is |ad ´ bc|, or in Euclid's Elements, Book I, Proposition 2). The idea can be strangely elusive.

(c) The situation here is significantly different. We start with Tanya's brothers and sisters, and finish with the related, but different, notion of "boys and girls in Tanya's family". The "3" does not represent anything specific: it is a numerical excess (of Tanya's brothers over her sisters). In contrast, the "1" seems to represent Tanya herself, who needs to be taken into account when we switch from the initial scenario (Tanya's brothers and sisters) to the final question about "boys and girls in Tanya's family".

(d) No doubt this can be solved by drawing a picture in which the underlying structure is only appreciated superficially. But beneath the surface, it seems to be a much more abstract representation of "3´1 " 2". The "3" certainly stands for the "three pieces". But the operation "´1" is not obviously subtracting anything.

The relevant observation is simply that, starting from one end, pieces and cuts alternate. So if we ignore the starting end, there must be the same number of pieces and cuts – except that if we start with a log (rather than a long tape from which we are cutting off pieces), the "last cut" is "the other end of the log", which has already been cut – so does not need to be cut again, and this obliges us to subtract 1 from the number of pieces to get the number of additional cuts.

Note: This idea arises in many settings, and is sometimes referred to as "Posts and gaps". Sometimes one has to "subtract 1" as here; at other times one has to "add 1" (e.g. when counting the number of "posts", if we are given the number of "gaps", or "fence panels").

Note: The impact of the extra step (switching from discrete counting number to continuous distance) can be seen more clearly in the number of errors made when students are faced with such variations as:

"There are ten lamp posts in my street, and they are 70 metres apart. How far is it from the first to the last?"

(h) One suspects that this superficially simple problem would prove inaccessible unless pupils have learned to represent word problems diagrammatically, or have already mastered simple algebra. The "3" and the "1" do not represent real-world entities; so one has to be prepared to mark a "3" on a number line, and to interpret "average" as indicating that the two unknown quantities lie equally spaced either side of it. "Half their difference" is then staring one in the face, and the smaller number (to the left) is clearly "3 ´ 1".

Note: This may look rather like the overdue train in part (e). We suggest that it is significantly different.

(i) The story line clearly adds layers of difficulty which we tend to overlook. Learning to "recognise structure" and to translate words into a form that allows one to calculate is clearly a non-trivial (and neglected) art. Distances in kilometres may convey something more active than the given "length of a barge pole" in part (b), or the reported times in part (e), even if the diagram – once constructed – is very similar (provided of course that "along the same road" is interpreted as meaning "in the same direction").

Note: Consider the following item from an authoritative international study TIMSS 20116 for pupils aged around 14:

"Points A, B, and C lie in a line and B is between A and C. If AB " 10 cm and BC " 5.2 cm, what is the distance between the midpoints of AB and BC?

A 2.4 cm B 2.6 cm C 5.0 cm D 7.6 cm"

The question is a multiple choice question, and the options represent different ways of failing to translate the words into a suitable diagram, or to interpret them correctly. The sampling (in around 50 countries) was done very carefully. So the different success rates in different countries (of which 5 are given below) suggest that some systems give far too little attention to helping pupils to learn the relevant underlying art:

Russia 60%, Hungary 41%, Australia 40%, England 38%, USA 29%

6 Trends in International Mathematics and Science Study, https://timssandpirls.bc.edu/ timss2011/index.html

distances along the plane's path (measured in "plane's lengths"),

and on the other hand

the time taken by the anti-aircraft fire to reach the plane.

This comparison has to be made because of the added complication of the change in the relative velocity of the gun and the plane.

The given rule of thumb specifies the direction in which a stationary gunner should aim; and the reported (unrealistically fast, yet presumed to be steady) motion of the gun introduces a 2-dimensional (vector) version of "swimming upstream" – which suggests the expected answer "two thirds of 3 plane lengths", so that "1" of the "3 plane's lengths" is compensated by the gun's motion.

(q) A solution is again dependent on representing the given information in some form. Whether or not one uses symbols, the wording invites the solver to use "my present age (in years)" as a preferred unit, and to represent "my brother's present age" as "3" of these basic units. The "3 ´ 1" then represents how much older he is than I am – and hence how old he was when I was born, or "how many times my present age he was when I was born".

Note: The choice of unit may conceal the fact that the question and solution are rooted in ratio and proportion.

The "tram on the opposite track" is travelling in the opposite direction, is 1 km away, and is "3 km ahead" (or "3 km behind"); so one of these trams is 1 km from the end of the track, and the other is on the other track and 2 km from one end (travelling in the opposite direction). There are exactly two possible configurations – each arising from the other if we reverse the direction of travel. By choosing the direction of travel (or by allowing "negative speed") we may assume that tram A is 2 km from the same end of the track and that tram B in front of it is 1 km beyond the end of the track on the opposite side. Tram C is 3 km ahead of B, and hence 4 km down that 4.5 km stretch of track (so has not yet "turned the corner"). Hence it is 1 km closer to its nearest neighbour (A) than it is to B.

79. If we ignore the first sentence, then there could be zero girls (and five boys). But the first sentence guarantees that there is at least one girl ("Katya and her friends"). So boys and girls must alternate, giving rise to 5 girls.

80. The problem requires a degree of "modelling" in that "60% solution of acid" suggests that the initial ratio

$$\text{``acid : water''} = 60 \text{ : 40.}$$

Hence the initial 10 litres is made up of 4 litres of water and 6 litres of acid. Adding water does not change the amount of acid; so we want 6 litres to be 20% of the final mix – which must therefore be 30 litres. Hence we should add 20 litres.

81. The difference in ages is 3 2 ˆ d, where d is the daughter's age in years. Six years ago the difference was three times the daughter's age, which was then d ´ 6 years. Hence

$$3(d-6) = \frac{3}{2} \times d,$$

so d " 12.

82.

Note: Underpinning all such problems is the "unitary method", which here comes into its own. It is an essential tool, which is scarcely taught, and not sufficiently practised. (As a result many students mindlessly translate "Tom takes 2 hours" as "T " 2", etc..)

(a) When they all work together we need to know not how long each takes to do the job, but at what rate each contributor works.

Tom does the job in 2 hours, so works at the rate of " 1 2 of a job in 1 hour". Dick works at a rate of " 1 3 of a job in 1 hour", and Harry works at the rate of " 1 4 of a job in 1 hour".

So working together, they can manage

$$\frac{1}{2} + \frac{1}{3} + \frac{1}{4} = \frac{13}{12}$$

of a job in 1 hour.

Hence, to complete 1 job they require 12 13 of an hour.

(b) As in part (a), we need to know the rate at which each man works.

Suppose that Tom completes the fraction t of a job in 1 hour, that Dick completes the fraction d of a job in 1 hour, and that Harry completes the fraction h of a job in 1 hour.

Then in 1 hour, working together, they complete pt`d`hq jobs; so to complete 1 job takes them

$$\frac{1}{t+d+h} \quad \text{hours.}$$

We therefore need to find "t ` d ` h".

  Similarly d ` h " 1 3 , and h ` t " 1 4 . Adding yields

$$2(t+d+h) = \frac{1}{2} + \frac{1}{3} + \frac{1}{4},$$

13

.

so

$$t + d + h = \frac{\gamma}{24}.$$
 Hence the time required for Tom, Dick and Happy to finish 1 job working together is
$$\alpha.$$

$$\frac{1}{t+d+h} = \frac{24}{13}$$

hours.

Note: Alternatively, one might let Tom take T hours to complete 1 job, Dick take D hours to complete 1 job, and Harry take H hours to complete 1 job. Then

$$t = \frac{1}{T}, \quad d = \frac{1}{D}, \quad h = \frac{1}{H}.$$

83. Imagine the two fields as strips of equal width – with the larger field twice as long as the smaller one.

The large strip was completely mowed in two parts:

Hence the whole team mowed two thirds of the large field and the half team mowed the remaining one third.

So the half team, who worked on the smaller field, mowed the equivalent of one third of the larger field – that is, two thirds of the (half-size) smaller field. Therefore the remaining one third of the smaller field was mowed by a single man on the second day.

The previous two thirds of the smaller field (twice as much) was mowed in half a day (half the time), so must have required 4 (" four times as many) men. So the whole team contained 8 mowers.

Alternatively, we may suppose that there are 2n mowers (since the team is said to split into two halves), and that each mower mows at the rate of "r large fields per day".

The total work done in completing the larger field is then

where each part is equal to

pnumber of men ˆ rate of workingq ˆ plength of time workedq.

That is 3 2 nr. So 3 2 nr " 1.

The total work done on the smaller field is

That is n`<sup>2</sup> <sup>2</sup> ˆ r. So <sup>n</sup>`2 2 ˆ r " 1 2 (since the smaller field is half the larger field). Hence 3 2 n " n ` 2.

84. The words "average speed" often provoke an unthinking assumption that one is simply being asked to find the average of the "speed numbers" given in the problem. A moment's thought should remind us that the "average speed" for a journey is not equal to the "average of the various speeds taken as pure numbers"; it is equal to

(the total distance travelled) ˜ (the total time taken).

If the distance up the hill is m miles, then the climb takes m 2 hours, and the descent takes m 4 hours. The total distance for the round trip is 2m miles, so Jack and Jill's average speed is

$$\frac{2m}{\frac{3m}{4}} = \frac{8}{3}\text{ mph.}$$

Note: We first meet averages for discrete quantities, or whole numbers, where the goal is to replace a collection of quantities, or numbers, by a single representative statistic. If n quantities contribute equally, then each contributes exactly p 1 n q th to the average.

One way of looking at this is to represent each of the quantities being averaged in a bar chart – as rectangles of width 1, and with height corresponding to the quantity represented. "Adding all the quantities and dividing by n" is then the same as "calculating the total area under the graph and then dividing by the total length of the interval". In other words, we have replaced the complicated bar chart by a constant function (or a single rectangle), which has the same domain as the bar chart, and which has the same area under it (or integral) as the more complicated bar chart.

More generally, given a function y " fpxq defined for values of x in the interval ra, bs, its average fra,bs (over the interval ra, bs) is defined to be

$$f\_{[a,b]} = \frac{\int\_a^b f(x)dx}{|b-a|}.$$

When we talk about "average speed", we are thinking of speed changing as a function of time; and the total distance covered in any given time interval ra, bs is equal to the area under the graph. We want a single "average speed" vra,bs (a constant function) that would cover the same distance in the same time as the more complicated reality of varying speed. That is,

$$v\_{[a,b]} = \frac{\int\_a^b v(t)dt}{|b-a|}.$$

In Problem 84 the walking speed is misleadingly given in terms of "up" and "down" – which represent the first half distance travelled, and the second half distance travelled. The careful solver knows that s/he has to find "total distance travelled" and divide by "total time taken"; but s/he may not notice that s/he has in fact reinterpreted the given information so that speed is seen as a function of time (rather than of distance).

85.

(a)(i) Let the distance covered on each lap be m km. Then the first lap takes me m 40 hours; the second lap takes me m 30 hours; the third lap takes me m 20 hours. So the total time taken for the three laps is

$$\frac{m}{40} + \frac{m}{30} + \frac{m}{20} = \frac{13m}{120} \text{ hours.}$$

Hence my average speed for the race covering 3m km is

$$\frac{3m}{\left(\frac{13m}{120}\right)} = \frac{360}{13} \text{ km/h.}$$

Note: Alternatively, because the two factors of m in the numerator and the denominator cancel each other, this answer may be formulated as the harmonic mean of the given speeds:

$$\frac{3}{\left[\frac{1}{40} + \frac{1}{30} + \frac{1}{20}\right]} \cdot$$

(ii) In the first hour I cycle 40 km; in the second hour I cycle 30 km; in the third hour I cycle 20 km. So in the three hours I cycle 40 ` 30 ` 20 " 90 km. So my average speed is 30 km/h.

Note: Alternatively, as long as the three time intervals t are equal, we land up with t as a factor in both the numerator and the denominator, so these common factors cancel out, and the answer is simply the arithmetic mean of the given speeds:

$$\frac{20+30+40}{3}$$

	- (ii) Again (unless u " v), the first cyclist spends more time cycling at the higher speed. Hence the first cyclist wins.

$$\frac{2}{\left[\frac{1}{u} + \frac{1}{v}\right]}\text{ km/h.}$$

Hence, part (b)(ii) shows that

$$\frac{u+v}{2} \gg \frac{2}{\left[\frac{1}{u} + \frac{1}{v}\right]} = \frac{2uv}{u+v}.$$

(ii) If we rearrange the required inequality

$$
\frac{u+v}{2} \geqslant \frac{2uv}{u+v},
$$

then we see that it is equivalent to proving that pu`vq 2 ě 4uv. This suggests that we should start with the universally true statement:

$$\left(\left(u-v\right)^{2}\geqslant 0\text{ for all }u,v\geqslant 0.$$

Adding 4uv to both sides yields pu ` vq <sup>2</sup> ě 4uv. Multiplying both sides by the non-negative quantity <sup>1</sup> 2pu`vq then gives the required inequality.

86. The only "modelling" required here is to translate the problem using the standard equations of kinematics. For motion from rest we have

(i) v " at, where t is the time, a is the uniform acceleration, and v the final speed, and

(ii) s " 1 2 at2 , where s is the distance travelled.

There is a question as to what units we should use. For the moment we stick to measuring v in km/h as given, s in km, t in hours, and a in the (unfamiliar) units of km/h2 : so 72 " at and 4 " 1 2 at2 .

Dividing the second equation by the first gives 1 18 " 1 2 t, so t " 1 9 hours (" 400 seconds).

Substituting in the first equation gives a " 72 ˆ 9 km/h2 (" 1 20 m/sec2 ).

Note: Equations (i) and (ii) can be summarised as saying that, under uniform acceleration a, the distance travelled is s " p 1 2 atq ˆ t. Hence the average speed for the complete journey is equal to exactly half of the final speed v " at.

In general, those tackling the problem may agree that the familiar units of speed and distance do not give us a very good gut feeling for the scale of acceleration. If we measure acceleration in km/h2 , then we get huge numbers for acceleration which one cannot easily relate to. And if we switch to m (metres), m/sec, and m/sec2 , then we get rather small numbers for the acceleration, which again convey relatively little.

[The original (Russian) version of this problem had the train travelling 2.1 km and reaching a speed of 54 km/h. This produces a nice answer for the time taken, but a relatively inscrutable answer for the acceleration. So we have changed the parameters.]

### 87.

''We explain why, when a vehicle accelerates from 0 to 20 mph, its average speed is more than 10 mph. In general, the average speed of an accelerating vehicle is more than half the final speed after the acceleration.

Consider first the case when the acceleration is constant: this means that the graph which represents the speed of the vehicle as a function of time is a straight line:

In that case, the distance travelled is equal to the area under the graph. But from the formula for the area of a triangle we know that this area equals the area of the rectangle with the same base and half the height of the triangle:

This means that the average speed in that case is exactly half of the final (maximum) speed.

But a car has higher acceleration in lower gears, that is, at smaller speeds. Therefore the graph of speed as a function of time is concave, and the area under the graph is greater than in the case of constant acceleration. Hence, while reaching the same speed, the car travels further and its average speed is higher:

We come to the conclusion that the average speed of an accelerating car is greater than half its speed at the end of acceleration."

Note: The text of this solution is reproduced from the appendix to a document prepared for, and submitted to, the Crown Prosecution Service in England. This may partly explain why it contains not a single formula. It was written by a student studying economics, and the mixture of language and graphs used illustrates the typical economist's way of thinking. Economists rarely have complete data, so they tend to rely on a combination of common sense and the basic patterns of economic variables – such as the "convexity" or "concavity" of functions. Indeed some chapters of mathematical economics could be described as outlining "the kinematics of money", and have surprising similarities to mechanics.

88. Suppose sunrise was t hours before noon – so that the first woman covers the total distance in t ` 4 hours, while the second covers the same distance in t ` 9 hours.

We know nothing about the distance from A to B, so it makes sense to choose this distance as our unit.

Then the first woman's speed is 1 t`4 , while the second woman's speed is <sup>1</sup> t`9 units per hour.

The relative speed of A and B (the speed with which the distance between them changes) is 1 t`<sup>4</sup> ` 1 t`9 .

They meet at noon, so in t hours, the distance between them reduces from 1 unit to 0.

Hence

$$1 = t \times \left(\frac{1}{t+4} + \frac{1}{t+9}\right);$$

that is, t 2 " 36, so t " 6, and sunrise was at p12 ´ 6q " 6 am.

89. Let us introduce a new measure of distance – which we call a league. (Readers may know from old documents or from poetry that this was an old measure of distance for journeys, without knowing exactly how far it was; so we feel free to use it as an abstract unit of unknown size.)

To mesh distance and time, the journey from St Louis to New Orleans needs to be some multiple of 7, and the journey from New Orleans to St Louis needs to be some multiple of 5. Hence we choose the distance to be equal to 5 ˆ 7 " 35 "leagues".

Then the speed of the paddle-steamer upstream is:

$$\frac{35}{7} = 5 \text{ \textquotedblleft leagues per day\textquotedblright}$$

and the speed downstream is:

$$\frac{35}{5} = 7 \text{ \textquotedblleft leagues per day\textquotedblright.}$$

The speed of the current gets subtracted from the speed of the paddle-steamer going upstream, and gets added to the speed of the paddle-steamer going downstream; so the speed of the current is:

$$\frac{7-5}{2} = 1 \text{ \textquotedblleft leguse per day\textquotedblright.}$$

Hence a raft will drift from St Louis to New Orleans in 35 1 " 35 days.

Note: This elegant solution involves the introduction of a hidden intermediate parameter, an unknown quantity which helps us reason about the problem. The parameter is apparently the distance (from St Louis to New Orleans); but it is in fact a measure of distance chosen so as to be compatible with the time taken.

The art of identifying, and choosing, relevant "hidden parameters", and the analysis of their relation to the data, and their mutual relations, constitute an important and challenging part of the mathematical modelling process.

Notice that if we reformulate the problem in more general terms, with the paddle-steamer taking "a days" downstream and "b days" upstream, then the answer "d days" (for the time to drift downstream) happens to be the harmonic mean of the quantities "a" and "´b":

$$d = \frac{2}{\frac{1}{a} + \frac{1}{=b}}.$$

90. [This is "Problem 108" in Paolo dell'Abbaco's Trattato d'aritmetica (c.1370), with a rough translation of the solution procedure given there courtesy of Roy Wagner.]

"Do the following: multiply 5 by 8, which makes 40. Then say thus: in 40 days one will make the trip 8 times, and the other 5 times, so both together will make the trip 13 times.

Now say: if 40 days equals 13 trips, how many days are needed [on average] for one trip? And so multiply 1 times 40, which makes 40; then divide this by 13, which makes 3 days and 1 13 of a day.

And so I say that in 3 days and 1 13 of a day the two will come together.

And as this is done, so all similar problems are done."

Note: The problem as stated conveys an air of reality by giving the distance "from here to Florence" in miles; but this fact is not mentioned in the solution! Instead, the solution starts by introducing a hidden parameter, measured by a dimensionless unit: a trip.

This move (to invent a natural unit of measurement) also featured in Problem 89 above and has deep mathematical reasons. Problem 89 was borrowed from an interview with Vladimir Arnold (Notices of the AMS, vol. 44, no. 4), where we read:

Interviewer: Please tell us a little bit about your early education. Were you already interested in mathematics as a child?

Arnold: [. . . ] The first real mathematical experience I had was when our schoolteacher I.V. Morotzkin gave us the following problem [VA then formulated Problem 89].

I spent a whole day thinking on this oldie, and the solution (based on what are now called scaling arguments, dimensional analysis, or toric variety theory, depending on your taste) came as a revelation.

The feeling of discovery that I had then (1949 ) was exactly the same as in all the subsequent much more serious problems – be it the discovery of the relation between algebraic geometry of real plane curves and four-dimensional topology (1970 ), or between singularities of caustics and of wave fronts and simple Lie algebras and Coxeter groups (1972 ). It is the greed to experience such a wonderful feeling more and more times that was, and still is, my main motivation in mathematics.

Arnold refers here to scaling arguments or dimensional analysis: that is, the mathematical art of choosing and analysing the use of units of measurement. This has its origins in, and includes as an integral part, Euclid's classical theory of proportion.

91. Suppose as before that the sun rises t hours before noon; but replace 4 pm (the time the woman starting at A arrived at B) by a pm, and replace 9 pm (the time the woman starting at B arrived at A) by b pm. Let C be the point where they meet (at noon).

Then, since each woman walks at a constant speed, we have

$$\frac{t}{a} = \frac{|AC|}{|CB|} \text{ (for the woman starting from } A\text{)},$$

and

t b " |BC| |CA| (for the woman starting from Bq.

Hence

$$\frac{t}{a} = \frac{|AC|}{|CB|} = \frac{b}{t},$$

so t 2 " ab.

Note: This totally unexpected result validates the choice of the unknown t as the time in hours from sunrise to noon. Not knowing its significance in advance, this choice was motivated by the observation that "noon" occurs in the problem as the only common "origin", or reference point for time data.

The first rule of intelligent tinkering is to save all the parts. Paul R. Ehrlich (1932– )

Many important aspects of serious mathematics have their roots in the world of arithmetic. However, when we implement an arithmetical procedure by combining numbers with very different meanings to produce a single numerical output, it becomes almost impossible to see how the separate ingredients contribute to the final answer. In other words, calculating exclusively with numbers contravenes Paul Ehrlich's "first rule of intelligent tinkering". This is why in Chapters 1 and 2 we stressed the need to move beyond blind calculation, and to begin to think structurally – even when calculating purely with numbers. Algebra can be seen as a remarkable way of "tinkering with numbers", so that we not only "keep all the parts", but manage to keep them separate (by giving them different names), and hence can see clearly what contribution each ingredient variable makes to the final output. To benefit from this feature of algebra, we need to learn to "read" algebraic expressions, and to interpret what they are telling us – in much the same way that we learn to read numbers (so that, where appropriate, 100 is seen as 102 , and 10 is seen as 1 ` 2 ` 3 ` 4).

Before algebra proper was invented (around 1600), the ability to extract the general picture lying hidden inside each calculation was restricted to specialists. The ancient Babylonians (1700–1500 BC) described their general procedures as recipes, presented in the context of problems involving particular numbers. But they did this in such a way as to demonstrate convincingly that whoever formulated the procedure had managed to see "the general in the particular". The ancient Greeks used a geometrical setting to reveal generality, and encoded what we would see as "algebraic" methods in geometrical language. In the 9th century AD, Arabs such as Al-Khwarizmi (c.780–c.850), managed to encapsulate generality using a very limited kind of algebra, without the full symbolical language that would emerge later. The abacists, such as Paolo dell'Abbaco (1282–1374) who featured in Chapter 3, clearly saw that the power and spirit of mathematics was rooted in this generality. But modern algebraic symbolism – in particular, the idea that to express generality we need to use letters to represent not only variables, but also important parameters (such as the coefficients a, b, c in a general quadratic ax2 ` bx ` c) – had to wait for the inscrutable writings of Vi`ete (1540–1603), and especially for Fermat (1601–1665) and Descartes (1596–1650) who simplified and extended Vi`ete's ideas in the 1630s.

Within a generation, the huge potential of this systematic use of symbols was revealed by the triumphs of Newton (1642–1727), Leibniz (1646–1716), and others in the years before 1700. Later, the refinements proposed by Euler (1707–1783) in his many writings throughout the 18th century, made this new language and its discoveries accessible to us all – much as Stevin's (1548–1620) version of place value for numbers made calculation accessible to Everyman.

Our coverage of algebra is necessarily selective. We focus on a few ideas that are needed in what follows, and which should ideally be familiar – but with an emphasis that may be less familiar. When working algebraically, the key mathematical messages are mostly implicit in the manipulations themselves. Hence many of the additional comments in this chapter are to be found as part of the solutions, rather than within the main text.

### 4.1. Simultaneous linear equations and symmetry

Problem 92 Dad took our new baby to the clinic to be weighed. But the baby would not stay still and caused the needle on the scales to wobble. So Dad held the baby still and stood on the scales, while nurse read off their combined weight: 78kg. Then nurse held the baby, while Dad read off their combined weight: 69kg. Finally Dad held the nurse, while the baby read off their combined weight: 137kg. How heavy was the baby? 4

The situation described in Problem 92 is representative of a whole class of problems, where the given information incorporates a certain symmetry, which the solver would be wise to respect. Hence one should hesitate before applying systematic brute force (as when using the information from one weighing to substitute for one of the three unknown weights – a move which effectively reduces the number of unknowns, but which fails to respect the symmetry in the data).

A similar situation arises in certain puzzles like the following.

Problem 93 Numbers are assigned (secretly) to the vertices of a polygon. Each edge of the polygon is then labelled with the sum of the numbers at its two end vertices.

In case any reader is inclined to dismiss such problems as "artificial puzzles", it may help to recall two familiar instances (Problems 94 and 96) which give rise to precisely the above situation.

Problem 94 In the triangle ABC with sides of lengths a (opposite A), b (opposite B), and c (opposite C), we want to locate the three points where the incircle touches the three sides – at point P (on BC), Q (on CA), and R (on AB). To this end, let the two tangents to the incircle from A (namely AQ and AR) have length x, the two tangents from B (namely BP and BR) have length y, and the two tangents from C (namely CP and CQ) have length z. Find the values of x, y, z in terms of a, b, c. 4

The second instance requires us first to review the basic properties of midpoints in terms of vectors.

### Problem 95

"MN is parallel to Y Z and half its length".

(c) Given any quadrilateral ABCD, let P be the midpoint of AB, let Q be the midpoint of BC, let R be the midpoint of CD, and let S be the midpoint of DA. Prove that P QRS is always a parallelogram. 4

### Problem 96

The previous five problems explore a common structural theme – namely the link between certain sums (or averages) and the original, possibly unknown, data. However this algebraic link was in every case embedded in some practical, or geometrical, context. The next few problems have been stripped of any context, leaving us free to focus on the underlying structure in a purely algebraic, or arithmetical, spirit.

Problem 97 Solve the following systems of simultaneous equations.

$$\begin{aligned} \text{(a)} \ (\text{i)} \ x+y=1, \quad y+z=2, \quad x+z=3\\ \text{(ii)} \ uv=2, \quad vw=4, \quad uw=8\\ \text{(b)} \ (\text{i)} \ x+y=2, \quad y+z=3, \quad x+z=4\\ \text{(ii)} \ uv=6, \quad vw=10, \quad uw=15\\ \text{(iii)} \ uv=6, \quad vw=10, \quad uw=30\\ \text{(iv)} \ uw=4, \quad vw=8, \quad uw=16 \end{aligned}$$

Problem 98 Use what you know about solving two simultaneous linear equations in two unknowns to construct the general positive solution to the system of equations:

$$u^a v^b = m, \quad u^c v^d = n.$$

Interpret your result in the language of Cramer's Rule. (Gabriel Cramer (1704–1752)). 4

### Problem 99

(a) For which values b, c does the following system of equations have a unique solution?

$$x + y + z = 3, \quad xy + yz + zx = b, \quad x^2 + y^2 + z^2 = c$$

(b) For which values a, b, c does the following system of equations have a unique solution?

$$x + y + z = a, \quad xy + yz + zx = b, \quad x^2 + y^2 + z^2 = c \qquad \triangle y$$

### 4.2. Inequalities and modulus

The transition from school to university mathematics is in many ways marked by a shift from simple variables, equations and functions, to conditions and analysis involving inequalities and modulus.

Problem 100 What is | ´ x| equal to: x or ´x? (What if x is negative?) 4

### 4.2.1 Geometrical interpretation of modulus, of inequalities, and of modulus inequalities

### Problem 101

(a) Mark on the coordinate line all those points x in the interval r0, 1q which have the digit "1" immediately after the decimal point in their decimal expansion. What fraction of the interval r0, 1q have you marked?

Note: "r0, 1q" denotes the set of all points between 0 and 1, together with 0, but not including 1. r0, 1s denotes the interval including both endpoints; and p0, 1q denotes the interval excluding both endpoints.

Problem 102 Mark on the coordinate line all those points x for which two of the following inequalities are true, and five are false:

$$\forall x > 1, \ x > 2, \ x > 3, \ x > 4, \ x > 5, \ x > 6, \ x > 7. \tag{7.1}$$

Problem 103 Mark on the coordinate line all those points x for which

$$|x - 5| = 3. \tag{7}$$

### Problem 104

(a) Mark on the coordinate line all those points x for which two of the following inequalities are true, and five are false:

$$|x| \succ 1, \ |x| \succ 2, \ |x| \succ 3, \ |x| \succ 4, \ |x| \succ 5, \ |x| \succ 6, \ |x| \succ 7.$$

(b) Mark on the coordinate line all those points x for which two of the following inequalities are true, and five are false:

$$\begin{array}{c} \neg|x-1| > 1, \ |x-2| > 2, \ |x-3| > 3, \ |x-4| > 4, \ |x-5| > 5, \ |x-6| > 6, \ |x-7| > \frac{7}{\Delta} \\\\ \end{array}$$

Problem 105 Mark on the coordinate line all those points x for which

$$|x+1|+|x+2|=2. \tag{\Delta}$$

Problem 106 Find numbers a and b with the property that the set of solutions of the inequality

$$|x - a| < b$$

consists of the interval p´1, 2q. 4

### Problem 107

(a) Mark on the coordinate plane all points px, yq satisfying the inequality

$$|x - y| < 3.$$

(b) Mark on the coordinate plane all points px, yq satisfying the inequality

$$|x - y + 5| < 3.$$

(c) Mark on the coordinate plane all points px, yq satisfying the inequality

$$|x - y| < |x + y|. \tag{7}$$

#### 4.2.2 Inequalities

Problem 108 Suppose real numbers a, b, c, d satisfy a b ă c d .

(i) Prove that

$$\frac{a}{b} < \frac{\left(\frac{a}{b} + \frac{c}{d}\right)}{2} < \frac{c}{d}.$$

(ii) If b, d ą 0, prove that

$$
\frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}.\tag{7}
$$

Problem 109 (Farey series) When the fully cancelled fractions in r0, 1s with denominator ď n are arranged in increasing order, the result is called the Farey series (or Farey sequence) of order n.

$$
\frac{1}{9}, \frac{2}{9}, \frac{3}{9}, \dots, \frac{8}{9}.
$$

Into which of the ten subintervals do they fall?

(ii) Imagine the n points

$$\frac{1}{n+1}, \frac{2}{n+1}, \frac{3}{n+1}, \dots, \frac{n}{n+1}$$

dividing the interval r0, 1s into n ` 1 subintervals of length <sup>1</sup> n`1 . Now insert the n ´ 1 points

$$\frac{1}{n}, \frac{2}{n}, \frac{3}{n}, \dots, \frac{n-1}{n}.$$

Into which of the n ` 1 subintervals do they fall?

	- (i) In the Farey series of order n the first two fractions are 0 1 ă 1 n , and the last two fractions are n´1 n ă 1 1 . Prove that every other adjacent pair of fractions a b ă c d in the Farey series of order n satisfies bd ą n.
	- (ii) Let a b ă c d be adjacent fractions in the Farey series of order n. Prove (by induction on n) that bc ´ ad " 1.

 Students take turns to replace two numbers a, b from the current list by their sum divided by ? 2. Eventually one number is left on the board. Prove that the final number must be less than 2000. 4

### 4.3. Factors, roots, polynomials and surds

### Problem 113

	- (ii) Find another such prime.
	- (ii) Find another such prime.
	- (ii) Find another such prime.
	- (ii) Find another such prime. 4

Problem 114 Factorise x 4 ` 1 as a product of two quadratic polynomials with real coefficients. 4

### 4.3.1 Standard factorisations

The challenge to factorise unfamiliar expressions, may at first leave us floundering. But if we assume that each such problem is solvable with the tools at our disposal, we then have no choice but to fall back on the standard tools we have available (in particular, the standard factorisation of a difference of two squares, in which "cross terms" cancel out). The next problem extends this basic repertoire of standard factorisations.

### Problem 115

	- (ii) Factorise a 4 ´ b 4 as a product of one linear factor and one factor of degree 3, and as a product of two linear factors and one quadratic factor.
	- (ii) Factorise a 5 ` b 5 as a product of one linear factor and one factor of degree 4.
	- (iii) Factorise a 2n`<sup>1</sup> ` b 2n`1 as a product of one linear factor and one factor of degree 2n. 4

Problem 115 develops the ideas that were implicit in Problem 113. The clue lies in Problem 113(a), and in the comment made in the main text in Chapter 1 (after Problem 4 in Chapter 1), which we repeat here:

"The last part [of Problem 113(a)] is included to emphasise a frequently neglected message:

Words and images are part of the way we communicate. But most of us cannot calculate with words and images.

To make use of mathematics, we must routinely translate words into symbols. So "numbers" need to be represented by symbols, and points in a geometric diagram need to be properly labelled before we can begin to calculate, and to reason, effectively."

As soon as one reads the words "one less than a square", one should instinctively translate this into the form "x 2 ´ 1". Bells will then begin to ring; for it is impossible to forget the factorisation

$$x^2 - 1 = (x - 1)(x + 1).$$

And it follows that:

for a number that factorises in this way to be prime, the smaller factor x ´ 1 must be equal to 1;

6 x " 2, so there is only one such prime.

The integer factorisations in Problem 113(c) – namely

$$3^3 - 1 = 2 \times 13, \; 4^3 - 1 = 3 \times 21, \; 5^3 - 1 = 4 \times 31, \; 6^3 - 1 = 5 \times 43, \; \dots$$

may help one to remember (or to discover) the related factorisation

x 3 ´ 1 " px ´ 1qpx 2 ` x ` 1q.

6 For a number that factorises in this way to be prime, the smaller factor "x ´ 1" must be equal to 1;

6 x " 2, so there is only one such prime.

Problem 113 parts (a) and (c) highlight the completely general factorisation (Problem 115(a)(iii)):

$$x^n - 1 = (x - 1)(x^{n-1} + x^{n-2} + \dots + x^2 + x + 1).$$

This family of factorisations also shows that we should think about the factorisation of x 2 ´ 1 as px ´ 1qpx ` 1q, with the uniform factor px ´ 1q first (rather than as px ` 1qpx ´ 1qq. Similarly, the results of Problem 115 show that we should think of the familiar factorisation of a 2 ´ b 2 as pa ´ bqpa ` bq, (not as pa ` bqpa ´ bq, but always with the factor pa ´ bq first).

The integer factorisations in Problem 113(d) – namely

$$3^3 + 1 = 4 \times 7, 4^3 + 1 = 5 \times 13, 5^3 + 1 = 6 \times 21, 6^3 + 1 = 7 \times 31, 7^3 + 1 = 8 \times 43, \dots$$

may help one to remember (or to discover) the related factorisation

$$x^3 + 1 = (x+1)(x^2 - x + 1).$$

6 For such a number to be prime, one of the factors must be equal to 1.

This time one has to be more careful, because the first bracket may not be the "smaller factor" – so there are two cases to consider:

The factorisation for x 3 ` 1 works because "3 is odd", which allows the alternating `{´ signs to end in a "`" as required. Hence Problem 113(d)(iii) highlights the completely general factorisation for odd powers:

$$x^{2n+1} + 1 = (x+1)(x^{2n} - x^{2n-1} + x^{2n-2} - \dots + x^2 - x + 1).$$

You probably know that there is no standard factorisation of x 2 ` 1, or of x <sup>4</sup> ` 1 (but see Problem 114 above).

### Problem 116

(a) Derive a closed formula for the sum of the geometric series

$$1 + r + r^2 + r^3 + \dots + r^n.$$

(The meaning of closed formula was discussed in the Note to the solution to Problem 54(b) in Chapter 2.)

(b) Derive a closed formula for the sum of the geometric series

$$(a+ar+ar^2+ar^3+\cdots+ar^n.\,\qquad\qquad\qquad\Delta$$

We started this subsection by looking for prime numbers of the form x 2 ´ 1. A simple-minded approach to the distribution of prime numbers might look for formulae that generate primes – all the time, or infinitely often, or at least much of the time. In Chapter 1 (Problem 25) you showed that no prime of the form 4k ` 3 can be "represented" as a sum of two squares (i.e. in the form "x <sup>2</sup> ` y 2"), and we remarked that every other prime can be so represented in exactly one way. It is true (but not obvious) that roughly half the primes fall into the second category; so it follows that substituting integers for the two variables in the polynomial x 2 ` y 2 produces a prime number infinitely often.

Problem 117 Experiment suggests, and Goldbach (1690–1764) showed in 1752 that no polynomial in one variable, and with integer coefficients, can give prime values for all integer values of the variable. But Euler (1707–1783) was delighted when he discovered the quadratic

$$f(x) = x^2 + x + 41.$$

Clearly fp0q " 41 is prime. And fp1q " 43 is also prime. What is the first positive integer n for which fpnq is not prime? 4

Problem 117 should be seen as a particular instance of the question as to whether prime numbers can be captured by a polynomial with integer coefficients, and in particular by a quadratic. The next two problems consider the simplest instances of representing prime numbers by expressions involving exponentials (that is, where the variable is in the exponent).

### Problem 118

	- (ii) How many primes are there among the first five such numbers

$$2^2 - 1, \; 2^3 - 1, \; 2^5 - 1, \; 2^7 - 1, \; 2^{11} - 1?$$

	- (ii) In the simplest case, where a " 2, how many primes are there among the first five such numbers

2 1 ` 1, 2 <sup>2</sup> ` 1, 2 4 ` 1, 2 <sup>8</sup> ` 1, 2 16 ` 1? 4

Primes of the form 2p´1 are called Mersenne primes (after Marin Mersenne (1588–1648)). We now know at least fifty such primes (with the exponent p ranging up to around 80 million). Finding new primes is not in itself important, but the search for Mersenne primes has been used as a focus for many new developments in programming, and in number theory.

Primes of the form 2n ` 1 are called Fermat primes (after Pierre de Fermat (1601–1665)). The story here is very different. We now refer to the number 2 <sup>n</sup> ` 1 with n " 2 k as the k th Fermat number fk. You showed in Problem 118 (as Fermat did himself) that f0, f1, f2, f3, f4 are all prime. Fermat then rather rashly claimed that fn is always prime. However, Euler showed (100 years later) that the very next Fermat number f5 fails to be prime. And despite all the power of modern computers, we have still not found another Fermat number that is prime!

### 4.3.2 Quadratic equations

The general solution of quadratic equations dates back to the ancient Babylonians (« 1700 BC). Our modern understanding depends on two facts:

Problem 119 Solve the following quadratic equations:

(a) x 2 ´ 3x ` 2 " 0 (b) x <sup>2</sup> ´ 1 " 0 (c) x <sup>2</sup> ´ 2x ` 1 " 0 (d) x 2 ` ? 2x ´ 1 " 0 (e) x <sup>2</sup> ` x ´ ? 2 " 0 (f) x 2 ` 1 " 0 (g) x <sup>2</sup> ` ? 2x ` 1 " 0 4

### Problem 120 Let

$$p(x) = x^2 + \sqrt{2}x + 1.$$

Find a polynomial qpxq such that the product ppxqqpxq has integer coefficients. 4

### Problem 121

(a) I am thinking of two numbers, and am willing to tell you their sum s and their product p. Express the following procedure algebraically and explain why it will always determine my two unknown numbers.

Halve the sum s, and square the answer. Then subtract the product p and take the square root of the result, to get the answer. Add "the answer" to half the sum and you have one unknown number; subtract "the answer" from half the sum and you have the other unknown number.

(b) I am thinking of the length of one side of a square. All I am willing to tell you are two numbers b and c, where when I add b times the side length to the area I get the answer c. Express the following procedure algebraically and explain why it will always determine the side length of my square.

Take one half of b, square it and add the result to c. Then take the square root. Finally subtract half of b from the result.

	- (i) Prove that the diagonal AC is parallel to the side ED.
	- (ii) If AC and BD meet at X, explain why AXDE is a rhombus.
	- (iii) Prove that triangles ADX and CBX are similar.
	- (iv) If AC has length x, set up an equation and find the exact value of x.

4

Problem 121(a), (b) link to Problem 111(a) (and to Problem 129 below), in relating the roots and the coefficients of a quadratic. If we forget for the moment that the coefficients are usually known, while the roots are unknown, then we see that if α and β are the roots of the quadratic

$$x^2 + bx + c,$$

then

$$(x - \alpha)(x - \beta) = x^2 + bx + c, \quad (x + \alpha)(x - \beta) = 0$$

so

$$
\alpha + \beta = -b \text{ and } \alpha\beta = c.
$$

In other words, the two coefficients b, c are equal to the two simplest symmetric expressions in the two roots α and β. Part (a) of the next problem is meant to suggest that all other symmetric expressions in α and β (that is, any expression that is unchanged if we swap α and β) can then be written in terms of b and c. The full result proving this fact is generally attributed to Isaac Newton (1642–1727). Part (b) suggests that, provided one is willing to allow case distinctions, something similar may be true of anti-symmetric expressions (where the effect of swapping α and β is to multiply the expression by "´1").

Problem 122 Let α and β be the roots of the quadratic equation

$$x^2 + bx + c = 0.$$

	- (ii) Write α 2β ` β 2α in terms of b and c only.
	- (iii) Write α 3 ` β 3 ´ 3αβ in terms of b and c only.
	- (ii) Write α 2β ´ β 2α in terms of b and c only.
	- (iii) Write α 3 ´ β 3 in terms of b and c only. 4

#### Problem 123 (Nested surds, simplification of surds)

(a)(i) For any positive real numbers a, b, prove that

$$
\sqrt{a} + \sqrt{b} = \sqrt{a + b + \sqrt{4ab}}
$$

	- (ii) Simplify a 5 ´ 16 and a 6 ´ 20. 4

Problem 124 (Integer polynomials with a given root) We know that α " 1 is a root of the polynomial equation x 2 ´ 1 " 0; that α " ? 2 is a root of x 2 ´ 2 " 0; and that α " ? 3 is a root of x 2 ´ 3 " 0.

(a) Find a quadratic polynomial with integer coefficients which has

$$\alpha = 1 + \sqrt{2}$$

as a root.

(b) Find a quadratic polynomial with integer coefficients which has

$$\alpha = 1 + \sqrt{3}$$

as a root.

(c) Find a polynomial with integer coefficients which has

$$\alpha = \sqrt{2} + \sqrt{3}$$

as a root. What are the other roots of this polynomial?

(d) Find a polynomial with integer coefficients which has

$$\alpha = \sqrt{2} + \frac{1}{\sqrt{3}}$$

as a root. What are the other roots of this polynomial? 4

#### Problem 125

#### Problem 126 (Polynomial long division) Find

Problem 127 Find the remainder when we divide x 2013 ` 1 by x <sup>2</sup> ` x ` 1. 4

### 4.4. Complex numbers

Up to this point, the chapter and solutions have largely avoided mentioning complex numbers. However, the present chapter would be incomplete were we not to interpret some of the earlier material in terms of complex numbers. Readers who have already met complex numbers will probably still find much in the next two sections that is new. Those for whom complex numbers are as yet unfamiliar should muddle through as best they can, and may then be motivated to learn more in due course.

We already know that the square x 2 of any real number x is ě 0.

And that is where the matter would have rested.

From a modern perspective, we can see that complex numbers are implicit in the formula for the roots of a quadratic equation: complex numbers become explicit as soon as the coefficients of a quadratic ax2 ` bx ` c give rise to a negative discriminant b 2 ´ 4ac ă 0.

But this may not have been quite how complex numbers were discovered. Contrary to oft-repeated myths, complex numbers may not have forced themselves on our attention by someone asking about "solutions to the quadratic equation x 2 " ´1". As long as we inhabit the domain of real numbers, we can be sure that no known number x could possibly have such a square, so we are unlikely to go in search of it.

New ideas in the history of mathematics tend to emerge when a fresh analysis of familiar entities forces us to consider the possible existence of some previously unsuspected universe. In the time from the ancient world up to the fifteenth century, the idea of "number", and of calculation, was restricted to the world of real (usually positive) numbers. In such a world, quadratic equations with non-real solutions simply could not arise.

However, in the Brave New World of the Renaissance, where novelty, exploration, and discovery were part of the Zeitgeist, a general method for solving cubic equations was part of the as-yet-undiscovered "wild west" of mathematics, part of the mathematical New World which invited exploration. Notice that this was not a wildly speculative venture (like trying to solve the meaningless equation "x 2 " ´1"), since a cubic polynomial always has at least one real root. After three thousand years in which little progress had been made, the first half of the sixteenth century witnessed an astonishing burst of progress, resulting in the solution not only of cubic equations, but also of quartic equations. We postpone the details until Section 4.5. All we note here is that,

the general method for solving cubic equations published in 1545, was given as a procedure, illustrated by examples, that showed how to find genuinely real solutions to equations of the third degree having genuinely real (and positive) coefficients.

The procedure clearly worked. And it proceeded as follows:

Construct the real solution x as the sum x " u ` v of two intermediate answers u and v – where the two summands u and v sometimes turned out to be what we would call "conjugate complex numbers", whose imaginary parts cancelled out, leaving a real result for the required root x.

Those who devised the procedure had no desire to leave the real domain: they were focused on a problem in the real domain (a cubic equation with real coefficients, having a real root), and devised a general procedure to find that genuinely real root. But the procedure they discovered led the solver on a journey that sometimes "passed into the complex domain", before returning to the real domain! (See Problem 129.)

Working with complex numbers depends on two skills – one very familiar, and one less so.

• The familiar skill is a willingness to work with a "number" in terms of its properties only, without wishing to evaluate it.

We are thoroughly familiar with this when we work with 2 3 and other fractions: we know that 2 3 " 2ˆ 1 3 ; and all we know about 1 3 is that "whenever we have 3 copies of 1 3 , we can simplify this to 1". Much the same happens when we first learn to work with ? 2, where we carry out such calculations as p1 ` ? 2q <sup>2</sup> " 3 ` 2 ? 2, based only on collecting up like terms and the fact that ? 2 ˆ ? 2 can always be replaced by 2.

	- First, these new solutions come in pairs: if i is one solution of x 2 " ´1 then ´i is another (because p´1q ˆ p´1q " 1 means that p´xq 2 " x 2 for all "numbers" x).
	- Second, the equation x 2 " ´1 has exactly two solutions – one the negative of the other (if x and y are both solutions, then x 2 " y 2 , so x 2 ´ y 2 " px ´ yqpx ` yq " 0, so either x " y, or x " ´y).
	- Third, we have no way of telling these two solutions apart: we know that each is the negative of the other, but there is no way of singling out one of them as "the main one" (as we could when defining the square root of a positive real such as 2). We can call them ˘i, but they are each as good as the other. This important fact is often undermined by referring to one of these roots as ? ´1 (as if it were the dominant partner), and to the other as ´ ? ´1 (as if it were somehow just the "negative" of the main root).

The truth is that "? ´1" is a serious abuse of notation, because there is no way to extend the definition of the function " ? " in the way that this implies: when we try to "take square roots" of negative (or complex) numbers, the output is inescapably "two-valued", so "? " is no longer a function. The two roots of x 2 " ´1 are like Tweedledum and Tweedledee: we know there are two of them, and we know how they are related; but we have no way of distinguishing them, or of singling one of them out.

Once we accept this, we can write complex numbers in the form a ` bi, where a and b are real numbers (just as we used to write numbers in the form a ` b ? 2, where a and b are rational numbers). And we can proceed to add, subtract, multiply, and divide such expressions, and then collect up the "real" and "imaginary" parts to tidy up the answer.

### Problem 128

Problem 129 Divide 10 into two parts, whose product is 40. 4

Problem 129 appears in Chapter XXXVII of Girolamo Cardano's (1501–1576) book Ars Magna (1545). Having previously presented the general methods for solving quadratic, cubic, and quartic equations, he honestly confronts the phenomenon that his method for solving cubic equations (see Problem 135) produces the required real (and positive) solution x as a sum of complex conjugates u and v – involving not only negative numbers, but square roots of negative numbers. After presenting the formal solution of Problem 129, and having shown that the calculation works exactly as it should, he adds the bemused remark:

"So progresses arithmetic subtlety, the end of which . . . is as refined as it is useless."

Arithmetic with complex numbers in the form a`bi is done by carrying out the required operations, and then collecting up the "real" and "imaginary" parts as separate components – just as with adding vectors pa, bq. We treat the two parts as Cartesian coordinates, and so identify the complex number a ` bi with the point pa, bq in the complex plane.

The "Cartesian" representation a ` bi is very convenient for addition. But the essential definition (and significance) of complex numbers is rooted in multiplication. And for multiplication it is often much better to work with complex numbers written in polar form. Suppose we mark the complex number w " a ` bi in the complex plane.

The ? modulus |w| of w (often denoted by r) is the distance r " a 2 ` b <sup>2</sup> of the complex number a ` bi from the origin in the complex plane.

The angle θ, measured anticlockwise from the positive real axis to the line joining the complex number w to the origin, is called the argument, Argpwq " θ, of w.

It is then easy to check that a " r cos θ, b " r sin θ, and that

$$w = r(\cos \theta + i \sin \theta).$$

This is the polar form for w. Instead of focusing on the Cartesian coordinates a, b, the polar form pinpoints w in terms of

### Problem 130

(a) Given two complex numbers in polar form:

w " rpcos θ ` isin θq, z " spcos φ ` isin φq,

show that their product is precisely

wz " rspcospθ ` φq ` isinpθ ` φqq.

(b) (de Moivre's Theorem: Abraham de Moivre (1667–1754)) Prove that

$$(\cos \theta + i \sin \theta)^n = \cos(n\theta) + i \sin(n\theta).$$

(c) Prove that, if

$$z = r(\cos \theta + i \sin \theta)$$

satisfies z n " 1 for some integer n, then r " 1. 4

The last three problems in this subsection look more closely at "roots of unity" – that is, roots of the polynomial equation x n " 1. In the real domain, we know that:

In contrast, in the complex domain, there are n "n th roots of unity". Problem 130(c) shows that these "roots of unity" all lie on the unit circle, centered at the origin. And if we put nθ " 2kπ in Problem 130(b) we see that the n nth roots of unity include the point "1 " cos 0 ` isin 0", and are then equally spaced around that circle with θ " 2kπ n p1 ď k ď n ´ 1q, and form the vertices of a regular n-gon.

### Problem 131

Problem 132 Use Problem 131(d) to factorise x 4 ` 1 as a product of four linear factors, and hence as a product of two quadratic polynomials with real coefficients. 4

### Problem 133

### 4.5. Cubic equations

The first recorded procedure for finding the positive roots of any given quadratic equation dates from around 1700 BC (ancient Babylonian). A corresponding procedure for cubic equations had to wait until the early sixteenth century AD. The story is a slightly complicated one – involving public contests, betrayal, and much else besides.

In Section 4.4 we saw that the cubic equation x 3 " 1 has three solutions – two of which are complex numbers. But in the sixteenth century, even negative numbers were viewed with suspicion, and complex numbers were still unknown. Moreover, symbolical algebra had not yet been invented, so everything was carried out in words: constants were "numbers"; a given multiple of the unknown was referred to as so many "things"; a given multiple of the square of the unknown was simply referred to as "squares"; and so on.

In short, we know that an improved method for sometimes finding a (positive) unknown which satisfied a cubic equation was devised by Scipione del Ferro (1465–1526) around 1515. He kept his method secret until just before his death, when he told his student Antonio del Fiore (1506–??). Niccol`o Tartaglia (1499–1557) then made some independent progress in solving cubic equations. At some stage (around 1535) Fiore challenged Tartaglia to a public "cubic solving contest". In preparing for this event, Tartaglia managed to improve on his method, and he seems to have triumphed in the contest. Tartaglia naturally hesitated to divulge his method in order to preserve his superiority, but was later persuaded to communicate what he knew to Girolamo Cardano (1501–1576) after Cardano promised not to publish it (either never, or not before Tartaglia himself had done so). Cardano improved the method, and his student Ferrari (1522–1565) extended the idea to give a method for solving quartic equations – all of which Cardano then published, contrary to his promise, but with full attribution to the rightful discoverers, in his groundbreaking book Ars Magna (1545 – just two years after Copernicus (1473–1543) published his De revolutionibus . . . ). Problem 134 illustrates the necessary first move in solving any cubic equation. Problem 135 then illustrates the general method in a relatively simple case.

### Problem 134

Problem 135 The equation x 3 ` 3x 2 ´ 4 " 0 clearly has "x " 1" as a positive solution. (The other two solutions are x " ´2, and x " ´2 – a repeated root; however negatives were viewed with suspicion in the sixteenth century, so this root might well have been ignored.) Try to understand how the following sequence of moves "finds the root x " 1":

$$(u+v)^3 = u^3 + 3uv(u+v) + v^3$$

as your cubic equation in y;

The simple method underlying Problem 135 is in fact completely general. Given any cubic equation

$$ax^3 + bx^2 + cx + d = 0 \quad \text{(with } a \neq 0\text{)}$$

we can divide through by a to reduce this to

$$x^3 + px^2 + qx + r = 0$$

with leading coefficient " 1. Then we can substitute y " x ` p 3 and reduce this to a cubic equation in y

$$y^3 - 3\left(\frac{p}{3}\right)^2 y + qy + \left[r + 2\left(\frac{p}{3}\right)^3 - q\left(\frac{p}{3}\right)\right] = 0$$

which we can treat as having the form

$$y^3 - my - n = 0.$$

So we can set y " u ` v (for some unknown u and v yet to be chosen), and treat the last equation as an instance of the identity

$$(u+v)^3 - 3uv(u+v) - (u^3 + v^3) = 0$$

which it will become if we simply choose u and v to solve the simultaneous equations

$$3uv = m, \quad u^3 + v^3 = n.$$

We can then solve these equations to find u, then v – and hence find y " u`v and x " y ´ p 3 .

### 4.6. An extra

Back in Chapter 1, Problem 6 we introduced the Euclidean algorithm for integers. The same idea was extended to polynomials with integer coefficients in Problem 126. In both these settings one starts with a domain (whether the set of integers, or the set of all polynomials with integer coefficients) where there is a notion of divisibility: given two elements m, n in the relevant domain, we say

"n divides m" if there exists an element q in the domain such that m " qn.

The next problem invites you to think how one might extend the Euclidean algorithm to a new domain, namely the Gaussian integers Zris – the set of all complex numbers a ` bi in which the real and imaginary "coordinates" a and b are integers.

Problem 136 Complex numbers a ` bi, where both a and b are integers, are called Gaussian integers. Try to formulate a version of the "division algorithm" for "division with remainder" (where the remainder is always "less than" the divisor in some sense) for pairs of Gaussian integers. Extend this to construct a version of the Euclidean algorithm to find the HCF of two given Gaussian integers. 4

> It is a profoundly erroneous truism . . . that we should cultivate the habit of thinking what we are doing. The precise opposite is the case. Civilisation advances by extending the number of important operations which we can perform without thinking about them.

> > Alfred North Whitehead (1861–1947)

### 4.7. Chapter 4: Comments and solutions

92. Answer: Humour aside, this is a common situation.

We know d ` b, n ` b, d ` n rather than the values of d, b, n.

The key is to exploit the symmetry in the given data, rather than solving blindly. Adding all three two-way totals gives 2pd ` b ` nq " 284, whence d ` b ` n " 142. We can then subtract the given value of d ` n " 137 to get the value of b " 5.

#### 93.

(a) Let the numbers at the three vertices be A, B, C. Adding shows that

$$a + b + c = 2(A + B + C)$$

so

$$A = \frac{a+b+c}{2} - (B+C) = \frac{b+c-a}{2}$$

etc.

(c) Note: We postpone the "solution" of part (b), and address part (c) first. Let the numbers at the five vertices be A, B, C, D, E. Adding shows that

$$d + e + a + b + c = 2(A + B + C + D + E)$$

so

$$\begin{aligned} A &=& \frac{d+e+a+b+c}{2} - (B+C) - (D+E) \\ &=& \frac{d-e+a-b+c}{2} \end{aligned}$$

etc.

(b) The second part is different. The four given edge-values do not determine the four unknown vertex-values. It may look as though four pieces of information should suffice to find four unknowns; but there is a catch: the sum of the numbers on the two opposite edges AB and CD is just the sum of the numbers at the four vertices, and so is equal to the sum of the numbers on the edges BC and DA. Hence one of the given edge-values is determined by the other three.

Note: This distinction between polygons with an odd and an even number of vertices would arise in exactly the same way if each edge was labelled with the average ("half the sum") of the numbers at its two end vertices.

$$\textbf{94.}\ a = BC = BP + PC = y + z; \ b = x + z; \ c = x + y. \ \text{Hence}\ a$$

$$a+b+c=2(x+y+z)$$

so

So

$$x + y + z = \frac{a + b + c}{2}.$$

$$\begin{aligned} x^2 &= \frac{a+b+c}{2} - (y+z)^2\\ &= \frac{b+c-a}{2} \end{aligned}$$

etc.

95.

(a) Let

$$M = \left(\frac{a+c}{2}, \frac{b+d}{2}\right).$$

The shift, or vector, from pa, bq to pc, dq goes

"along c ´ a in the x-direction" and "up d ´ b in the y-direction".

Draw the ordinate through Y and the abscissa through Z, to meet at P, so creating a right angled triangle with legs Y P of length |c ´ a| and P Z of length |d ´ b|. The midpoint of Y P clearly lies halfway along Y P at

$$S = \left(a + \frac{c - a}{2}, b\right)$$

and the midpoint of P Z clearly lies halfway up P Z at

$$T = \left(c, d - \frac{d-b}{2}\right).$$

Then 4Y SM and 4MT Z are both right-angled triangles and are congruent (by RHS congruence). Hence Y M " MZ, so M is the midpoint of Y Z.

(b)

$$M = \left(\frac{a}{2}, \frac{b}{2}\right), \quad N = \left(\frac{c}{2}, \frac{d}{2}\right)$$

so vector

$$\mathbf{MN} = \left(\frac{c-a}{2}, \frac{d-b}{2}\right) = \frac{1}{2}\mathbf{BC}.$$

(c) Note: We use the result from part (b), but not the method from part (b). By part (b) applied to 4BAC, P Q is half the length of AC and parallel to AC. By part (b) applied to 4DAC, SR is half the length of AC and parallel to AC. Hence P Q is parallel to SR.

Similarly one can prove (applying part (b) twice – first to 4ABD, and then to 4CBD) that P S is parallel to QR.

Hence P QRS is a parallelogram.

96.

 $\mathbf{r}(\mathbf{a})$   $\mathbf{p} = \frac{1}{2}(\mathbf{x} + \mathbf{y})$ ,  $\mathbf{q} = \frac{1}{2}(\mathbf{y} + \mathbf{z})$ ,  $\mathbf{r} = \frac{1}{2}(\mathbf{z} + \mathbf{x})$ , so
$$\mathbf{p} + \mathbf{q} + \mathbf{r} = \mathbf{x} + \mathbf{y} + \mathbf{z}$$
.

Hence

$$\begin{array}{rcl} \mathbf{x} & = & (\mathbf{p} + \mathbf{q} + \mathbf{r}) - (\mathbf{y} + \mathbf{z}) = \mathbf{p} - \mathbf{q} + \mathbf{r} \\ \mathbf{y} & = & (\mathbf{p} + \mathbf{q} + \mathbf{r}) - (\mathbf{x} + \mathbf{z}) = \mathbf{p} + \mathbf{q} - \mathbf{r} \\ \mathbf{z} & = & (\mathbf{p} + \mathbf{q} + \mathbf{r}) - (\mathbf{x} + \mathbf{y}) = \mathbf{q} + \mathbf{r} - \mathbf{p}. \end{array}$$

(b)

$$\mathbf{p} = \frac{1}{2}(\mathbf{w} + \mathbf{x}), \ \mathbf{q} = \frac{1}{2}(\mathbf{x} + \mathbf{y}), \ \mathbf{r} = \frac{1}{2}(\mathbf{y} + \mathbf{z}), \ \mathbf{s} = \frac{1}{2}(\mathbf{z} + \mathbf{w})$$

so

$$
\mathbf{p} + \mathbf{q} + \mathbf{r} + \mathbf{s} = \mathbf{w} + \mathbf{x} + \mathbf{y} + \mathbf{z}.
$$

Hence

$$\mathbf{w} = (\mathbf{p} + \mathbf{q} + \mathbf{r} + \mathbf{s}) - (\mathbf{x} + \mathbf{y} + \mathbf{z});$$

but there is no obvious way to pin down px ` y ` zq.

In fact different quadrilaterals may give rise to the same four "midpoints". (It is an interesting exercise to identify the family of quadrilaterals corresponding to a given set of four midpoints.)

97.

(a)(i) As in Problems 93-95 we instinctively add to get

$$2(x+y+z) = 6$$

so

$$x + y + z = 3.$$

Hence

$$\begin{array}{rcl} x & = & 3 - (y + z) = 1 \\ y & = & 3 - (x + z) = 0 \\ z & = & 3 - (x + y) = 2. \end{array}$$

(ii) The same idea (replacing addition by multiplication) leads to

$$2 \times 4 \times 8 = 64 = uv \cdot vw \cdot wu = (uvw)^2$$

so uvw " ˘8. Hence

$$\begin{aligned} u &= \quad \frac{uvw}{vw} = \frac{\pm 8}{4} = \pm 2\\ v &= \quad \frac{uvw}{uw} = \frac{\pm 8}{8} = \pm 1\\ w &= \quad \frac{uvw}{uv} = \frac{\pm 8}{2} = \pm 4. \end{aligned}$$

6 pu, v, wq " p2, 1, 4q or p´2, ´1, ´4q.

Note: Alternatively, we may notice that u, v, w are either all positive, or all negative. If we restrict in the first instance to purely positive solutions, then we may set u " 2 x , v " 2 y , w " 2 z , translate (ii) into (i), and conclude that px, y, zq " p1, 0, 2q, so that pu, v, wq " p2, 1, 4q. We must then remember the negative solution pu, v, wq " p´2, ´1, ´4q.

(b)(i) As in (a)(i) we add to get 2px ` y ` zq " 9, so x ` y ` z " 9 2 . Hence

$$\begin{array}{rcl} x & = & \frac{9}{2} - (y+z) = \frac{3}{2} \\ y & = & \frac{9}{2} - (x+z) = \frac{1}{2} \\ z & = & \frac{9}{2} - (x+y) = \frac{5}{2} \end{array}$$

(ii) The same idea leads to

$$6 \times 10 \times 15 = 900 = uv \cdot vw \cdot wu = \left(uvw\right)^2,$$

so uvw " ˘30. Hence

$$\begin{array}{rcl} u & = & \frac{uvw}{vw} = \frac{\pm 30}{10} = \pm 3\\ v & = & \frac{uvw}{uw} = \frac{\pm 30}{15} = \pm 2\\ w & = & \frac{uvw}{uv} = \frac{\pm 30}{6} = \pm 5. \end{array}$$

Either u, v, w are all positive, or all negative. 6 pu, v, wq " p3, 2, 5q or p´3, ´2, ´5q.

(iii) The same idea leads to

$$6 \times 10 \times 30 = 2 \times 900 = vw \cdot wu = (uvw)^2,$$

so uvw " ˘30? 2. Hence

$$\begin{aligned} u &=& \frac{uvw}{vw} = \frac{\pm 30\sqrt{2}}{10} = \pm 3\sqrt{2} \\ v &=& \frac{uvw}{uw} = \frac{\pm 30\sqrt{2}}{15} = \pm 2\sqrt{2} \\ w &=& \frac{uvw}{uv} = \frac{\pm 30\sqrt{2}}{6} = \pm 5\sqrt{2} .\end{aligned}$$

Either u, v, w are all positive, or all negative. 6 pu, v, wq " p3 ? 2, 2 ? 2, 5 ? 2q or p´3 ? 2, ´2 ? 2, ´5 ? 2q.

(iv) We could of course repeat the same method.

Or we could again look in the first instance for positive solutions, notice that 4 " 2 2 , 8 " 2 3 , 16 " 2 4 , and take logs (to base 2). Then

$$\begin{aligned} \log\_2 u + \log\_2 v &=& 2\\ \log\_2 v + \log\_2 w &=& 3\\ \log\_2 u + \log\_2 w &=& 4, \end{aligned}$$

so (from part (i)) any positive solution satisfies

$$
\log\_2 u = \frac{3}{2}, \; \log\_2 v = \frac{1}{2}, \; \log\_2 w = \frac{5}{2},
$$

so

$$(u,v,w) = (2\sqrt{2}, \sqrt{2}, 4\sqrt{2}).$$

We must then remember to include

$$(u,v,w) = (-2\sqrt{2}, -\sqrt{2}, -4\sqrt{2}).$$

98. The simplest idea is to take logs, and reduce the system to a familiar linear system:

$$\begin{aligned} a \cdot \log u + b \cdot \log v &= \quad \log m \\ c \cdot \log u + d \cdot \log v &= \quad \log n \end{aligned}$$

Multiplying the first equation by c and subtracting it from the second equation multiplied by a gives:

$$
\log v \quad = \quad \frac{a \cdot \log n - c \cdot \log m}{ad - bc}.
$$

Multiplying the first equation by d and subtracting b times the second equation gives:

$$
\log u \quad = \quad \frac{d \cdot \log m - b \cdot \log n}{ad - bc}.
$$

If the numerators and denominators are expressed in determinant form, we get the 2 ˆ 2 version of Cramer's Rule. The original unknowns u, v can then be obtained by taking suitable powers.

What emerges looks interesting:

$$\begin{array}{rcl} u & = & m^{\frac{d}{ad-bc}} \cdot n^{-\frac{b}{ad-bc}}\\ v & = & m^{-\frac{c}{ad-bc}} \cdot n^{\frac{a}{ad-bc}} \end{array}$$

but it is not clear how it generalises.

#### 99.

(a) x`y`z " 3 is the equation of a plane through the three points p3, 0, 0q, p0, 3, 0q, p0, 0, 3q.

x 2 ` y <sup>2</sup> ` z 2 " c is the equation of a sphere, centered at the origin, with radius ? c. The sphere misses the plane completely when c ă 3, meets the plane in a single point when c " 3, and cuts the plane in a circle C when c ą 3 (the circle lying in the positive octant provided c ă 9).

If xy ` yz ` zx " b meets this intersection at all, then any permutation of the three coordinates x, y, z produces another point which also satisfies the other two equations (since they are both symmetrical). Hence for the system to have a unique solution, the circle C must contain a point with x " y " z. Hence c " 3, and b " 3, and the unique solution is

$$(x, y, z) = (1, 1, 1).$$

(b) We must have c ě 0 for any solution. If c " 0, then for a unique solution, we must have x " y " z " 0, so a " b " 0. If we exclude this case, then we may assume that c ą 0.

$$x + y + z = a$$

is the equation of a plane through the three points pa, 0, 0q, p0, a, 0q, p0, 0, aq.

$$x^2 + y^2 + z^2 = c$$

is the equation of a sphere, centre the origin, with radius ? c, which misses the plane completely when c ă a 2 3 , meets the plane in a single point when c " a 2 3 , and cuts the plane in a circle C when c ą a 2 3 (the circle lying in the positive octant provided c ă a 2 ). If

$$xy + yz + zx = b$$

meets this intersection at all, then any permutation of the three coordinates x, y, z produces another point which also satisfies the other two equations (since they are both symmetrical). Hence for the system to have a unique solution, the circle C must contain a point with x " y " z. Hence that point is x " y " z " a 3 , so c " a 2 3 " b, and the unique solution is

$$(x, y, z) = \left(\frac{a}{3}, \frac{a}{3}, \frac{a}{3}\right).$$

100. | ´ x| is never negative. If x ě 0, then | ´ x| " x; if x is negative, then ´x is positive, so | ´ x| " ´x.

Note: We need to learn to see both x and ´x as algebraic entities, with x as a placeholder (which may well be negative, in which case ´x would be positive).

#### 101.

(a) The interval r0.1, 0.2q. We have marked exactly 1 10 of the interval r0, 1q. (b) This needs a little thought. First we mark the interval r0.1, 0.2q, of length 1 10 . Then we mark 9 smaller intervals

r0.01, 0.02q, r0.21, 0.22q, . . . , r0.91, 0.92q

of total length 9 ¨ ` 1 10 ˘2 . Then 92 smaller intervals

$$[0.001, 0.002), \ [0.021, 0.022), \ \dots, \ [0.991, 0.992)$$

of total length 92 ¨ ` 1 10 ˘3 . And so on.

(0.1, 0.2)
$$\begin{aligned} \cup \quad & [0.01, 0.02) \cup [0.21, 0.22) \cup [0.31, 0.32) \cup [0.41, 0.42) \\ & \cup [0.51, 0.52) \cup [0.61, 0.62) \cup [0.71, 0.72) \\ & \cup [0.81, 0.82) \cup [0.91, 0.92) \\ \cup \quad & [0.001, 0.002) \cup [0.021, 0.022) \cup [0.031, 0.032) \cup \cdots \\ \cup \quad & \cdots \end{aligned}$$

It would seem that a vast number of points are left unmarked – namely, every point whose decimal representation uses only 0s, 2s, 3s, 4s, 5s, 6s, 7s, 8s, and 9s. However, the total length of the marked intervals is given by adding:

$$\frac{1}{10} + 9 \cdot \left(\frac{1}{10}\right)^2 + 9^2 \cdot \left(\frac{1}{10}\right)^3 + 9^3 \cdot \left(\frac{1}{10}\right)^4 + 9^4 \cdot \left(\frac{1}{10}\right)^5 + 9^5 \cdot \left(\frac{1}{10}\right)^6 + \dotsb$$

That is an infinite geometric series with first term a " 1 10 and common ratio r " 9 10 , and hence with sum " 1. In other words, the total length of what remains unmarked is zero.

r0.01, 0.02q, r0.21, 0.22q

of total length 2 ¨ ` 1 3 ˘2 . Then 22 smaller intervals

r0.001, 0.002q, r0.021, 0.022q, r0.201, 0.202q, r0.221, 0.222q

of total length 22 ¨ ` 1 3 ˘3 . And so on.

r0.1, 0.2q

Y r0.01, 0.02q Y r0.21, 0.22q Y r0.001, 0.002q Y r0.021, 0.022qq Y r0.201, 0.202q Y r0.2201, 0.02202q Y ¨ ¨ ¨

The set of marked points is the complement of the famous Cantor set (Georg Cantor (1845–1918)) and has total length

$$\frac{1}{3} + 2 \cdot \left(\frac{1}{3}\right)^2 + 2^2 \cdot \left(\frac{1}{3}\right)^3 + 2^3 \cdot \left(\frac{1}{3}\right)^4 + 2^4 \cdot \left(\frac{1}{3}\right)^5 + 2^5 \cdot \left(\frac{1}{3}\right)^6 + \dotsb$$

This is an infinite geometric series with first term a " 1 3 and common ratio r " 2 3 , and so has sum " 1.

Hence, the total length of what remains unmarked is zero.

Note: The set described in (d) leaves as its complement a collection of points – the Cantor set – which consists of the "endpoints" of the intervals that have been removed; these are points whose base 3 expansion involves only 0s and 2s. This complement:

102. (2, 3]. Each inequality implies all the ones before it. Hence the two which are true must be the first two. Hence x ď 3, and x ą 2.

103. If x ´ 5 ě 0, then we must solve x ´ 5 " 3; so x " 8; if x ´ 5 ă 0, we must solve x ´ 5 " ´3, so x " 2.

Note: The fact that |x| denotes the positive value of the pair tx, ´xu can be rephrased as: |x| is equal to the distance from x to 0.

In the same way, |x ´ 5| denotes the positive member of the pair

$$\{x - 5, -(x - 5)\}$$

so |x ´ 5| is equal to the distance from x ´ 5 to 0 (i.e. the distance from x to 5). This is a very important way to think about expressions like |x ´ 5|.

#### 104.

105. ´ 5 2 , ´ 1 2 ( . (We need all points x for which

"the distance from x to ´1" plus "the distance from x to ´2"

equals 2. This excludes all points between ´2 and ´1, for which the sum is equal to 1; for points between ´ 5 2 and ´ 1 2 the sum is ă 2; for points in ` ´8, ´ 5 2 ˘ or ` ´ 1 2 , 8 ˘ the sum is ą 2.)

106. a " 1 2 , b " 3 2 . (For solutions to exist, we must have b ą 0. The solutions of the given inequality then consist of all x such that

"the distance from x to a is less than b"

that is, all x in the interval pa ´ b, a ` bq. Hence a ´ b " ´1, a ` b " 2.)

#### 107.

$$
\left| 1 - \frac{2y}{x+y} \right| < 1.
$$

In other words:

$$0 < \frac{2y}{x+y} < 2.$$

If y ą 0, then x ` y ą 0, so 2x ` 2y ą 2y, whence x ą 0 (so "x ą 0 and y ą 0"). If y ă 0, then x ` y ă 0, so 2x ` 2y ă 2y, whence x ă 0 (so "x ă 0 and y ă 0"). If x ą 0 and y ą 0, or x ă 0 and y ă 0, then clearly |x ´ y| ă |x ` y|.)

108. Let

$$x = \frac{a}{b} < \frac{c}{d} = y.$$

(i) Since x ă y, it follows that

$$x - \frac{x}{2} = \frac{x}{2} < \frac{y}{2},$$

so x ă x`y 2 ; moreover <sup>x</sup> <sup>2</sup> ă y ´ y 2 , so <sup>x</sup>`y 2 ă y. (ii) Since a b ă c d and b, d ą 0, we can multiply both sides by bd to get ad ă bc. Therefore

$$a(b+d) = ab + ad \prec ba + bc = b(a+c),$$

and

$$(a+c)d = ad + cd < bc + dc = (b+d)c.$$

6 a b ă a`c b`d , and a`<sup>c</sup> <sup>b</sup>`d ă c d (since b, d, and b ` d are all ą 0, so we can divide the first inequality by bpb ` dq and the second by dpb ` dq).

#### 109.

(a)

$$\frac{10}{1} < \frac{1}{7} < \frac{1}{6} < \frac{1}{5} < \frac{1}{4} < \frac{2}{7} < \frac{1}{3} < \frac{2}{5} < \frac{3}{7} < \frac{1}{2} < \frac{4}{7} < \frac{3}{5} < \frac{2}{3} < \frac{5}{7} < \frac{3}{4} < \frac{4}{5} < \frac{5}{6} < \frac{6}{7} < \frac{1}{10}$$

(b)(i) It is tempting simply to consider the decimals

$$\frac{1}{9} = 0.111\dots, \frac{2}{9} = 0.222\dots, \frac{3}{9} = 0.333\dots, \dots, \dots, \frac{8}{9} = 0.888\dots$$

in order to conclude that these fractions miss the first and last subinterval, and then fall one in each of the remaining subintervals. In preparation for part (ii), it is better to observe that

$$\frac{1}{9} = \frac{1}{10} + \frac{1}{90}, \frac{2}{9} = \frac{2}{10} + \frac{2}{90}, \frac{3}{9} = \frac{3}{10} + \frac{3}{90}, \dots, \frac{8}{9} = \frac{8}{10} + \frac{8}{90}$$

and notice that

$$
\frac{0}{10} < \frac{1}{90} < \dots < \frac{8}{90} < \frac{1}{10},
$$

so that, for 1 ď m ď 9,

$$
\frac{m}{10} < \frac{m}{9} < \frac{m+1}{10};
$$

hence exactly one 9 th goes in each of the other eight subintervals.

	- ∗ 1 n`<sup>1</sup> ă 1 n and <sup>n</sup>´<sup>1</sup> <sup>n</sup> ă n n`1 , so none of the n ths land up in the first or last subintervals;
	- ∗ then rewrite

$$\frac{1}{n} = \frac{1}{n+1} + \frac{1}{n(n+1)},\\\frac{2}{n} = \frac{2}{n+1} + \frac{2}{n(n+1)},\\\dots,\frac{n-1}{n} = \frac{n-1}{n+1} + \frac{n-1}{n(n+1)}$$

and notice that

$$\frac{0}{n+1} < \frac{1}{n(n+1)} < \dots < \frac{n-1}{n(n+1)} < \frac{1}{n+1},$$

so, for 1 ď m ď n,

$$
\frac{m}{n+1} < \frac{m}{n} < \frac{m+1}{n+1};
$$

hence exactly one n th goes in each of the other n ´ 1 subintervals.

simple objects and "elementary" proofs can sometimes be more intricate than one anticipates.

Note 2: If

$$\frac{a}{b} < \frac{c}{d}$$

are consecutive terms in a Farey series, then "bc ´ ad" must be an integer ą 0. The fact that this difference is always equal to 1 is easily checked in any particular case, but it is unclear exactly why this is necessarily true (rather than an accident) – or even how one would go about proving it. Every treatment of Farey series has to find its own way round this difficulty. We give the simplest proof we can (in the sense that it assumes no more than we have already used: a little about numbers and some algebra). But it is not at all "easy". We indicate a different approach in the "Notes" at the end of part (d).

(i) [The fact that, except for the two end intervals, we have bd ą n will be needed in the proof of part (c)(ii).]

We proceed by mathematical induction on n (the "order" of the Farey series) – a technique which we have already met in Chapter 2 (Problems 54–59, 76) and which will be addressed more fully in Chapter 6.

∗ When n " 1, the Farey series of order n is just:

$$\frac{0}{1} < \frac{1}{1}$$

and this subinterval is both the first and the last, so the claim is "vacuously true" (because there is "nothing to check"). When n " 2, the Farey series of order n is:

$$
\frac{0}{1} < \frac{1}{2} < \frac{1}{1},
$$

and again the only subintervals are the first and the last, so again there is nothing to check.

∗ We now suppose that we know the claim is true for the Farey series of order k, for some k ą 1, and show that it must then also be true for the Farey series of order k ` 1. (Since we know it is true for n " 2, it will then be true for n " 3; and once we know it is true for n " 3, it must then be true for n " 4; and so on.)

To show that the claim is true for the Farey series of order k`1, we consider any adjacent pair of fractions

$$\frac{a}{b} < \frac{c}{d}$$

(other than the first pair and the last pair ) in the Farey series of order k`1.

Claim bd ą k ` 1.

Proof Note first that, since we are avoiding the two end subintervals, both b and d are ą 1.

Suppose first that the pair a b ă c d are not adjacent in the previous Farey series of order k. Then at least one of the two fractions has been inserted in creating the Farey series of order k`1, and so has denominator " k`1. (The fractions inserted are precisely those with denominator "k ` 1" which cannot be reduced by cancelling.) Hence the product

$$bd \geqslant 2(k+1) > k+1.$$

Thus we may assume that the pair a b ă c d were already adjacent in the Farey series of order k. But then by our "induction hypothesis" (namely that the desired result is already known to be true for the Farey series of order k), we know that bd ą k. If bd ą k ` 1, then the pair <sup>a</sup> <sup>b</sup> ă c d satisfies the required condition. Hence we only have to worry about the possibility that bd " k `1. Suppose that bd " k ` 1. Then the interval a b ă c d has length

$$\frac{bc - ad}{bd} = \frac{r}{k+1}$$

for some positive integer r " bc ´ ad.

If r ą 1, then the interval would have length ą 1 k`1 , so a b ă c d would not be successive terms in the series (for we would have inserted some additional term when moving from the Farey series of order k to the Farey series of order k ` 1).

Hence we can be sure that r " 1, that the subinterval a b ă c d has length exactly 1 k`1 . Now successive fractions with denominator k ` 1 differ by exactly 1 k`1 , so some fraction with denominator k+1 must lie in this subinterval. Since no additional fraction is inserted between them in passing from the series of order k to the series of order k`1, a b and c d must both be "cancelled versions" of two successive fractions with denominator k ` 1. But then, by part (b)(ii), there would have to be a fraction with denominator k in the interval a b ă c d – which is not the case.

Therefore the possibility bd " k ` 1 does not in fact occur.

So we can be sure that in every case, bd ą k ` 1.

Hence whenever the result is true for the Farey series of order k, it must then also be true for the Farey series of order k ` 1.

It follows that the result is true for the Farey series of order n, for all n ě 1. QED

Let a b ă c d be adjacent fractions in the Farey series of order k ` 1.

If a b ă c d were already adjacent fractions in the Farey series of order k (i.e. if no fraction has been inserted between a b and c d in passing from the series of order k to the series of order k ` 1), then we already know (by the induction hypothesis) that bc ´ ad " 1.

Thus we may concentrate on the case where a b ă c d are not adjacent fractions in the Farey series of order k. By (b)(iii), at most one fraction with denominator k ` 1 is inserted between any two adjacent fractions in the Farey series of order k, so we have either

$$
\frac{a}{b} < \frac{c}{d} < \frac{e}{f},
$$

with a b ă e f being adjacent fractions in the Farey series of order k (so be ´ af " 1), or

$$
\frac{e}{f} < \frac{a}{b} < \frac{c}{d},
$$

with e f ă c d being adjacent fractions in the Farey series of order k (so fc ´ ed " 1). We consider the first of these possibilities (the second is entirely similar).

Suppose

"

$$
\frac{a}{b} < \frac{c}{d} < \frac{e}{f},
$$

with a b ă e f being adjacent fractions in the Farey series of order k. By part (i) we know that bf ě k ` 1; and by induction we know that be ´ af " 1. Hence the interval <sup>a</sup> <sup>b</sup> ă e f has length at most <sup>1</sup> k`1 . We have to prove that bc ´ ad " 1.

$$\text{Let } bc - ad = r > 0 \text{, and } ed - fc = s > 0.$$

Then sa ` re " c, and sb ` rf " d.

In particular, HCFpr, sq " 1 (since HCFpc, dq " 1).

Hence c d belongs to the family

$$S = \left\{ \frac{xa+ye}{xb+yf} \,:\, \text{where } x, y \text{ are any positive integers with } HCF(x,y) = 1 \right\}.$$

\*

Since everything is positive, easy algebra shows that

$$
\frac{a}{b} < \frac{xa+ye}{xb+yf} < \frac{e}{f},
$$

so every element of S lies between a b and e f .

As long as we choose x, y such that HCFpx, yq " 1, any common factor of xa ` ye and xb ` yf would also divide both

$$(b(xa+ye)-a(xb+yf)=(be-af)y=y,$$

and

$$e(xb+yf) - f(xa+ye) = (be-af)x = x.$$

Hence

$$HCF(xa+ye, xb+yf) = 1$$

so each element of S is in lowest terms (i.e. no further cancelling is possible). We have shown that " c d belongs to the family S", and that all elements of S fit between a b and e f ; which are adjacent fractions in the Farey series of order k. So none of the elements of S can have arisen before the series of order k ` 1. But each fraction in S arises at some stage in a Farey series.

And the first to arise (because it has the smallest denominator) is " a`<sup>e</sup> b`f ". Hence

$$\frac{c}{d} = \frac{a+e}{b+f},$$

so r " s " 1, and bc ´ ad " 1 as required. QED

(d) Let

$$\frac{a}{b} < \frac{c}{d} < \frac{e}{f}$$

be three successive terms in any Farey sequence. By (c) we know that bc´ad " 1, and that de ´ cf " 1. In particular, bc ´ ad " de ´ cf, so

$$\frac{c}{d} = \frac{a+e}{b+f}.$$

Note 1: It may not be clear why we are proving this result "again" – since it appeared in the final line of the solution to part (c). However, in part (c) the statement that

$$\frac{c}{d} - \frac{a+e}{b+f}$$

was arrived at within the induction step, and so was subject to other assumptions. In contrast, now that the result in part (c) has been clearly established, we can use it to prove part (d) without any hidden assumptions.

Note 2: If we represent each fraction a b in the Farey series of order n by the point pb, aq, then each point lies in the right angled triangle joining p0, 0q, pn, 0q, and pn, nq, and each fraction in the Farey series is equal to the gradient of the line, or vector, joining the origin to the integer lattice point pb, aq. The ordering of the fractions in the Farey series corresponds to the sequence of increasing gradients, from 0 1 up to 1 1 . If a b and e f are adjacent fractions in some Farey

$$\text{QED}$$

series, then the result in (d) says that the next fraction to be inserted between them is a`<sup>e</sup> b`f corresponding to the vector sum of pb, aq and pf, eq. And the result in (c) says that the area of the parallelogram with vertices p0, 0q, pb, aq, pf, eq, pb ` f, a ` eq is equal to 1 (see Problem 57(b)). Hence the result in (c) reduces to the fact that

Theorem Any parallelogram, whose vertices are integer lattice points (i.e. points pb, aq where both coordinates are integers), and with no additional lattice points inside the parallelogram or on the four sides, has area 1.

#### 110.

	- (i) If x ą 0, then x 2 ´ x ´ 2 " px ´ 2qpx ` 1q ď 0. 6 ´1 ď x ď 2 (and x ą 0); hence 0 ă x ď 2, and all such x satisfy the original inequality.
	- (ii) If x ă 0, then x 2 ´ x ´ 2 ě 0, so px ´ 2qpx ` 1q ě 0. 6 either x ď ´1, or x ě 2 (and x ă 0); hence x ď ´1, and all such x satisfy the original inequality.

#### 111.

(a) If a ` b " 5 and ab " 7, then a, b are solutions of

$$(x-a)(x-b) = x^2 - 5x + 7 = 0.5$$

But the roots of this quadratic equation are

$$\frac{5 \pm \sqrt{25 - 28}}{2} = \frac{5 \pm \sqrt{-3}}{2},$$

so a and b cannot be "positive reals".

(b) We abbreviate the "arithmetic mean" by AM, the "geometric mean" by GM, the "harmonic mean" by HM, and the "quadratic mean" by QM.

$$\left(\sqrt{a} - \sqrt{b}\right)^2 \gg 0$$

so

$$a + b \geqslant 2\sqrt{ab}$$

therefore

$$
\sqrt{ab} \rhd \frac{2ab}{a+b} \qquad \text{(GM \gg HM)}
$$

and

$$
\sqrt{ab} \lessapprox \frac{a+b}{2} \qquad \text{(GM \lessapprox AM)}.
$$

Also

$$
\left(\frac{a-b}{2}\right)^2 \geqslant 0,
$$

so

$$\frac{a^2 + b^2}{4} \geqslant \frac{2ab}{4}$$

whence

$$\frac{a^2 + b^2}{2} \geqslant \frac{a^2 + b^2 + 2ab}{4} = \left(\frac{a+b}{2}\right)^2.$$

Therefore

$$