CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location: 
       

Solutions.



304.
Prove that, for any complex numbers z and w,
( |z |+ |w |)
 z

|z |
+  w

|w |

2 |z + w | .
Solution 1.
( |z |+ |w |)

 z

|z |
+  w

|w |

=
z + w +  |z |w

|w |
+  |w |z

|z |

|z + w |+  1

|z ||w |
|
-
z
 
zw +
-
w
 
zw |
= |z + w |+  |z w |

|z ||w |
|
-
z
 
+
-
w
 
| = 2 |z + w | .

Solution 2. Let z = aei a and w = bei b, with a and b real and positive. Then the left side is equal to

|(a + b)(ei a + ei b) |
= |aei a + aei b + bei a+ bei b |
|aei a + bei b |+ |aei b + bei a | .

Observe that

|z + w |2
= |(aei a + bei b)(ae-i a + be-i b) |
= a2 + b2 + ab[ei (a- b) + ei (b- a)]
= |(aei b + bei a)(ae-i b + be- i a) |
from which we find that the left side does not exceed
|aei a + bei b |+ |aei b + bei a | = 2 |aei a + bei b | = 2 |z + w | .

Solution 3. Let z = aei a and w = bei b, where a and b are positive reals. Then the inequality is equivalent to


 1

2
(eia + eib)
|leia + (1 - l)ei b |
where l = a/(a+b). But this simply says that the midpoint of the segment joining eia and eib 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

|mz |
+  mw

|mw |

=
 z

|z |
+  w

|w |

 ,

|m|[ |z |+ |w |] = |mz + mw | ,
and
|m||z + w | = |mz + mw | .
So the inequality is equivalent to
( |t |+ 1)
 t

|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)2 + sin2 q
 
2

 

(r cosq+ 1)2 + r2 sin2 q
 
= 2

 

r2 + 2rcosq+ 1
 
 .
Now,
4 (r2 + 2r cosq+ 1)
- (r + 1)2(2 + 2cosq)
= 2r2(1 - cosq) + 4r(cosq- 1) + 2(1 - cosq)
= 2(r - 1)2(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

|z |
+   w

|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 n2 = 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 g2st < 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 < n2 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 pk 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 pk 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 qa(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 PQR and PQR are congruent. Then

QPR + 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 PQR, 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 1/2 onto HJK. Also, HJK is similar with factor 1/2 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)2+ (sinb- sina)2
 
= |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
 m

p
= .ABABABAB ... = (10k A + B)(10-2k +10-4k + )
where A and B are two distinct blocks of k digits. Prove that
A + B = 10k - 1 .
(For example, 3/7 = 0.428571 ... and 428 + 571 = 999.)
Solution. We have that
 m

p
=  10kA + B

102k - 1
=  10kA + B

(10k - 1)(10k + 1)
whence
m(10k - 1)(10k + 1) = p(10k A + B) = p(10k - 1)A + p(A + B) .
Since the period of m/p is 2k, A B and p does not divide 10k - 1. Hence 10k - 1 and p are coprime and so 10k - 1 must divide A + B. However, A 10k - 1 and B 10k - 1 (since both A and B have k digits), and equality can occur at most once. Hence A + B < 2 ×10k - 2 = 2(10k - 1). It follows that A + B = 10k - 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 { fn (x) : n = 0, 1, 2, } of polynomials by
f0 (x) 1

fn+1 (x) = x fn (x) + fn (ax)
for n 0.
(a) Prove that, for all n, x,
fn (x) = xn fn (1/x) .
(b) Determine a formula for the coefficient of xk (0 k n) in fn (x).
Solution 1. The polynomial fn (x) has degree n for each n, and we will write
fn (x) = n

k=0 
b(n, k) xk .
Then
xn fn (1/x) = n

k=0 
b(n, k)xn-k = n

k=0 
b(n, n - k)xk .
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 fn (x) = (x + 1)n = k=0n (n || k) xn. Also, when a = 0, fn (x) = xn + xn-1 + + x + 1 = (xn+1 - 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,

fn+1(k)
= n

k=0 
b(n, k)xk+1 + n

k=0 
ak b(n, k)xk
= n

k=1 
b(n, k-1) xk + b(n, n)xn+1 + b(n, 0)+ n

k=1 
ak b(n, k) xk
= b(n, 0) + n

k=1 
[b(n, k-1) + ak b(n, k)]xk+ b(n, n)xn+1 ,
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 f1 (x) = x + 1, b(n, 0) = b(n, n) = 1 for each n. Also
b(n + 1, k) = b(n, k-1) + ak 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:

f0(x) = 1;     f1(x) = 1 + x;     f2(x) = 1 + (a + 1)x + x2;

f3(x) = 1 + (a2 + a + 1)x + (a2 + a + 1)x2 + x3;

f4(x) = 1 + (a3 + a2 + a + 1)x + (a4 + a3 + 2a2 + a + 1)x2+ (a3 + a2 + a + 1)x3 + x4;

f5(x) = (1 + x5) + (a4 + a3 + a2 + a + 1)(x + x4)+ (a6 + a5 + 2a4 + 2a3 + 2a2 + a + 1)(x2 + x3) .
We make the empirical observation that
b(n + 1, k) = an+1-kb(n, k-1) + b(n, k)
(2)
which, with (1), yields
(an+1-k - 1)b(n, k-1) = (ak - 1)b(n, k)
so that
b(n+1, k) =
 ak - 1

an+1-k - 1
+ ak
b(n, k) =
 an+1 - 1

an+1-k - 1

b(n, k)
for n k. This leads to the conjecture that
b(n, k) =
 (an - 1)(an-1 - 1) (ak+1 - 1)

(an-k - 1)(an-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) + ak 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

 an - 1

an-k - 1


 ak+1 - 1

a - 1


 ak - 1

an-k+1 - 1
+ ak
=  (an+1 - 1)(an - 1) (ak+1 - 1)

(an+1-k - 1)(an-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 f0 (x) = 1, f1 (x) = x + 1 and f1 (x) - f0 (x) = x = a0 x f0 (x/a). Assume as an induction hypothesis that fk (x) = xk f(1/x) and

fk (x) - fk-1 (x) = ak-1 x fk-1(x/a)
for 0 k n. This holds for k = 1.

Then

fn+1 (x) - fn (x)
= x[fn(x) - f(n-1)(x)] + [fn(ax) - fn-1(ax)]
= an-1x2 fn-1(x/a) + an-1axfn-1(x)
= anx [fn-1(x) + (x/a)fn-1(x/a) = an x fn(x/a) ,
whence
fn+1(x)
= fn (x) + an x fn(x/a) = fn(x) + an x(x/a)nfn(a/x)
= xn fn(1/x) + xn+1 fn (a/x) = xn+1 [(1/x)fn(1/x) + fn(a/x)] = xn+1fn+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
 s

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 |2 = p2 + q2, |AC |2 = c2, |BC |2 = (p2 - 2pc + c2)+ q2, |CD |2 = (c2 - 2cr + r2) + s2 and |AD |2 = r2 + s2, we have that

2rc = AC2 + AD2 - CD2
so that, since c is rational, r is rational. Hence s2 is rational.

Similarly

2pc = AC2 + AB2 - BC2 .
Thus, p is rational, so that q2 is rational.


2qs = q2 + s2 - (q - s)2 = q2 + s2 - [(p - r)2 + (q - s)2] + p2 - 2pr + r2
is rational, so that both qs and q/s = (qs)/s2 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

 AP

AB
=  sinABP

sinAPB
and
 CP

BC
=  sinPBC

sinBPC
 .
Since APB + BPC = 180, therefore sinAPB = sinBPC and
 AP

CP
=  AB sinABP

BC sinPBC
=  AB sinABP sinPBC

BC sin2 PBC
=  AB (cosABP cosPBC - cos(ABP + PBC))

BC (1 - cos2 PBC)
=  AB (cosABD cosDBC - cosABC)

BC (1 - cos2 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 = n

k=0 

n
k

x (x + k)k-1 (y - k)n-k .
(b) Prove that
(x + y)n = 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, Pnf(x) is defined recursively by P0 f(x) = f(x) and Pk+1f(x) = P(Pk-1) f(x)), for k 1. Thus Ekf(x) = f(x + k) and
D2 f(x) = Df(x + 1) - Df(x) = f(x + 2) - 2f(x + 1) + f(x) = (E2 - 2E + I)f(x) = (E - I)2f(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
En f(x) = (I + D)n f(x) =

n
k

Dk f(x)
and
Dn f(x) = (E - I)n f(x) = n

k = 0 
(-1)n-k
n
k

Ek 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 Dd f(x) is constant, and Dn 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)n 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

xm-lkl
= m-1

l=0 

m-1
l

xm-l m

k=0 
(-1)k
m
k

kl = 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)n
by induction. When n = 1, this becomes
1 ·x(x)-1y + 1 ·x(x - z)0(y+z)0 = 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)n and g(y) = k=0n (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.

© Canadian Mathematical Society, 2014 : https://cms.math.ca/