129

THE ACADEMY CORNER

No. 18
Bruce Shawyer
All communications about this column should be sent to Bruce
Shawyer, Department of Mathematics and Statistics, Memorial University
of Newfoundland, St. John's, Newfoundland, Canada. A1C 5S7

Memorial University Undergraduate

Mathematics Competition
September 25, 1997
We present in this issue, two solutions from Bob Prielipp, University of
Wisconsin{Oshkosh, Wisconsin, USA, to the above competition, which was
printed in Academy Corner No. 15 [1997: 449].
2. The surface area of a closed cylinder is twice the volume. Determine
the radius and height of the cylinder given that the radius and height
are both integers.
Solution.
Let r be the radius and h be the height of the closed cylinder, where r
and h are both positive integers.
If the surface area of the closed cylinder is twice the volume, then
2rh + 2r = 2r h:
2 2

It follows that h + r = rh. Thus

(r , 1)(h , 1) = rh , r , h + 1 = 0 + 1 = 1:
Hence r , 1 = 1 and h , 1 = 1 (since r and h are both positive integers), so
that r = 2 and h = 2.
It is easily checked that if r = 2 and h = 2, then the surface area of
the closed cylinder is twice the volume.
130

3. Prove that
1 + 41 + 19 + : : : + n1 < 2:
2

Solution. [Slightly shortened by the editor.]

We use mathematical induction to prove, for each positive integer n,
1 + 14 + 19 + : : : + n1 < 2 , n1 :
2

The result clearly holds for n = 1.

Assume that the result holds for n = k. Then
1 + 14 + 91 + : : : + k1 + (k +1 1)
2 2
 
< 2 , k1 + (k +1 1) 2

= 2 , (kk+ 1) , k = 2 , k + k + 1
2 2

(k + 1) 2 k(k + 1)2

k ( k + 1)
< 2 , k(k + 1) = 2 , k + 1 : 1
2

Hence, by induction, the result holds.

Equality holds if and only if n = 1.

Advance Notice
At the summer 1999 meeting of the Canadian Mathematical Society, to
be held in St. John's, Newfoundland, there will be a Mathematics Education
Session on the topic \What Mathematics Competitions do for Mathematics".
Invited speakers include Edward Barbeau, Toronto; Tony Gardner, Birm-
ingham, England; Ron Dunkley, Waterloo; and Rita Janes, St. John's. Any-
one interested in givinga paper at this session should contact one of the orga-
nizers, Bruce Shawyer or Ed Williams, at the Department of Mathematics and
Statistics, Memorial University of Newfoundland, St. John's, Newfoundland,
Canada.
email addresses:
bshawyer@math.mun.ca
ewilliam@math.mun.ca
 131

THE OLYMPIAD CORNER

No. 189
R.E. Woodrow
All communications about this column should be sent to Professor R.E.
Woodrow, Department of Mathematics and Statistics, University of Calgary,
Calgary, Alberta, Canada. T2N 1N4.
We begin this issue with an exam set sent in by one of our newer cor-
respondents. My thanks go to Enrique Valeriano, National University of
Engineering, Lima, Peru.
PERU'S SELECTION TEST FOR
THE XII IBEROAMERICAN OLYMPIAD
August 1997 | 3.5 hours
1. Given an integer a > 2, the sequence a ; a ; a ; : : : is de ned as
0 0 1 2
follows:
ak = aak(1 + ak ); if ak is an odd number;
ak = k ; if ak is an even number:
+1

+1 2

Prove that there is a nonnegative integer p such that ap > ap > ap .

+1 +2

2. A positive integer is called \almost-triangular" if the number is

itself triangular or is the sum of di erent triangular numbers. How many
almost-triangular numbers are there in the set f1; 2; 3; : : : ; 1997g?
Note: The triangular numbers are a ; a ; a ; : : : ; ak ; : : : ; where
a = 1, and ak = k + ak, , for all k  2.
1 2 3

1 1

3. An n  n chessboard (n  2) is numbered with n non-zero num-

2

bers. This chessboard is called an \Incaican Board" if, for each square the
number written on the square is the di erence between two of the numbers
written on two of the neighbouring squares (sharing a common edge). For
which values of n can one obtain Incaican Boards?
4. Let ABC be a given acute triangle. Give a ruler and compass con-
struction of an equilateral triangle DEF with D on BC , E on AC , and F
on AB such that the perpendiculars to BC at D, to AC at E , and to AB
at F , respectively, are concurrent.

Next we give the Third and Fourth Grade problems of the 38 Mathe- th

matics Competition for Secondary School Students of the Republic of Slove-

nia. My thanks go to Richard Nowakowski, Canadian Team Leader to the
IMO in Hong Kong, for collecting this contest and forwarding it to me.
132

REPUBLIC OF SLOVENIA
th
38 Mathematics Competition
for Secondary School Students
April, 1994
Third Grade
1. Let n be a natural number. Prove: if 2n + 1 and 3n + 1 are perfect
squares, then n is divisible by 40.
2. Show that cos(sin x) > sin(cos x) holds for every real number x.
3. The polynomial p(x) = x + ax + bx + c has only real roots. Show
3 2

that the polynomial q (x) = x , bx + acx , c has at least one nonnegative

3 2 2

root.
4. Let the point D on the hypotenuse AC of the right triangle ABC
be such that jAB j = jCDj. Prove that the bisector of \BAC , the median
through B , and the altitude through D, of the triangle ABD have a common
point.
Fourth Grade
1. Prove that there does not exist a function f : Z ! Z, for which
f (f (x)) = x + 1 for every x 2 Z.
2. Put a natural number in every empty eld of the table so that you
get an arithmetic sequence in every row and every column.

74

186

103

3. Prove that every number of the sequence

49; 4489; 444889; 44448889; : : :
is a perfect square (in every number there are n fours, n , 1 eights and a
nine).
4. Let Q be the midpoint of the side AB of an inscribed quadrilat-
eral ABCD and S the intersection of its diagonals. Denote by P and R
the orthogonal projections of S on AD and BC respectively. Prove that
jPQj = jQRj.
 133

As a nal contest for your puzzling pleasure in this number, we give the
VIII Nordic Mathematical Contest. Again my thanks go to Richard Nowakowski,
Canadian Team leader to the IMO in Hong Kong, for collecting this contest
and forwarding it to me.
VIII NORDIC MATHEMATICAL CONTEST
th March 17 , 1994
Time: 4 hours
1. Let O be a point in the interior of an equilateral triangle ABC with
side length a. The lines AO, BO and CO intersect the sides of the triangle
at the points A , B and C respectively. Prove that
1 1 1

jOA j + jOB j + jOC j < a:

1 1 1

2. A nite set S of points in the plane with integer coordinates is called

a two-neighbour set, if for each (p; q ) in S exactly two of the points (p +1;q ),
(p; q + 1), (p , 1; q), (p; q , 1) are in S . For which n does there exist a two-
neighbour set which contains exactly n points?
3. A square piece of paper ABCD is folded by placing the corner D
at some point D0 on BC (see gure). Suppose AD is carried into A0 D0 ,
crossing AB at E . Prove that the perimeter of triangle EBD0 is half as long
as the perimeter of the square. A 0

A E B

D 0

D C
4. Determine all positive integers n < 200 such that n 2
+ (n + 1) is
2

a perfect square.

Turning now to comments and solutions related to the February 1997

number of the corner, we welcome two alternate solutions to problems of
the Sixth Irish Mathematical Olympiad sent in by another new contributor
whom we also welcome.
3. [1995: 151{152; 1997: 9{13] Sixth Irish Mathematical ,n

Olympiad.
For nonnegative integers n, r the binomial coecient r denotes the
number
,
of combinations of n objects chosen r at a time, with the convention
that n = 1 and nr = 0 if n < r. Prove the identity
,

0
1
X n , r + 1r , 1 = n
d=1 d d,1 r
134

for all integers n, r with 1  r  n.

Alternate Solution by Mohammed Aassila, UFR de Mathematique et
d'Informatique, L'Universite Louis Pasteur, Strasbourg, France.
We have
(1 + x)n = (1 + x)n,r (1 + x)r, 2
+1 1
3
"m,r # r, 
X n , r + 1
+1
X r , 1 1

= xi 4
i xj 5 j
i=0 j =0
m,X ,1 n , r + 1r , 1
r+1 rX
= i j xi+ j
i=0 j =0
The coecient of xr is
r
X
 r n , r + 1r , 1
n , r + 1r , 1 = X
d=0 d r,d d d
=1
d,1
4. [1995:151{152; 1997: 9{13] Sixth Irish Mathematical Olympiad.
Let x be a real number with 0 < x <  . Prove that, for all natural
numbers n, the sum
sin x + sin33x + sin55x +


+ sin(2 n , 1)x
2n , 1
is positive.
Alternate solution by Mohammed Aassila, UFR de Mathematique et
d'Informatique, L'Universite Louis Pasteur, Strasbourg, France.
We know that
2 sin x sin(2k , 1)x = cos(2k , 2)x , cos 2kx:
Hence

2 sin x sin x + sin3 x +


+ sin(2n , 1)x 

3 2n , 1
= 1 , cos 2x + cos 2x ,3 cos 4x +


+ cos(2n ,2n2),
x , cos 2nx
1
= 1 , cos 2x 1 , 3 , cos 4x 3 , 5 ,


, 2n ,nx1
   
1 1 1 cos 2

 1 , 1 , 13 + 13 , 15 +


+ 2n1, 1 = 0:
    
 135

Next we turn to solutions to problems of the Latvian 44 Mathematical

Olympiad given in the February number of the Corner last year [1997: 78].
LATVIAN 44 MATHEMATICAL OLYMPIAD
Final Grade, 3 Round
rd
Riga, 1994
1. It is given that cos x = cos y and sin x = , sin y. Prove that
sin 1994x + sin 1994y = 0.
Solutions by Miguel Amengual Covas, Cala Figuera, Mallorca, Spain;
by Mansur Boase, student, St. Paul's School, London, England; by Panos
E. Tsaoussoglou, Athens, Greece; and by Zun Shan and Edward T.H. Wang,
Wilfrid Laurier University, Waterloo, Ontario. We give the solutionof Covas.
More generally, we prove that sin mx + sin my = 0 where m is an
integer.
    
Since sin mx + sin my = 2 sin m x y cos m x,y , it is sucient
+
2 2
   
to show that sin x y = 0 since sin m x y = 0 follows easily by induc-
+
2
+
2
tion from
sin (m + 1) x +2 y = sin m (x +2 y) cos x +2 y
     

+ cos m (x +2 y) sin x +2 y :
   

Now,
cos x = cos y () cos x , cos y = 0
() ,2 sin x +2 y sin x ,2 y = 0 (1)
and
sin x = , sin y () sin x + sin y = 0
() 2 sin x +2 y cos x ,2 y = 0 : (2)
Squaring each of (1) and (2) and adding, we nd
4 sin x +2 y sin (x ,2 y ) + cos (x ,2 y ) = 0:
  
2 2 2

| {z }
=1

Hence sin x y = 0.
+
2

3. It is given that a > 0, b > 0, c > 0, a + b + c = abc. Prove that at

least one of the numbers a, b, c exceeds 17=10.
136

Solutionsby Miguel Amengual Covas, Cala Figuera, Mallorca, Spain; by

Heinz-Jurgen Sei ert, Berlin, Germany; by Panos E. Tsaoussoglou, Athens,
Greece; and by Zun Shan and Edward T.H. Wang, Wilfrid Laurier University,
Waterloo, Ontario. We give two solutions of Shan and Wang.
First Solution.
Pn
We show,
Qn
in general, that if xi > 0 for i = 1; 2; : : : ; n, such that
i i x = i xi , then maxfxi : i = 1; 2; : : : ; ng  n = n, . In partic-
1 ( 1)

ular, when n = 3 we get

=1 =1

p
maxfx ; x ; x g  3 > 1:7 = 17
1 2 3
10 :
By the arithmetic-geometric mean inequality we have
1Xn !n Y n n
X
n x i  xi = xi;
i=1 i=1 i=1
Pn
and thus i=1 xi  nn=(n,1).
Without loss of generality, we may assume that maxfxi : i = 1; 2; : : : ; ng =
xn . Then nxn  Pni xi  nn= n, from which xn  n = n, follows.
=1
( 1) 1 ( 1)

Second Solution (without the AM-GM inequality). Pn Qn

Suppose xi > 0 (Q i= 1 ; 2 ; : : : ; n) such that i xi = i xi . Then
dividing both sides by ni xi we get
=1 =1

=1

n
X 1
i x x
=1
:1: :2x^i : : : xn = 1;
where x^i indicates that the factor xi is missing. Hence for some j we have
1  1 or n  x x : : : x^ : : : x :
x x : : : x^j : : : xn n j1 2 n
1 2

Without loss we may assume that xn = maxfxi : i = 1; 2; : : : ; ng.

Then xnn,  x x : : : x^j : : : xn  np, from which xn  n = n, follows. In
1
1 2
1 ( 1)

particular, for n = 3, we get x  3 > 1:7 = .

3
17
10

4. Solve the equation 1!+2!+3!+


+ n! = m in natural numbers.

3

Solution by Zun Shan and Edward T.H. Wang, Wilfrid Laurier Univer-
sity, Waterloo, Ontario.
We solve the more general problem of nding all solutions of the Dio-
phantine equation 1! + 2! + 3! +


+ n! = mk in natural numbers, n, m,
and k. For convenience, let Sn = 1! + 2! + 3! +


+ n!.
When k = 1 clearly m = Sn is the only solution for any n.
When k = 2 we claim that the equation Sn = m has exactly two 2

solutions: n = m = 1 and n = m = 3. Note rst that d!  0(mod 10)

 137

for all d  5 and S = 1 + 2 + 6 + 24 = 33  3(mod 10). Hence

Sn  3(mod 10) for all n  4. However, it is easy to see that the last digit
4

of a perfect square can never be 3 and so there are no solutions if n  4.

Checking the cases when n = 1; 2; 3 directly reveals that there are precisely
two solutions, as given above.
When k  3 we show that n = m = 1 is the only solution. If
n  2 then clearly Sn k 0(mod 3). But mk  0(mod 3) implies
m  0(mod 3) and so m  0(mod 27) as k  3. Since d!  0(mod 27)
for all d  9 and since
S = 1 + 2 + 6 + 24 + 120 + 720 + 5040 + 40320 = 46233 6= 0 (mod 27)
8

there are no solutions if n  8. On the other hand, direct checking shows that
for n = 2; 3; 4; 5; 6; 7, Sn = 3; 9; 33; 153; 873, and 5913, none of which is a
perfect k power for any k  3. Finally, it is trivial to see that n = m = 1
th

is a solution.
Remark: The special case of this problem when k = 2 was proposed by
E.T.H. Wang as Quicky Q657 in the Mathematics Magazine, 52 (1979), p. 47.
The general case was also proposed by him as problem #4203 in Mathmedia
(in Chinese) 4(2), 1980; p. 64 with solution in 4(3), 1980, p. 49. This is a
journal published by the Institute of Mathematics, Academia Sinica, Taipei,
Taiwan.
5. There are 1994 employees in the oce. Each of them knows 1600
others of them. Prove that we can nd 6 employees, each of them knowing
all 5 others.
Solution by Zun Shan and Edward T.H. Wang, Wilfrid Laurier Univer-
sity, Waterloo, Ontario.
Let E denote the set of these 1994 employees. For each x 2 E , let S (x)
denote the set of all employees whom x does not know. Then by assumption,
jS(x)j = 393 for all x 2 E. Let a and b be any two employees who know
each other. Since
jS(a) [ S(b)j  2  393 = 786 < 1992;
9c 2 E such that a, b, and c form a triple of mutual acquaintances. Since
jS(a) [ S(b) [ S(c)j  3  393 = 1179 < 1991;
9d 2 E such that a, b, c, and d form a quadruple of mutual acquaintances.
Since
jS(a) [ S(b) [ S(c) [ S(d)j  4  393 = 1572 < 1990;
9e 2 E such that a, b, c, d, and e form a quintuple of mutual acquaintances.
Finally, since
jS(a) [ S(b) [ S(c) [ S(d) [ S(e)j  5  393 = 1965 < 1989;
138

9f 2 E such that a, b, c, d, e, and f form a sextuple of mutual acquaintances.

1st SELECTION ROUND
1. It is given that x and y are positive integers and 3x + x = 4y + y.2 2

Prove that x , y , 3x + 3y + 1 and 4x + 4y + 1 are squares of integers.

Solutions by Miguel Amengual Covas, Cala Figuera, Mallorca, Spain;
by Panos E. Tsaoussoglou, Athens, Greece; and by Zun Shan and Edward
T.H. Wang, Wilfrid Laurier University, Waterloo, Ontario. We give the solu-
tion by Shan and Wang and their comment.
Note rst that the given equation implies the following two equations:
(x , y)(3x + 3y + 1) = y 2
(1)
(x , y)(4x + 4y + 1) = x 2
(2)
(1)  (2) yields (x , y ) (3x + 3y + 1)(4x + 4y + 1) = (xy ) which
2 2

implies that (3x + 3y + 1)(4x + 4y + 1) is a perfect square. But clearly

gcd(3x +3y +1; 4x +4y +1) = 1 since 4(3x +3y +1) , 3(4x +4y +1) = 1.
Therefore, 3x + 3y + 1 and 4x + 4y + 1 are both squares, which, together
with (1) (or (2)), implies that x , y is also a square.
Comment: This would be a much better problem had it asked to show
only that x , y is a square. This is an example of a case when asking to prove
too many things actually gives the solution away, in some sense.
Shan and Wang also proposed the followingproblem inspired by this one.
The Diophantine equation 3x + x = 4y + y is satis ed when x = 30
2 2

and y = 26.
(a) Find another solution in positive integers.
(b) Are there in nitely many solutions in positive integers? Is so, de-
scribe all of them.
2nd SELECTION ROUND
1. It is given that 0  xi  1, i = 1; 2; : : : ; n. Find the maximum of
the expression
x x


xn
+ + + x x : : : xn, + 1 :
1 2

x x : : : xn + 1 x x x : : : xn + 1
2 3 1 3 4 1 2 1

Solutions by Murray S. Klamkin, University of Alberta, Edmonton, Al-

berta; and by Zun Shan and Edward T.H. Wang, Wilfrid Laurier University,
Waterloo, Ontario. We rst give the solution of Shan and Wang.
Clearly n  2 for the question to make sense. Let Sn denote the given
sum. We prove that Sn  n , 1. For n = 2, equality holds if and only if
x = 0, x = 1 or x = 1, x = 0 or x = x = 1. For n  3, equality
holds if and only if one of the xi 's is 0 and the others are all equal to 1. We
1 2 1 2 1 2

rst establish a lemma:

 139

Lemma. Suppose that the xi 's are reals such that 0  xi  1 for all
i = 1; 2; : : : ; n, where n  2. Then x + x +


+ xn  n , 1+ x x


xn
with equality holding if and only if xi 6= 1 for at most one i, i = 1; 2; : : : ; n.
1 2 1 2

Proof. For n = 2, x + x  x x + 1 , (1 , x )(1 , x )  0, which

is clearly true. Equality holds if and only if x = 1 or x = 1. Suppose the
1 2 1 2 1 2

assertion holds for some n  2. Then

1 2

x + x +


+ xn + xn  n , 1 + x x


xn + xn
1 2 +1 1 2 +1

 n , 1 + x x


xn xn + 1 1 2 +1

= n + x x


xn : 1 2 +1

(The 2 inequality is by the n = 2 case.)

nd

If equality holds, then it must hold in both inequalities above. By the

induction hypotheses, we then have
(i) at most one of x ; x ; : : : ; xn is di erent from 1 and
1 2

(ii) either xn = 1 or x x


xn = 1.
+1 1 2

Since x x


xn = 1 clearly implies x = x =


= xn = 1, our assertion

1 2 1 2
about the equality follows.
Now we proceed to prove the claim about Sn. For n = 2,
S = x x+ 1 + x x+ 1  x x+ x + x x+ x = 1:
2
1 2 1 2

2 1 2 1 1 2

It is readily seen that equality holds if and only if x = 0, x = 1 or x = 1,

x = 0, or x = x = 1. For n  3 we apply the lemma above and obtain
1 2 1

2 1 2

Sn  x x+xx

+
x


++1xn  (n ,x 1)

1 2

x
+ x x


xn  n , 1:



xn + 1
1 2

n 1 2 1 2

If equality holds, then the 2 inequality implies xj =

nd
6 1 for at most one j and
the 3 inequality implies (n , 1)x x


xn = x x


xn , which implies
rd

that xi = 0 for at least one i. Hence xi = 0 for some i and xj = 1 for all
1 2 1 2

j= 6 i. It is obvious that this condition is also sucient. This completes the

proof.
And here is Klamkin's somewhat more abbreviated solution with gen-
eralization.
Since the expression is convex in each of the variables, the maximum
value is achieved when each variable takes on 0 or 1. Clearly this occurs when
one variable is 0 and the rest are 1 giving the maximum value of n , 1. The
same maximum occurs if any of the numerators xi are replaced by xi i where
i  1.
A similar result, using convexity, that
X xui + Y(1 , x )v  1;
1 + s , xi i
140

where 0  xi  1, u; v  1, s = xi and the sum and product are over

P

i = 1; 2; : : : ; n, is given in [1].
Reference:
[1] M.S. Klamkin, USA Mathematical Olympiads 1972{1986, M.A.A.,
Washington D.C., 1988, p. 82.
3. A triangle ABC is given. From the vertex B, n rays are constructed
intersecting the side AC . For each of the n +1 triangles obtained, an incircle
with radius ri and excircle (which touches the side AC ) with radius Ri is
constructed. Prove that the expression
r r : : : rn
1 2 +1

R R : : : Rn
1 2 +1

depends on neither n nor on which rays are constructed.

Solution by Miguel Amengual Covas, Cala Figuera, Mallorca, Spain.
If A, B , C are the angles of a triangle, then
r = s tan A2 tan B2 tan C2 and ra = s tan ;
2
A
where r, ra are the inradius and the radius of the excircle opposite A, and s
is the semiperimeter.
It follows that
r = tan B tan C :
ra 2 2
Next we apply this result to each of n + 1 triangles obtained (see gure at
the top of the next page). This yields
r1 = tan A tan 1
Rr 1 , 1
2 2

R2
2 = tan 180
tan 2










2 2




rn = tan 180 , n,1 tan n
Rrn+1
n 2
180 , n C 2
Rn+1 = tan 2 tan 2 :
Multiplying these equalities, we observe that the product of all the
right hand members is
A 
tan
tan
   
tan n cot n

C
2 cot 2
tan 2 cot 2


2
tan 2
1 1 2 2

2 2
= tan A2
tan C2 ;
and we get
r r


rn, A C
R R


Rn = tan 2
tan 2
1 2 1

1 2 +1

which depends on neither n nor on which rays are constructed.

 141
B

A 1 2 n C

3rd SELECTION ROUND

3. Let ABCD be an inscribed quadrilateral. Its diagonals intersect
at O. Let the midpoints of AB and CD be U and V . Prove that the lines
through O, U and V , perpendicular to AD, BD and AC respectively, are
concurrent.
Solution by Toshio Seimiya, Kawasaki, Japan.
Case 1. Neither is AC orthogonal to BD, nor is AD a diameter.
U A
B
M
X
S H O

Y
N
C
V
D

Let M , N be the feet of the perpendiculars from U , V to BD, AC

respectively, and let S be the intersection of UM and V N . Let X , Y be
the feet of the perpendiculars from A, D to BD, AC respectively, and let
H be the intersection of AX and DY . Since U is the midpoint of AB, and
UM kAX , M is the midpoint of BX . Similarly N is the midpoint of CY .
Since \AXD = \AY D = 90 , A, X , Y , D are concyclic. Therefore
\Y XD = \Y AD = \CAD = \CBD. Thus we have XY kBC .
Since M , N are the midpoints of BX , CY respectively, we have MN kXY .
Since SM kHX , XN kHY , and MN kXY , MX , NY and SH are concur-
rent at O. Therefore S , H , O are collinear.
Since AH ? OD and DH ? OA, H is the orthocentre of
OAD, so that
HO ? AD. Thus we have SO ? AD.
Thus the lines through O, U and V , perpendicular to AD, BD and AC
respectively, are concurrent at S .
142

Case 2. AC is orthogonal to BD.

B
M U
C O A

D
Let M be the midpoint of BC . Since U is the midpoint of AB , we get
UM ? AC , so that UM ? BD. Similarly we have V M ? AC .
Since AC ? BD and M is the midpoint of BC , by Brahmagupta's
Theorem we have MO ? AD. (See: H.S.M. Coxeter and S.L. Greitzer,
Geometry Revisited, p. 59).
Thus the lines through O, U and V , perpendicular to AD, BD and AC
respectively, are concurrent at M .
Case 3. AD is a diameter.
A
U
B
q

S
O
C

V q

D
Let S be the intersection of AB and CD. Since AB ? BD and
CD ? AC , S is the orthocentre of
OAD. Thus SO ? AD.
Hence the lines through O, U and V , perpendicular to AD, BD and
AC respectively, are concurrent at S.
That completes this number of the Olympiad Corner. Send me your
nice solutions and suggestions for future issues.
 143

BOOK REVIEWS
Edited by ANDY LIU
Vita Mathematica
edited by Ronald Calinger,
published by the MAA, Notes and Reports Series, 1996,
ISBN# 0-88385-097-4, softcover, 350+ pages, $34.95.
Reviewed by Maria de Losada, Bogota, Colombia.
This collection of papers read at the August 1992 Quadrennial Meet-
ing of the International Study Group on the Relations between History and
Pedagogy of Mathematics at the University of Toronto and the Seventh Inter-
national Congress on Mathematical Education at Universite Laval in Quebec,
edited and refereed, begins with a somewhat ponderous re ection on the dif-
ferent tendencies in research in the history of mathematics, contrasting the
approaches of cultural and mathematical historians.
Looking at the role of problems in the history and teaching of mathe-
matics, Evelyne Barbin reminds us that \one of the perverse e ects of edu-
cation : : : [is] that answers are given to questions that have not been asked.
The history of mathematics shows us that questions must come rst, and
[that] it is through questions that we make sense of mathematical concepts."
In the historical studies (from antiquity to the Scienti c Revolution)
can be found intriguing material that is not of easy access. Swetz's paper on
the enigmas of Chinese mathematics is informative as it strives to provide a
balanced presentation and Katz's treatment of medieval Hebrew and Islamic
mathematics provides useful and little known information in a concise and
well ordered manner.
Noteworthy among the more recent historical studies is Judith
Grabiner's paper which contrasts historical perspectives of the calculus, the
geometric (McLaurin) and algebraic (Lagrange), linking these naturally with
education and culture and suggesting that \progress in mathematics is made
by those who sharpen their thinking by exercising the courage of their some-
times idiosyncratic convictions". On an entirely di erent note, the detailed
history given by Ronald Calinger of the University of Berlin Mathematics
Seminar examines every facet of that paradigmatically successful structuring
of a research tradition, in which many of the recurrent themes of this book,
such as starting from problems and learning from the masters, were put into
practice.
The third section of the collection, devoted to the integration of history
with mathematics teaching recounts many valuable experiences, two titles of
note being Mathematical Masterpieces: Teaching with Original Sources and
A History of Mathematics Course for Teachers, Based on Great Quotations.
144

Although they are presented as summaries and have catchy titles, these ar-
ticles refer to teaching experiences that are both substantive and well struc-
tured. In the rst of these, Reinhard Laubenbacher and David Pengelley
reveal not only a polished list of original sources that can be used with un-
dergraduates, but also aspects of their pedagogical approach. In the second,
Israel Kleiner begins with quotations addressing the question \What is math-
ematics?" that are arranged in \antagonistic" pairs to bring across the un-
derlying message of mathematics as an activity whose history is susceptible
to chronological, thematical, topical and biographical study, as long as sight
is not lost of Lakatos' remark: \The history of mathematics, lacking the guid-
ance of philosophy [is] blind, while the philosophy of mathematics, turning
its back on the most intriguing phenomena in the history of mathematics,
[is] empty."
It is unfortunate that the book has so many typos! Not only are foot-
note numbers routinely formatted incorrectly, but there are also plenty of
errors in the text.
In general, this is good formative reading for those with an appetite
for historical material, but especially useful in its treatment of interrelations
between history and pedagogy.

The Canadian Mathematical Society has initiated a new series of book-

lets of enrichment material for interested and mathematically talented high
school students.
La Societe mathematique du Canada vient de lancer une serie de livrets
d'enrichissement pour les e leves du secondaire interesses et forts en mathe-
matiques.
A Taste Of Mathematics
Aime{T{On les Mathematiques
See the enclosed yer for more details of the ATOM series.
Voir le depliant ci-inclus pour plus de renseignements sur la collection ATOM .
 145

Sum of powers of a nite sequence:

a geometric approach
William O.J. Moser
In this note we give a geometric-combinatoric derivation of a formula
for the sum of r powers of a nite positive integer sequence:
th

r X
X n 
ai(r; `) ;
ar + ar +


+ arn =
1 2
` (1)
`=1 i=1
where
n =  k nn,k ; if 0  k  n ,
  !

k 0; if k > n  1 ,
!( )!

and the numbers (r;`) are determined by the recurrence

(r; 1) = 1; r = 1; 2; 3;


; (1; `) = 0; ` = 2; 3;


; (2)
(r; `) = `((r , 1; ` , 1) + (r , 1; `)); r  2; `  2 :
The derivation parallels, simpli es and generalizes the proof given in
[1], and seems to be more elementary than proofs given in [2] and [3].
For xed (but arbitrary) positive integers m; r, let Lmr denote the ( )

r-dimensional integer lattice points

f(x ; x ;


; xr ) j xi integers, 0  x ; x ;


; xr  mg ;
1 2 1 2

and for w  1 let Smr (w) denote the set of r-dimensional \cubes" with faces
( )

parallel to the coordinate planes, vertices in Lmr and width w. ( )

Of course Smr (w) = ; if w > m. A cube in Smr (w) is identi ed by its

( ) ( )

vertex ( ) = ( ; ;


; r ) closest to (0;


; 0). Clearly

1 2

w +  m; w +  m;


; w + r  m;
1 2 1 ; ;


;
2 r  0;
or
0 1  m , w; 0   m , w;


;
2

0  r  m , w; 1  w  m ; (3)
so the number of cubes in Smr (w) is ( )

jSm (w)j = (0m; , w + 1) ; ifif 1w>wmm1 ,.

 r
r ( )

Copyright c 1998 Canadian Mathematical Society

146

For given 1  w  m we can also nd the number of ( )'s satisfying (3) as

follows. Any r-tuple ( ) satisfying (3) determines the sequence ( ) consist-
ing of the distinct values, in increasing order, of the entries in ( ):
( ) : 0  < <


< `  m , w; `  r :
1 2 (4)
Given a sequence ( ) satisfying (4) there are many r-tuples ( ) satisfying
(3) which have entries with values ( ). How many? Let (r;`) denote this
number. It depends on ` (and not on the particular numbers ;


; ` )
and satis es the recurrence (2). For, given ( ), there are ` choices (namely
1

; ;


; ` ) for the rst entry of ( ); ( ) can then be completed in

(r , 1; `) ways if the integer chosen for appears among the entries
1 2 1

; ;


; r, and in (r , 1; ` , 1) ways otherwise; (2) then follows.

1

2 3

The numbers (r; `) are exhibited in the display below:

r n` 1 2 3 4 5 6
1 1 0 0 0 0 0
2 1 2! 0 0 0 0
3 1 6 3! 0 0 0
4 1 14 36 4! 0 0
5 1 30 150 240 5! 0
.. .. .. .. .. .. ..
. . . . . . .
Since there are m,w`
,

+1
ways of choosing the sequence ( ) satisfying
(4) we nd that
Xr m , w + 1
r
(m , w + 1) = (r; `); 1  w  m; 1  `  r;
`=1 `
and setting a = m , w + 1  1
r  
X a (r;`); a  1; r  1 :
ar = `
=1`
Summing over a set of a's we have (1). Taking ai = a + (i , 1)d,
i = 1; 2;


; n in (1), we have
X r X
n a + (i , 1)d
ar + (a + d)r +


+ (a + (n , 1)d)r = ` (r; `) ;
` i =1 =1

the sum of the r powers of an arithmetic progression. When a = d = 1

th

Xr n + 1
r r r
s (n) = 1 + 2 +


+ n = r
` + 1 (r; `) ;
( )

` =1
 147

n 
X i = n + 1 .
since
i=1 ` `+1
The display below exhibits s r (n) for r = 1; 2; 3; 4; 5:
( )

s
(1)
(n) 1,n
+1
2

1n + 2! n
,
,

s(2)
(n) +1
2
+1
3

s(3)
(n) 1,n
+ 6,n
+ 3!,n

+1
2
+1
3
+1
4

1n + 14 n + 36 n + 4! n
,
,
,
,

s(4)
(n) +1
2
+1
3
+1
4
+1
5

s(5)
(n)1,n
+ 30,n
+ 150,n
+ 240,n
+ 5!,n
+1
2
+1
3
+1
4
+1
5
+1
6

References
1. [1] Moser, W., Sums of d powers. Math. Gazette 75 (1991) 332.
th

2. [2] Paul, J.L., On the sum of the k powers of the rst n integers.
th

Amer. Math. Monthly 78 (1971) 271{273. MR 43 #4092.

3. [3] Wagner, C., Combinatorial proofs of formulas for power sums. Arch.
Math. (Basel) 68 (1997), no. 6, 464{467.
148

THE SKOLIAD CORNER

No. 29
R.E. Woodrow
In this number we give the rst round of the 1996{97 Alberta High
School Mathematics Competition written in November of 1996. The top stu-
dents from Round 1 are invited to take part in the second round competition
written in February. There are book prizes for individuals and teams based
on the Round 1 results, and scholarships and cash prizes for Round 2. (See
[1997:410-411, 479-481] where we gave Round 2 of the 1996{97 contest and
the answers.) More information about the contest can be found at the web-
site: www.math.ualberta.ca/ ahsmc/. My thanks go to the organizers of the
committee (chaired by T. Lewis, University of Alberta) for permission to use
these materials.
ALBERTA HIGH SCHOOL
MATHEMATICS COMPETITION
Part I | November, 1996
1. An eight-inch pizza is cut into 3 equal slices. A ten-inch pizza is cut
into 4 equal slices. A twelve-inch pizza is cut into 6 equal slices. A fourteen
inch pizza is cut into 8 equal slices. From which pizza would you take a slice
if you want as much pizza as possible?
(a) 8-inch (b) 10-inch (c) 12-inch (d) 14-inch (e) does not matter
2. One store sold red plums at four for a dollar and yellow plums at
three for a dollar. A second store sold red plums at four for a dollar and
yellow plums at six for a dollar. You bought m red plums and n yellow
plums from each store, spending a total of ten dollars. How many plums in
all did you buy?
(a) 10 (b) 20 (c) 30 (d) 40 (e) not enough information
3.
A Six identical cardboard pieces are
piled on top of one another, and
D B the result is shown in the dia-
F E C gram.

The third piece to be placed is:

(a) A (b) B (c) C (d) D (e) E
 149

4. A store o ered triple the GST in savings. A sales clerk calculated the
selling price by rst reducing the original price by 21% and then adding the 7%
GST based on the reduced price. A customer protested, saying that the store
should rst add the 7% GST and then reduce that total by 21%. They agreed on
a compromise: the clerk just reduced the original price by the 14% di erence.
How do the three ways compare with one another from the customer's point
of view?
(a) The clerk's way is the best. (c) The compromise is the best.
(b) The customer's way is the best. (d) All three ways are the same.
(e) The compromise is the worst while the other two are the same.
5. If m and n are integers such that 2m , n = 3, then what will m , 2n
equal?
(a) ,3 only (b) 0 only (c) only multiples of 3
(d) any integer (e) none of these
6. If x is x% of y, and y is y% of z, where x, y and z are positive real
numbers, what is z ?
(a) 100 (b) 200 (c) 10; 000 (d) does not exist (e) cannot be determined
7. About how many lines can one rotate a regular hexagon through
some angle x, 0 < x < 360 , so that the hexagon again occupies its original
position?
(a) 1 (b) 3 (c) 4 (d) 6 (e) 7
8. AB is a diameter of a circle of radius 1 unit. CD is a chord perpen-
dicular to AB that cuts AB at E . If the arc CAD is 2=3 of the circumference
of the circle, what is the length of the segment AE ?
p
(a)2
3
(b)
3
2
(c) 
2
(d) 2
3
(e) none of these
9. One of Kerry and Kelly lies on Mondays, Tuesdays and Wednesdays,
and tells the truth on the other days of the week. The other lies on Thursdays,
Fridays and Saturdays, and tells the truth on the other days of the week. At
noon, the two had the following conversation:
Kerry : I lie on Saturdays.
Kelly : I will lie tomorrow.
Kerry : I lie on Sundays.
On which day of the week did this conversation take place?
(a) Monday (b) Wednesday (c) Thursday (d) Saturday (e) Sunday
150

10. How many integer pairs (m; n) satisfy the equation

m(m + 1) = 2n ?
(a) 0 (b) 1 (c) 2 (d) 3 (e) more than 3
11. Of the following triangles given by the lengths of their sides, which
one has the greatest area?
(a) 5; 12; 12 (b) 5; 12; 13 (c) 5; 12; 14 (d) 5; 12; 15 (e) 5; 12; 16
12. If x < y and x < 0, which of the following numbers is never
greater than any of the others?
(a) x + y (b) x , y (c) x + jy j (d) x , jy j (e) ,jx + y j
13. An x by y ag, with x < y, consists of two perpendicular white
stripes of equal width and four congruent blue rectangles at the corners. If
the total area of the blue rectangles is half that of the ag, what is the length
of the shorter side of each blue rectangle?
p2 2 p2 2 p2 2
(a) x,y x y
+
4
+
(b) x,y x y
px2
+
2
+
(c) x y x y
3 + +
4
+

2
(d) x y
3 + +
2
y+
(e) none of these
14. A game is played with a deck of ten cards numbered from 1 to 10.
Shue the deck thoroughly.
i) Take the top card. If it is numbered 1, you win. If it is numbered k,
where k > 1, go to (ii).
ii) If this is the third time you have taken a card, you lose. Otherwise,
put the card back into the deck at the k position from the top and go to (i).
th

What is the probability of winning?

(a)1
5
(b) 5
18
(c) 13
45
(d) 3
10
(e) none of these
15. Five of the angles of a convex polygon are each equal to 108.
In which of the following ve intervals does the maximum angle of all such
polygons lie?
(a) (105; 120 ) (b) (120; 135 ) (c) (135; 150 )
(d) (150; 165 ) (e) (165; 180 )
16. Which one of the following numbers cannot be expressed as the
di erence of the squares of two integers?
(a) 314159265 (b) 314159266 (c) 314159267
(d) 314150268 (e) 314159269
 151

In the last number we gave the problems of the Final Round of the
British Columbia Colleges Junior High School Mathematics Contest 1997.
Here are the ocial solutions. My thanks for sending the materials to me go
to John Grant McLoughlin, now of the Faculty of Education, Memorial Uni-
versity of Newfoundland, who participated in formulating the exams while
he was at Okanagan College.
BRITISH COLUMBIA COLLEGES
Junior High School Mathematics Contest
Final Round 1997 | Part A
1. The buttons of a phone are arranged as shown at the right. If the
buttons are one centimetre apart, centre-to-centre, when you dial the num-
ber 592-7018 the distance, in centimetres, travelled by your nger is:
1 2 3

4 5 6

7 8 9

Solution. Each of the distances between successive digits in the phone

number is the hypotenuse of a right-angled
p2; p5triangle
p5; pwith pinteger sides.
p5, forThea
6 lengths pcan be easily
p pp computed as ; 2 ; 10 ;
p and p
total
p of 2 2 + 3 5 + 2 5. This can be rearranged into 5(3 + 2) +
2 2. Answer is (A)
2. What is the total number of ones digits needed in order to write the
integers from 1 to 100?
Solution. Clearly we need only one 1 for all the single digit numbers,
and (since we are only interested in one 3-digit number, namely 100) we need
only one 1 for all the 3-digit numbers under consideration. For the 2-digit
numbers there are nine which have a 1 in the units position (11; 21; : : : ; 91),
and 10 which have a 1 in the tens position (10; 11; : : : ; 19), for a grand total
of 21 ones needed. Answer is (D)
3. The number of solutions (x; y; z) in positive integers for the equa-
tion 3x + y + z = 23 is:
Solution. Clearly, there are only 7 possible values for x, namely 1
through 7. When x = 7, we have y + z = 2, which has a single solution
y = z = 1; when x = 6, we have y + z = 5, which has 4 solutions:
(y;z) = (1; 4); (2; 3); (3; 2); (4; 1). In this way we see that by reducing the
value of x by 1 we increase the number of solutions by 3. Thus the total
number of solutions are 1 + 4 + 7 + 10 + 13 + 16 + 19 = 70.Answer is (D)
152

4. In the diagram below the upper scale AB has ten 1 centimetre divi-
sions. The lower scale CD also has ten divisions but it is only 9 centimetres
long. If the right hand end of the fourth division of scale CD coincides ex-
actly with the right hand end of the seventh division of scale AB , what is the
distance, in centimetres, from A to C ?
A B
C D

Solution. Let E be the right hand end of the fourth division of scale
CD (which is also the right hand end of the seventh division of scale AB).
The distance AE is 7 cm. The distance CE is 4  0:9 = 3:6 cm. Thus the
distance AC = AE , CE = 3:4 cm. Answer is (E)
5. Triangle ABCpis equilateral with sides tangent to the circle with
centre at O and radius 3. The area of the quadrilateral AOCB , in square
units, is:
A

O B

C
Solution. First join the points B and O. Since an intersecting tangent
and radius of a circle are perpendicular, this produces 2 congruent right an-
gled triangles, namely BOA and BOC , each of which is a 30 , 60 , 90
triangle, which means that side BO is twice the length of side AO. Using
the Theorem of Pythagoras we have
2
p 2
p
BA = (2 3) , ( 3) = 12 , 3 = 9:
2

Thus BA = BC = 3. The area of triangle p BOA is now
p3
3. Since this

1
2
is half the area we seek, the answer is 3 3. Answer is (A)
6. Times such as 1:01, 1:11,: : : are called palindromic times because
their digits read the same forwards and backwards. The number of palin-
dromic times on a digital clock between 1:00 a.m. and 11:59 a.m. is:
Solution. Let us rst consider single digit hours. The rst and last digits
must be the same, but the middle digit can be anything. Thus there are 6
such palindromic times each hour (since there are 6 possible middle digits),
for a total of 54 such palindromic times between 1:00 am and 9:59 am. For
two digit hours (that is, 10 and 11), in order to be a palindromic time the
minutes are completely determined by the hour; there are only two such
times, namely 10:01 and 11:11. So the grand total number of palindromic
times between 1:00 a.m. and 11:59 a.m. is 56. Answer is (D)
 153

7. Ted's television has channels 2 through 42. If Ted starts on channel

15 and surfs, pushing the channel up button 518 times, when he stops he will
be on channel:
Solution. Ted's television set has a total of 41 channels. Thus every
time he pushes the channel up button 41 times he returns to the channel he
starts with. Since
518 = 12
41 + 26
we see that he has e ectively gone up 26 channels from his starting point at
channel 15. He should thus be at channel 15+26=41. Answer is (E)
8. Consider a three-digit number with the following properties:
1. If its tens and ones digits are switched, its value would increase
by 36.
2. Instead, if its hundreds and ones digits are switched its value
would decrease by 198.
Suppose that only the hundreds and tens digits are switched. Its value would:
Solution. Let n be a three-digit number with the given properties. Let
a, b, and c represent its hundreds digit, its tens digit and its ones digit, re-
spectively. Then n = 100a + 10b + c. By property 1 we see that
100a + 10c + b = n + 36 = (100a + 10b + c) + 36;
or 9(c , b) = 36;
that is, c , b = 4:
By property 2 we have
100c + 10b + a = n , 198 = (100a + 10b + c) , 198;
or 99(a , c) = 198;
that is, a , c = 2:
Note that the two relations established above (when added) yield a , b = 6.
Now let us consider the switch of the hundreds and the tens digits of n; the
new number is
100b + 10a + c = 100a + 10b + c + 100(b , a) + 10(a , b)
= n , 90(a , b) = n , 540:
Answer is (B)
9. Speedy Sammy Seamstress sews seventy-seven stitches in sixty-six
seconds. The time, in seconds, it takes Sammy to stitch fty- ve stitches is:
Solution. It takes Sammy seconds to sew a single stitch. For 55
6

stitches it will take 55
= 47 seconds.

7
6
7
1
7
Answer is (E)
154

10. How many positive integers less than or equal to 60 are divisible
by 3, 4, or 5?
Solution. There are 20 integers between 1 and 60 which are divisible by
3, 15 divisible by 4, and 12 divisible by 5. If we simply add up these numbers
to get 20 + 15 + 12 = 47, we will have counted those integers divisible by at
least two of 3, 4, or 5 more than once. Thus we must subtract from this total
the number of integers between 1 and 60 divisible by both 3 and 4 (that is,
divisible by 12), namely 5; the number divisible by both 3 and 5, namely 4;
and the number divisible by both 4 and 5, namely 3. Thus our accumulated
total is now 47 , (5 + 4 + 3) = 35. However, the integer 60, which is the
only positive integer in our range divisible by all of 3, 4, and 5 was at rst
counted 3 times, and now is not counted at all. Thus we must add 1 back
into the total. So our total is 36.
Alternate method: Simply enumerate all the numbers between 1 and
60 and test each one. Those that are divisible by 3, 4, or 5 are: 3, 4, 5, 6, 8,
9, 10, 12, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 33, 35, 36, 39, 40, 42,
44, 45, 48, 50, 51, 52, 54, 55, 56, 57 and 60. There are 36 numbers in this
list. Answer is (C)
Final Round 1997 | Part B
1. (a) The pages of a thick telephone directory are numbered from 1
to N . A total of 522 digits is required to print the pages. Find N .
Solution. From 1 to 9 inclusive there are 9 single digit numbers, which
uses up 9 digits. From 10 to 99 inclusive there are 90 2-digit numbers, which
uses up a further 180 digits. So far we have used up 189 digits before we
get to 3-digit numbers leaving us with 522 , 189 = 333 digits still to be
accounted for. With this many digits we can make up 111 3-digit numbers.
Starting at 100 and proceeding for 111 numbers brings us to page 210. Thus
N = 210.
(b) There are 26 pages in the local newspaper. Suppose that you pull a
sheet out and drop it on the oor. One of the pages facing you is numbered
19. What are the other page numbers on the sheet?
Solution. Since the newspaper has 26 pages, the outer sheet has pages
1, 2, 25, and 26. The next outermost sheet has pages 3, 4, 23, and 24. The
next sheet has 5, 6, 21, and 22. Finally the sheet we are interested in has
pages 7, 8, 19, and 20. So the other page numbers are 7, 8, and 20.
2. Create expressions for the numbers 1; 2; 3; : : : ; 10 by using each of
the digits 1, 9, 9, and 7. Note that the digits must appear separately; that is,
numbers like 17 are not allowed. Only the basic operations +, ,, ,  and
brackets (if necessary) may be used. Other mathematical symbols such as p
are not allowed. Every expression must include one 1, two 9's, and one 7, in
any order.
 155

Solution. There are several acceptable answers for this question. Here
are some:
1 7  (9 , 9) + 1
=
2 (9 + 7)  (9 , 1)
=
3 9  (9 + 1 , 7)
=
4 (9 , 1)  (9 , 7)
=
5 (9 + 1)  (9 , 7) = 7 , (9  9) , 1
=
6 9,9+7,1
=
7 9 , 9 + 7  1 = (9 , 9)  1 + 7
=
8 9,9+7+1
=
9 99+7+1
=
10 9+9,7,1
=
3. (a) Decide whichpis greater: p6 + p8 or p5 + p9.
p p p
Solution. Let x = 6 + 8 and y = 5 + 9. Then
p
x = 6 + 8 + 2 48 = 14 + 2 48
2
p
p p
y = 5 + 9 + 2 45 = 14 + 2 45
2

p p
Since 48 > 45, we see that x > y and thus it follows that
2 2
p x >py since
both are positive real numbers. Therefore, the larger value is 6 + 8.
(b) Show that x2x  2 for any real number x > 0.
+1

Solution. Note that (x , 1)  0 for all real numbers x. This can be

2

rewritten as x , 2x + 1  0, and thus we have x + 1  2x. Since we are

2 2

given x > 0 we can divide both sides of the inequality by x and preserve the
direction of the inequality to get
x + 1  2:
2

x
4. In the plane gure shown below, ABCD is a square with AB =
12. If A0 , B0 , C 0 , and D0 are the midpoints of AO, BO, CO, and DO,
respectively, then:
A B
A 0
B 0

D 0
C 0

D C
156

(a) Find the area of the square A0 B 0 C 0 D0 .

Solution. Triangles AOB and A0 OB 0 are similar since both are isosce-
les right angled triangles. Since A0 O is one half the length of AO we see that
A0 B0 is also one half the 0length of AB ; that is, A0 B 0 is 6 units in length,
which makes the square A B 0 C 0 D0 have area 36 square units.
(b) Find the area of the shaded region.
Solution. Triangle BA0 B 0 has a base A0 B 0 of 6 units, and an altitude
which is one half of the altitude of triangle AOB (from its base AB ); that is,
triangle BA0 B 0 has altitude 3 from its base A0 B 0 . Thus the area of triangle
BA0 B0 is
6
3 = 9 square units. Since the shaded area comprises 4 such
1

triangles, the total shaded area is 36 square units.

2

Alternate method for (b): Triangles A0 OB and A0 B 0 B have the same

altitude from the base OB 0 B , and they have the same length for a base, since
B0 is the midpoint of OB . Thus their areas must be the same. But the area
of triangle A0 OB 0 is clearly of the area of the square A0 B 0 C 0 D0 computed
1

in part (a); that is, 9 square units. Thus, triangle BA0 B 0 has area 9 and we
4

nish as in the rst method.

(c) Find the area of the trapezoid AA0 B 0 B .
Solution. Since the parallel sides of the trapezoid have lengths 12 and 6,
and since its altitude is 3 (as seen in part (b) above), we see that the area of
the trapezoid is:
1 3(6 + 12) = 27:
2
Alternate method for (c): The area we seek is of the di erence be-
1

tween the areas of the squares ABCD and A0 B 0 C 0 D0 , which is:

4

1 (12 , 6 ) = 1 (144 , 36) = 27:

2 2

4 4
5. The gure below shows the rst three in a sequence of square arrays
of dots. The numbers of dots in the three arrays are 1, 5, and 13.
r r r

r r r r

r r r r r

r r r r

r r r

(a) Find the number of dots in the next array in the sequence.
Solution. There are several ways of looking at the arrays. One way is to
notice that in going from one array to the next we build around the outside
of the array a new set of dots. That is, we add 4 dots to the single dot to get
 157

array 2. We then add 4
2 = 8 dots around array 2 to get array 3. We would

then add 4
3 = 12 dots around array 3 to get array 4. This leaves us with
13 + 12 = 25 dots in the next array.
(b) Find the number of dots in the sixth array in the sequence.
Solution. To carry on to array 6 we need rst to get array 5 from array
4. Using the process described in part (a) we would get 25 + 4
4 = 41 dots
in array 5 and 41 + 4
5 = 61 dots in array 6.
(c) Find an expression for an in terms of n alone.
Solution. By observing the dot pattern, the number of dots seems to
be in the order of n . If we subtract n from an for the rst few values of n
2 2

we see that what remains is (n , 1) . Since an = n + (n , 1) satis es the

2 2 2

relation from part (d) above, and since it coincides with the rst few values
of an , this must be the solution for an .
(d) If an is the number of dots in the n array in the sequence, nd a
th

relation between an , an , and n.

+1

Solution. From the above analysis, if we denote by an the number of

dots in the n array, then
th

an = an + 4n:
+1

That completes the Skoliad Corner for this number. I need contest
materials suited to this feature, so please send me your materials, as well as
comments and suggestions for the future of the Skoliad Corner.
158

MATHEMATICAL MAYHEM
Mathematical Mayhem began in 1988 as a Mathematical Journal for and by
High School and University Students. It continues, with the same emphasis,
as an integral part of Crux Mathematicorum with Mathematical Mayhem.
All material intended for inclusion in this section should be sent to the
Mayhem Editor, Naoki Sato, Department of Mathematics, Yale University,
PO Box 208283 Yale Station, New Haven, CT 06520{8283 USA. The electronic
address is still
mayhem@math.toronto.edu
The Assistant Mayhem Editor is Cyrus Hsia (University of Toronto).
The rest of the sta consists of Adrian Chan (Upper Canada College), Jimmy
Chui (Earl Haig Secondary School), Richard Hoshino (University of Waterloo),
David Savitt (Harvard University) and Wai Ling Yee (University of Waterloo).

Mayhem Problems
The Mayhem Problems editors are:
Richard Hoshino Mayhem High School Problems Editor,
Cyrus Hsia Mayhem Advanced Problems Editor,
David Savitt Mayhem Challenge Board Problems Editor.
Note that all correspondence should be sent to the appropriate editor |
see the relevant section. In this issue, you will nd only problems | the
next issue will feature only solutions.
We warmly welcome proposals for problems and solutions. We request
that solutions from this issue be submitted by 1 February 1999, for publica-
tion in issue 4 of 1999. Also, starting with this issue, we would like to re-open
the problems to all CRUX with MAYHEM readers, not just students, so now
all solutions will be considered for publication.

Erratum
We regret to report that the High School porblems in volume 24, issue 1
[1998: 42], were mislabelled. Instead of H223, H224, H225 and H226,
they should have been labelled H233, H234, H235 and H236 respectively.
We kindly ask readers to respect the new labelling when submitting solutions.
 159

High School Problems

Editor: Richard Hoshino, 17 Norman Ross Drive, Markham, Ontario,
Canada. L3S 3E8 <rhoshino@undergrad.math.uwaterloo.ca>
H237. The letters of the word MATHEMATICAL are arranged at ran-
dom. What is the probability that the resulting arrangement contains no
adjacent A's?
H238. Johnny is dazed and confused. Starting at A(0; 0) in the Carte-
sian grid, he moves 1 unit to the right, then r units up, r units left, r units
2 3

down, r units right, r units up, and continues the same pattern inde -
4 5

nitely. If r is a positive number less than 1, he will be approaching a point

B(x; y). Show that the length of the line segment AB is greater than . 7
10

H239. Find all pairs of integers (x; y) which satisfy the equation
y (x + 1) + x (y + 16) = 448.
2 2 2 2

H240. Proposed by Alexandre Trichtchenko, Brook eld High School,

Ottawa, Ontario.
A Pythagorean triple (a; b; c) is a triple of integers satisfying the equa-
tion a + b = c . We say that such a triple is primitive if gcd(a; b; c) = 1.
2 2 2

Let p be an odd integer with exactly n prime divisors. Show that there exist
exactly 2n, primitive Pythagorean triples where p is the rst element of
1

the triple. For example, if p = 15, then (15; 8; 17) and (15; 112; 113) are the
primitive Pythagorean triples with rst element 15.

Advanced Problems
Editor: Cyrus Hsia, 21 Van Allan Road, Scarborough, Ontario, Canada.
M1G 1C3 <hsia@math.toronto.edu>
A213. Show that the number of non-negative integer solutions to the
equation a + b + c + d = 98, where a  b  c  d, is equal to the number
of non-negative integer solutions to the equation p + 2q + 3r + 4s = 98.
A214. Show that any rational number can be written as the sum of
a nite number of distinct unit fractions. A unit fraction is of the form n , 1

where n is an integer.
A215. For a xed integer n  2, determine the maximum value of
k +


+ kn, where k , : : : , kn are positive integers with k +


+ kn  7n.
1 1
3
1
3

(Polish Mathematical Olympiad)

160

A216. Given a continuous function f : R ! R satisfying the condi-

tions:
f (1000) = 999;
f (x)
f (f (x)) = 1 for all x 2 R:
Determine f (500).
(Polish Mathematical Olympiad)

Challenge Board Problems

Editor: David Savitt, Department of Mathematics, Harvard University,
1 Oxford Street, Cambridge, MA, USA 02138 <dsavitt@math.harvard.edu>
Editorial Notes: Part (b) is the interesting part of C77. Part (a) is a
commonly asked problem, but I think it is better to ask it again than simply
to state it for use in (b).
C77. Let Fn denote the n Fibonacci number, with F = 1 and
th

F = 1. (Then F = 2, F = 3, F = 5, etc.)
0

1 2 3 4
(a) Prove that each positive integer is uniquely expressible in the form
Fa1 +


+ Fak , where the subscripts form a strictly increasing sequence of
positive integers, no pairpof which are consecutive.
(b) Let  = (1 + 5), and for any positive integer n, let f (n) equal
1

the integer nearest to n. If n = Fa1 +


+ Fak is the expression for n

2

from part (a), prove that f (n) = Fa1 +


+ Fak .

+1 +1

C78. Let n be a positive integer. An n  n matrix A is a magic matrix

of order m if each entry is a non-negative integer
P and each row and column
sum is m. (That is, for all i and j , k Aik = k Akj = m.)
P

Let A be a magic matrix of order m. Show that A can be expressed as

the sum of m magic matrices of order 1.
 161

Tips on Inequalities
Naoki Sato
graduate student, Yale University

Inequalities can be dicult to solve because there are few systematic

methods for tackling even the most simple formulations. Indeed, solving
usually involves a trial and error of di erent approaches, before one hits
the right combination of estimations and manipulations. In this article, we
expose some useful standard approaches and techniques. We recall two basic
and fundamental inequalities:
AM-GM Inequality. For all x , x , : : : , xn  0,
1 2

x + x +


+ xn  pn x x


x ;
1 2

n 1 2n
with equality if and only if x = x =


= xn .
1 2

Cauchy-Schwarz Inequality (CSB). For all real xi , yi , i = 1, 2, : : : , n,

(x y + x y +


+ xn yn)  (x + x +


+ xn )(y + y +


+ yn );
1 1 2 2
2 2
1
2
2
2 2
1
2
2
2

with equality if and only if the vectors (x ; x ; : : : ; xn ) and (y ; y ; : : : ; yn)

1 2 1 2
are proportional.
Manipulating the Expressions
A typical approach in proving an inequality of the form A  B is to
nd intermediate expressions, so we have a chain
A  P  P 


 Pn  B:
1 2

These are usually found through using the classic inequalities, and by manip-
ulating terms until we get what we want. As anyone who has worked with
inequalities knows, this takes great care; one constantly has to make sure
that the estimates are not too crude, and that the inequality signs are going
the right way. In this kind of approach, there are several things one should
keep in mind:
1. Is the inequality sharp or strict?
An inequality is sharp if equality occurs at a point, and strict if equal-
ity never occurs. It is always a good idea to check which type it is, though
it is usually given or obvious. A strict inequality may allow for generous
estimates, but not always. A sharp inequality leaves no such allowance.
2. If equality does occur, when/where does it occur?
Copyright c 1998 Canadian Mathematical Society
162

The points where equality occurs are points you must work around. In
the chain above, each intermediate inequality must become an equality at
these points. This is a good check of whether your intermediate expressions
are the right ones.
Pairing and Grouping
In inequalities where several terms are involved, it might be possible
to group terms together and prove \smaller" inequalities.
Problem 1.
(a) Prove that x + y + z  xy + yz + zx for all x, y , z 2 R.
2 2 2

(b) Prove that x + y + z  x y + y z + z x for all x, y , z  0.

3 3 3 2 2 2

Solution. (a) No grouping is immediately obvious. We know x + y  2 2

2xy, but how can we incorporate this? By adding x + y  2xy , y + z  2 2 2 2

2yz, and z + x  2zx, and dividing by 2, we obtain the desired inequality.

2 2

(b) Here, we know 2x + y = x + x + y  3x y by AM-GM. We

3 3 3 3 3 2

then add the other two corresponding inequalities, and then divide by 3.
Problem 2. For all a, b, c, d > 0, show that
a3 + b3 + c3 + a3 + b3 + d3 + a3 + c3 + d3 + b3 + c3 + d3  a2 + b2 + c2 + d2 :
a+b+c a+b+d a+c+d b+c+d
Solution. We claim that
a +b +c  a +b +c :
3 3 3 2 2 2

a+b+c 3
Then, the problem follows by symmetry. Our inequality is equivalent to
3a + 3b + 3c  (a + b + c )(a + b + c) ;
3 3 3 2 2 2

which, in turn, is equivalent to

2a3 + 2b3 + 2c3 , a2 b , ab2 , a2 c , ac2 , b2 c , bc2
= (a , a b , ab + b ) + (a , a c , ac + c ) + (b , b c , bc + c )
3 2 2 3 3 2 2 3 3 2 2 3

= (a , b) (a + b) + (a , c) (a + c) + (b , c) (b + c)  0 ;
2 2 2

which is true. Note that this inequality also follows from Chebyshev's in-
equality.
The Cauchy-Schwarz Inequality
The Cauchy-Schwarz inequality is a good way to deal with squares and
especially fractions.
Problem 3. For x , x , : : : , xn > 0, show that
1 2

+ xx +


+ xn  x + x +


+ xn :
2
1
2
2
2
1 2

x +x x +x
1 2 xn + x
2 23 1
 163

Solution. By CSB,
[(x + x ) + (x + x ) +


+ (xn + x )]
1 2 2 3 1

 x x+ x + x x+ x +


+ x x+n x
 
2 2 2
1 2

1n 2 2 3 1

 (x + x +


+ xn) : 1 2
2

The result then follows by dividing each side by 2 (x + x +


+ xn ). 1 2

Problem 4. Prove that for a , a , : : : , an > 0, 1 2

(a + a +


+ an )  a + a +


+ an :
1 2
2
1 2

2(a + a +


+ an ) a + a a + a
2
1
2
2
2 a +a 2 3 3 4 1 2

(1990{1991 IMO Correspondence)

Solution. Recall that CSB states that for all real xi , yi, i = 1, 2, : : : , n,
xy
( 1 1+ x2 y2 +


+ xn yn )2  ,x21 + x22 +


+ x2n
,y12 + y22 +


+ yn2
:
Setting xi = p4 ai , yi = 4 ai , we obtain
p
3

(a + ,a +


+ an ) 2

 pa + pa +


+ pan
,a pa + a pa +


+ anpan
:
1 2

1 2 1 1 2 2

Setting xi = pai , yi = ai , we obtain

,
a pa + a pa +


+ a,npan

1 1 2 2
2

 (a + a +


+ an) a + a +


+ an
:
1 2
2
1
2
2
2

Combining these two, we obtain

(a + a +


+ an) 3

 ,pa + pa +


+ pan
,a + a +


+ an
:

1 2
2 2 2 2
1 2 1 2

q
Finally, setting xi = ai + ai , yi = ai+1aiai+2 , we obtain
p
+1 +2 +

, pa + pa +


+ pan

1 2
2


a a a n

 2 (a + a +


+ an) a + a + a + a +


+ a + a : 1 2
1 2
2 3 3 4 1 2

The last two inequalities give the desired result.

Elementary Symmetric Polynomials
Given a set of variables X , such as X = fx; y;z g, a polynomial is sym-
metric in X if it is invariant under any permutation of the variables under X ,
and homogeneous of degree k if every term in the polynomial has degree k.
164

For example, x + y + z , xyz is symmetric but not homogeneous in X ,

2 2 2

and x + x y , xyz is homogeneous of degree 3 but not symmetric in X .

3 2

The elementary symmetric polynomials in X are the polynomials ob-

tained as the sum of the products of the variables in X , taken k at a time.
For X = fx; y;z g, these would be x + y + z , xy + xz + yz , and xyz . Note
that each of these is homogeneous. A theorem of Gauss states that any sym-
metric, homogeneous polynomial in X can be expressed as a polynomial in
these elementary polynomials.
After all these tedious de nitions, we nally get to the point that it can
be useful to use these elementary polynomials.
Problem 5. For non-negative reals x, y , and z satisfying x + y + z = 1,
show that    
1 +1 1 +1 1 + 1  64 :
x y z
Proof. Expanding, we rst must show
1 + x1 + y1 + 1z + xy
1 + 1 + 1 + 1  64 :
xz yz xyz
By AM-GM,
xyz  x + y3 + z = 27
1 1  27 :
  3

so that
xyz
Therefore,
1 + x1 + y1 + 1z + xy
1 + 1 + 1 + 1
xz yz xyz
 1+ 3 3 + 1
p3 xyz 3 x y z
+p 2 2 2 xyz

1 
= 1 + p3 xyz
3

 4 = 64 :
3

Problem 6. Prove that

7;
0  yz + zx + xy , 2xyz  27
where x, y , and z are non-negative real numbers for which x + y + z = 1.
(1984 IMO, #1)
Proof. Let S = xy + xz + yz , 2xyz , P = (1 , 2x)(1 , 2y )(1 , 2z ).
Then
P = 1 , 2(x + y + z) + 4(xy + xz + yz) , 8xyz = 4S , 1 :
 165

We must show that 0  S  , or equivalently, ,1  P  . Since

7 1

0  x; y;z  1, ,1  2x , 1; 2y , 1; 2z , 1  1, so ,1  P . Now, if
27 27

one of the variables, say x, was greater than 1=2, then the other two would
be less than 1=2, and we would have 1 , 2x < 0, 1 , 2y , 1 , 2z > 0, and
P < 0 < . Otherwise, x, y, and z are at most 1=2, and all factors of P
1

are non-negative, so by AM-GM,

27

P  1 , 2 x

+ 1 , 2 y + 1 , 2 z 
= 1:
3

3 27
Introducing and Removing Constraints
Inequalities often come with constraints on the variables. Removing
these constraints can simplify the problem. Alternately, introducing them
may help as well. The most common way of removing a constraint is to
\homogenize" the given inequality. For example, suppose we are given the
expression x + xy , 2, where xyz = 1. Then
3

x + xy , 2 = x + xy p3 xyz , 2xyz:
3 3

This new expression is homogeneous of degree 3. It's not pretty, but for
the expressions given in problems, most of the time it will be nice and much
easier to work with.
At this point, we introduce an inequality that is not well-known, but
that seems to pop up from time to time.
Schur's Inequality. For all x, y , z  0 and non-negative integers n,
xn(x , y)(x , z) + yn(y , z)(y , x) + zn(z , x)(z , y)  0 :
For n = 1, this becomes
x + y + z + 3xyz  x y + xy + x z + xz + y z + yz ;
3 3 3 2 2 2 2 2 2

or in shorthand, x + 3xyz  x y . This is a useful inequality to know,

P 3
P 2

with which we present another solution.

Problem 6. Prove that
7;
0  yz + zx + xy , 2xyz  27
where x, y , z are non-negative real numbers for which x + y + z = 1.
(1984 IMO, #1)
Solution. This is equivalent to the following problem: For x, y , z  0,
prove that
7 (x + y + z ) :
0  (yz + zx + xy )(x + y + z ) , 2xyz  27 3
166

This is the homogeneous version of the original inequality. The expression

in the middle expands to x y + xyz , which is clearly non-negative. We
P 2

focus on the right inequality, which becomes

P 2
7 P x + 7 P x y + 14 P xyz ;
x y + xyz  27 3 2
9 9
which implies
6 P x y  7 P x + 15xyz :
2 3

This is where we must think backwards. What results do we know that

we can use to prove this? By Schur's, 5 x y  5 x + 15xyz (we try
P P 2 3

to eliminate the xyz term). Hence, to prove the above inequality, we must
show that x y  2 x , which is left as an exercise for the reader (it has
P 2
P 3

been virtually done already in this article).

We stated early in the solution that the modi ed problem was equiva-
lent to the original problem. It is easy to see that the modi ed problem im-
plies the original problem (which is the only direction we actually needed),
but what about the converse? What if x + y + z 6= 1? In such a case, we can
normalize.
A property of homogeneous polynomials, and an alternate de nition,
is the following: p(x ; x ; : : : ; xn ) is homogeneous of degree k if
1 2

p(x ; x ; : : : ; xn ) = kp(x ; x ; : : : ; xn)

1 2 1 2

for all  2 R.
Going back to the original problem,
p(x; y; z) = (yz + zx + xy)(x + y + z) , 2xyz :
If x + y + z = 0, then all three variables must be 0, and the inequality
follows. Otherwise, we can set  = x y z , and so we must show
1
+ +

0  p x + xy + z ; x + yy + z ; x + zy + z  27 7:
 

This is the original problem. Thus, we can set x + y + z equal to 1, or

indeed anything we want to (except 0). It can be vital to exploit this degree
of freedom. We perform a similar setting in the next problem.
Problem 7. Given 0 < a  b, and x , x , : : : , xn  0, show that
1 2

(xa1 + xa2 +


+ xan )1=a  (xb1 + xb2 +


+ xbn)1=b :

Solution. If xb1 + xb2 +


+ xbn = 0, then the problem is solved.
Otherwise, by the arguments above, we can assume xb1 + xb2 +


+ xbn = 1.
Then
xbi  1 =) xi  1 =) xbi ,a  1 =) xbi  xai
=) xa + xa +


+ xan  xb + xb +


+ xbn = 1
1 2 1 2

=) (xa + xa +


+ xan) =a  1 = (xb + xb +


+ xbn ) =b:

1 2
1
1 2
1
 167

Problems
1. Prove that if x, y , and z are non-negative real numbers such that
x + y + z = 1, then
2(x + y + z ) + 9xyz  1 :
2 2 2

2. For any real numbers a, b, and c, show that

min (a , b) ; (b , c) ; (c , a)  a + b2 + c :
 2

2 2
2 2 2

3. Let a, b, and c be the sides of a triangle with perimeter 2. Prove that

a + b + c + 2abc < 2.
2 2 2

4. For non-negative reals x, y , and z satisfying 2xyz + xy + xz + yz = 1,

prove that x + y + z  . 3
2

5. For all positive integers n, show that

1
3
5


2n , 1  p 1 :
2 4 6 2n 3n + 1
(Hint: The inequality is almost certainly not sharp, so there is some
room for approximation. The RHS suggests squaring.)
6. Show that if x, y , and z are non-negative reals such that x + y + z = 1,
then 
1 ,1
 
1 ,1 
1 ,1  8:
x y z
(Note: The solution in Problem 5 does not work!)
7. Given a, b, c, d, e > 0, abcde = 1, show that
a + b + c + d + e  a + b+ c +d + e:
4 4 4 4 4

(A favourite of Ravi Vakil's. Find as many di erent solutions as you

can.)
8. Show that if non-negative reals a, b, and c satisfy
1 + 1 + 1 = 1;
1+a 1+b 1+c
then abc  8.
168

Riveting Properties of Pascal's Triangle

Richard Hoshino
student, University of Waterloo

Consider the following table of integers, known as Pascal's Triangle:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
..
.
This table is named after the French mathematician Blaise Pascal, who
conceived of it at the age of thirteen (although the Chinese discovered some
properties of this triangle in the early 14 century, centuries before Pascal
th

was even born!).

To generate a row of Pascal's Triangle, look at the row immediately
above it. Each element of the triangle is the sum of the two elements above
it (for example, the second element of the fourth row is 4 because 4 = 1+3).
By convention, we denote the top row as the 0 row, and we denote the left
th

most entry of each row as the 0 entry, even though it may seem a little
th

awkward at rst.
Let us show that this table is the same as the following table:
,0

,1
0 ,1

,2
0 ,2
1 ,2

,3
0 ,3
1 ,3
2 ,3

,4
0 ,4
1 ,4
2 ,4
3 ,4

,5
0 ,5
1 ,5
2 ,5
3 ,5
4 ,5

0 1 2 3 4 5
..
.
,n

In this table, k is determined by the formula k nn,k . Thus, we
!(
!
,n

will
)!
show that the k element of the n row of Pascal's Triangle equals,
k ,for
th th


all integers
,
,
,

n and k . Each of these elements in the triangle, namely , , 0 1

, , , : : : , is called a binomial coecient, since the coecients of the

0 0
1 2 2

expansion of the binomial (1 + x)n correspond to the entries of the n row

1 0 1
th

Copyright c 1998 Canadian Mathematical Society

 169

of Pascal's Triangle (for example, (1 + x) = x + 4x + 6x + 4x + 1). Let

4 4 3 2

us prove these statements, as they will be fundamental to our analysis of the

properties of Pascal's Triangle.
Now nk denotes the number of ways
,

,n

we may select k objects from a
set of n objects. By convention, we let = 1, since there is technically
only \one" way we may select nothing from a set of n objects. Let us show
0

that
n + n = n+1
     

k k,1 k
for all n and k. Note that the right side denotes the number of ways we may
select a k-member committee from a class of n girls and one boy (we choose
k members from , a
set of (n +1) people). Now, if the boy is on the committee,
then we have k,n ways of selecting the,remaining k , 1 members. And if he
is not on the committee, then there are nk ways of selecting the committee.
1

Hence,
n + n = n+1 :
     

k k,1 k
This is known as Pascal's Identity.
,

Since 0
= 1, the table of binomial coecients corresponds directly
to Pascal's Triangle { since the initial element is the same and, like Pascal's
0

Triangle, each element is the sum of the two directly above it. Thus, we can
determine any element in Pascal's Triangle with this formula. For example,
,

the thirty- fth element in the seventy-ninth row of Pascal's Triangle is . 79
35

We now prove that the entries in the n row of Pascal's Triangle are
th

the coecients in the expansion of (1 + x)n . We proceed by induction. The

case is trivial for n = 1. Suppose that
(1 + x)n = n + nx + nx +


+ nxk +


+ nxn
 
2

0 1 2 k n
for some n. Then
)n  = (1+ x)n(1 + x)
(1 + x +1

= 0 + 1 x + 2 x +


+ nn xn (1 + x)
n n n   
2

= n + n + n x +


+ n +  n  xn + nxn :

 
+1

0 1 0 n n,1 n
Since n = n = nn = nn = 1, and using Pascal's Identity for
,
,

+1
,
, +1

,
at the case for n + 1. Hence, the

0 0 +1
all the other terms, we immediately arrive
coecient of xk in (1 + x)n is equal to nk .
Now we illustrate some of the really neat properties of Pascal's
Triangle.
170

Theorem 1.
(i) The sum of the coecients in the n row of Pascal's Triangle is 2n .
th

(ii) If we alternately add and subtract the digits in the n row of Pascal's th

Triangle, we always arrive at zero. For example, 1 , 4 + 6 , 4 + 1 = 0

for n = 4.
Proof. (i) Since
(1 + x)n = n + nx +


+ nxk +


+ nxn;
 

0 1 k n
substituting x = 1 into this expression yields
2n = n0 + n1 +


+ nn :
     

(ii) The second part of the theorem is left as an exercise. It is the same
technique as above; just substitute a di erent value for x. Can you guess
which value of x we ought to substitute?
Theorem 2. If the binary representation of n contains p ones, then there
are 2p odd numbers in the n row of Pascal's Triangle. For example, since
th

9 = 1001 , there are 2 = 4 odd numbers in the ninth row.

2
2

Proof. We shall analyze everything in modulo 2. For those of you not

familiar with modular arithmetic, when we say that x is congruent to y mod-
ulo m, which is written x  y (mod m), we mean that x and y are numbers
such that when both are divided by m, they give the same remainder. For
example, 1998 is congruent to 2 modulo 4. Also, if r  0(mod 2), then r is
even.
We rst show that
(1 + x) n  1 + x n (mod 2)
2 2

for all non-negative integers n. We proceed by induction. If n = 0, the claim

is immediate. Suppose the claim is true for some n = k. Then
(1+x) k+1  ((1+x) k )  (1+x k )  1+2x k +x k+1  1+x k+1(mod 2);
2 2 2 2 2 2 2 2

and so it is also true for n = k + 1. Hence, by induction, the claim has been
veri ed.
Here is an example for a speci c case. Let n = 50. Then 50 = 2 + 1

2 + 2 = 2 + 16 + 32. Hence,
4 5

(1 + x) 50
= (1 + x) (1 + x) (1 + x)
2 16 32

 (1 + x )(1 + x )(1 + x )
2 16 32

 1 + x + x + x + x + x + x + x (mod 2):
2 16 18 32 34 48 50
 171

Hence, there are eight odd entries in the 50 row of Pascal's Triangle, th
,
,
,
,
,
,
,
,

namely , , , , , , , and . Since 50 = 11010 ,
50
0
50
2
50
16
50
18
50
32
50
34
50
48
50
50 2

this veri es that there are exactly 2 = 8 odd terms in this row.
3

For a general n, suppose there are p ones in the binary representation

of n. Then
(1 + x)n = (1 + x) a1 (1 + x) a2


(1 + x) ap ;
2 2 2

where 0  a < a <


< ap and the ai digit of the binary representation
th

of n is 1, starting from 0 at the right. The right side is congruent to

1 2

(1 + x a1 )(1 + x a2 )


(1 + x ap )
2 2 2

modulo 2, and when we expand the right side, we will arrive at an expression
with 2p terms. Note that there must be exactly 2p terms, since each exponent
xk can be formed in only one way by multiplying coecients from the set
fx a1 ; x a2 ; : : : ; x ap g. This is a direct result from the binary representation
2 2 2

of k. Hence, if n has p ones in its binary representation, (1 + x)n modulo 2

has 2p terms, and hence there are 2p odd entries in the n row of Pascal's th

Triangle.
Theorem 3. (The Fibonacci sequence is the sequence, 1, 1, 2, 3, 5, 8,
13, 21, 34, : : : , where each element in the sequence is the sum of the two
before it. More formally, we say that the Fibonacci sequence fFn g satis es
the conditions F = 1, F = 1, and Fn = Fn, + Fn, for all n > 1.)
0 1 1 2
We can derive the Fibonacci sequence from Pascal's Triangle in the following
manner.
F =1 - 1
F
0
=1 - 1  : 1:
F - 1: 2
1
=2 1
F
2
=3 - 1
: 3 :
 3 1
F - 1
: 4  6
3
=5 4 1
F
4

5 =8 - 1 5 10 10 5 1
..
.

In other words, for all n, we have

2
2  
2
n ,
F n = 0 + 1 + 2 +


+ nn
n 1  
2 n , 2  

and
2 n + 1 
2
 
n
2 n ,
F n = 0 + 1 + 2 +


+ n :
2 +1
1  
n + 1 
172

For example,
F = 70 + 61 + 52 + 43 = 1 + 6 + 10 + 4 = 21:
       
7

Proof. We prove this theorem using double induction: we know that

the claim is true for F and F . Suppose the claim is true for some F k and
F k . Then we want to show that
0 1 2

2 +1

F k = 2k 0+ 2 + 2k 1+ 1 + 22k +


+ kk + 1;
      
2 +2
+1
that is, the right side is equal to the (2k + 2) Fibonacci number. But
th

F k = F k + F 
2 +2 2 k   
2 +1

= 2 k + 1 + 2k + 2k +


+ k + 1 + k + 1 + k

0   0  1  k , 1   k k
= 2k 0+ 1 + 2k 1+ 1 + 22k +


+ k +k 2 + kk ;
 

by Pascal's Identity. Since k =1= k and kk = 1 = kk

,
,
,
,

2 +1
0
2 +2
0
+1
+1
, we
have
F k = 2k 0+ 2 + 2k 1+ 1 + 22k +


+ kk +
      
1;
2 +2
+1
as required.
The second part of the induction follows similarly { assume the claim is
true for F k, and F k, and show that the claim is also true for F k . The
2 1 2 2 +1
proof is left as an exercise. Now we are done { since the proposition is true
for k = 0 and k = 1, it is true for k = 2. Since it is true for k = 1 and k = 2,
it is true for k = 3, etc. Then by double induction, the claim is true for all
non-negative integers n.
Exercises
1. Show that nk = n,n k , and use this fact to show that Pascal's Triangle
,
,

is symmetric about the vertical line that separates the triangle into two
equal halves.
2. For which n is nn odd?
,
2

3. Let an represent the number of elements in the n row of Pascal's th

Triangle that are congruent to 1 modulo 3. Let bn represent the number

of elements in the n row of Pascal's Triangle that are congruent to 2
th

modulo 3. Prove that for all n, an , bn is a power of two.

(This problem was on the IMO short list one year { it is very tough!)
 173

Swedish Mathematics Olympiad

1985 Qualifying Round
1. The real numbers a, b, and c satisfy the equations
ab + b = ,1
bc + c = ,1
ca + a = ,1
Calculate the product abc.
2. 1985 runners reported for a marathon. They were assigned the num-
bers 1, 2, : : : , 1985. However, a number of runners dropped out be-
fore the race. In fact, among the starting runners, there were no two
for whom one runner's number was 10 times the other. What is the
greatest number of runners that could have participated?
3. In the system of equations
a x+b y+c z+d u = 0
1 1 1 1

a x+b y+c z+d u = 0

2 2 2 2

a x+b y+c z+d u = 0

3 3 3 3

a x+b y+c z+d u = 0

4 4 4 4

the coecients a , b , c , and d are even integers and the other co-
1 2 3 4
ecients are odd integers. Prove that the only solution in integers is
x = y = z = u = 0.
4. The non-negative integers p, q , r, and s satisfy the equality
(p + q ) + p = (r + s) + r:
2 2

Show that p = r and q = s.

5. Let f be de ned by
f (x) = 4x xsinsinxx + 9 :
2 2

Find the least value of f over the interval 0 < x <  .

6. The point P lies on the perimeter or inside a given triangle T . The point
P 0, in the plane of the triangle, lies at a distance d from P0 . Let r and r0
be the radii of the smallest circles, with centres P and P respectively,
which contain T . Show that
r + d  3r 0 :
Give an example where equality holds.
174

1985 Final Round

1. Let a > b > 0. Prove that
(a , b) < a + b , pab < (a , b) :
2 2

8a 2 8b
2. Find the least natural number such that if the rst digit is placed last,
the new number is 7=2 times as large as the original number. (The
numbers are written in the decimal system.)
3. A, B , and C are three points on a circle with radius r, and AB = BC .
D is a point inside the circle such that the triangle BCD is equilateral.
The line through A and D meets the circle at the point E . Show that
DE = r.
4. The polynomial p(x) of degree n has real coecients, and p(x)  0 for
all x. Show that
p(x) + p0(x) + p00(x) +


+ p n (x)  0:
( )

5. In a right-angled coordinate system, a triangle has vertices A(a; 0),

B(0; b), and C (c; d), where the numbers a, b, c, and d are positive.
Show that if we denote the origin by O,
AB + BC + CA  2CO:
6. X-wich has a vibrant club-life. For every pair of inhabitants there is
exactly one club to which they both belong. For every pair of clubs there
is exactly one person who is a member of both. No club has fewer than
3 members. At least one club has 17 members. How many people live
in X-wich?
 175

PROBLEMS
Problem proposals and solutions should be sent to Bruce Shawyer, De-
partment of Mathematics and Statistics, Memorial University of Newfound-
land, St. John's, Newfoundland, Canada. A1C 5S7. Proposals should be ac-
companied by a solution, together with references and other insights which
are likely to be of help to the editor. When a submission is submitted with-
out a solution, the proposer must include sucient information on why a
solution is likely. An asterisk (?) after a number indicates that a problem
was submitted without a solution.
In particular, original problems are solicited. However, other inter-
esting problems may also be acceptable provided that they are not too well
known, and references are given as to their provenance. Ordinarily, if the
originator of a problem can be located, it should not be submitted without
the originator's permission.
To facilitate their consideration, please send your proposals and so-
lutions on signed and separate standard 8 "11" or A4 sheets of paper.
1

These may be typewritten or neatly hand-written, and should be mailed to

2

the Editor-in-Chief, to arrive no later than 1 November 1998. They may also
be sent by email to crux-editors@cms.math.ca. (It would be appreciated if
email proposals and solutions were written in LATEX). Graphics les should
be in epic format, or encapsulated postscript. Solutions received after the
above date will also be considered if there is sucient time before the date
of publication. Please note that we do not accept submissions sent by FAX.

2306. Proposed by Vedula N. Murty, Visakhapatnam, India.

CORRECTION to (a) Give an elementary proof of the inequality:
 
x
sin 2

> 1 2+x x ;
2 2
(0 < x < 1): (1)
2

2326?. Proposed by Walther Janous, Ursulinengymnasium, Inns-

bruck, Austria.
Prove or disprove that if A, B and C are the angles of a triangle, then
2 < X
,
1 , sin A
,1 + 2 sin A
 9 :
,A
2 2
 cyclic

2327. Proposed by Christopher J. Bradley, Clifton College, Bristol,
UK.
The sequence fan g is de ned by a = 1, a = 2, a = 3, and
1 2 3

an = an , an, + aan ; n  3 :
2

n,
+1 1
2

Prove that each an 2 N, and that no an is divisible by 4.

176

2328?. Proposed by Walther Janous, Ursulinengymnasium, Inns-

bruck, Austria.
It is known from Wilson's Theorem that the sequence fyn : n  0g,
with yn =
n! + 1 , contains in nitely many integers; namely, y 2 N if and
n+1 n
only if n + 1 is prime.
(a) Determine all integer members of the sequences fyn(a) : n  0g, with
yn = n! + a , in the cases a = 2, 3, 4.
n+a
(b) Determine all integer members of the sequences fyn (a) : n  0g, with
yn = nn!++ aa , in the cases a  5.
2329?. Proposed by Walther Janous, Ursulinengymnasium, Inns-
bruck, Austria.
Suppose that p and t > 0 are real numbers. De ne
p(t) := tp + t,p + pp and p(t) := ,t + t,
p + 2 : 1

(a) Show that p (t)  p (t) for p  2.

(b) Determine the sets of p: A, B and C , such that
1. p (t)  p (t),
2. p (t) = p (t),
3. p (t)  p (t).
2330. Proposed by Florian Herzig, student, Perchtoldsdorf, Austria.
Prove that
e = 3 , 11!
3 + 3 2! , 3! + 4! , 5! + : : : ;

11 11
53 53
309 309
2119
where
11 = 3
3 + 2
1;
53 = 4
11 + 3
3;
309 = 5
53 + 4
11;
2119 = 6
309 + 5
53;
..
.
[Ed: There is enough information here to deduce the general term.]
2331. Proposed by Paul Yiu, Florida Atlantic University, Boca Ra-
ton, Florida, USA.
Let p be an odd prime. Show that there is at most one non-degenerate
integer triangle with perimeter 4p and integer area. Characterize those primes
for which such triangles exist.
 177

2332. Proposed by D.J. Smeenk, Zaltbommel, the Netherlands.

Suppose x and y are integers. Solve the equation
x y , 7x y + 12x , 21xy , 4y + 63x + 70y , 174 = 0:
2 2 2 2 2

2333. Proposed by D.J. Smeenk, Zaltbommel, the Netherlands.

You are given that D and E are points on the sides AC and AB re-
spectively of 4ABC . Also, DE is not parallel to CB . Suppose F and G are
points of BC and ED respectively such that
BF : FC = EG : GD = BE : CD:
Show that GF is parallel to the angle bisector of \BAC .
2334. Proposed by Toshio Seimiya, Kawasaki, Japan.
Suppose that ABC is a triangle with incentre I , and that BI , CI meet
AC , AB at D, E respectively. Suppose that P is the intersection of AI with
DE. Suppose that PD = PI .
Find angle ACB .
2335. Proposed by Toshio Seimiya, Kawasaki, Japan.
Triangle ABC has circumcircle ,. A circle ,0 is internally tangent to ,
at P , and touches sides AB , AC at D, E respectively. Let X , Y be the feet
of the perpendiculars from P to BC , DE respectively.
Prove that PX = PY sin A . 2

2336. Proposed by Toshio Seimiya, Kawasaki, Japan.

The bisector of angle A of a triangle ABC meets BC at D. Let , and ,0
be the circumcircles of triangles ABD and ACD respectively, and let P , Q
be the intersections of AD with the common tangents to ,, ,0 respectively.
Prove that PQ = AB
AC .
2

2337. Proposed by Iliya Bluskov, Simon Fraser University, Burnaby,

BC.
Let F (1) =

n + 2n + 2 , and, for each i > 1, let
2

n +n+1  2

F (i) =

n + 22
n + i + 1 F (i , 1) .
n +n+i 2

Find F (n).

Some readers have pointed out that problem 2287 [1997: 501] is the
same as problem 2234 [1997: 168], and that problem 2288 [1997: 501] is
the same as problem 2251 [1997: 299]. Also part (a) of problem 2306 [1998:
46; 175] is the same as the rst part of 2296 [1997; 503]. The editors missed
these duplications. Proposers are asked not to submit the same problem
more than once.
178

SOLUTIONS
No problem is ever permanently closed. The editor is always pleased to
consider for publication new solutions or new insights on past problems.

2219. [1997: 110] Proposed by Christopher J. Bradley, Clifton Col-

lege, Bristol, UK.
Show that there are an in nite number of solutions of the simultaneous
equations:
x , 1 = (u + 1)(v , 1)
2

y , 1 = (u , 1)(v + 1)
2

with x; y;u; v positive integers and x 6= y .

I. Solution by Charles Ashbacher, Cedar Rapids, Iowa, USA; Edward
J. Barbeau, University of Toronto, Toronto, Ontario; Charles R. Diminnie,
Angelo State University, San Angelo, TX, USA; Florian Herzig, student, Per-
chtoldsdorf, Austria; Cyrus Hsia, student, University of Toronto, Toron-
to, Ontario; Walther Janous, Ursulinengymnasium, Innsbruck, Austria; and
Vaclav Konecny, Ferris State University, Big Rapids, Michigan, USA.
For positive integers n, the quadruples
(x; y;u; v ) = (1; 2n + 1; 2n + 2n + 1; 1)
2

give an in nite set of solutions in which x 6= y , since

2
x , 1 = (u + 1)(v , 1) = 0
and
y , 1 = 4n + 4n = (u , 1)(v + 1):
2 2

II. Solution by Edward J. Barbeau, University of Toronto, Toronto, On-

tario; Digby Smith, Mount Royal College, Calgary, Alberta; and the pro-
poser.
For any positive integer n, the quadruple
(x; y; u; v ) = (2n , n; 2n + n; 4n + n; n)
2 2 3

is a solution in which x 6= y , since

x , 1 = (u + 1)(v , 1) = 4n , 4n + n , 1
2 4 3 2

and
y , 1 = (u , 1)(v + 1) = 4n + 4n + n , 1:
2 4 3 2

III. Solution by Charles R. Diminnie, Angelo State University, San An-

gelo, TX, USA; and Zun Shan and Edward T.H. Wang, Wilfrid Laurier Univer-
sity, Waterloo, Ontario.
 179

It is well known that the Pell equation s , 2t = 1 has in nitely many

2 2

solutions in positive integers s, t. Clearly, s > t > 1.

If we set u = s + t, v = s , t, x = t , 1 and y = t + 1, then
(u + 1)(v , 1) = s , (t + 1) = t , 2t = (t , 1) , 1 = x , 1, and
2 2 2 2 2

(u , 1)(v + 1) = s , (t , 1) = t + 2t = (t + 1) , 1 = y , 1.
2 2 2 2 2

Also solved by MANSUR BOASE, student, St. Paul's School, London,

England; FLORIAN HERZIG, student, Perchtoldsdorf, Austria (a second
solution); RICHARD I. HESS, Rancho Palos Verdes, California, USA;
MICHAEL LAMBROU, University of Crete, Crete, Greece (two solutions);
GERRY LEVERSHA, St Paul's School, London, England; and PANOS E.
TSAOUSSOGLOU, Athens, Greece.
The families given by I, II and III above, do not exhaust all the possi-
ble solutions. It is interesting to note that the \smallest" solution produced
by all these families is (1; 3; 5; 1). The next smallest ones are (1; 5; 13; 1),
(6; 10; 34; 2) and (11; 13; 29; 5), respectively. Both Herzig and Leversha ob-
tained another in nite set of solutions in which v = 2, by considering the
Pell equation 3x , y = 8. Their \smallest" solution is (6; 10; 34; 2) listed
2 2

above. However, the next solution, (22; 38; 482; 2) is not obtainable from
any of the families given in I, II and III.

2220. Proposed by Joaqun Gomez  Rey, IES Luis Bu~nuel, Alcorcon,

Madrid, Spain.
Let V be the set of an icosahedron's twelve vertices, which can be par-
titioned into four classes of three vertices, each one in such a way that the
three selected vertices of each class belong to the same face.
How many ways can this be done?
Solution by Florian Herzig, student, Perchtoldsdorf, Austria.
I will prove that there are 10 di erent ways of partitioning the vertices
of an icosahedron in the described manner. Since only the topological prop-
erties of the icosahedron are important, consider the graph of the vertices:
see gure on next page.
We want to nd four triangles in this graph such that each vertex is
used exactly once. Consider the vertex A. There are ve triangles having
A as vertex. Because of (spatial) symmetry we may assume that triangle
ABM is chosen. Thus for the triangle containing point C only two choices
remain: 4CFL and 4CFK . Without loss of generality we may assume that
triangle CFL is chosen. Now notice that the only \free" triangle containing
D is 4DZY and nally 4EKX remains.
We have covered all possibilities already. For this case there are two
di erent ways of nding \disjoint" triangles because we may choose from
two equivalent triangles for vertex C . If all ve possible triangles at vertex
180
A r

D
r

M r
L
r

Z Y
r r

E r X F
r

K
r

B r
C
r

A are considered, we get a total of 10 di erent con gurations as claimed.

Also solved by MANSUR BOASE, student, St. Paul's School, London,
England; JORDI DOU, Barcelona, Spain; RICHARD I. HESS, Rancho Palos
Verdes, California, USA; WALTHER JANOUS, Ursulinengymnasium, Inns-
bruck, Austria; MICHAEL LAMBROU, University of Crete, Crete, Greece;
and the proposer. There were two incorrect solutions.
Several solvers noted that the centres of the faces used in the partition
are the vertices of a tetrahedron.

2221. [1997: 111] Proposed by Sefket

 Arslanagic, University of Sara-
jevo, Sarajevo, Bosnia and Herzegovina.
Find all members of the sequence an = 3 n, + 2n, (n 2 N) which
2 1 1

are the squares of any positive integer.

Solution by David Doster, Choate Rosemary Hall, Wallingford, Con-
necticut, USA.
We have a = 4 and a = 29. For n  3, 3 n,  3(mod 4) and 2 1

,
2  0(mod 4). Thus, an  3(mod 4). But a positive integer is a
n 1
1 2

square only if it is congruent to 0 or 1(mod 4). Hence, a = 4 is the only1

square in the sequence.
Also solved by SAM BAETHGE, Nordheim, Texas, USA; FRANCISCO
BELLOT ROSADO, I.B. Emilio Ferrari, Valladolid, Spain and MARI A
ASCENSION  LOPEZ
 CHAMORRO, I.B. Leopoldo Cano, Valladolid, Spain;
MANSUR BOASE, student, St. Paul's School, London, England;
CHRISTOPHER J. BRADLEY, Clifton College, Bristol, UK; MIGUEL ANGEL
CABEZON  OCHOA, Logro~no, Spain; ADRIAN CHAN, student, Upper Canada
College, Toronto, Ontario; GORAN CONAR, student, Gymnasium Varazdin,
Varazdin, Croatia; YEO KENG HEE, Hwa Chong Junior College, Singapore;
 181

FLORIAN HERZIG, student, Perchtoldsdorf, Austria; RICHARD I. HESS,

Rancho Palos Verdes, California, USA; CYRUS HSIA, student, University of
Toronto, Toronto, Ontario; ROBERT B. ISRAEL, University of British
Columbia, Vancouver, BC; WALTHER JANOUS, Ursulinengymnasium, Inns-
bruck, Austria; MICHAEL LAMBROU, University of Crete, Crete, Greece;
KEE-WAI LAU, Hong Kong; GERRY LEVERSHA, St Paul's School, London,
England; GOTTFRIED PERZ, Pestalozzigymnasium, Graz, Austria; BOB
PRIELIPP, University of Wisconsin{Oshkosh, Wisconsin, USA; ISTVAN 
REIMAN, Budapest, Hungary; HEINZ-JURGEN SEIFFERT, Berlin, Germany;
D.J. SMEENK, Zaltbommel, the Netherlands; DAVID R. STONE, Georgia
Southern University, Statesboro, Georgia, USA; PANOS E. TSAOUSSOGLOU,
Athens, Greece; ZUN SHAN and EDWARD T.H. WANG, Wilfrid Laurier Uni-
versity, Waterloo, Ontario; and the proposer.

2222. [1997: 111] Proposed by Shawn Godin, St. Joseph Scollard

Hall, North Bay, Ontario.
Find the value of the continued root:
v s
u r
4 + 27 4 + 29 4 + 31 4 + 33p


:
u q
t

NOTE: This was inspired by the problems in chapter 26 \Ramanujan, In nity

and the Majesty of the Quattuordecillion", pp. 193{195, in \Keys to In nity"
by Cli ord A. Pickover, John Wiley and Sons, 1995.
I. Solution by Robert B. Israel, University of British Columbia, Van-
couver, BC.
The answer is 29. More generally, for any positive integer n, we claim
that s r
4 + n 4 + (n + 2) 4 + (n + 4)p


= n + 2 ;
q

where the left side is de ned as the limit of

v v
u u s
u r
u u
t p
F (n;m) = 4 + n 4 + (n + 2) 4 + (n + 4)


4 + m 4
t
q

as m ! 1 (where m is an integer and (m , n) is even).

If g (n;m) = F (n;m) , (n + 2), we have
F (n;m) , (n + 2) = (4 + nF (n + 2; m)) , (4 + n(n + 4))
2 2

= n(F (n + 2; m) , (n + 4)) ;
so
g(n;m) = F (n;m)n+ n + 2 g(n + 2; m) :
182

Clearly F (n;m) > 2, so

jg(n;m)j < n +n 4 jg(n + 2; m)j :
By iterating this, we obtain
jg(n;m)j < mn((m
n + 2) jg(m;m)j < n(n + 2) :
+ 2) m
Therefore g (n;m) ! 0 as m ! 1.
II. Solution by Efstratios Rappos, Girton College, University of Cam-
bridge, England
Let
s r
Sn = 4 + (2n , 1) 4 + (2n + 1) 4 + (2n + 3)p



q

Sn satis es the recurrence relation

q
Sn = 4 + (2n , 1)Sn +1

if and only if
(Sn , 2)(Sn + 2) = (2n , 1)Sn : +1

By inspection, this admits Sn = 2n + 1 as a solution. We only have to prove

that S = 3 to make this induction complete. Let
1
v s
u r
u q p
Tn = 4 + 4 + 3


(2n , 3) 4 + (2n , 1) 2n + 3)
t

and
s r q p
Un = 4 + 4 + 3


(2n , 3) 4 + (2n , 1)(2n + 3) = 3 :
Clearly Tn  Un and the latter is identically
p
equal to 3. Therefore,
p
using the
fact that B  A > 0 implies that (4 + A)=(4 + B )  A=B ,
r



+ (2n , 1)p2n + 3
q
T n Tn 4 +
1  3 = U = q p
n 4 +


(2n , 1))(2n + 3)
rq



+ (2n , 1)p2n + 3 s
 qp 


 2 2n1+ 3
n+1



+ (2n , 1)(2n + 3)
= 1 ,! 1
(2n + 3) 21 n+1( )
 183

as n ! 1 [for example, by rewriting as expf, ln(2n + 3)=2n g and using

+1

L'H^opital's rule]. This proves that S = limn!1 Tn = 3. The required

expression is precisely S and hence its value is 29.
1

14

Also solved or answered by MANSUR BOASE, student, St. Paul's School,

London, England; CHRISTOPHER J. BRADLEY, Clifton College, Bristol, UK;
DAVID DOSTER, Choate Rosemary Hall, Wallingford, Connecticut, USA;
RICHARD I. HESS, Rancho Palos Verdes, California, USA; WALTHER JANOUS,

Ursulinengymnasium, Innsbruck, Austria; VACLAV  Y,
KONECN  Ferris State
University, Big Rapids, Michigan, USA; MICHAEL LAMBROU, University
of Crete, Crete, Greece; KEE-WAI LAU, Hong Kong; GERRY LEVERSHA, St
Paul's School, London, England; J.A. MCCALLUM, Medicine Hat, Alberta;

HEINZ-JURGEN SEIFFERT, Berlin, Germany; and the proposer.
Several readers made reference to the July 1996 issue of the Mathe-
matical Gazette, which contained a similar problem, Problem 80E posed by
Tony Ward: evaluate:
s r
1 + 1 1 + 2 1 + 3p


:
q

Bradley notes that the solution appeared in the March 1997 issue where the
value of the continued root was proved to be 2, and to be \well-de ned".
He also adds that the editor of the Problems section of the Gazette con-
cludes \Clearly, the problem raises some deep questions about the meaning
of `well-de ned'." Along the same lines as this editorial comment, Murray
S. Klamkin, University of Alberta, Edmonton, Alberta adds that \the value
can be anything since there is no de nition regarding the continuation of the
root". Klamkin refers to A. Herschfeld, On In nite Radicals, Amer. Math.
Monthly, 42 (1935) 419-429 where Herschfeld notes that Ramanujan's so-
lution for r
1 + 2 1 + 3p1 +


= 3
q

is incomplete since one may write similarly that

p q p
4 = 1 + 2
(15=2) = 1 + 2 1 + 3
(221=12)
r
1 + 2 1 + 3p1 +


:
q
=
Despite these comments most solvers expressed no diculty in understand-
ing the meaning of the continued root, and for that reason we have decided
to print the above \solutions". Another reference to similar problems given
by several readers was to J.M. Borwein, G. de Barra, Nested Radicals, Amer.
Math. Monthly, 98 (1991) 735-739.
184

2224. [1997: 111] Proposed by Waldemar Pompe, student, Univer-

sity of Warsaw, Poland.
Point P lies inside triangle ABC . Triangle BCD is erected outwardly
on side BC such that \BCD = \ACP and \CBD = \ABC . Prove that if
the area of quadrilateral PBDC is equal to the area of triangle ABC , then
triangles ACP and BCD are similar.
Solution by Ian June L. Graces, Manila, The Philippines; and Giovanni
Mazzarello, Firenze, Italy.
Let A0 and P 0 be the respective images of A and P under re ection
in the line BC . Note that B; D; A0 are collinear (by the de nition of D).
Denoting by [XY Z ] the area of 4XY Z , we have
[P 0CB ] = 21 P 0 C
BC sin \P 0 CB;
and
[A0 CD] = 12 A0 C
CD sin \A0 CD:
As a consequence of the given conditions ([PBDC ] = [ABC ]) and the e ect
of the re ection, [P 0 CB ] = [A0 CD] (these are the complements of 4BDC
in PBDC and in 4A0 CB ) and \A0 CD = \P 0 CB . Thus
A0 C
CD = P 0C
BC:
In other words, (by SAS) we have 4A0 CP 0  4BCD.
From the re ection we have 4A0 CP 0 
= ACP , and the desired result
follows.
Also solved by FRANCISCO BELLOT ROSADO, I.B. Emilio Ferrari, and
MARI A ASCENSION  LOPEZ
 CHAMORRO, I.B. Leopoldo Cano, Valladolid,
Spain; MANSUR BOASE, student, St. Paul's School, London, England;
CHRISTOPHER J. BRADLEY, Clifton College, Bristol, UK; ADRIAN CHAN,
student, Upper Canada College, Toronto, Ontario; FLORIAN HERZIG, stu-
dent, Perchtoldsdorf, Austria; WALTHER JANOUS, Ursulinengymnasium,

Innsbruck, Austria; VACLAV KONECN Y,
 Ferris State University, Big Rapids,
Michigan, USA; MICHAEL LAMBROU, University of Crete, Crete, Greece;
GERRY LEVERSHA, St Paul's School, London, England; ISTVAN  REIMAN,
Budapest, Hungary; TOSHIO SEIMIYA, Kawasaki, Japan; D.J. SMEENK,
Zaltbommel, the Netherlands; and the proposer.
 185

2225. [1997: 111] Proposed by Kenneth Kam Chiu Ko, Mississauga,

Ontario.
(a) For any positive integer n, prove that there exists a unique n-digit
number N such that:
(i) N is formed with only digits 1 and 2; and
(ii) N is divisible by 2n .
(b) Can digits \1" and \2" in (a) be replaced by any other digits?
Solution by Robert B. Israel, University of British Columbia, Vancou-
ver, BC.
We can use any two non-zero digits whose di erence is odd. Let the
digits be a and b, where a; b 2 f1; 2; : : : ; 9g and a , b is odd.
There are 2n di erent n{digit numbers formed with these two digits,
and 2n residue classes modulo 2n . I claim that the 2n numbers are all in
distinct residue classes. By the Pigeonhole Principle, exactly one of these
numbers must be in the residue class 0.
Consider two distinct n{digit numbers, N and N , formed with the
digits a and b. Suppose that the rst digit, counting from right to left, where
1 2

they di er, is in the 10k position, 0  k  n , 1, where N has a and N

has b. Then N , N  (a , b)10k = (a , b)5k2k (mod 10k ), and thus
1 2
+1

modulo 2k . Since (a , b)5k is odd, we have N 6 N (mod 2n).

1 2
+1
1 2

Also solved by SAM BAETHGE, Nordheim, Texas, USA; CARL BOSLEY,

student, Washburn Rural High School, Topeka, Kansas, USA; CHRISTOPHER
J. BRADLEY, Clifton College, Bristol, UK; CURTIS COOPER, Central Mis-
souri State University, Warrensburg, Missouri, USA; CHARLES R.
DIMINNIE, Angelo State University, San Angelo, TX, USA; FLORIAN
HERZIG, student, Perchtoldsdorf, Austria; RICHARD I. HESS, Rancho Pa-
los Verdes, California, USA; CYRUS HSIA, student, University of Toronto,
Toronto, Ontario; WALTHER JANOUS, Ursulinengymnasium, Innsbruck, Aus-

tria; VACLAV KONECN  Y,
 Ferris State University, Big Rapids, Michigan, USA;
MICHAEL LAMBROU, University of Crete, Crete, Greece; GERRY
LEVERSHA, St Paul's School, London, England; KATHLEEN E. LEWIS, SUNY
Oswego, Oswego, NY, USA; GOTTFRIED PERZ, Pestalozzigymnasium, Graz,
Austria; JOEL SCHLOSBERG, student, Hunter College High School, New
York, NY, USA; ZUN SHAN and EDWARD T.H. WANG, Wilfrid Laurier Uni-
versity, Waterloo, Ontario; DAVID R. STONE, Georgia Southern University,
Statesboro, Georgia, USA; KENNETH M. WILKE, Topeka, Kansas, USA; YEO
KENG HEE, student, Hwa Chong Junior College, Singapore; and the pro-
poser.
Besides Israel, only Lambrou, Leversha and Schlosberg proved the more
general result presented above. Shan and Wang pointed out that if fa; bg =
f2; 4g, f2; 8g, f4; 6g, f6; 8g or f4; 8g, then the \existence" claim is still true
and the \uniqueness" claim would be true if one strengthens condition (ii)
to 2n jN for the rst four pairs, and to 2n jN for the pair f4; 8g.
+1 +2
186

Diminnie asked whether any similar results are possible if 2n is re-

placed by kn for 3  k  9.

2226. [1997: 166] Proposed by K.R.S. Sastry, Dodballapur, India.

An old man willed that, upon his death, his three sons would receive
the u , v , w parts of his herd of camels respectively. He had uvw , 1
th th th

camels in the herd when he died. Obviously, their sophisticated calculator

could not divide uvw , 1 exactly into u, v or w parts. They approached a
distinguished CRUX problem solver for help, who rode over on his camel,
which he added to the herd and then ful lled the old man's wishes, and took
the one camel that remained, which was, of course, his own.
Dear CRUX reader, how many camels were there in the herd?
I. Solution by Robert B. Israel, University of British Columbia, Van-
couver, BC.
There were 41 camels. We may assume u  v  w. Of course u  2,
and vw + uw + uv = uvw , 1.
If u = 2, the equation becomes (v , 2)(w , 2) = 5. Since the only
factorization of 5 is 1  5, this means v = 3, w = 7, and uvw , 1 = 41.
If u = 3, the equation becomes (2v , 3)(2w , 3) = 11. Again there is
only one factorization, and v = 2 (which violates u  v ).
Finally, if u  4 we have 1 , 1=(uvw) = 1=u + 1=v + 1=w  3=4 so
uvw  4, which is impossible.
II. Solution by Michael Lambrou, University of Crete, Crete, Greece.
This solution is so much in keeping with the spirit of the problem that the
editor felt a need to share it with all CRUX readers.
\In the holy name of the Almighty," said the distinguished problem
solver who saw the CRUX of the matter, \if you add my humble camel to
your herd then there will be uvw camels to share. Your kind selves, whose
renowned hospitality o ered me your well to quench my thirst, will receive
uv, vw, and wu camels respectively. This amply ful ls the deceased's will,
whose soul may rest in tranquility."
\So," interrupted the sophisticated calculator, a student of logistics (the
art of the practical arithmetician), perpetuator of the Pythagorean doctrine
that whole numbers are the essence of nature, \we must then have that uv +
vw + wu +1 equals uvw, since numbers are the balance of ideas, the epitome
of fairness, and we must take into account the camel of our distinguished
guest. We cannot let him leave our oasis for his long journey to redeem his
pilgrimage pledge, without a fair chance to cross the desert."
The sophisticated calculator, well versed in the new art of Al-jabr, could
 187

easily re-write the condition as

u + v + w = (u , 1)(v , 1)(w , 1):
\What?" he exclaimed. \If any of u, v , w is 1, then the right hand side is a
product of numbers, one of which is nothing!" He was perplexed although
he had seen this `nothing' number in Ptolemy's Almagest, the monumental
astronomical work, in the Table of Chords in Chapter One. \I do not un-
derstand," he continued. \How can nothing exist? It is contrary to nature.
Nature abhors void because it would make motion impossible, as falling bod-
ies would have to have in nite speed."
\On the contrary," said the distinguished problem solver, \in my long
travels I have heard that the wise men of the east have discovered a nothing
number. They call it `as-sifr', and it comes from the Sanskrit `sunya'. It has
the property that when multiplied by anything it gives as-sifr. So, mathe-
matically speaking, we have to exclude equality of any of u, v , w to 1 because
this would contradict the equation: u + v + w = (u , 1)(v , 1)(w , 1)."
\Perhaps mathematically we have to exclude this case but we have an
inheritance problem," answered the calculator, trying to gain time, \ and this
nothing is not, philosophically speaking, on solid ground." He then turned to
the respectful cadi, the assessor of values and conservator of culture, whose
judgment had a Rhadamanthean wisdom. \What do you say, esteemed rev-
erend?"
The cadi replied that \if any of u, v , w was 1, then one of the sons
would take the entire herd, which is contrary to our sacred traditions. Surely
it was not the intention of their late father to incite hatred in the thoughts of
the two losers. Surely he did not want to upset the good values and bonds
of his family." This answer satis ed the calculator.
\Fine! May your shadow never be less, but let us continue the analysis.
We may assume that w  v  u > 1 since birth rites allow shares to be
larger or lesser. But could u be 4 or more?"
\I hope not," continued the calculator, \because the u part would be
th

too small, unworthy of the respect showed to his late father. Ah yes, if u  4
then
3w  u + v + w = (u , 1)(v , 1)(w , 1)  3
3(w , 1)
giving 9  6w, which cannot be, since then w = 1, but then he would
take the entire herd, inciting hatred in the thoughts of the other two, as
forewarned by the incontestable cadi."
\So we must have u  3. Let us then see what happens if u = 3. Here
w  v  u = 3 gives
3 + 2w  u + v + w = (u , 1)(v , 1)(w , 1)  2
2(w , 1) ;
188

that is, 7  2w, giving w = 1, 2, or 3. The cases w = 1; 2 are excluded

since w  u = 3, leaving 3 = w  u = 3; that is, all shares equal,
u = v = w = 3. But this does not satisfy the original equation and must be
dropped."
The dropping of the equal shares possibility came as a relief to all. It
must have been Almighty's wish since not all three sons deserved an equal
share. One of the three was certainly more praiseworthy spiritually, as he
attended prayers and consulted often the holy book.
\Last but not least we have to analyze the possibility u = 2." Every-
body listened carefully, especially potential brides, because u = 2 meant
that one son would take half the herd. That is, as much as the other two
together. Wise is the Lord!
\So we have
2 + v + w = 1(v , 1)(w , 1)
which, after some Al-jabr, gives
(v , 2)w = 2v + 1."
At this point the problem solver interrupted again. \Observe," he said,
\if v = 2 then the left hand side gives as-sifr, which is incompatible with the
right, so this case must be dropped."
\I will do as you say," replied the calculator, \although I think there is
a deeper reason for that. Harmony with nature does not allow u = v = 2
because the original equation then becomes
4+w = w,1
and, if anything is added to 4, be it something of substance or void, you get
at least 4 more than the addend, and not one less than the addend."
\We, therefore, have," he continued:
\w = 2vv,+21 = 2 + v ,5 2
This is a dicult situation. How can an integer equal a fraction? Only when
what seems a fraction is not really a fraction but an integer concealed. We are
rescued from this dicult situation by appealing to the ideas of Diophantus.
I am so glad I have a recent manuscript with a translation of his eternal book,
because the original Greek is too dicult."
\This is how he approaches such problems: The denominator v , 2
must be a divisor of 5, a sacred number, the number of Platonic solids and
the length of the hypotenuse of the eternal triangle. Divine wisdom arranged
that 5 has the prime property that it possesses precisely two divisors, unity
and itself. So v is either 3 or 7. It cannot be 7 because w would then be 3, a
smaller number. This leaves v = 3 and w = 7."
 189

\Thus the total number of camels in the original herd is 41. One camel
is left over for our guest, which he can have back, as it is not counted in
the 41. The shares are 21, 14, and 6 respectively," concluded the calculator
boastfully.
Everybody applauded the sagacity of this artful manipulator of numbers
whose eurhythmic mind interpreted the inheritance laws with the infallible
ways of the mathematician.
The distinguished problem solver smiled to himself. He had succeeded
again. In a true Socratic manner he led the dialogue by giving imperceptible
hints, the CRUX of the matter, to his counterpart who then discovered the
truth that had been known to the problem solver from the very beginning.
He saddled his camel, thanked for the hospitality and the knowledge he ac-
quired, savoured a sip of water and left for the next stage of his Promethean
journey.
Also solved or answered by SAM BAETHGE, Nordheim, Texas, USA;
FRANCISCO BELLOT ROSADO, I.B. Emilio Ferrari, and MARI A
ASCENSION  LOPEZ
 CHAMORRO, I.B. Leopoldo Cano, Valladolid, Spain;
MANSUR BOASE, student, St. Paul's School, London, England;
CHRISTOPHER J. BRADLEY, Clifton College, Bristol, UK; ADRIAN CHAN,
student, Upper Canada College, Toronto, Ontario; CHARLES R. DIMINNIE,
Angelo State University, San Angelo, TX, USA; IAN JUNE L. GARCES, Ateneo
de Manila University, The Philippines and GIOVANNI MAZZARELLO, Fer-
rovie dello Stato, Florence, Italy; DAVID HANKIN, Hunter College Campus
Schools, New York, NY, USA; FLORIAN HERZIG, student, Perchtoldsdorf,
Austria; JOHN G. HEUVER, Grande Prairie Composite High School, Grande
Prairie, Alberta; D. KIPP JOHNSON, Beaverton, Oregon, USA; GERRY
LEVERSHA, St Paul's School, London, England; GOTTFRIED PERZ, Pesta-
lozzigymnasium, Graz, Austria; REZA SHAHIDI, student, University of Wa-
terloo, Waterloo, Ontario; D.J. SMEENK, Zaltbommel, the Netherlands;
DAVID STONE and VREJ ZARIKIAN, Georgia Southern University, States-
boro, Georgia; PANOS E. TSAOUSSOGLOU, Athens, Greece; PAUL YIU,
Florida Atlantic University, Boca Raton, Florida, USA; and the proposer.
There were two incomplete solutions.
Lambrou also considers the general problem where the number of camels
is p , 1, and u, v , w all divide evenly into p. In addition to the solution
given above he nds 13 other solutions (u; v;w; p), where w  v  w:
(2; 3; 8; 24), (2; 3; 9; 18), (2; 3; 10; 15), (2; 3; 12; 12), (2; 4; 5; 20),
(2; 4; 6; 12), (2; 4; 8; 8), (2; 5; 5; 10), (2; 6; 6; 6), (3; 3; 4; 12),
(3; 3; 6; 6), (3; 4; 4; 6), (4; 4; 4; 4):
190

2229. [1997: 167] Proposed by Kenneth Kam Chiu Ko, Mississauga,

Ontario.
(a) Let m be any positive integer greater than 2, such that x  1 (mod m)
2

whenever (x; m) = 1.
Let n be a positive integer. If mjn +1, prove that the sum of all divisors
of n is divisible by m.
?
(b) Find all possible values of m.
Solution by Kee-Wai Lau, Hong Kong (modi ed by the editor).
(a) We rst show that n cannot be a perfect square.
Suppose that n = k . Then k  ,1(mod m). But kjn, mjn + 1 and
2 2

(n; n + 1) = 1 together imply that (k; m) = 1, and so, k  1(mod m).

2

Thus 1  ,1(mod m), which is false since m > 2. Therefore, all the di-
visors of n can be grouped into pairs (s; t), where st = n and s 6= t. It
then suces to show that mj(s + t). As above, (s; m) = 1 implies
that s  1(mod m). Adding st  ,1(mod m), we have that
2

s(s + t)  0(mod m), or s + t  0(mod m).

(b) We show that the possible values of m are precisely 3, 4, 6, 8, 12, and 24.
For each m such that 3  m  24, direct checking of those x with
1 < x < m and (x; m) = 1 reveals that these values are indeed the only
ones that satisfy the described condition.
Assume then that m > 24 and let p , p , p , : : : , denote the se-
quence of prime numbers. Then 2jm, for otherwise (2;m) = 1 implies that
1 2 3

2  1(mod m), which is false. Similarly, 3jm and 5jm. If (7; m) = 1,

2

then 7  1(mod m), or mj48, which is impossible since 5jm. Thus 7jm.
2

Suppose that pi jm for all i = 1, 2, : : : , k, for some k Q 4. If

(m; pk ) = 1, then pk  1(mod m), which implies that pk > ki pi.
+1
2
+1
2
+1 =1
However, this contradicts the Bonse Inequality, which states that for all
k  4, pk < Qki pi. (See, for example, chapter 27 of The Enjoyment
2
+1 =1
of Mathematics by H. Rademacher and O. Toeplitz; Dover, 1990.)
It follows that pk jm and so m is divisible by any prime, which
is clearly impossible. This shows that if m > 24, we cannot have
+1

x  1(mod m) whenever (x; m) = 1, and the proof is complete.

2

Also solved by ADRIAN BIRKA, student, Lakeshore Catholic High

School, Port Colbourne, Ontario; MANSUR BOASE, student, St. Paul's School,
London, England; CHRISTOPHER J. BRADLEY, Clifton College, Bristol, UK;
ADRIAN CHAN, student, Upper Canada College, Toronto, Ontario;
FLORIAN HERZIG, student, Perchtoldsdorf, Austria; RICHARD I. HESS,
Rancho Palos Verdes, California, USA; D. KIPP JOHNSON, Beaverton, Ore-
gon, USA; MICHAEL LAMBROU, University of Crete, Crete, Greece; and

HEINZ-JURGEN SEIFFERT, Berlin, Germany.
 191

Part (a) only was solved by JIMMY CHUI, student, Earl Haig Sec-
ondary School, North York, Ontario; WALTHER JANOUS, Ursulinengym-
nasium, Innsbruck, Austria; SEAN MCILROY, student, University of British
Columbia, Vancouver, BC; JOEL SCHLOSBERG, student, Hunter College High
School, New York, NY, USA; and the proposer.
Regarding the solution to (b), the Bonse Inequality was also used, ex-
plicitly or implicitly, by Boase, Bradley, Herzig and Sei ert. This inequality
is an easy consequence of Bertrand's Postulate as shown by Herzig and Seif-
fert. Johnson gave a solution using Bertrand's Postulate directly.

2230. [1997: 167] Proposed by Waldemar Pompe, student, Univer-

sity of Warsaw, Poland.
Triangles BCD and ACE are constructed outwardly on sides BC and
CA of triangle ABC such that AE = BD and \BDC + \AEC = 180.
The point F is chosen to lie on the segment AB so that
AF = DC :
FB CE
Prove that
DE = EF = FD :
CD + CE BC AC
Solution by Toshio Seimiya, Kawasaki, Japan.
Let G be a point on AE produced beyond E such that \ECG = \DCB .
Since \CEG = 180 , \AEC = \CDB , we have 4CEG  4CDB ,
(directly similar) from which we have 4CBG  4CDE . Thus
\BGC = \DEC: (1)
Since AF CD BD AE
FB = CE = EG = EG ; we get FE k BG, so that
\AGB = \AEF: (2)
Hence we have from (1) and (2)
\FED = \AEC , (\AEF + \DEC )
= \AEC , (\AGB + \BGC )
= \AEC , \AGC
= \ECG
= \BCD: (3)
Similarly we have
\FDE = \ACE: (4)
192

Let H be a point on CD produced beyond D such that DH = EC . Since

BD = AE and \BDH = 180 , \BDC = \AEC , we have
4BDH = 4AEC;
so that BH = AC , and \BHD = \ACE:
As \FED = \BCD = \BCH , and \FDE = \ACE = \BHD =
\BHC , we have 4FDE  4BHC .
Thus we get
DE = EF = FD :
HC BC BH
Since HC = CD + DH = CD + CE , and BH = AC , we have
DE = EF = FD :
CD + CE BC AC
Also solved by FLORIAN HERZIG, student, Perchtoldsdorf, Austria;
 REIMAN, Budapest, Hungary; and the proposer.
ISTVAN

Crux Mathematicorum
Founding Editors / Redacteurs-fondateurs: Leopold Sauve & Frederick G.B. Maskell
Editors emeriti / Redacteur-emeriti: G.W. Sands, R.E. Woodrow, Bruce L.R. Shawyer
Mathematical Mayhem
Founding Editors / Redacteurs-fondateurs: Patrick Surry & Ravi Vakil
Editors emeriti / Redacteurs-emeriti: Philip Jong, Je Higham,
J.P. Grossman, Andre Chang, Naoki Sato, Cyrus Hsia