Solutions.

304.

Prove that, for any complex numbers z and w,

( |z |+ |w |)

ê
ê

|z |

|w |

ê
ê

£ 2 |z + w | .

Solution 1.

( |z |+ |w |)

ê
ê

|z |

|w |

ê
ê

z + w +

|z |w

|w |

|w |z

|z |

ê
ê

£ |z + w |+

|z ||w |

zw +

zw |

= |z + w |+

|z w |

|z ||w |

| = 2 |z + w | .

Solution 2. Let z = ae^{i a} and w = be^{i b}, with a and b real and positive. Then the left side is equal to

|(a + b)(e^{i a} + e^{i b}) |

= |ae^{i a} + ae^{i b} + be^{i a}+ be^{i b} |

£ |ae^{i a} + be^{i b} |+ |ae^{i b} + be^{i a} | .

Observe that

|z + w |²

= |(ae^{i a} + be^{i b})(ae^{-i a} + be^{-i b}) |

= a² + b² + ab[e^{i (a- b)} + e^{i (b- a)}]

= |(ae^{i b} + be^{i a})(ae^{-i b} + be^{- i a}) |

from which we find that the left side does not exceed

|ae^{i a} + be^{i b} |+ |ae^{i b} + be^{i a} | = 2 |ae^{i a} + be^{i b} | = 2 |z + w | .

Solution 3. Let z = ae^{i a} and w = be^{i b}, where a and b are positive reals. Then the inequality is equivalent to

ê
ê

(e^ia + e^ib)

ê
ê

£ |le^ia + (1 - l)e^{i b} |

where l = a/(a+b). But this simply says that the midpoint of the segment joining e^ia and e^ib on the unit circle in the Argand diagram is at least as close to the origin as another point on the segment.

Solution 4. [G. Goldstein] Observe that, for each m Î C,

ê
ê

|mz |

|mw |

ê
ê

|z |

|w |

ê
ê

|m|[ |z |+ |w |] = |mz + mw | ,

and

|m||z + w | = |mz + mw | .

So the inequality is equivalent to

( |t |+ 1)

ê
ê

|t |

+ 1

ê
ê

£ 2 |t + 1 |

for t Î C. (Take m = 1/w and t = z/w.)

Let t = r(cosq+ i sinq). Then the inequality becomes

(r + 1)

(cosq+ 1)² + sin² q

£ 2

(r cosq+ 1)² + r² sin² q

= 2

r² + 2rcosq+ 1

Now,

4 (r² + 2r cosq+ 1)

- (r + 1)²(2 + 2cosq)

= 2r²(1 - cosq) + 4r(cosq- 1) + 2(1 - cosq)

= 2(r - 1)²(1 - cosq) ³ 0 ,

from which the inequality follows.

Solution 5. [R. Mong] Consider complex numbers as vectors in the plane. q = (|z |/|w |)w is a vector of magnitude z in the direction w and p = (|w |/|z |)z is a vector of magnitude w in the direction z. A reflection about the angle bisector of vectors z and w interchanges p and w, q and z. Hence |p + q | = |w + z |. Therefore

( |z |+ |w |)

ê
ê

|z |

|w |

ê
ê

= |z + q + p + w | £ |z + w |+ |p + q |

= 2 |z + w | .

305.: Suppose that u and v are positive integer divisors of the positive integer n and that uv < n. Is it necessarily so that the greatest common divisor of n/u and n/v exceeds 1?

Solution 1. Let n = ur = vs. Then uv < n Þv < r, u < s, so that n² = uvrs Þ rs > n. Let the greatest common divisor of r and s be g and the least common multiple of r and s be m. Then m £ n < rs = gm, so that g > 1.

Solution 2. Let g = gcd (u, v), u = gs and v = gt. Then gst £ g²st < n so that st < n/g. Now s and t are a coprime pair of integers, each of which divides n/g. Therefore, n/g = dst for some d > 1. Therefore n/u = n/(gs) = dt and n/v = n/(gt) = ds, so that n/u and n/v are divisible by d, and so their greatest common divisor exceeds 1.

Solution 3. uv < n Þnuv < n² Þ n < (n/u)(n/v). Suppose, if possible, that n/u and n/v have greatest common divisor 1. Then the least common multiple of n/u and n/v must equal (n/u)(n/v). But n is a common multiple of n/u and n/v, so that (n/u)(n/v) £ n, a contradiction. Hence the greatest common divisor of n/u and n/v exceeds 1.

Solution 4. Let P be the set of prime divisors of n, and for each p Î P. Let a(p) be the largest integer k for which p^k divides n. Since u and v are divisors of n, the only prime divisors of either u or v must belong to P. Suppose that b(p) is the largest value of the integer k for which p^k divides uv.

If b(p) ³ a(p) for each p Î P, then n would divide uv, contradicting uv < n. (Note that b(p) > a(p) may occur for some p.) Hence there is a prime q Î P for which b(q) < a(q). Then q^a(q) is not a divisor of either u or v, so that q divides both n/u and n/v. Thus, the greatest common divisor of n/u and n/v exceeds 1.

Solution 5. [D. Shirokoff] If n/u and n/v be coprime, then there are integers x and y for which (n/u)x + (n/v) = 1, whence n(xv + yu) = uv. Since n and uv are positive, then so is the integer xv + yu. But uv < nÞ 0 < xv + yu < 1, an impossibility. Hence the greatest common divisor of n/u and n/v exceeds 1.

306.: The circumferences of three circles of radius r meet in a common point O. They meet also, pairwise, in the points P, Q and R. Determine the maximum and minimum values of the circumradius of triangle PQR.

Answer. The circumradius always has the value r.

Solution 1. [M. Lipnowski] ÐQPO = ÐQRO, since OQ is a common chord of two congruent circles, and so subtends equal angles at the respective circumferences. (Why are angle QPO and QRO not supplementary?) Similarly, ÐOPR = ÐOQR. Let P¢ be the reflected image of P in the line QR so that triangle P¢QR and PQR are congruent. Then

ÐQP¢R + ÐQOR

= ÐQPR + ÐQOR = ÐQPO + ÐRPO + ÐQOR

= ÐQRO + ÐOQR + ÐQOR = 180^° .

Hence P¢ lies on the circle through OQR, and this circle has radius r. Hence the circumradius of PQR equals the circumradius of P¢QR, namely r.

Solution 2. [P. Shi; A. Wice] Let U, V, W be the centres of the circle. Then OVPW is a rhombus, so that OP and VW intersect at right angles. Let H, J, K be the respective intersections of the pairs (OP, VW), (OQ, UW), (OP, UV). Then H (respectively J, K) is the midpoint of OP and VW (respectively OQ and UW, OP and UV). Triangle PQR is carried by a dilation with centre O and factor ¹/₂ onto HJK. Also, HJK is similar with factor ¹/₂ to triangle UVW (determined by the midlines of the latter triangle). Hence triangles PQR and UVW are congruent. But the circumcircle of triangle UVW has centre O and radius r, so the circumradius of triangle PQR is also r.

Solution 3. [G. Zheng] Let U, V, W be the respective centres of the circumcircles of OQR, ORP, OPQ. Place O at the centre of coordinates so that

U ~ (r cosa, r sina)

V ~ (r cosb, r sinb)

W ~ (r cosg, r sing)

for some a, b, g. Since OVPW is a rhombus,

P ~ (r (cosb+ cosg), r (sinb+ sing)) .

Similarly, Q ~ ( r (cosa+ cosg),r (sina+ sing), so that

|PQ | = r

(cosb- cosa)²+ (sinb- sina)²

= |UV | .

Similarly, |PR | = |UW | and |QR | = |VW |. Thus, triangles PQR and UVW are congruent. Since O is the circumcentre of triangle UVW, the circumradius of triangle PQR equals the circumradius of triangle UVW which equals r.

Solution 4. Let U, V, W be the respective centres of the circles QOR, ROP, POQ. Suppose that ÐOVR = 2b; then ÐOPR = b. Suppose that ÐOWQ = 2g; then ÐOPQ = g. Hence ÐQPR = b+ g. Let r be the circumradius of triangle PQR. Then |QR | = 2rsin(b+ g).

Consider triangle QUR. The reflection in the axis OQ takes W to U so that ÐQUO = ÐQWO = 2g. Similarly, ÐRUO = 2g, whence ÐQUR = 2(b+ g). Thus triangle QUR is isosceles with |QU | = |QR | = r and apex angle QUR equal to 2 (b+ g). Hence |QR | = 2rsin(b+ g). It follows that r = r.

Comment. This problem was the basis of the logo for the 40th International Mathematical Olympiad held in 1999 in Romania.

307.

Let p be a prime and m a positive integer for which m < p and the greatest common divisor of m and p is equal to 1. Suppose that the decimal expansion of m/p has period 2k for some positive integer k, so that

= .ABABABAB ... = (10^k A + B)(10^-2k +10^-4k + ¼)

where A and B are two distinct blocks of k digits. Prove that

A + B = 10^k - 1 .

(For example, 3/7 = 0.428571 ... and 428 + 571 = 999.)

Solution. We have that

10^kA + B

10^2k - 1

10^kA + B

(10^k - 1)(10^k + 1)

whence

m(10^k - 1)(10^k + 1) = p(10^k A + B) = p(10^k - 1)A + p(A + B) .

Since the period of m/p is 2k, A ¹ B and p does not divide 10^k - 1. Hence 10^k - 1 and p are coprime and so 10^k - 1 must divide A + B. However, A £ 10^k - 1 and B £ 10^k - 1 (since both A and B have k digits), and equality can occur at most once. Hence A + B < 2 ×10^k - 2 = 2(10^k - 1). It follows that A + B = 10^k - 1 as desired.

Comment. This problem appeared in the College Mathematics Journal 35 (2004), 26-30. In writing up the solution, it is clearer to set up the equation and clear fractions, so that you can argue in terms of factors of products.

308.

Let a be a parameter. Define the sequence { f_n (x) : n = 0, 1, 2, ¼} of polynomials by

f₀ (x) º 1

f_n+1 (x) = x f_n (x) + f_n (ax)

for n ³ 0.

(a) Prove that, for all n, x,

f_n (x) = xⁿ f_n (1/x) .

: (b) Determine a formula for the coefficient of x^k (0 £ k £ n) in f_n (x).

Solution 1. The polynomial f_n (x) has degree n for each n, and we will write

f_n (x) =

n
å
k=0

b(n, k) x^k .

Then

xⁿ f_n (1/x) =

n
å
k=0

b(n, k)x^n-k =

n
å
k=0

b(n, n - k)x^k .

Thus, (a) is equivalent to b(n, k) = b(n,n - k) for 0 £ k £ n.

When a = 1, it can be established by induction that f_n (x) = (x + 1)ⁿ = å_k=0ⁿ (n || k) xⁿ. Also, when a = 0, f_n (x) = xⁿ + x^n-1 + ¼+ x + 1 = (xⁿ⁺¹ - 1)(x - 1)^-1. Thus, (a) holds in these cases and b(n, k) is respectively equal to (n || k) and 1.

Suppose, henceforth, that a ¹ 1. For n ³ 0,

f_n+1(k)

n
å
k=0

b(n, k)x^k+1 +

n
å
k=0

a^k b(n, k)x^k

n
å
k=1

b(n, k-1) x^k + b(n, n)xⁿ⁺¹ + b(n, 0)+

n
å
k=1

a^k b(n, k) x^k

= b(n, 0) +

n
å
k=1

[b(n, k-1) + a^k b(n, k)]x^k+ b(n, n)xⁿ⁺¹ ,

whence b(n + 1, 0) = b(n, 0) = b(1, 0) and b(n + 1, n + 1) = b(n, n) = b(1, 1) for all n ³ 1. Since f₁ (x) = x + 1, b(n, 0) = b(n, n) = 1 for each n. Also

b(n + 1, k) = b(n, k-1) + a^k b(n, k)

(1)

for 1 £ k £ n.

We conjecture what the coefficients b(n, k) are from an examination of the first few terms of the sequence:

f₀(x) = 1; f₁(x) = 1 + x; f₂(x) = 1 + (a + 1)x + x²;

f₃(x) = 1 + (a² + a + 1)x + (a² + a + 1)x² + x³;

f₄(x) = 1 + (a³ + a² + a + 1)x + (a⁴ + a³ + 2a² + a + 1)x²+ (a³ + a² + a + 1)x³ + x⁴;

f₅(x) = (1 + x⁵) + (a⁴ + a³ + a² + a + 1)(x + x⁴)+ (a⁶ + a⁵ + 2a⁴ + 2a³ + 2a² + a + 1)(x² + x³) .

We make the empirical observation that

b(n + 1, k) = a^n+1-kb(n, k-1) + b(n, k)

(2)

which, with (1), yields

(a^n+1-k - 1)b(n, k-1) = (a^k - 1)b(n, k)

so that

b(n+1, k) =

é
ë

a^k - 1

a^n+1-k - 1

+ a^k

ù
û

b(n, k) =

é
ë

aⁿ⁺¹ - 1

a^n+1-k - 1

ù
û

b(n, k)

for n ³ k. This leads to the conjecture that

b(n, k) =

æ
è

(aⁿ - 1)(a^n-1 - 1) ¼(a^k+1 - 1)

(a^n-k - 1)(a^n-k-1 - 1) ¼(a - 1)

ö
ø

b(k, k)

(3)

where b(k, k) = 1.

We establish this conjecture. Let c(n, k) be the right side of (3) for 1 £ k £ n-1 and c(n, n) = 1. Then c(n, 0) = b(n, 0) = c(n, n) = b(n, n) = 1 for each n. In particular, c(n, k) = b(n, k) when n = 1.

We show that

c(n + 1, k) = c(n, k-1) + a^k c(n, k)

for 1 £ k £ n, which will, through an induction argument, imply that b(n, k) = c(n, k) for 0 £ k £ n. The right side is equal to

æ
è

aⁿ - 1

a^n-k - 1

ö
ø

æ
è

a^k+1 - 1

a - 1

ö
ø

é
ë

a^k - 1

a^n-k+1 - 1

+ a^k

ù
û

(aⁿ⁺¹ - 1)(aⁿ - 1) ¼(a^k+1 - 1)

(a^n+1-k - 1)(a^n-k - 1) ¼(a - 1)

= c(n+1, k)

as desired. Thus, we now have a formula for b(n, k) as required in (b).

Finally, (a) can be established in a straightforward way, either from the formula (3) or using the pair of recursions (1) and (2).

Solution 2. (a) Observe that f₀ (x) = 1, f₁ (x) = x + 1 and f₁ (x) - f₀ (x) = x = a⁰ x f₀ (x/a). Assume as an induction hypothesis that f_k (x) = x^k f(1/x) and

f_k (x) - f_k-1 (x) = a^k-1 x f_k-1(x/a)

for 0 £ k £ n. This holds for k = 1.

Then

f_n+1 (x) - f_n (x)

= x[f_n(x) - f_(n-1)(x)] + [f_n(ax) - f_n-1(ax)]

= a^n-1x² f_n-1(x/a) + a^n-1axf_n-1(x)

= aⁿx [f_n-1(x) + (x/a)f_n-1(x/a) = aⁿ x f_n(x/a) ,

whence

f_n+1(x)

= f_n (x) + aⁿ x f_n(x/a) = f_n(x) + aⁿ x(x/a)ⁿf_n(a/x)

= xⁿ f_n(1/x) + xⁿ⁺¹ f_n (a/x) = xⁿ⁺¹ [(1/x)f_n(1/x) + f_n(a/x)] = xⁿ⁺¹f_n+1(1/x) .

The desired result follows.

Comment. Because of the appearance of the factor a - 1 in denominators, you should dispose of the case a = 1 separately. Failure to do so on a competition would likely cost a mark.

309.: Let ABCD be a convex quadrilateral for which all sides and diagonals have rational length and AC and BD intersect at P. Prove that AP, BP, CP, DP all have rational length.

Solution 1. Because of the symmetry, it is enough to show that the length of AP is rational. The rationality of the lengths of the remaining segments can be shown similarly. Coordinatize the situation by taking A ~ (0, 0), B ~ (p, q), C ~ (c, 0), D ~ (r, s) and P ~ (u, 0). Then, equating slopes, we find that

r - u

s - q

r - p

so that

sr - ps

s - q

= r - u

whence u = r - [(sr - ps)/(s - q)] = [(ps - qr)/(s - q)].

Note that |AB |² = p² + q², |AC |² = c², |BC |² = (p² - 2pc + c²)+ q², |CD |² = (c² - 2cr + r²) + s² and |AD |² = r² + s², we have that

2rc = AC² + AD² - CD²

so that, since c is rational, r is rational. Hence s² is rational.

Similarly

2pc = AC² + AB² - BC² .

Thus, p is rational, so that q² is rational.

2qs = q² + s² - (q - s)² = q² + s² - [(p - r)² + (q - s)²] + p² - 2pr + r²

is rational, so that both qs and q/s = (qs)/s² are rational. Hence

u =

p - r(q/s)

1 - (q/s)

is rational.

Solution 2. By the cosine law, the cosines of all of the angles of the triangle ACD, BCD, ABC and ABD are rational. Now

sinÐABP

sinÐAPB

and

sinÐPBC

sinÐBPC

Since ÐAPB + ÐBPC = 180^°, therefore sinÐAPB = sinÐBPC and

AB sinÐABP

BC sinÐPBC

AB sinÐABP sinÐPBC

BC sin² ÐPBC

AB (cosÐABP cosÐPBC - cos(ÐABP + ÐPBC))

BC (1 - cos² ÐPBC)

AB (cosÐABD cosÐDBC - cosÐABC)

BC (1 - cos² ÐDBC)

is rational. Also AP + CP is rational, so that (AP/CP)(AP + CP) = ((AP/CP) + 1)AP is rational. Hence AP is rational.

310.

(a) Suppose that n is a positive integer. Prove that

(x + y)ⁿ =

n
å
k=0

æ
è

n
k

ö
ø

x (x + k)^k-1 (y - k)^n-k .

(b) Prove that

(x + y)ⁿ =

n
å
k=0

æ
è

n
k

ö
ø

x (x - kz)^k-1 (y + kz)^n-k .

Comments. (a) and (b) are equivalent. To obtain (b) from (a), replace x by -x/z and y by -y/z. On the other hand, the substitution z = -1 yields (a) from (b).

The establishment of the identities involves the recognition of a certain sum which arise in the theory of finite differences. Let f(x) be a function of x and define the following operators that take functions to functions:

If(x) = f(x)

Ef(x) = f(x + 1) = (I + D)f(x)

Df(x) = f(x + 1) - f(x) = (E - I)f(x) .

For any operator P, Pⁿf(x) is defined recursively by P⁰ f(x) = f(x) and P^k+1f(x) = P(P^k-1) f(x)), for k ³ 1. Thus E^kf(x) = f(x + k) and

D² f(x) = Df(x + 1) - Df(x) = f(x + 2) - 2f(x + 1) + f(x) = (E² - 2E + I)f(x) = (E - I)²f(x) .

We have an operational calculus in which we can treat polynomials in I, E and D as satisfying the regular rules of algebra. In particular

Eⁿ f(x) = (I + D)ⁿ f(x) =

æ
è

n
k

ö
ø

D^k f(x)

and

Dⁿ f(x) = (E - I)ⁿ f(x) =

n
å
k = 0

(-1)^n-k

æ
è

n
k

ö
ø

E^k f(x) =

n
å
k = 0

(-1)^n-k

æ
è

n
k

ö
ø

f(x + k) ,

for each positive integer n, facts than can be verified directly by unpacking the operational notation.

Now let f(x) be a polynomial of degree d ³ 0. If f(x) is constant (d = 0), then Df(x) = 0. If d ³ 1, then Df(x) is a polynomial of degree d - 1. It follows that D^d f(x) is constant, and Dⁿ f(x) = 0 whenever n > d. This yields the identity

n
å
k=0

(-1)^k

æ
è

n
k

ö
ø

f(x + k) = 0

for all x whenever f(x) is a polynomial of degree strictly less than n.

Solution 1. [G. Zheng]

n
å
k=0

æ
è

n
k

ö
ø

x(x + k)^k-1 (y - k)^n-k =

n
å
k=0

æ
è

n
k

ö
ø

x(x + k)^k-1 [(x + y) - (x + k)]^n-k

n
å
k=0

n-k
å
j=0

æ
è

n
k

ö
ø

x(x + k)^k-1

æ
è

n-k
j

ö
ø

(x + y)^j (-1)^n-k-j(x + k)^n-k-j

å
0 £ k £ n - j £ n

(-1)^n-k-j

æ
è

n
k

ö
ø

æ
è

n-k
j

ö
ø

x (x + k)^n-j-1(x + y)^j

n
å
j=0

n-j
å
k = 0

(-1)^n-k-j

æ
è

n
j

ö
ø

æ
è

n-j
k

ö
ø

x(x + k)^n-j-1 (x + y)^j

n
å
j=0

(-1)^n-j

æ
è

n
j

ö
ø

(x + y)^j

n-j
å
k=0

(-1)^k

æ
è

n-j
k

ö
ø

x(x + k)^n-j-1

= (x + y)ⁿ x(x + 0)^-1 + x

n-1
å
j=1

(-1)^n-j

æ
è

n
j

ö
ø

(x + y)^j

n-j
å
k=0

(-1)^k

æ
è

n-j
k

ö
ø

(x + k)^n-j-1 .

Let m = n - j so that 1 £ m £ n. Then

n-j
å
k=0

(-1)^k

æ
è

n-j
k

ö
ø

(x + k)^n-j-1

m
å
k=0

(-1)^k

æ
è

m
k

ö
ø

(x + k)^m-1

m
å
k=0

(-1)^k

æ
è

m
k

ö
ø

m-1
å
l=0

æ
è

m-1
l

ö
ø

x^m-lk^l

m-1
å
l=0

æ
è

m-1
l

ö
ø

x^m-l

m
å
k=0

(-1)^k

æ
è

m
k

ö
ø

k^l = 0 .

The desired result now follows.

Solution 2. [M. Lipnowski] We prove that

n
å
k=0

æ
è

n
k

ö
ø

x (x - kz)^k-1 (y + kz)^n-k = (x + y)ⁿ

by induction. When n = 1, this becomes

1 ·x(x)^-1y + 1 ·x(x - z)⁰(y+z)⁰ = y + x = x + y .

Assume that for n ³ 2,

n-1
å
k=0

æ
è

n-1
k

ö
ø

x(x - kz)^k-1(y + zk)^n-k-1 = (x + y)^n-1 .

Let f(y) = (x + y)ⁿ and g(y) = å_k=0ⁿ (n || k)x(x - kz)^k-1 (y + kz)^n-k. We can establish that f(y) = g(y) for all y by showing that f¢(y) = g¢(y) for all y (equality of the derivatives with respect to y) and f(-x) = g(-x) (equality when y is replaced by -x).

That f¢(y) = g¢(y) is a consequence of the induction hypothesis and the identity (n || k)(n - k) = n ((n-1) || k). Also

g(-x)

n
å
k=0

æ
è

n
k

ö
ø

x (x - kz)^k-1(-x + kz)^n-k

= x

n
å
k=0

(-1)^n-k

æ
è

n
k

ö
ø

(x - kz)^n-1 = 0 ,

by appealing to the finite differences result. The desired result now follows.