OLYMON

VOLUME 2
2001
Problems 55-126
This is the Mathematical Olympiads Correspondence Program sponsored by the Canadian Mathematical
Society and the University of Toronto Department of Mathematics. The organizer and editor is Edward J.
Barbeau of the University of Toronto Department of Mathematics, and the problems and solutions for this
volume of Olymon were prepared by Edward J. Barbeau of the University of Toronto, Dragos Hrimiuk
of the University of Alberta and Valeria Pandelieva in Ottawa.
Notes. A real-valued function f dened on an interval is concave i f((1t)u+tv) (1t)f(u)+tf(v)
whenever 0 < t < 1 and u and v are in the domain of denition of f(x). If f(x) is a one-one function
dened on a domain into a range, then the inverse function g(x) dened on the set of values assumed by f
is determined by g(f(x)) = x and f(g(y)) = y; in other words, f(x) = y if and only if g(y) = x.
A sequence x
n
converges if and only if there is a number c, called its limit, such that, as n increases,
the number x
n
gets closer and closer to c. If the sequences is increasing (i.e., x
n+1
x
n
for each index n)
and bounded above (i.e., there is a number M for which x
n
M for each n, then it must converge. [Do you
see why this is so?] Similarly, a decreasing sequence that is bounded below converges. [Supply the denitions
and justify the statement.] An innite series is an expression of the form

k=a
x
k
= x
a
+x
a+1
+x
a+2
+ +
x
k
+ , where a is an integer, usually 0 or 1. The nth partial sum of the series is s
n

n
k=a
x
k
. The series
has sum s if and only if its sequence s
n
of partial sums converges and has limit s; when this happens, the
series converges. If the sequence of partial sums fails to converge, the series diverges. If every term in the
series is nonnegative and the sequence of partial sums is bounded above, then the series converges. If a series
of nonnegative terms converges, then it is possible to rearrange the order of the terms without changing the
value of the sum.
A rectangular hyperbola is an hyperbola whose asymmptotes are at right angles.
55. A textbook problem has the following form: A man is standing in a line in front of a movie theatre.
The fraction x of the line is in front of him, and the fraction y of the line is behind him, where x and
y are rational numbers written in lowest terms. How many people are there in the line? Prove that, if
the problem has an answer, then that answer must be the least common multiple of the denominators
of x and y.
56. Let n be a positive integer and let x
1
, x
2
, , x
n
be integers for which
x
2
1
+x
2
2
+ +x
2
n
+n
3
(2n 1)(x
1
+x
2
+ +x
n
) +n
2
.
Show that
(a) x
1
, x
2
, , x
n
are all nonnegative;
(b) x
1
+x
2
+ +x
n
+n + 1 is not a perfect square.
57. Let ABCD be a rectangle and let E be a point in the diagonal BD with DAE = 15

. Let F be a
point in AB with EF AB. It is known that EF =
1
2
AB and AD = a. Find the measure of the angle
EAC and the length of the segment EC.
58. Find integers a, b, c such that a ,= 0 and the quadratic function f(x) = ax
2
+bx +c satises
f(f(1)) = f(f(2)) = f(f(3)) .
1
59. Let ABCD be a concyclic quadrilateral. Prove that
[AC BD[ [AB CD[ .
60. Let n 2 be an integer and M = 1, 2, , n. For every integer k with 1 k n 1, let
x
k
=

min A+ max A : A M, A has k elements

where min A is the smallest and max A is the largest number in A. Determine

n
k=1
(1)
k1
x
k
.
61. Let S = 1!2!3! 99!100! (the product of the rst 100 factorials). Prove that there exists an integer k
for which 1 k 100 and S/k! is a perfect square. Is k unique? (Optional: Is it possible to nd such
a number k that exceeds 100?)
62. Let n be a positive integer. Show that, with three exceptions, n! +1 has at least one prime divisor that
exceeds n + 1.
63. Let n be a positive integer and k a nonnegative integer. Prove that
n! = (n +k)
n

_
n
1
_
(n +k 1)
n
+
_
n
2
_
(n +k 2)
n

_
n
n
_
k
n
.
64. Let M be a point in the interior of triangle ABC, and suppose that D, E, F are points on the respective
side BC, CA, AB. Suppose AD, BE and CF all pass through M. (In technical terms, they are cevians.)
Suppose that the areas and the perimeters of the triangles BMD, CME, AMF are equal. Prove that
triangle ABC must be equilateral.
65. Suppose that XTY is a straight line and that TU and TV are two rays emanating from T for which
XTU = UTV = V TY = 60

. Suppose that P, Q and R are respective points on the rays TY , TU

and TV for which PQ = PR. Prove that QPR = 60

.
66. (a) Let ABCD be a square and let E be an arbitrary point on the side CD. Suppose that P is a point
on the diagonal AC for which EP AC and that Q is a point on AE produced for which CQ AE.
Prove that B, P, Q are collinear.
(b) Does the result hold if the hypothesis is weakened to require only that ABCD is a rectangle?
67. (a) Consider the innite integer lattice in the plane (i.e., the set of points with integer coordinates) as
a graph, with the edges being the lines of unit length connecting nearby points. What is the minimum
number of colours that can be used to colour all the vertices and edges of this graph, so that
(i) each pair of adjacent vertices gets two distinct colours; AND
(ii) each pair of edges that meet at a vertex get two distinct colours; AND
(iii) an edge is coloured dierently that either of the two vertices at the ends?
(b) Extend this result to lattices in real ndimensional space.
68. Let a, b, c > 0, a < bc and 1 +a
3
= b
3
+c
3
. Prove that 1 +a < b +c.
69. Let n, a
1
, a
2
, , a
k
be positive integers for which n a
1
> a
2
> a
3
> > a
k
and the least common
multiple of a
i
and a
j
does not exceed n for all i and j. Prove that ia
i
n for i = 1, 2, , k.
2
70. Let f(x) be a concave strictly increasing function dened for 0 x 1 such that f(0) = 0 and f(1) = 1.
Suppose that g(x) is its inverse. Prove that f(x)g(x) x
2
for 0 x 1.
71. Suppose that lengths a, b and i are given. Construct a triangle ABC for which [AC[ = b. [AB[ = c and
the length of the bisector AD of angle A is i (D being the point where the bisector meets the side BC).
72. The centres of the circumscribed and the inscribed spheres of a given tetrahedron coincide. Prove that
the four triangular faces of the tetrahedron are congruent.
73. Solve the equation:
__
2 +

2
_
x
+
__
2

2
_
x
= 2
x
.
74. Prove that among any group of n + 2 natural numbers, there can be found two numbers so that their
sum or their dierence is divisible by 2n.
75. Three consecutive natural numbers, larger than 3, represent the lengths of the sides of a triangle. The
area of the triangle is also a natural number.
(a) Prove that one of the altitudes cuts the triangle into two triangles, whose side lengths are natural
numbers.
(b) The altitude identied in (a) divides the side which is perpendicular to it into two segments. Find
the dierence between the lengths of these segments.
76. Solve the system of equations:
log x +
log(xy
8
)
log
2
x + log
2
y
= 2 ,
log y +
log(x
8
/y)
log
2
x + log
2
y
= 0 .
(The logarithms are taken to base 10.)
77. n points are chosen from the circumference or the interior of a regular hexagon with sides of unit length,
so that the distance between any two of them is not less that

2. What is the largest natural number
n for which this is possible?
78. A truck travelled from town A to town B over several days. During the rst day, it covered 1/n of the
total distance, where n is a natural number. During the second day, it travelled 1/m of the remaining
distance, where m is a natural number. During the third day, it travelled 1/n of the distance remaining
after the second day, and during the fourth day, 1/m of the distance remaining after the third day. Find
the values of m and n if it is known that, by the end of the fourth day, the truck had travelled 3/4 of
the distance between A and B. (Without loss of generality, assume that m < n.)
79. Let x
0
, x
1
, x
2
be three positive real numbers. A sequence x
n
is dened, for n 0 by
x
n+3
=
x
n+2
+x
n+1
+ 1
x
n
.
Determine all such sequences whose entries consist solely of positive integers.
80. Prove that, for each positive integer n, the series

k=1
k
n
2
k
converges to twice an odd integer not less than (n + 1)!.
3
81. Suppose that x 1 and that x = x| +x, where x| is the greatest integer not exceeding x and the
fractional part x satises 0 x < 1. Dene
f(x) =
_
x| +
_
x

x
.
(a) Determine the small number z such that f(x) z for each x 1.
(b) Let x
0
1 be given, and for n 1, dene x
n
= f(x
n1
). Prove that lim
n
x
n
exists.
82. (a) A regular pentagon has side length a and diagonal length b. Prove that
b
2
a
2
+
a
2
b
2
= 3 .
(b) A regular heptagon (polygon with seven equal sides and seven equal angles) has diagonals of two
dierent lengths. Let a be the length of a side, b be the length of a shorter diagonal and c be the length
of a longer diagonal of a regular heptagon (so that a < b < c). Prove that:
a
2
b
2
+
b
2
c
2
+
c
2
a
2
= 6
and
b
2
a
2
+
c
2
b
2
+
a
2
c
2
= 5 .
83. Let C be a circle with centre O and radius 1, and let F be a closed convex region inside C. Suppose
from each point C, we can draw two rays tangent to F meeting at an angle of 60

. Describe F.
84. Let ABC be an acute-angled triangle, with a point H inside. Let U, V , W be respectively the reected
image of H with respect to axes BC, AC, AB. Prove that H is the orthocentre of ABC if and only
if U, V , W lie on the circumcircle of ABC,
85. Find all pairs (a, b) of positive integers with a ,= b for which the system
cos ax + cos bx = 0
a sin ax +b sin bx = 0
has a solution. If so, determine its solutions.
86. Let ABCD be a convex quadrilateral with AB = AD and CB = CD. Prove that
(a) it is possible to inscribe a circle in it;
(b) it is possible to circumscribe a circle about it if and only if AB BC;
(c) if AB AC and R and r are the respective radii of the circumscribed and inscribed circles, then
the distance between the centres of the two circles is equal to the square root of R
2
+r
2
r

r
2
+ 4R
2
.
87. Prove that, if the real numbers a, b, c, satisfy the equation
na| +nb| = nc|
for each positive integer n, then at least one of a and b is an integer.
88. Let I be a real interval of length 1/n. Prove that I contains no more than
1
2
(n+1) irreducible fractions
of the form p/q with p and q positive integers, 1 q n and the greatest common divisor of p and q
equal to 1.
4
89. Prove that there is only one triple of positive integers, each exceeding 1, for which the product of any
two of the numbers plus one is divisible by the third.
90. Let m be a positive integer, and let f(m) be the smallest value of n for which the following statement
is true:
given any set of n integers, it is always possible to nd a subset of m integers whose sum is divisible by
m
Determine f(m).
91. A square and a regular pentagon are inscribed in a circle. The nine vertices are all distinct and divide the
circumference into nine arcs. Prove that at least one of them does not exceed 1/40 of the circumference
of the circle.
92. Consider the sequence 200125, 2000125, 20000125, , 200 00125, (in which the nth number has
n + 1 digits equal to zero). Can any of these numbers be the square or the cube of an integer?
93. For any natural number n, prove the following inequalities:
2
(n1)/(2
n2
)

2
4

4
8

8
2
n

2
n
< 4 .
94. ABC is a right triangle with arms a and b and hypotenuse c = [AB[; the area of the triangle is s square
units and its perimeter is 2p units. The numbers a, b and c are positive integers. Prove that s and p
are also positive integers and that s is a multiple of p.
95. The triangle ABC is isosceles is isosceles with equal sides AC and BC. Two of its angles measure 40

.
The interior point M is such that MAB = 10

and MBA = 20

. Determine the measure of CMB.

96. Find all prime numbers p for which all three of the numbers p
2
2, 2p
2
1 and 3p
2
+4 are also prime.
97. A triangle has its three vertices on a rectangular hyperbola. Prove that its orthocentre also lies on the
hyperbola.
98. Let a
1
, a
2
, , a
n+1
, b
1
, b
2
, , b
n
be nonnegative real numbers for which
(i) a
1
a
2
a
n+1
= 0,
(ii) 0 b
k
1 for k = 1, 2, , n.
Suppose that m = b
1
+b
2
+ +b
n
| + 1. Prove that
n

k=1
a
k
b
k

m

k=1
a
k
.
99. Let E and F be respective points on sides AB and BC of a triangle ABC for which AE = CF. The
circle passing through the points B, C, E and the circle passing through the points A, B, F intersect at
B and D. Prove that BD is the bisector of angle ABC.
100. If 10 equally spaced points around a circle are joined consecutively, a convex regular inscribed decagon
P is obtained; if every third point is joined, a self-intersecting regular decagon Q is formed. Prove that
the dierence between the length of a side of Q and the length of a side of P is equal to the radius of
the circle. [With thanks to Ross Honsberger.]
101. Let a, b, u, v be nonnegative. Suppose that a
5
+b
5
1 and u
5
+v
5
1. Prove that
a
2
u
3
+b
2
v
3
1 .
[With thanks to Ross Honsberger.]
5
102. Prove that there exists a tetrahedron ABCD, all of whose faces are similar right triangles, each face
having acute angles at A and B. Determine which of the edges of the tetrahedron is largest and which
is smallest, and nd the ratio of their lengths.
103. Determine a value of the parameter so that
f(x) cos
2
x + cos
2
(x +) cos xcos(x +)
is a constant function of x.
104. Prove that there exists exactly one sequence x
n
of positive integers for which
x
1
= 1 , x
2
> 1 , x
3
n+1
+ 1 = x
n
x
n+2
for n 1.
105. Prove that within a unit cube, one can place two regular unit tetrahedra that have no common point.
106. Find all pairs (x, y) of positive real numbers for which the least value of the function
f(x, y) =
x
4
y
4
+
y
4
x
4

x
2
y
2

y
2
x
2
+
x
y
+
y
x
is attained. Determine that minimum value.
107. Given positive numbers a
i
with a
1
< a
2
< < a
n
, for which permutation (b
1
, b
2
, , b
n
) of these
numbers is the product
n

i=1
_
a
i
+
1
b
i
_
maximized?
108. Determine all real-valued functions f(x) of a real variable x for which
f(xy) =
f(x) +f(y)
x +y
for all real x and y for which x +y ,= 0.
109. Suppose that
x
2
+y
2
x
2
y
2
+
x
2
y
2
x
2
+y
2
= k .
Find, in terms of k, the value of the expression
x
8
+y
8
x
8
y
8
+
x
8
y
8
x
8
+y
8
.
110. Given a triangle ABC with an area of 1. Let n > 1 be a natural number. Suppose that M is a point on
the side AB with AB = nAM, N is a point on the side BC with BC = nBN, and Q is a point on the
side CA with CA = nCQ. Suppose also that T = AN CM, R = BQAN and S = CMBQ,
where signies that the singleton is the intersection of the indicated segments. Find the area of the
triangle TRS in terms of n.
111. (a) Are there four dierent numbers, not exceeding 10, for which the sum of any three is a prime number?
(b) Are there ve dierent natural numbers such that the sum of every three of them is a prime number?
6
112. Suppose that the measure of angle BAC in the triangle ABC is equal to . A line passing through the
vertex A is perpendicular to the angle bisector of BAC and intersects the line BC at the point M.
Find the other two angles of the triangle ABC in terms of , if it is known that BM = BA+AC.
113. Find a function that satises all of the following conditions:
(a) f is dened for every positive integer n;
(b) f takes only positive values;
(c) f(4) = 4;
(d)
1
f(1)f(2)
+
1
f(2)f(3)
+ +
1
f(n)f(n + 1)
=
f(n)
f(n + 1)
.
114. A natural number is a multiple of 17. Its binary representation (i.e., when written to base 2) contains
exactly three digits equal to 1 and some zeros.
(a) Prove that there are at least six digits equal to 0 in its binary representation.
(b) Prove that, if there are exactly seven digits equal to 0 and three digits equal to 1, then the number
must be even.
115. Let U be a set of n distinct real numbers and let V be the set of all sums of distinct pairs of them, i.e.,
V = x +y : x, y U, x ,= y .
What is the smallest possible number of distinct elements that V can contain?
116. Prove that the equation
x
4
+ 5x
3
+ 6x
2
4x 16 = 0
has exactly two real solutions.
117. Let a be a real number. Solve the equation
(a 1)
_
1
sin x
+
1
cos x
+
1
sin xcos x
_
= 2 .
118. Let a, b, c be nonnegative real numbers. Prove that
a
2
(b +c a) +b
2
(c +a b) +c
2
(a +b c) 3abc .
When does equality hold?
119. The medians of a triangle ABC intersect in G. Prove that
[AB[
2
+[BC[
2
+[CA[
2
= 3([GA[
2
+[GB[
2
+[GC[
2
) .
120. Determine all pairs of nonnull vectors x, y for which the following sequence a
n
: n = 1, 2, is (a)
increasing, (b) decreasing, where
a
n
= [x ny[ .
121. Let n be an integer exceeding 1. Let a
1
, a
2
, , a
n
be posive real numbers and b
1
, b
2
, , b
n
be arbitrary
real numbers for which

i=j
a
i
b
j
= 0 .
7
Prove that

i=j
b
i
b
j
< 0 .
122. Determine all functions f from the real numbers to the real numbers that satisfy
f(f(x) +y) = f(x
2
y) + 4f(x)y
for any real numbers x, y.
123. Let a and b be the lengths of two opposite edges of a tetrahedron which are mutually perpendicular and
distant d apart. Determine the volume of the tetrahedron.
124. Prove that
(1
4
+
1
4
)(3
4
+
1
4
)(5
4
+
1
4
) (11
4
+
1
4
)
(2
4
+
1
4
)(4
4
+
1
4
)(6
4
+
1
4
) (12
4
+
1
4
)
=
1
313
.
125. Determine the set of complex numbers z which satisfy
Im (z
4
) = (Re (z
2
))
2
,
and sketch this set in the complex plane. (Note: Im and Re refer respectively to the imaginary and real
parts.)
126. Let n be a positive integer exceeding 1, and let n circles (i.e., circumferences) of radius 1 be given in the
plane such that no two of them are tangent and the subset of the plane formed by the union of them is
connected. Prove that the number of points that belong to at least two of these circles is at least n.
Solutions and Comments
55. A textbook problem has the following form: A man is standing in a line in front of a movie theatre.
The fraction x of the line is in front of him, and the fraction y of the line is behind him, where x and
y are rational numbers written in lowest terms. How many people are there in the line? Prove that, if
the problem has an answer, then that answer must be the least common multiple of the denominators
of x and y.
Solution. Let p and q be the denominators of x and y, when written in their lowest terms; each
denominator has no positive divisor save 1 in common with the corresponding numerator. Let n be the
number of people in line. Since xn and yn are integers, p and q must both divide n, so that n is a multiple
of m, the least common multiple of p and q.
1 x y can be written as a fraction of the form u/m. Since (u/m)n = u(n/m) = 1, we must have
that u = n/m = 1, so that in particular m = n.
Comment. This is quite a dicult question to write up, because you have to put your nger quite
precisely on the main issues involved. Many solvers relied on statements that were equally if not more
dicult to see than the result of the problem. The point of a solution is to show how a result can be
obtained from simpler or more wellknown propositions.
56. Let n be a positive integer and let x
1
, x
2
, , x
n
be integers for which
x
2
1
+x
2
2
+ +x
2
n
+n
3
(2n 1)(x
1
+x
2
+ +x
n
) +n
2
.
Show that
(a) x
1
, x
2
, , x
n
are all nonnegative;
(b) x
1
+x
2
+ +x
n
+n + 1 is not a perfect square.
8
Solution 1. The inequality can be rewritten as
n

i=1
(x
i
n)(x
i
n 1) 0 .
(The line over n 1 is a form of bracket.) Since each summand is positive for integers other than n and
n 1, the inequality can hold only if each x
i
is equal to either n or n 1. Therefore,
n
2
+ 1 = n(n 1) +n + 1 x
1
+x
2
+ +x
n
+n + 1 n
2
+n + 1 < (n + 1)
2
.
Parts (a) and (b) follow easily from this.
Solution 2. [R. Furmaniak] Taking the dierence between the right and left sides leads to the equivalent
inequality
n

k=1
[2x
k
(2n 1)]
2
n .
Since each term in the sum is odd, it can only be 1. Therefore 2x
k
(2n 1) = 1, whence x
k
is equal to
n or n 1 for each k. The solution can be concluded as before.
Solution 3. [O. Bormashenko, M. Holmes] The given inequality is equivalent to
n

i=1
x
i
(x
i
2n 1) n
2
n
3
.
Observe that, for each i,
x
i
(2n 1 x
i
) [
1
2
(2n 1)]
2
= n
2
n +
1
4
.
This is a consequence of the arithmetic-geometric means inequality when the left side is positive, and obvious
when the left side is negative. Since x
i
is supposed to be an integer, we must have
x
i
(2n 1 x
i
) n
2
n
and equality occurs if and only if x
i
= n or x
i
= n 1. (One way to see this is to note that the left side is a
quadratic and can take each of its values no more than twice.) Multiplying by 1 yields that
x
i
(x
i
2n 1) n n
2
whence
n

i=1
x
i
(x
i
2n 1) n
2
n
3
, .
with equality if and only if each x
i
is equal to n or n 1. But because of the given inequality, equality does
occur. The solution can now be completed as before.
Solution 4. The given inequality is equivalent to
n

i=1
(n x
i
)
2

i=1
(n x
i
) . (1)
However, since x
i
is an integer for each i, (n x
i
)
2
(n x
i
) with equality if and only if n x
i
is equal to
0 or 1. Thus
n

i=1
(n x
i
)
2

i=1
(n x
i
) (2)
9
with equality if and only if n x
i
= 0 or 1 for each i. But (1) and (2) together imply that equality does
occur for each i, whence x
i
is equal to either n or n 1. The solution is completed as before.
57. Let ABCD be a rectangle and let E be a point in the diagonal BD with DAE = 15

. Let F be a
point in AB with EF AB. It is known that EF =
1
2
AB and AD = a. Find the measure of the angle
EAC and the length of the segment EC.
Solution. We begin with the observation that tan 15

= 2

3. (Exercise: Use either tan =

(sin 2)/(1 + cos 2)
1
or tan = tan(3 2) with = 15

.) Let a and b be the respective lengths of

AD and FE, so that [AF[ = (2

3)b, [AB[ = 2b and [FB[ =

3b. Then tan FEB =

3, so that
FEB = ADB = 60

. Hence [BE[ = 2b, [BD[ = 2a and [ED[ = 2(a b). Since a/2b = cot ADB =
1/

3, 3a
2
= 4b
2
.
Since DAC = ADB = 60

and DAE = 15

, it follows that EAC = 45

.
We can determine [EC[ using the law of cosines in DEC. Thus,
[EC[
2
= 4b
2
+ 4(a b)
2
8(a b)b

3/2
= 8b
2
8ab + 4a
2
4ab

3 + 4b
2

3
= 4b
2
(2 +

3) 4ab(2 +

3) + 4a
2
= 3a
2
(2 +

3) 2a
2

3(2 +

3) + 4a
2
= a
2
(4

3) ,
whence [EC[ = a
_
4

3.
Comment. The length of EC can be found more straightforwardly by introducing an additional point.
Produce the line FE to meet CD at G. Then EGC is a right triangle for which [EG[ = ab and [GC[ =

3b.
Applying pythagoras theorem yields
[EC[
2
= a
2
2ab + 4b
2
= a
2

3a
2
+ 3a
2
= (4

3)a
2
.
58. Find integers a, b, c such that a ,= 0 and the quadratic function f(x) = ax
2
+bx +c satises
f(f(1)) = f(f(2)) = f(f(3)) .
Solution 1. Suppose that f(p) = f(q) with p ,= q. Then a(p
2
q
2
) + b(p q) = 0, from which
p + q = b/a. It follows from this (Explain!) that f(x) can take the same value at at most two distinct
points. In particular, it is not possible that f(1) = f(2) = f(3). Nor can f(1), f(2), f(3) take three dierent
values. Therefore, two of these take one value and the third a second value.
We make another preliminary observation. Suppose f(p) = f(q) = u, f(r) = v and f(u) = f(v),
where p, q, r are dierent, and also u and v are dierent. Then, from the rst paragraph, we have that
p +q = u +v = b/a.
Suppose, now, that (p, q, r) = (1, 2, 3) and that f(1) = u. Then
a +b +c = u
4a + 2b +c = u
9a + 3b +c = 3 u
so that 2(5a + 2b +c) = f(1) +f(3) = 3, which is not possible, since a, b and c are integers.
10
Suppose that (p, q, r) = (2, 3, 1). Then we are led to 2(5a + 2b +c) = 5, again an impossibility.
Suppose that (p, q, r) = (1, 3, 2) and that f(1) = u. Then
a +b +c = u
9a + 3b +c = u
4a + 2b +c = 4 u
so that 4a +b = 0 and 5a +b = 2u 4. This leads to the assignment
(a, b, c) = (2u 4, 8u + 16, 7u 12)
so that
f(x) = (2u 4)(x
2
4x) + (7u 12)
= (2u 4)(x 2)
2
(u 4)
= (2u 4)(x 1)(x 3) +u .
It can be checked that f(u) and f(4 u) are equal to 2u
3
12u
2
+ 23u 12.
We can get a particular example by taking u = 0 to obtain the polynomial f(x) = 4(x 1)(x 3), in
which case f(1) = f(3) = 0, f(2) = 4 and f(0) = f(4) = 12.
Solution 2. Let f(x) = ax
2
+bx +c. Then f(1) = a +b +c, f(2) = 4a + 2b +c and f(3) = 9a + 3b +c.
Then
f(f(2)) f(f(1)) = a[(4a + 2b +c)
2
(a +b +c)
2
] +b[(4a + 2b +c) (a +b +c)]
= (3a +b)[a(5a + 3b + 2c) +b]
= (3a +b)(5a
2
+ 3ab + 2ac +b)
f(f(3)) f(f(1)) = a[(9a + 3b +c)
2
(a +b +c)
2
] +b[(9a + 3b +c) (a +b +c)]
= (8a + 2b)[a(10a + 4b + 2c) +b]
= 2(4a +b)(10a
2
+ 4ab + 2ac +b)
Suppose that f(f(1)) = f(f(2)) = f(f(3)). If b = 3a, then we must have 0 = 10a
2
+ 4ab + 2ac + b =
10a
2
12a
2
+ 2ac 3a, whence c = a + (3/2). In this case, a and c cannot both be integers. However, if
b = 4a, then 0 = 5a
2
+3ab +2ac +b = 5a
2
12a
2
+2ac 4a, whence c = (7a/2) +2. So we can get integer
coecients by taking (a, b, c) = (2t, 8t, 7t + 2) for some integer t.
Comment. To get a single solution quickly, just try to make f(1) = f(3) = 1 and f(2) = 3. This leads
immediately to f(x) = (x 2)
2
+ 3 = 2x
2
+ 8x 5.
59. Let ABCD be a concyclic quadrilateral. Prove that
[AC BD[ [AB CD[ .
Solution 1. [O. Bormashenko, P. Cheng] Let the diagonals intersect in M and assign the lengths:
AB = a, BC = b, CD = c, DA = d, AM = r. BM = p, CM = s, DM = q. Since ABD = ACD
and BAC = BDC, triangles MDC and MAB are similar, so that, for some k, q = kr, s = kp, c = ka.
Wolog, we may assume that k 1. Note that in triangle MAB, we have that p < r + a and r < p + a,
whence a < p r < a or [p r[ < a.
[AC BD[ = [(r +s) (p +q)[ = (k 1)[p r[
(k 1)a = [c a[ = [AB CD[ .
11
Solution 2. Let the diagonals intersect in M and assign the lengths: AB = a, BC = b, CD = c,
DA = d, AM = r. BM = p, CM = s, DM = q. Let BAC = BDC = , ABD = ACD = and
AMB = DMC = .
Applying the Law of Sines, we nd that
p =
a sin
sin
q =
c sin
sin
r =
a sin
sin
s =
c sin
sin
.
Hence
p r =
a(sin sin )
sin
q s =
c(sin sin )
sin
whence
(p +q) (r +s) =
(a c)(sin sin )
sin
=
(a c)2 cos(( +)/2) sin(( )/2)
sin( +)
=
(a c) sin(( )/2)
sin(( +)/2)
.
Since (+)/2 90

, the absolute value of the sine in the numerator is less than the sine in the denominator,
and so we nd that
[(p +q) (r +s)[ [a c[ ,
as desired.
Solution 3. [R. Furmaniak] Let O be the circumcentre of ABCD with R the circumradius. Let AOB =
, BOC = , COD = and DOA = . Wolog, we can let be the largest of these angles.
We have that
AB = 2Rsin

2
CD = 2Rsin

2
AC = 2Rsin
+
2
BD = 2Rsin
+
2
.
Thus
AB CD = 2R
_
sin

2
sin

2
_
= 4Rsin

4
cos
+
4
and
AC BD = 4Rsin

4
cos
+ + 2
4
.
Since ( + 2 +)/4 and ( +)/4 both do not exceed ( + + +)/4 = 90

, we have that
cos
+ + 2
4
cos
+
4
,
and this yields the desired result.
60. Let n 2 be an integer and M = 1, 2, , n. For every integer k with 1 k n, let
x
k
=

min A+ max A : A M, A has k elements

where min A is the smallest and max A is the largest number in A. Determine

n
k=1
(1)
k1
x
k
.
12
Solution 1. For any set S = a
1
, a
2
, , a
k
we dene the related set S

= (n + 1) a
k
, (n + 1)
a
k1
, , (n + 1) a
1
. As S runs through all the subsets of 1, 2, , n with k elements, S

also runs
through the same class of subsets; the mapping S S

is one-one. If, say, a

1
is the minimum element and
a
k
the maximum element of S, then (n +1) a
1
is the maximum and (n +1) a
k
the minimum element of
S

. Hence the sum of the minima and maxima of the two sets is
(a
1
+a
k
) + 2(n + 1) a
1
a
k
= 2(n + 1) .
The sum of the maxima and minima of all the sets SS

is equal to 2x
k
= 2(n+1)
_
n
k
_
, so that x
k
= (n+1)
_
n
k
_
.
Hence
n

k=1
(1)
k1
x
k
= (n + 1)
n

k=1
(1)
k
_
n
k
_
= (n + 1)[(1 1)
n
1] = n + 1 .
Solution 2. [R. Furmaniak] For a given k and m with 1 k, m n, the number of ksubsets of M
with m as the smallest element is
_
nm
k1
_
, and the number of ksubsets of M with m as the largest element
is
_
m1
k1
_
, We use the convention that
_
0
0
_
= 1 and
_
x
y
_
= 0 when x < y. From this, we see that
x
k
=
_
nk+1

m=1
m
_
n m
k 1
__
+
_
n

m=k
m
_
m1
k 1
__
=
_
n

m=1
m
__
n m
k 1
_
+
_
m1
k 1
___
.
Hence
n

k=1
(1)
k1
x
k
=
n

m=1
_
m
n

k=1
(1)
k1
_
n m
k 1
__
+
n

m=1
_
m
n

k=1
(1)
k1
_
m1
k 1
__
.
=
_
n1

m=1
m
n

k=1
(1)
k1
_
n m
k 1
__
+n
_
0
0
_
+
_
n1

m=2
m
n

k=1
_
m1
k 1
__
+ 1
_
0
0
_
.
Now, when n m 1,
n

k=1
(1)
k1
_
n m
k 1
_
= (1 1)
nm
= 0
and, when m 2,
n

k=1
(1)
k1
_
m1
k 1
_
= (1 1)
m1
= 0 .
It follows that the required sum is equal to n + 1.
Solution 3. [O. Bormashenko] Denote by the quantity

n
k=1
(1)
k1
x
k
. Let m be a number between 1
and n1, inclusive. m is the minimum of a kset for exactly
_
nm
k1
_
sets. For a particular k, m as minimum
contributes n
_
nm
k1
_
to the sum for x
k
. Fixing m, m as minimum contributes to the value
m
n

k=1
(1)
k1
_
n m
k 1
_
= 0 ,
where
_
i
j
_
= 0 when j > i. The only other possible minimum is n, and this is a minimum only for the
singelton n, so that n as minimum contributes n to the sum .
By a similar argument, for any number m = 2, 3, , n, m as maximum contributes 0 to the sum . 1
is maximum only for the singleton 1 and contributes the value 1 to the sum . Hence = n + 1.
13
61. Let S = 1!2!3! 99!100! (the product of the rst 100 factorials). Prove that there exists an integer k
for which 1 k 100 and S/k! is a perfect square. Is k unique? (Optional: Is it possible to nd such
a number k that exceeds 100?)
Solution 1. Note that, for each positive integer j, (2j 1)!(2j)! = [(2j 1)!]
2
2j. Hence
S =
50

j=1
[(2j 1)!]
2
[2j] = 2
50
50!
_
50

j=1
(2j 1)!
_
2
,
from which we see that k = 50 is the required number.
We show that k = 50 is the only possibility. First, k cannot exceed 100, for otherwise 101! would be a
factor of k! but not S, and so S/k! would not even be an integer. Let k 100. The prime 47 does not divide
k! for k 46 and divides 50! to the rst power. Since S/50! is a square, it evidently divides S to an odd
power. So k 47 in order to get a quotient divisible by 47 to an even power. The prime 53 divides each k!
for k 53 to the rst power and divides S/50!, and so S to an even power. Hence, k 52.
The prime 17 divides 50! and S/50!, and hence S to an even power, but it divides each of 51! and 52!
to the third power. So we cannot have k = 51 or 52. Finally, look at the prime 2. Suppose that 2
2u
is the
highest power of 2 that divides S/50! and that 2
v
is the highest power of 2 that divides 50!; then 2
2u+v
is the
highest power of 2 that divides S. The highest power of 2 that divides 48! and 49! is 2
v1
and the highest
power of 2 that divides 46! and 47! is 2
v5
. From this, we deduce that 2 divides S/k! to an odd power when
47 k 49. The desired uniqueness of k follows.
Solution 2. Let p be a prime exceeding 50. Then p divides each of m! to the rst power for p m 100,
so that p divides S to the even power 100 (p 1) = 101 p. From this, it follows that if 53 k, p must
divide S/k! to an odd power.
On the other hand, the prime 47 divides each m! with 47 m 93 to the rst power, and each m! with
94 m 100 to the second power, so that it divides S to the power with exponent 54 + 7 = 61. Hence, in
order that it divide S/k! to an even power, we must make k one of the numbers 47, , 52.
By an argument, similar to that used in Solution 1, it can be seen that 2 divides any product of the
form 1!2! (2m1)! to an even power and 100! to the power with exponent
100/2| +100/4| +100/8| +100/16| +100/32| +100/64| = 50 + 25 + 12 + 6 + 3 + 1 = 97 .
Hence, 2 divides S to an odd power. So we need to divide S by k! which 2 divides to an odd power to get a
perfect square quotient. This reduces the possibilities for k to 50 or 51. Since
S = 2
99
3
98
4
97
99
2
100 = (2 4 50)(2
49
3
49
4
48
99)
2
= 50! 2
50
( )
2
,
S/50! is a square, and so S/51! = (S/50!) (51) is not a square. The result follows.
Solution 3. As above, S/(50!) is a square. Suppose that 53 k 100. Then 53 divides k!/50! to the
rst power, and so k!/50! cannot be square. Hence S/k! = (S/50!) (k!/50!) cannot be square. If k = 51 or
52, then k!/50! is not square, so S/k! cannot be square. Suppose that k 46. Then 47 divides 50!/k! to the
rst power, so that 50!/k! is not square and S/k! = (S/50!) (50!/k!) cannot be square. If k = 47, 48 or 49,
then 50!/k! is not square and so S/k! is not square. Hence S/k! is square if and only if k = 50 when k 100.
62. Let n be a positive integer. Show that, with three exceptions, n! +1 has at least one prime divisor that
exceeds n + 1.
Solution. Any prime divisor of n! +1 must be larger than n, since all primes not exceeding n divide n!.
Suppose, if possible, the result fails. Then, the only prime that can divide n! + 1 is n + 1, so that, for some
positive integer r and nonnegative integer K,
n! + 1 = (n + 1)
r
= 1 +rn +Kn
2
.
14
This happens, for example, when n = 1, 2, 4: 1! + 1 = 2, 2! + 1 = 3, 4! + 1 = 5
2
. Note, however, that the
desired result does hold for n = 3: 3! + 1 = 7.
Henceforth, assume that n exceeds 4. If n is prime, then n +1 is composite, so by our initial comment,
all of its prime divisors exceed n + 1. If n is composite and square, then n! is divisible by the four distinct
integers 1, n,

n, 2

n, while is n is composite and nonsquare with a nontrivial divisor d. then n! is divisible

by the four distinct integers 1, d, n/d, n. Thus, n! is divisible by n
2
. Suppose, if possible, the result fails,
so that n! + 1 = 1 + rn + Kn
2
, and 1 1 + rn (mod n
2
). Thus, r must be divisible by n, and, since it is
positive, must exceed n. Hence
(n + 1)
r
(n + 1)
n
> (n + 1)n(n 1) 1 > n! + 1 ,
a contradiction. The desired result follows.
63. Let n be a positive integer and k a nonnegative integer. Prove that
n! = (n +k)
n

_
n
1
_
(n +k 1)
n
+
_
n
2
_
(n +k 2)
n

_
n
n
_
k
n
.
Solution 1. Recall the Principle of Inclusion-Exclusion: Let S be a set of n objects, and let P
1
, P
2
, ,
P
m
be m properties such that, for each object x S and each property P
i
, either x has the property P
i
or
x does not have the property P
i
. Let f(i, j, , k) denote the number of elements of S each of which has
properties P
i
, P
j
, , P
k
(and possibly others as well). Then the number of elements of S each having none
of the properties P
1
, P
2
, , P
m
is
n

1im
f(i) +

1i<jm
f(i, j)

1i<j<lm
f(i, j, l) + + (1)
m
f(1, 2, , m) .
We apply this to the problem at hand. Note that an ordered selection of n numbers selected from among
1, 2, , n+k is a permutation of 1, 2, , n if and only if it is constrained to contain each of the numbers
1, 2, , n. Let S be the set of all ordered selections, and we say that a selection has property P
i
i its fails
to include at least i of the numbers 1, 2, , n (1 i n). The number of selections with property P
i
is the
product of
_
n
i
_
, the number of ways of choosing the i numbers not included and (n +k i)
n
, the number of
ways of choosing entries for the n positions from the remaining n +k 1 numbers. The result follows.
Solution 2. We begin with a lemma:
n

i=0
(1)
i
_
n
i
_
i
m
=
_
0 (0 m n 1)
(1)
n
n! (m = n) .
We use the convention that 0
0
= 1. To prove this, note rst that i(i1) (im) = i
m+1
+b
m
i
m
+ +b
1
i+b
0
for some integers b
i
. We use an induction argument on m. The result holds for each positive n and for m = 0,
as the sum is the expansion of (1 1)
n
. It also holds for n = 1, 2 and all relevant m. Fix n 3. Suppose
15
that it holds when m is replaced by k for 0 k m n 2. Then
n

i=0
(1)
i
_
n
i
_
i
m+1
=
n

i=1
(1)
i
_
n
i
_
i(i 1) (i m)
m

k=0
b
k
n

i=0
(1)
i
_
n
i
_
i
k
=
n

i=m+1
(1)
i
_
n
i
_
i(i 1) (i m) 0
=
n

i=m+1
(1)
i
n!i!
i!(n i)!(i m1)!
=
nm1

j=0
(1)
m+1+j
n!
(n m1 j)!j!
=
nm1

j=0
(1)
m+1
(1)
j
n(n 1) (n m)[(n m1)!]
(n m1 j)!j!
= (1)
m+1
n(n 1) (n m)
nm1

j=0
(1)
j
_
n m1
j
_
= 0 .
(Note that the j = 0 term is 1, which is consistent with the 0
0
= 1 convention mentioned earlier.) So

n
i=0
(1)
i
_
n
i
_
i
m
= 0 for 0 m n 1. Now consider the case m = n:
n

i=1
(1)
i
_
n
i
_
i
n
=
n

i=1
(1)
i
_
n
i
_
i(i 1) (i n + 1)
n1

k=0
b
k
n

i=0
(1)
i
_
n
i
_
i
k
.
Every term in the rst sum vanishes except the nth and each term of the second sum vanishes. Hence

n
i=1
(1)
i
_
n
i
_
i
n
= (1)
n
n!.
Returning to the problem at hand, we see that the right side of the desired equation is equal to
(n +k)
n

_
n
1
_
(n +k 1)
n
+
_
n
2
_
(n +k 2)
n
+ (1)
n
_
n
n
_
(n +k n)
n
=
n

i=0
(1)
i
_
n
i
_
(n i +k)
n
=
n

i=0
(1)
i
_
n
i
_
n

j=0
_
n
j
_
(n i)
j
k
nj
=
n

i=0
n

j=0
(1)
i
_
n
i
__
n
j
_
(n i)
j
k
nj
=
n

j=0
_
n
j
_
k
nj
n

i=0
(1)
i
_
n
i
_
(n i)
j
=
n

j=0
_
n
j
_
k
nj
n

i=0
(1)
i
_
n
n i
_
(n i)
j
=
n

j=0
_
n
j
_
k
nj
n

i=0
(1)
n
(1)
i
_
n
i
_
i
j
.
When 0 j n 1, the sum

n
i=0
(1)
i
_
n
ni
_
(n i)
j
=

n
i=0
(1)
ni
_
n
i
_
i
j
vanishes, while, when j = n, it
assunes the value n!. Thus, the right side of the given equation is equal to
_
n
n
_
k
0
n! = n! as desired.
Solution 3. Let m = n+k, so that m n, and let the right side of the equation be denoted by R. Then
R = m
n

_
n
1
_
(m1)
n
+
_
n
2
_
(m2)
n
+ (1)
i
_
n
i
_
(mi)
n
+ + (1)
n
_
n
n
_
(mn)
n
= m
m
_
n

j=0
(1)
i
_
n
i
__

_
n
1
_
m
n1
_
n

i=1
(1)
i
i
_
n
i
__
+
_
n
2
_
m
n2
_
n

i=1
(1)
i
i
2
_
n
i
__
+
+ (1)
n
_
n
n
__
n

i=1
(1)
i
i
n
_
n
i
__
.
16
Let
f
0
(x) = (1 x)
n
=
n

i=0
(1)
i
_
n
i
_
x
i
and let
f
k
(x) = xDf
k1
(x)
for k 1, where Df denotes the derivative of a function f. Observe that, from the closed expression for
f
0
(x), we can establish by induction that
f
k
(x) =
n

i=0
(1)
i
i
k
_
n
i
_
x
i
so that R =

n
k=0
(1)
k
_
n
k
_
m
nk
f
k
(1).
By induction, we establish that
f
k
(x) = (1)
k
n(n 1) (n k + 1)x
k
(1 x)
nk
+ (1 x)
nk+1
g
k
(x)
for some polynomial g
k
(x). This is true for k = 1 with g
1
(x) = 0. Suppose if holds for k = j. Then
f

j
(x) = (1)
j
n(n 1) (n j + 1)x
j1
(1 x)
nj
(1)
j
n(n 1) (n j + 1)(n j)x
j
(1 x)
nj1
(n j + 1)(1 x)
nj
g
j
(x) + (1 x)
nj+1
g

j
(x) ,
whence
f
j+1
(x) = (1)
j+1
n(n
1
) (n j)x
j
(1 x)
n(j+1)
+ (1 x)
n(j+1)+1
[(1)
j
n(n 1) (n j + 1)x
j
(n j + 1)xg
k
(x) +x(1 x)g

j
(x)]
and we obtain the desired representation by induction. Then for 1 k n 1, f
k
(1) = 0 while f
n
(1) =
(1)
n
n!. Hence R = (1)
n
f
n
(1) = n!.
64. Let M be a point in the interior of triangle ABC, and suppose that D, E, F are respective points on
the side BC, CA, AB, which all pass through M. (In technical terms, they are cevians.) Suppose that
the areas and the perimeters of the triangles BMD, CME, AMF are equal. Prove that triangle ABC
must be equilateral.
Solution. [L. Lessard] Let the common area of the triangles BMD, CME and AMF be a and let their
common perimeter be p. Let the area and perimeter of AME be u and x respectively, of MFB be v
and y respectively, and of CMD be w and z respectively.
By considering pairs of triangles with equal heights, we nd that
AF
FB
=
a
v
=
2a +u
v +a +w
=
a +u
a +w
,
BD
DC
=
a
w
=
2a +v
u +a +w
=
a +v
a +u
,
CE
EA
=
a
u
=
2a +w
u +a +v
=
a +w
a +v
.
From these three sets of equations, we deduce that
a
3
uvw
= 1 ;
17
a
2
+ (w u)a uv = 0 ,
a
2
+ (u w)a vw = 0 ,
a
2
+ (v u)a uw = 0 ;
whence
a
3
= uvw and 3a
2
= uv +vw +uw .
This means that uv, vw, uw are three positive numbers whose geometric and arithmetic means are both equal
to a
2
. Hence a
2
= uv = vw = uw, so that u = v = w = a. It follows that AF = FB, BD = DC, CE = EA,
so that AD, BE and CF are medians and M is the centroid.
Wolog, suppose that AB BC CA. Since AB BC, AEB 90

, and so AM MC. Thus

x p. Similarly, y p and p z.
Consider triangles BMD and AME. We have BD AE, BM AM, ME =
1
2
BM and MD =
1
2
AM.
Therefore
p x = (BD +MD +BM) (AE +ME +AM) = (BD AE) +
1
2
(BM AM) 0
and so p x. Since also x p, we have that p = x. But this implies that AM = MC, so that ME AC
and AB = BC. Since BE is now an axis of a reection which interchanges A and C, as well as F and D, it
follows that p = z and p = y as well. Thus, AB = AC and AC = BC. Thus, the triangle is equilateral.
65. Suppose that XTY is a straight line and that TU and TV are two rays emanating from T for which
XTU = UTV = V TY = 60

. Suppose that P, Q and R are respective points on the rays TY , TU

and TV for which PQ = PR. Prove that QPR = 60

.
Solution 1. Let R be a rotation of 60

about T that takes the ray TU to TV . Then, if R transforms

Q Q

and P P

, then Q

lies on TV and the line Q

makes an angle of 60

with QP. Because of the

rotation, P

TP = 60

and TP

= TP, whence TP

P is an equilateral triangle.
Since Q

TP = TPP

= 60

, TV |P

P. Let T be the translation that takes P

to P. It takes Q

to
a point Q

on the ray TV , and PQ

= P

= PQ. Hence Q

can be none other than the point R [why?],

and the result follows.
Solution 2. The reection in the line XY takes P P, Q Q

and R R

. Triangles PQR

and
PQ

R are congruent and isosceles, so that TQP = TQ

P = TRP (since PQ

= PR). Hence TQRP is

a concyclic quadrilateral, whence QPR = QTR = 60

.
Solution 3. [S. Niu] Let S be a point on TU for which SR|XY ; observe that RST is equilateral. We
rst show that Q lies between S and T. For, if S were between Q and T, then PSQ would be obtuse and
PQ > PS > PR (since PRS > 60

> PSR in PRS), a contradiction.

The rotation of 60

with centre R that takes S onto T takes ray RQ onto a ray through R that intersects
TY in M. Consider triangles RSQ and RTM. Since RST = RTM = 60

, SRQ = 60

QRT =
TRM and SR = TR, we have that RSQ RTM and RQ = RM. (ASA) Since QRM = 60

,
RQM is equilateral and RM = RQ. Hence M and P are both equidistant from Q and R, and so at the
intersection of TY and the right bisector of QR. Thus, M = P and the result follows.
Solution 4. [H. Pan] Let Q

and R

be the respective reections of Q and R with respect to the axis

XY . Since RTR

= 120

and TR = TR

, QR

R = TR

R = 30

. Since Q, R, Q

, R

, lie on a circle with

centre P, QPR = 2QR

R = 60

, as desired.
Solution 5. [R. Barrington Leigh] Let W be a point on TV such that WPQ = 60

= WTU. [Why
does such a point W exist?] Then WQTP is a concyclic quadrilateral so that QWP = 180

QTP = 60

and PWQ is equilateral. Hence PW = PQ = PR.

18
Suppose W ,= R. If R is farther away from T than W, then RPT > WPT > WPQ = 60

60

>
TRP = RWP > 60

, a contradiction. If W is farther away from T than R, then WPT > WPQ =

60

60

> RWP = WRP > 60

, again a contradiction. So R = W and the result follows.

Solution 6. [M. Holmes] Let the circle through T, P, Q intersect TV in N. Then QNP = 180

QTP = 60

. Since PQN = PTN = 60

, PQN is equilateral so that PN = PQ. Suppose, if possible,

that R ,= N. Then N and R are two points on TV equidistant from P. Since PNT < PNQ = 60

and
PNR is isosceles, we have that PNR < 90

, so N cannot lie between T and R, and PRN = PNR =

PNT < 60

. Since PTN = 60

, we conclude that T must lie between R and N, which transgresses the

condition of the problem. Hence R and N must coincide and the result follows.
Solution 7. [P. Cheng] Determine S on TU and Z on TY for which SR|XY and QRZ = 60

. Observe
that TSR = SRT = 60

and SR = RT.
Consider triangles SRQ and TRZ. SRQ = SRT QRT = QRZ QRT = TRZ; QSR =
60

= ZTR, so that SRQ = TRZ (ASA).

Hence RZ = RQ RQZ is equilateral RZ = ZQ and RZQ = 60

. Now, both P and Z lie on

the intersection of TY and the right bisector of QR, so they must coincide: P = Z. The result follows.
Solution 8. Let the perpendicular, produced, from Q to XY meet V T, produced, in S. Then XTS =
V TY = 60

= XTU, from which is can be deduced that TX right bisects QS. Hence PS = PQ = PR,
so that Q, R, S are all on the same circle with centre P.
Since QTS = 120

, we have that SQT = QSR = 30

, so that QR must subtend an angle of 60

at
the centre P of the circle. The desired result follows.
Solution 9. [A.Siu] Let the right bisector of QR meet the circumcircle of TQR on the same side of
QR at T in S. Since QSR = QTR = 60

and QS = QR, SQR = SRQ = 60

. Hence STQ =
180

SRQ = 120

. But Y TQ = 120

, so S must lie on TY . It follows that S = P.

Solution 10. Assign coordinates with the origin at T and the xaxis along XY . The the respective
coordinates of Q and R have the form (u,

3u) and (v,

3v) for some real u and v. Let the coordinates of

P be (w, 0). Then PQ = PR yields that w = 2(u +v). [Exercise: work it out.]
[PQ[
2
[QR[
2
= (u w)
2
+ 3u
2
(u v)
2
3(u +v)
2
= w
2
2uw 4v(u +v) = w
2
2uw 2vw
= w
2
2(u +v)w = 0 .
Hence PQ = QR = PR and PQR is equilateral. Therefore QPR = 60

.
Solution 11. [J.Y. Jin] Let C be the circumcircle of PQR. If T lies strictly inside C, then 60

=
QTR > QPR and 60

= PTR > PQR = PRQ. Thus, all three angle of PQR would be less
than 60

, which is not possible. Similarly, if T lies strictly outside C, then 60

= QTR < QPR and

60

= PTR < PQR = PRQ, so that all three angles of PQR would exceed 60

, again not possible.

Thus T must be on C, whence QPR = QTR = 60

.
Solution 12. [C. Lau] By the Sine Law,
sin TQP
[TP[
=
sin 120

[PQ[
=
sin 60

[PR[
=
sin TRP
[TP[
,
whence sin TQP = sin TRP. Since QTP, in triangle QTP is obtuse, TQP is acute.
Suppose, if possible, that TRP is obtuse. Then, in triangle TPR, TP would be the longest side, so
PR < TP. But in triangle TQP, PQ is the longest side, so PQ > TP, and so PQ ,= PR, contrary to
hypothesis. Hence TRP is acute. Therefore, TQP = TRP. Let PQ and RT intersect in Z. Then,
60

= QTZ = 180

TQP QZT = 180

TRP RZP = QPR, as desired.

19
66. (a) Let ABCD be a square and let E be an arbitrary point on the side CD. Suppose that P is a point
on the diagonal AC for which EP AC and that Q is a point on AE produced for which CQ AE.
Prove that B, P, Q are collinear.
(b) Does the result hold if the hypothesis is weakened to require only that ABCD is a rectangle?
Solution 1. Let ABCD be a rectangle, and let E, P, Q be determined as in the problem. Suppose that
ACD = BDC = . Then PEC = 90

. Because EPQC is concyclic, PQC = PEC = 90

.
Because ABCQD is concyclic, BQC = BDC = . The points B, P, Q are collinear BQC =
PQC = 90

= 45

ABCD is a square.
Solution 2. (a) EPQC, with a pair of supplementary opposite angles, is concyclic, so that CQP =
CEP = 180

EPC ECP = 45

. Since CBAQ is concyclic, CQB = CAB = 45

. Thus,
CQP = CQB so that Q, P, B are collinear.
(b) Suppose that ABCD is a nonquare rectangle. Then taking E = D yields a counterexample.
Solution 3. (a) The circle with diameter AC that passes through the vertices of the square also passes
through Q. Hence QBC = QAC. Consider triangles PBC and EAC. Since triangles ABC and EPC are
both isosceles right triangles, BC : AC = PC : EC. Also BCA = PCE = 45

. Hence PBC EAC

(SAS) so that PBC = EAC = QAC = QBC. It follows that Q, P, B are collinear.
Solution 4. [S. Niu] Let ABCD be a rectangle and let E, P, Q be determined as in the problem. Let
EP be produced to meet BC in F. Since ABF = APF, the quadrilateral ABPF is concyclic, so that
PBC = PBF = PAF. Since ABCQ is concyclic, QBC = QAC = PAE. Now B, P, Q are
collinear
PBC = QBC PAF = PAE AC right bisects EF
ECA = ACB = 45

ABCD is a square .
Solution 5. [M. Holmes] (a) Suppose that BQ intersects AC in R. Since ABCQD is concyclic, AQR =
AQB = ACB = 45

, so that BQC = 45

. Since EQR = AQB = ECR = 45

, ERCQ is concyclic,
so that ERC = 180

EQC = 90

. Hence ER AC, so that R = P and the result follows.

Solution 6. [L. Hong] (a) Let QC intersect AB in F. We apply Menelaus Theorem to triangle AFC:
B, P, Q are collinear if and only if
AB
BF

FQ
QC

CP
PA
= 1 .
Let the side length of the square be 1 and the length of DE be a. Then [AB[ = 1. Since ADE FBC,
AD : DE = BF : BC, so that [BF[ = 1/a and [FC[ =

1 +a
2
/a. Since ADE CQE, CQ : EC =
AD : EA, so that [CQ[ = (1 a)/

1 +a
2
. Hence
[FQ[
[CQ[
= 1 +
[FC[
[CQ[
= 1 +
1 +a
2
a(1 a)
=
1 +a
a(1 a)
.
Since ECP is right isosceles, [CP[ = (1a)/

2 and [PA[ =

2[CP[ = (1+a)/

2. Hence [CP[/[PA[ =
(1 a)/(1 +a). Multiplying the three ratios together and taking account of the directed segments gives the
product 1 and yields the result.
Solution 7. (a) Select coordinates so that A (0, 1), B (0, 0), C (1, 0), D (1, 1) and E (1, t)
for some t with 0 t 1. It is straightforward to verify that P (1
t
2
,
t
2
).
Since the slope of AE is t 1, the slope of AQ should be (1 t)
1
. Since the coordinates of Q have the
form (1 +s, s(1 t)
1
) for some s, it is straightforward to verify that
Q
_
2 t
1 + (1 t)
2
,
t
1 + (1 t)
2
)
_
.
20
It can now be checked that the slope of each of BQ and BP is t(2 t)
1
, which yields the result.
(b) The result fails if A (0, 2), B (0, 0), C (1, 0), D (1, 2). If E (1, 1), then P (
3
5
,
4
5
) and
Q (
3
2
,
1
2
).
67. (a) Consider the innite integer lattice in the plane (i.e., the set of points with integer coordinates) as
a graph, with the edges being the lines of unit length connecting nearby points. What is the minimum
number of colours that can be used to colour all the vertices and edges of this graph, so that
(i) each pair of adjacent vertices gets two distinct colours; AND
(ii) each pair of edges that meet at a vertex get two distinct colours; AND
(iii) an edge is coloured dierently than either of the two vertices at the ends?
(b) Extend this result to lattices in real ndimensional space.
Solution 1. Since each vertex and the four edges emanating from it must have dierent colours, at least
ve colours are needed. Here is a colouring that will work: Let the colours be numbered 0, 1, 2, 3, 4. Colour
the point (x, 0) with the colour x (mod 5); colour the point (0, y) with the colour 2y (mod 5); colour the
points along each horizontal line parallel to the xaxis consecutively; colour the vertical edge whose lower
vertex has colour m (mod 5) with the colour m + 1 (mod 5); colour the horizontal edge whose left vertex
has the colour n (mod 5) with the colour n + 3 (mod 5).
This can be generalized to an ndimensional lattice where 2n + 1 colours are needed by changing
the strategy of colouring. The integer points on the line and the edges between them can be coloured
1 (3) 2 (1) 3 (2) 1 and so on, where the edge colouring is in parenthesis. Form a plane
by stacking these lines unit distance apart, making sure that each vertex has a dierent coloured vertex
above and below it; use colours 4 and 5 judiciously to colour the vertical edges. Now go to three dimensions;
stack up planar lattices and struts unit distance apart, colouring each with the colours 1, 2, 3, 4, 5, while
making sure that vertically adjacent vertices have separate colours, and use the colours 6 and 7 for vertical
struts. Continue on.
Solution 2. Consider the n dimensional lattice. Let the colours be numbered 0, 1, 2, , 2n. Assign
the vertex with coordinates (x
1
, x
2
, , x
n
) the colour x
1
+2x
2
+ +nx
n
, modulo 2n+1. Adjacent vertices
have distinct colours. For each adjacent vertex has the same coordinates, except in one position where the
coordinates dier by 1; if this is the ith coordinate, then the numbers of the two colours dier by i (mod
2n + 1).
Consider an edge joining a vertex with colour u to one of colour v; assign this edge the colour (n+1)(u+v)
(mod 2n+1). Since (n+1)(u+v) v n(uv) (mod 2n+1), the greatest common divisor of n and 2n+1
is 1 and u , v (mod 2n+1), it follows that the colour of this edge diers from v; similarly, it diers from u.
Finally, consider a pair of adjacent edges, with colours (n +1)(u +v) and (n +1)(v +w) (mod 2n +1).
The dierence between these colours, modulo 2n + 1, is equal to (n + 1)(u w). If the edges are collinear,
then this dierence is 2(n + 1)i for some i with 1 i n, and this is not congruent to zero modulo
2n + 1. If the edges are perpendicular, then this dierence is nonzero and of the form (n + 1)(i j). This
value, lying between 2n and 2n is not congruent to zero modulo 2n+1. Thus, adjacent edges have distinct
colours.
Therefore, we can achieve our goal with 2n + 1 colours, and, by looking at a vertex and its adjacent
edges, we see that this is minimal.
68. Let a, b, c > 0, a < bc and 1 +a
3
= b
3
+c
3
. Prove that 1 +a < b +c.
Solution 1. Since (1 + a)(1 a + a
2
) = (b + c)(b
2
bc + c
2
), and since 1 a + a
2
and b
2
bc + c
2
are
positive, we have that
1 +a < b +c 1 a +a
2
> b
2
bc +c
2
.
21
Suppose, if possible, that 1 +a b +c. Then
b
2
bc +c
2
1 a +a
2
(b +c)
2
3bc (1 +a)
2
3a > (1 +a)
2
3bc
(b +c)
2
> (1 +a)
2
b +c > 1 +a
which is a contradiction.
Solution 2. [J. Chui] Let u = (1 +a) (b +c). Then
(1 +a)
3
(b +c)
3
= u[(1 +a)
2
+ (1 +a)(b +c) + (b +c)
2
]
= u[(1 +a)
2
+ (1 +a)(b +c) +b
2
+ 2bc +c
2
] .
But also
(1 +a)
3
(b +c)
3
= (1 +a
3
) (b
3
+c
3
) + 3a(1 +a) 3bc(b +c)
= 0 + 3[a(1 +a) bc(b +c)] < 3bcu .
It follows from these that
0 > u[(1 +a)
2
+ (1 +a)(b +c) +b
2
bc +c
2
] = u[(1 +a)
2
+ (1 +a)(b +c) +
1
2
(b c)
2
+
1
2
(b
2
+c
2
)] .
Since the quantity in square brackets is positive, we must have that u < 0, as desired.
Solution 3. [A. Momin, N. Martin] Suppose, if possible, that (1 +a) (b +c). Then
0 (1 +a)
2
(b +c)
2
= (1 +a
2
) (b
2
+c
2
) 2(bc a) < (1 +a
2
) (b
2
+c
2
) .
Hence 1 +a
2
> b
2
+c
2
. It follows that
(1 a +a
2
) (b
2
bc +b
2
) = (1 +a
2
) (b
2
+c
2
) + (bc a) > 0
so that
(1 a +a
2
) > (b
2
bc +c
2
) .
However
(1 +a)(1 a +a
2
) = 1 +a
3
= b
3
+c
3
+ (b +c)(b
2
bc +c
2
) ,
from which it follows that 1 +a < b +c, yielding a contradition. Hence, the desired result follows.
Solution 4. [H. Pan] First, observe that a = c leads to b = 1 and a contradiction of the given conditions,
while a = b leads to c = 1 and a contradiction. Suppose, if possible, that that b > a > c. Then b
3
+ 1 >
a
3
+ 1 = b
3
+c
3
> c
3
+ 1, and c < 1 < b. Therefore,
bc > a b
3
c
3
> b
3
+c
3
1 (b
3
1)(c
3
1) > 0 ,
which contradicts b > 1 > c. In a similar way, we see that c > a > b cannot occur.
Thus, a must be either the largest or the smallest of the three numbers. Hence (a b)(a c) > 0,
whence a
2
+bc > a(b +c). Therefore
(b +c a)
3
= b
3
+c
3
a
3
+ 3b
2
c + 3bc
2
3ab
2
3ac
2
+ 3a
2
b + 3a
2
c 6abc
= 1 + 3b(a
2
+bc) + 3c(a
2
+bc) 3ab(b +c) 3ac(b +c)
= 1 + 3(b +c)[(a
2
+bc) a(b +c)] > 1
and the desired result follows.
22
Solution 5. [X. Li] If 1 +a
2
< b
2
+c
2
, then
(1 +a)
2
= 1 +a
2
+ 2a < b
2
+c
2
+ 2bc = (b +c)
2
,
whence b +c > 1 +a. On the other hand, if 1 +a
2
b
2
+c
2
, then
1 +a
2
a > b
2
+c
2
bc = (b
3
+c
3
)/(b +c) > 0 ,
whereupon,
(b +c)(b
2
+c
2
bc) = b
3
+c
3
= 1 +a
3
= (1 +a)(1 +a
2
a) > (1 +a)(b
2
+c
2
bc)
so that b +c > 1 +a.
Solution 6. [P. Gyrya] Let p(x) = x
3
3ax. Checking the rst derivative yields that p(x) is strictly
increasing for x >

a. Now 1 + a 2

a >

a and b + c 2

bc > 2

a >

a, so both 1 + a and b + c lie

in the part of the domain of p(x) where it strictly increases. Now
p(1 +a) = (1 +a)
3
3a(1 +a) = 1 +a
3
= b
3
+c
3
= (b +c)
3
3bc(b +c) < (b +c)
3
3a(b +c) = p(b +c)
from which it follows that 1 +a < b +c.
Solution 7. Consider the function g(x) = x(1 + a
3
x) = x(b
3
+ c
3
x). Then g(1) = g(a
3
) = a
3
and
g(b
3
) = g(c
3
) = (bc)
3
. Since a
3
< (bc)
3
and the graph of g(x) is a parabola opening down, it follows that b
3
and c
3
lie between 1 and a
3
.
Now consider the function h(x) = x
1/3
+ (b
3
+ c
3
x)
1/3
= x
1/3
+ (1 + a
3
x)
1/3
for 0 x 1 + a
3
.
Then h(1) = h(a
3
) = 1 +a and h(b
3
) = h(c
3
) = b +c. The graph of h(x) resembles an inverted parabola, so
since b
3
and c
3
lie between 1 and a
3
, it follows that 1 +a < b +c, as desired.
69. Let n, a
1
, a
2
, , a
k
be positive integers for which n a
1
> a
2
> a
3
> > a
k
and the least common
multiple of a
i
and a
j
does not exceed n for all i and j. Prove that ia
i
n for i = 1, 2, , k.
Solution 1. The result can be established by induction. It clearly holds when i = 1. Suppose that it
holds for 1 i m, so that, in particular ma
m
n. The least common multiple is equal to ba
m+1
= ca
m
for some positive integers b and c with c < b. If b m+ 1, then (m+ 1)a
m+1
ba
m+1
n by hypothesis.
Assume that b m. Then
(m+ 1)a
m+1
=
(m+ 1)c
b
a
m

(m+ 1)cn
bm
=
_
m+ 1
m
__
c
b
_
n
_
m+ 1
m
__
b 1
b
_
n
=
_
1
1
m
__
1
1
b
_
n
_
1 +
1
m
__
1
1
m
_
n =
_
1
1
m
2
_
n < n
as desired. The result now follows.
Solution 2. We can obtain the result by induction, it being known when i = 1. Suppose that the result
holds up to i = m. If (m+1)a
m
n, then the desired result for i = m+1 follows from a
m+1
> a
m
. On the
other hand, suppose that (m + 1)a
m
> n. With ba
m+1
= ca
m
the least common multiple of a
m
and a
m+1
,
we have that (m+ 1)a
m
> ca
m
, so that
a
m+1
=
c
b
a
m

c
c + 1
a
m

m
m+ 1
a
m

n
m+ 1
and the result follows.
23
70. Let f(x) be a concave strictly increasing function dened for 0 x 1 such that f(0) = 0 and f(1) = 1.
Suppose that g(x) is its inverse. Prove that f(x)g(x) x
2
for 0 x 1.
Comment. Begin with a sketch. The graph of the function is like a bow on top of a bowstring along
the line y = x. As x increases, the slope of the chord from the origin to (x, f(x)) decreases. The solution
begins with an analytic verication of this fact, using the denition of concavity.
Solution. Let 0 < v u. Then, taking t = (u v)/u in the denition of concavity, we have that
f(v)
vf(u) + (u v)f(0)
u
=
vf(u)
u
.
When (u, v) = (1, x), this yields f(x) x, so that x = g(f(x)) g(x) (since g(x) is an increasing function).
Let (u, v) = (x, g(x)) to obtain, for x ,= 0 that
x = f(g(x))
g(x)f(x)
x
.
It is straightforward to verify now that f(x)g(x) x
2
for all x [0, 1].
Comment. A special case is that f(x) = x
k
for 0 < k < 1, so that g(x) = x
1/k
. Then f(x)g(x) = x
k+(1/k)
and the result holds since 0 x 1 and k + (1/k) 2.
71. Suppose that lengths b, c and i are given. Construct a triangle ABC for which [AC[ = b. [AB[ = c and
the length of the bisector AD of angle A is i (D being the point where the bisector meets the side BC).
Solution 1. Analysis. Let AD meet the line through B parallel to AC in T. Then BTA = TAC =
TAB, so that [BT[ = [AB[ = c. By similar triangles, we have that [DT[ = ic/b so that [AT[ = i(b +c)/b.
Construction. Construct an isosceles triangle ABT with the lengths of AB and AT both equal to c
and the length of AT equal to i(b +c)/b. Cut AD o AT to have the length i, and let C be the intersection
of AD and the line through A parallel to BT.
Proof of construction. Since BAT = BTA = CAT, the segment AT bisects angle BAC. The
length of AD is i and the length of AB is c, by construction. From the similar triangles, DBT and ADC,
we nd that the length of AC is i multiplied by c = [BT[ and divided by [i(b +c)/b] i = ic/b = [DT[.
Feasibility. In order for the construction to work, we require that the sum of the lengths of AB and
BT exceed that of AT. This requires 2c > i(b +c)/b or i < 2bc/(b +c).
Solution 2. Analysis. Let be equal to angles BAD and CAD, where ABC is the required triangle
with bisector AD. Since the area of ABC is the sum of the areas of ABD and ADC, we have that
bc sin 2 = i(b +c) sin , whence cos = (b +c)i/2bc.
Sketch of construction and proof. By Euclidean means it is possible to construct the lengths b+c,
(b + c)i, 2bc and (b + c)/2bc using proportionalities. Thus, we can obtain the cosine of the angle , and so
nd itself. Construct triangle ABC with the respective lengths of AB and AC equal to c and b and
BAC = 2. The calculation in the analysis can be used to verify that the length of the bisector is equal to
2bc cos /(b +c), and so equal to i. Note that for to be found, it is necessary to have (b +c)i 2bc.
72. The centres of the circumscribed and the inscribed spheres of a given tetrahedron coincide. Prove that
the four triangular faces of the tetrahedron are congruent.
Solution 1. Let O be the common centre of the circumscribed and inscribed spheres of the tetrahedron
ABCD. The plane BCO bisects the dihedral angle formed by the planes BCD and BCA, so that the
circles determined by BCD and BCA in these planes must be congruent. Thus, BAC = BDC =
, say. Similarly, we nd that ABC = ADC = , ABC = ADC = , ACB = ADB = ,
BAD = BCD = , and BAD = BCD = . From the sum of angles of various triangles, we nd that
+ = +, + = + and + = +, whence = , = , = . From this, we see that all
24
the triangles are similar, and congruence follows from the fact that each pair of triangles have corresponding
sides in common.
Solution 2. Let R and r be respectively the circumradius and the inradius of ABCD, let the faces BCD,
ACD, ABD and ABC touch the insphere in the respective points P, Q, T, S, and let O be the common
centre of the insphere and the circumsphere. Since triangle OSA is right with [OS[ = r and [OA[ = R, we
have that [SA[ =

R
2
r
2
. Similarly, [SB[ = [SC[ =

R
2
r
2
, so that S is the centre of a circle with
radius

R
2
r
2
passing through A, B, C. The same can be said about P, Q, T, and the faces that contain
them.
It can be seen that ABT ABS, ACQ ACS, ADQ ADT, BCP BCS, BDP
BDR and CDP CDQ. Now
ABS +ACS = 90

BCS = 90

BCP = BDP +CDP

and
ABT +BDT = 90

DAT = 90

DAQ = ACQ+DCQ .
Since ABS = ABT, ACS = ACQ, BDP = BDT and CDP = DCQ, it follows that ABS
CDP = (ACS BDP) = 0

so ABC = BCD.
Obtaining other similar angle equalities, we can determine that the faces are equiangular. Taking note
of common sides, we can then deduce their congruence.
73. Solve the equation:
__
2 +

2
_
x
+
__
2

2
_
x
= 2
x
.
Solution 1. By inspection, we nd that x = 2 satises the equation. We show that no other value of x
does so. Observe that
_
2

2 < 1. When x < 0, the second term of the left side exceeds 1 while the right
side is less than 1, so the equation is not satised. Henceforth, let x 0 and let
f(x) 2
x

__
2 +

2
_
x
and g(x) = (
_
2

2)
x
.
Note that, if a > b > 1, then a
x
b
x
= b
x
((a/b)
x
1) is an increasing function of x. Thus, f(x) is
increasing and g(x) is decreasing as x increases. If 0 x < 2, then f(x) < f(2) = g(2) < g(x), while if
x > 2, then f(x) > f(2) = g(2) > g(x). The desired result follows.
Solution 2. The equation can be rewritten in the form
f(y) a
y
+ (1 a)
y
= 1
where 2y = x and a =
1
4
(2 +

2). Note that 0 < a < 1, so that each term is a strictly decreasing function
of y. Thus, f(y) assumes each of its values at most once, and since f(1) = 1, we nd that x = 2 is the only
solution.
Solution 3. Observe that
1 +

2
2
= 1 + cos

4
= 2 cos
2

8
and
1

2
2
= 1 sin

4
= 2 sin
2

8
.
25
The equation becomes
_
cos

8
_
x
+
_
sin

8
_
x
= 1 .
This holds for x = 2. If x > 2, then x 2 > 0 and so
_
cos

8
_
x
=
_
cos

8
_
x2
_
cos

8
_
2
<
_
cos

8
_
2
with a similar inequality for the sine function. Thus, when x > 2, the left side is less than 1. Similarly, it
can be shown that when x < 2, the left side exceeds 1. Hence the unique solution is x = 2.
Comment. Generally, the solutions involved a function similar to that used in Solution 2, and it was
shown that it was impossible for there to be more than one solution. Some students came up with the use
of trigonometry as in Solution 3.
74. Prove that among any group of n + 2 natural numbers, there can be found two numbers so that their
sum or their dierence is divisible by 2n.
Solution 1. For 0 k n, let S
k
be the subset of numbers x among the n + 2 numbers for which x
diers from either k or 2n k by a multiple of 2n. Since there are n + 2 numbers and only n + 1 subsets,
the Pigeonhole Principle provides that some subset must contain at least two numbers u and v, say. Either
u and v both leave the same remainder upon division by 2n and so dier by a multiple of 2n, or else one of
them diers from k by a multiple of 2n while the other diers from 2n k by a multiple of 2n. In the latter
case, u +v is a multiple of 2n.
Solution 2. [A. Fink] Consider an arbitrary set of n + 2 natural numbers. If any two are congruent
modulo 2n, then their dierence is divisible by 2n and the result follows. Suppose otherwise, that all numbers
have distinct residues modulo 2n. Apportion these residues into the n+1 sets: 0, 1, 2n1, 2, 2n2,
, n 1, n +1, n. Since there are n +2 numbers, at least one of these sets must contain two residues,
and so the two numbers involved must sum to a multiple of 2n.
75. Three consecutive natural numbers, larger than 3, represent the lengths of the sides of a triangle. The
area of the triangle is also a natural number.
(a) Prove that one of the altitudes cuts the triangle into two triangles, whose side lengths are natural
numbers.
(b) The altitude identied in (a) divides the side which is perpendicular to it into two segments. Find
the dierence between the lengths of these segments.
Solution 1. Let the side lengths be x 1, x, x + 1. By Herons formula, the area A of the triangle is
given by
A
2
=
3
16
x
2
(x + 2)(x 2) =
(3(x
2
4))x
2
16
.
Since A is an integer, x must be even and 3(x
2
4) must be the square of a multiple of 2 3 = 6. Hence
for some integer y, we have that 3(x
2
4) = (6y)
2
= 36y
2
or x
2
12y
2
= 4. (Comment. This is a
Pells equation and it has innitely many solutions (x, y) = (x
n
, y
n
) given by (x
n
, y
n
) = 2(7 + 2

12)
n
and
(4 +

12)(7 + 2

12)
n
.
(a) The area A of the triangle is
1
4
(6xy) =
3xy
2
where x is even and x
2
12y
2
= 4. The altitude to the
side of length x is 2A/x = 3y, an integer. This is the desired altitude.
(b) The triangle is subdivided by the altitude in (a) into two right triangles whose hypotenuses have
lengths x 1 and x + 1. Hence, the side of length x is split into two parts of lengths
_
(x 1)
2
(3y)
2
=
_
x
2
2x + 1 9y
2
=
_
(x
2
/4) 2x + 4 =
1
2
(x 4)
26
and
_
(x + 1)
2
(3y)
2
=
_
x
2
+ 2x + 1 9y
2
=
_
(x
2
/4) + 2x + 4 =
1
2
(x + 4) .
The dierence between the lengths of these segments is 4. (Note that the sum is x. as expected.) (Exercise.
Give some numerical examples.)
Solution 2. [L. Tchourakov] With the above notation, we nd that A = x
_
3(x
2
4)/4, so that the
length of the altitude to the side of length x is
1
2
_
3(x
2
4). If x were odd, then the numerator of the
fraction for A would be odd and A not an integer. Hence x is even, and so is the altitude. Let u be one of
the two parts of the side cut o by the altitude. By the pythagorean theorem,
u
2
= (x + 1)
2

3(x
2
4)
4
=
(x + 4)
2
4
,
so that u = 2 + x/2. Since x is even, u is an integer. The altitude cuts the side into parts of length u and
x u = u 4, and so (b) follows.
76. Solve the system of equations:
log x +
log(xy
8
)
log
2
x + log
2
y
= 2 ,
log y +
log(x
8
/y)
log
2
x + log
2
y
= 0 .
(The logarithms are taken to base 10.)
Solution 1. Let u = log x, v = log y and w = u
2
+v
2
. Note that w is nonzero. The equations become
u + (u + 8v)/w = 2 and v + (8u v)/w = 0 .
Squaring and adding the equations u + 8v = (2 u)w and 8u v = vw yields 65(u
2
+ v
2
) = (4 4w +
u
2
+v
2
)w
2
, or 65 = (4 4u +w)w. We can also write the system as
(w + 1)u + 8v = 2w
8u + (w 1)v = 0 ,
which can be solved to yield
u =
2w(w 1)
w
2
65
v =
16w
65 w
2
.
Hence
w = u
2
+v
2
=
4w
2
(w 1)
2
+ 256w
2
(65 w
2
)
=(65 w
2
)
2
= 4w(w 1)
2
+ 256w
=
0 = w
4
4w
3
122w
2
260w + 65
2
= (w 13)(w 5)[(w + 7)
2
+ 4
2
] .
The two relevant solutions are w = 13 and w = 5.
When w = 13, 17 4u = 5, which leads to (u, v) = (3, 2). When w = 5, 9 4u = 13, so that
(u, v) = (1, 2). The desired solutions are (x, y) = (10
3
, 10
2
), (10
1
, 10
2
).
Solution 2. With the same notation as (1), we can write the given equations in terms of u and v.
Multiply the rst equation by u and the second by v and add them to obtain the equation 2uv + 8 = 2v,
27
whereupon u = 1 (4/v). Eliminating u from the second equation yields v
4
16 = 0, whereupon v = 2 or
v = 2. The remaining part of the solution is easily completed.
77. n points are chosen from the circumference or the interior of a regular hexagon with sides of unit length,
so that the distance between any two of them is not less than

2. What is the largest natural number
n for which this is possible?
Solution. [O. Ivrii] Let the hexagon be ABCDEF. Consider the points A, C, E. Since the lengths of
AC, AE and CE are each

3 >

2, the task is possible for n = 3. We show that it is impossible for n 4.

Consider four points, M, N, P, Q, within the hexagon with each pair distant at least

2; let O be the
centre of the hexagon. We have that
2 [MN[
2
= [OM[
2
+[ON[
2
2[OM[[ON[ cos MON 1 + 1 2[OM[[ON[ cos MON .
It follows that cos MON 0, or MON 90

. Similarly, all four angles MON, NOP, POQ, QOM

should be at least 90

. Since the four sum to 360

, each must be exactly 90

, and so the lengths of each of

OM, ON, OP, OQ equal 1. Thus, all four points must be vertices of the hexagon. But this is impossible,
since no two diagonals of the hexagon intersect in a right angle.
Thus, we have proved by contradiction that n cannot be 4. It is straightforward to see that n cannot
exceed 4 either. So the largest n with the desired property is 3.
78. A truck travelled from town A to town B over several days. During the rst day, it covered 1/n of the
total distance, where n is a natural number. During the second day, it travelled 1/m of the remaining
distance, where m is a natural number. During the third day, it travelled 1/n of the distance remaining
after the second day, and during the fourth day, 1/m of the distance remaining after the third day. Find
the values of m and n if it is known that, by the end of the fourth day, the truck had travelled 3/4 of
the distance between A and B. (Without loss of generality, assume that m < n.)
Solution. [R. Furmaniak, J. Rin] Let d be the distance remaining at the beginning of a two-day period.
The distance remaining at the end of the period is
d
_
d
n
+
1
m
_
d
d
n
__
= d
_
1
1
m
__
1
1
n
_
.
Thus, every two days the remaining distance is reduced by a factor of r = (1 (1/m))(1 (1/n)). (Note
that this is symmetric in m and n.) After four days, the distance remaining is reduced by a factor of r
2
; it
is given in the problem that this is 1/4. Hence r = 1/2.
Hence
1
2
=
_
1
1
m
__
1
1
n
_
=mn = 2(m1)(n 1)
=0 = mn 2(m+n) + 2
=2 = (m2)(n 2) .
Since m and n are positive integers with m < n, we must have n2 = 2 and m2 = 1, i.e., (m, n) = (3, 4).
79. Let x
0
, x
1
, x
2
be three positive real numbers. A sequence x
n
is dened, for n 0 by
x
n+3
=
x
n+2
+x
n+1
+ 1
x
n
.
Determine all such sequences whose entries consist solely of positive integers.
28
Solution 1. Let the rst three terms of the sequence be x, y, z. Then it can be readily checked that the
sequence must have period 8, and that the entries cycle through the following:
x, y, z,
y +z + 1
x
,
x +y +z + 1 +xz
xy
,
(x +y + 1)(y +z + 1)
xyz
,
x +y +z + 1 +xz
yz
,
x +y + 1
z
.
For all of these entries to be positive integers, it is necessary that y + z + 1 be divisible by x, x + y + 1 be
divisible by z and (x + 1)(z + 1) be divisible by y. In particular, x y +z + 1 and z x +y + 1.
Without loss of generality, we can assume that the smallest entry in the sequence is y. Then,
y +z + 1
x
y
and
x +y + 1
z
y
whence
xy
2
= y(xy) y(y +z + 1)
= y
2
+yz +y y
2
+x +y + 1 +y
= x + (y + 1)
2
.
Hence
x(y
2
1) (y + 1)
2
so that either y = 1 or
y x
y + 1
y 1
= 1 +
2
y 1
.
The latter yields (y 1)
2
2 so that y 2.
Suppose that y = 1. Then x y +z + 1 = z + 2 y +x + 3 = x + 4. Since x divides x and y +z + 1,
it must divide their dierence, which cannot exceed 4. Hence x = y + z + 1 or x must be one of 1, 2, 3, 4.
Similarly, z = x +y + 1 or z must be one of 1, 2, 3, 4.
If x = y +z + 1 = z + 2, then x +y + 1 = z + 4 and so z divides 4. We get the periods
(3, 1, 1, 1, 3, 5, 9, 5)
(4, 1, 2, 1, 4, 3, 8, 3)
(6, 1, 4, 1, 6, 2, 9, 2) .
The case z = x+y+1 yields essentially the same periods. Otherwise, 1 x, z 4 and we nd the additional
possible period
(2, 1, 2, 2, 5, 4, 5, 2)
For each period, x
0
can start anywhere.
Suppose that y = 2. Then x y + z + 1 z + 3 x + 6, so that x must divide some number not
exceeding 6. Similarly, z cannot exceed 6. If x = 2, then x + y + 1 = 5 and so z = 5; this yields the period
(2, 2, 5, 4, 5, 2, 2, 1) already noted. If x = 3, then z must be 2, 3 or 6, and we obtain (3, 2, 3, 2, 3, 2, 3, 2); the
possibilities z = 2, 6 do not work. If x = 4, z = 7, which does not work. If x = 5, then z = 2, 4 and we get a
period already noted. If x = 6, then z = 3, which does not work.
29
Hence there are ve possible cycles and the sequence can begin at any term in the cycle:
(1, 1, 1, 3, 5, 9, 5, 3)
(1, 2, 1, 4, 3, 8, 3, 4)
(1, 2, 2, 5, 4, 5, 2, 2)
(1, 4, 1, 6, 2, 9, 2, 6)
(2, 3, 2, 3, 2, 3, 2, 3)
Solution 2. [O. Ivrii] We show that the sequence contains a term that does not exceed 2. Suppose that
none of x
0
, x
1
and x
2
is less than 3. Let k = max(x
1
, x
2
). Then, noting that k is an integer and that k 3,
we deduce that
x
3
=
x
1
+x
2
+ 1
x
0

2k + 1
3
< k
so x
3
k 1 and
x
4
=
x
2
+x
3
+ 1
x
1

2k
3
k 1
so that max(x
3
, x
4
) = k 1. If k 1 3, we repeat the process to get a strictly lower bound on the next two
terms. Eventually, we obtain two consecutive terms whose maximum is less than 3. In fact, we can deduce
that there is an entry equal to either 1 or 2 arbitrarily far out in the sequence.
Suppose, from some point on in the sequence, there is no term equal to 1. Then there are three
consecutive terms a, 2, b. The previous term is (a+3)/b and the following term is (b +3)/a, so that a divides
b + 3 and b divides a + 3. Since a 3 b a + 3, b divides two numbers that dier by at most 6; similarly
with a. Hence, neither a nor b exceeds 6. Testing out possibilities leads to (a, b) = (6, 3), (5, 2), (3, 3).
Finally, we suppose that the sequence has three consecutive terms a, 1, b and by similar arguments are
led to the sequences obtained in the rst solution.
Comment. C. Lau established that x
n
x
n+4
= x
n+2
x
n+6
and thereby obtained the periodicity. R.
Barrington Leigh showed that, if all terms of the sequence were at least equal to 2, then the sequence y
n

dened by y
n
= max(x
n
, x
n+1
) satises y
n+1
y
n
. Since the same recursion denes the sequence going
backwards, we also have y
n1
y
n
, for all n. Hence y
n
is a constant sequence, and so x
n
is either
constant or has period 2. It is straightforward to rule out the constant possibility. If the periodic segment
of the sequence is (a, b), then b = (a + b + 1)/a or (a 1)(b 1) = 2 and we are led to the segment (2, 3).
Otherwise, there is a 1 in the sequence and we can conclude as before.
80. Prove that, for each positive integer n, the series

k=1
k
n
2
k
converges to twice an odd integer not less than (n + 1)!.
Solution 1. Since the series consists of nonnegative terms, we can establish its convergence by eventually
showing that it is dominated term by term by a geometric series with common ratio less than 1. Noting that
n k log
k
(3/2) for k suciently large, we nd that for large k, k
n
< (3/2)
k
and the kth term of the series
is dominated by (3/4)
k
. Thus the sum of the series is dened for each nonnegative integer n.
For nonnegative integers n, let
S
n
=

k=1
k
n
2
k
.
30
Then S
0
= 1 and
S
n

1
2
S
n
=

k=1
k
n
2
k

k=1
k
n
2
k+1
=

k=1
k
n
2
k

k=1
(k 1)
n
2
k
=

k=1
k
n
(k 1)
n
2
k
=

k=1
__
n
1
_
k
n1
2
k

_
n
2
_
k
n2
2
k
+
_
n
3
_
k
n3
2
k
+ (1)
n1
1
2
k
_
whence
S
n
= 2
__
n
1
_
S
n1

_
n
2
_
S
n2
+
_
n
3
_
S
n3
+ (1)
n1
_
.
An induction argument establishes that S
n
is twice an odd integer.
Observe that S
0
= 1, S
1
= 2, S
2
= 6 and S
3
= 26. We prove by induction that, for each n 0,
S
n+1
(n + 2)S
n
from which the desired result will follow. Suppose that we have established this for n = m1. Now
S
m+1
= 2
__
m+ 1
1
_
S
m

_
m+ 1
2
_
S
m1
+
_
m+ 1
3
_
S
m2

_
m+ 1
4
_
S
m3
+
_
.
For each positive integer r,
_
m+ 1
2r 1
_
S
m2r+2

_
m+ 1
2r
_
S
m2r+1

__
m+ 1
2r 1
_
(m2r + 3)
_
m+ 1
2r
__
S
m2r+1
=
_
m+ 1
2r 1
_
[(m2r + 3)
_
m2r + 2
2r
__
S
m2r+1
0 .
When r = 1, we get inside the square brackets the quantity
(m+ 1)
m
2
=
m+ 2
2
while when r > 1, we get
(m2r + 3)
_
m2r + 2
2r
_
> (m2r + 3) (m2r + 2) = 1 .
Hence
S
m+1
2
__
m+ 1
1
_
S
m

_
m+ 1
2
_
S
m1
_
2
_
(m+ 1)S
m

m(m+ 1)
2

1
m+ 1
S
m
_
= 2
_
m+ 1
m
2
_
s
m
= (m+ 2)S
m
.
31
Solution 2. Dene S
n
as in the foregoing solution. Then, for n 1,
S
n
=
1
2
+

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

k=1
(k + 1)
n
2
k
=
1
2
+
1
2

k=1
k
n
+
_
n
1
_
k
n1
+ +
_
n
n1
_
k + 1
2
k
=
1
2
+
1
2
_
S
n
+
_
n
1
_
S
n1
+ +
_
n
n 1
_
S
1
+ 1
_
whence
S
n
=
_
n
1
_
S
n1
+
_
n
2
_
S
n2
+ +
_
n
n 1
_
S
1
+ 2 .
It is easily checked that S
k
2 (mod 4) for k = 0, 1. As an induction hypothesis, suppose this holds for
1 k n 1. Then, modulo 4, the right side is congruent to
2[
n

k=0
_
n
k
_
2] + 2 = 2(2
n
2) + 2 = 2
n+1
2 ,
and the desired result follows.
For n 1,
S
n+1
S
n
=
_
n+1
1
_
S
n
+
_
n+1
2
_
S
n1
+ +
_
n+1
n
_
S
1
+ 2
S
n
= (n + 1) +
_
n+1
2
_
S
n1
+
_
n+1
3
_
S
n2
+ + (n + 1)S
1
+ 2
_
n
1
_
S
n1
+
_
n
2
_
S
n2
+ +nS
1
+ 2
(n + 1) + 1 = n + 2 ,
since each term in the numerator of the latter fraction exceeds each corresponding term in the denominator.
Solution 3. [of the rst part using an idea of P. Gyrya] Let f(x) be a dierentiable function and let D
be the dierentiation operator. Dene the operator L by
L(f)(x) = x D(f)(x) .
Suppose that f(x) = (1 x)
1
=

k=0
x
k
. Then, it is standard that L
n
(f)(x) has a power series expansion
obtained by term-by-term dierentiation that converges absolutely for [x[ < 1. By induction, it can be shown
that the series given in the problem is, for each nonnegative integer n, L
n
(f)(1/2).
It is straightforward to verify that
L((1 x)
1
) = x(1 x)
2
L
2
((1 x)
1
) = x(1 +x)(1 x)
3
L
3
((1 x)
1
) = x(1 + 4x +x
2
)(1 x)
4
L
4
((1 x)
1
) = x(1 + 11x + 11x
2
+x
3
)(1 x)
5
.
In general, a straightforward induction argument yields that for each positive integer n,
L
n
(f)(x) = x(1 +a
n,1
x + +a
n,n2
x
n2
+x
n1
)(1 x)
(n+1)
32
for some integers a
n,1
, , a
n,n2
. Hence
L
n
(f)(1/2) = 2(2
n1
+a
n,1
2
n2
+ +a
n,n2
2 + 1) ,
yielding the desired result.
81. Suppose that x 1 and that x = x| +x, where x| is the greatest integer not exceeding x and the
fractional part x satises 0 x < 1. Dene
f(x) =
_
x| +
_
x

x
.
(a) Determine the smallest number z such that f(x) z for each x 1.
(b) Let x
0
1 be given, and for n 1, dene x
n
= f(x
n1
). Prove that lim
n
x
n
exists.
81. Solution. (a) Let x = y +z, where y = x| and z = x. Then
f(x)
2
= 1 +
2

yz
y +z
,
which is less than 2 because

yz
1
2
(y + z) by the arithmetic-geometric means inequality. Hence 0
f(x)

2 for each value of x. Taking y = 1, we nd that

lim
x2
f(x)
2
= lim
z1
_
1 +
2

z
1 +z
_
= 2 ,
whence supf(x) : x 1 =

2.
(b) In determining the fate of x
n
, note that after the rst entry, the sequence lies in the interval [1, 2).
So, without loss of generality, we may assume that 1 x
0
< 2. If x
n
= 1, then each x
n
= 1 and the limit is
1. For the rest, note that f(x) simplies to (1 +

x 1)/

x on (1, 2). The key point now is to observe that

there is exactly one value v between 1 and 2 for which f(v) = v, f(x) > x when 1 < x < v and f(x) < x
when v < x < 2. Assume these facts for a moment. A derivative check reveals that f(x) is strictly increasing
on (1, 2), so that for 1 < x < v, x < f(x) < f(v) = v, so that the iterates x
n
constitute a bounded,
increasing sequence when 1 < x
0
< v which must have a limit. (In fact, this limit must be a xed point of
f and so must be v.) A similar argument shows that, if v < x
0
< 2, then the sequence of iterates constitute
a decreasing convergent sequence (with limit v).
It remains to show that a unique xed point v exists. Let x = 1 +u with u > 0. Then it can be checked
that f(x) = x if and only if 1 +2

u +u = 1 +3u +3u
2
+u
3
or u
5
+6u
4
+13u
3
+12u
2
+4u 4 = 0. Since
the left side is strictly increasing in u, takes the value 4 when u = 0 and the value 32 when u = 1, the
equation is satied for exactly one value of u in (0, 1); now let v = 1 + u. The value of V turns out to be
about 1.375, (Note that f(x) > x if and only if x < u.)
82. (a) A regular pentagon has side length a and diagonal length b. Prove that
b
2
a
2
+
a
2
b
2
= 3 .
(b) A regular heptagon (polygon with seven equal sides and seven equal angles) has diagonals of two
dierent lengths. Let a be the length of a side, b be the length of a shorter diagonal and c be the length
of a longer diagonal of a regular heptagon (so that a < b < c). Prove that:
a
2
b
2
+
b
2
c
2
+
c
2
a
2
= 6
33
and
b
2
a
2
+
c
2
b
2
+
a
2
c
2
= 5 .
82. Solution 1. (a) Let ABCDE be the regular pentagon, and let triangle ABC be rotated about C so
that B falls on D and A falls on E. Then ADE is a straight angle and triangle CAE is similar to triangle
BAC. Therefore
a +b
b
=
b
a
=
b
a

a
b
= 1 =
b
2
a
2
+
a
2
b
2
2 = 1
so that b
2
/a
2
+a
2
/b
2
= 3, as desired.
(b) Let A, B, C, D, E be consecutive vertices of the regular heptagon. Let AB, AC and AD have
respective lengths a, b, c, and let BAC = . Then = /7, the length of BC, of CD and of DE is a, the
length of AE is c, CAD = DAE = , since the angles are subtended by equal chords of the circumcircle
of the heptagon, ADC = 2, ADE = AED = 3 and ACD = 4. Triangles ABC and ACD can be
glued together along BC and DC (with C on C) to form a triangle similar to ABC, whence
a +c
b
=
b
a
. (1)
Triangles ACD and ADE can be glued together along CD and ED (with D on D) to form a triangle similar
to ABC, whence
b +c
c
=
b
a
. (2)
Equation (2) can be rewritten as
1
b
=
1
a

1
c
. whence
b =
ac
c a
.
Substituting this into (1) yields
(c +a)(c a)
ac
=
c
c a
which simplies to
a
3
a
2
c 2ac
2
+c
3
= 0 . (3)
Note also from (1) that b
2
= a
2
+ac.
a
2
b
2
+
b
2
c
2
+
c
2
a
2
6 =
a
4
c
2
+b
4
a
2
+c
4
b
2
6a
2
b
2
c
2
a
2
b
2
c
2
=
a
4
c
2
+ (a
4
+ 2a
3
c +a
2
c
2
)a
2
+c
4
(a
2
+ac) 6a
2
c
2
(a
2
+ac)
a
2
b
2
c
2
=
a
6
+ 2a
5
c 4a
4
c
2
6a
3
c
3
+a
2
c
4
+ac
5
a
2
b
2
c
2
=
a(a
2
+ 3ac +c
2
)(a
3
a
2
c 2ac
2
+c
3
)
a
2
b
2
c
2
= 0 .
b
2
a
2
+
c
2
b
2
+
a
2
c
2
5 =
(a
4
+ 2a
3
c +a
2
c
2
)c
2
+a
2
c
4
+a
4
(a
2
+ac) 5a
2
c
2
(a
2
+ac)
a
2
b
2
c
2
=
a
6
+a
5
c 4a
4
c
2
3a
3
c
3
+ 2a
2
c
4
a
2
b
2
c
2
=
a
2
(a + 2c)(a
3
a
2
c 2ac
2
+c
3
)
a
2
b
2
c
2
= 0 .
34
Solution 2. (b) [R. Barrington Leigh] Let the heptagon be ABCDEFG; let AD and BG intersect at
P, and BF and CG intersect at Q. Observe that [PD[ = [GE[ = b, [AP[ = c b, [GP[ = [DE[ = a,
[BP[ = b a, [GQ[ = [AB[ = a, [CQ[ = c a. From similarity of triangles, we obtain the following:
a
c
=
c b
a
=
a
c

c
a
+
b
a
= 0 (APG ADE)
c a
a
=
c
b
=
c
a

c
b
= 1 (QBC CEG)
c b
a
=
b a
b
=
c
a

b
a
+
a
b
= 1 (APG DPB)
b a
a
=
b
c
=
b
a

b
c
= 1 (ABP ADB) .
Adding these equations in pairs yields
b
a
+
a
c

c
b
= 1 =
b
2
a
2
+
a
2
c
2
+
c
2
b
2
+ 2
_
b
c

c
a

a
b
_
= 1
and
c
a
+
a
b

b
c
= 2 =
c
2
a
2
+
a
2
b
2
+
b
2
c
2
+ 2
_
c
b

b
a

a
c
_
= 4 .
The desired result follows from these equations.
Solution 3. (b) [of the second result by J. Chui] Let the heptagon be ABCDEFG and = /7. Using
the Law of Cosines in the indicated triangles ACD and ABC, we obtain the following:
cos 2 =
a
2
+c
2
b
2
2ac
=
1
2
_
a
c
+
c
a

b
2
ac
_
cos 5 =
2a
2
b
2
2a
2
= 1
1
2
_
b
a
_
2
from which, since cos 2 = cos 5,
1 +
1
2
_
b
a
_
2
=
1
2
_
a
c
+
c
a

b
2
ac
_
or
b
2
a
2
= 2 +
a
c
+
c
a

b
2
ac
. (1)
Examining triangles ABC and ADE, we nd that cos = b/2a and cos = (2c
2
a
2
)/(2c
2
) = 1
(a
2
/2c
2
), so that
a
2
c
2
= 2
b
a
. (2)
Examining triangles ADE and ACF, we nd that cos 3 = a/2c and cos 3 = (2b
2
c
2
)/(2b
2
), so that
c
2
b
2
= 2
a
c
. (3)
Adding equations (1), (2), (3) yields
b
2
a
2
+
c
2
b
2
+
a
2
c
2
= 6 +
c
2
bc b
2
ac
.
35
By Ptolemys Theorem, the sum of the products of pairs of opposite sides of a concylic quadrilaterial is equal
to the product of the diagonals. Applying this to the quadrilaterals ABDE and ABCD, respectively, yields
c
2
= a
2
+bc and b
2
= ac +a
2
, whence c
2
bc b
2
= a
2
+bc bc ac a
2
= ac and we nd that
b
2
a
2
+
c
2
b
2
+
a
2
c
2
= 6 1 = 5 .
Solution 4. [of the second result by X. Jin] By considering isosceles triangles with side-base pairs (a, b),
(c, a) and (b, c), we nd that b
2
= 2a
2
(1 cos 5), a
2
= 2c
2
(1 cos ), c
2
= 2b
2
(1 cos 3), where = /7.
Then
b
2
a
2
+
c
2
b
2
+
a
2
c
2
= 2[3 (cos + cos 3 + cos 5)] .
Now,
sin (cos theta + cos 3 + cos 5) =
1
2
[sin 2 + (sin 4 sin 2) + (sin 6 sin 4)]
=
1
2
sin 6 =
1
2
sin ,
so that cos + cos 3 + cos 5 = 1/2. Hence b
2
/a
2
+c
2
/b
2
+a
2
/c
2
= 2(5/2) = 5.
Solution 5. (b) There is no loss of generality in assuming that the vertices of the heptagon are placed
at the seventh roots of unity on the unit circle in the complex plane. Then = cos(2/7) + i sin(2/7) be
the fundamental seventh root of unity. Then
7
= 1, 1 + +
2
+ +
6
= 0 and (,
6
), (
2
,
5
), (
3
,
4
)
are pairs of complex conjugates. We have that
a = [ 1[ = [
6
1[
b = [
2
1[ = [
9
1[
c = [
3
1[ = [
4
1[ .
It follows from this that
b
a
= [ + 1[
c
b
= [
2
+ 1[
a
c
= [
3
+ 1[ ,
whence
b
2
a
2
+
c
2
b
2
+
a
2
c
2
= ( + 1)(
6
+ 1) + (
2
+ 1)(
5
+ 1) + (
3
+ 1)(
4
+ 1)
= 2 + +
6
+ 2 +
2
+
5
+ 2 +
3
+
4
= 6 + ( +
2
+
3
+
4
+
5
+
6
) = 6 1 = 5 .
Also
a
b
= [
4
+
2
+ 1[
b
c
= [
6
+
3
+ 1[
c
a
= [
2
+ + 1[ ,
whence
a
2
b
2
+
b
2
c
2
+
c
2
a
2
= (
4
+
2
+ 1)(
3
+
5
+ 1) + (
6
+
3
+ 1)( +
4
+ 1) + (
2
+ + 1)(
5
+
6
+ 1)
= (3 + 2
2
+
3
+
4
+ 2
5
) + (3 + + 2
3
+ 2
4
+
6
) + (3 + 2 +
2
+
5
+ 2
6
)
= 9 + 3( +
2
+
3
+
4
+
5
+
6
) = 9 3 = 6 .
Solution 6. (b) Suppose that the circumradius of the heptagon is 1. By considering isosceles triangles
with base equal to the sides or diagonals of the heptagon and apex at the centre of the circumcircle, we see
that
a = 2 sin = 2 sin 6 = 2 sin 8
b = 2 sin 2 = 2 sin 9
c = 2 sin 3 = 2 sin 4
36
where = /7 is half the angle subtended at the circumcentre by each side of the heptagon. Observe that
cos 2 =
1
2
( +
6
) cos 4 =
1
2
(
2
+
5
) cos 6 =
1
2
(
3
+
4
)
where is the fundamental primitive root of unity. We have that
b
a
= 2 cos = 2 cos 6
c
b
= 2 cos 2
a
c
= 2 cos 4
whence
b
2
a
2
+
c
2
b
2
+
a
2
c
2
= 4 cos
2
6 + 4 cos
2
2 + 4 cos
2
4
= (
3
+
4
)
2
+ ( +
6
)
2
+ (
2
+
5
)
2
=
6
+ 2 + +
2
+ 2 +
5
+
4
+ 2 + = 6 1 = 5 .
Also
a
b
=
sin 6
sin 2
= 4 cos
2
2 1 = ( +
6
)
2
1 = 1 +
2
+
5

b
c
=
sin 9
sin 3
= 4 cos
2
3 1 = 4 cos
2
4 1 = (
2
+
5
)
2
1 = 1 +
4
+
3
c
a
=
sin 3
sin
= 4 cos
2
6 1 = (
3
+
4
)
2
1 = 1 +
6
+ ,
whence
a
2
b
2
+
b
2
c
2
+
c
2
a
2
= (3 + 2
2
+
3
+
4
+ 2
5
) + (3 + + 2
3
+ 2
4
+
6
) + (3 + 2 +
2
+
5
+ 2
6
)
= 9 + 3( +
2
+
3
+
4
+
5
+
6
) = 9 3 = 6 .
83. Let C be a circle with centre O and radius 1, and let F be a closed convex region inside C. Suppose
from each point on C, we can draw two rays tangent to F meeting at an angle of 60

. Describe F.
Solution. Let A be an arbitrary point on the circumference of C. Draw rays AC, AB, BD tangent to
F; let AC and BD intersect at P. Since CAB = ABD = 60

, APM = 60

and APB is equilateral

and contains F. Suppose, if possible, that P lies strictly inside the circle. Let CE be the second ray from C
tangent to F. Then ACE = 60

, so CE is parallel to DB and lies strictly on the opposite side of BD to

F; thus, it cannot be tangent to F and we have a contradiction. Similarly, if P lies strictly outside the circle,
the second ray from C, CE, tangent to F is parallel to and distinct from BD. We have that F is tangent to
AC, BD and CE, an impossibility since DE, within the circle, lies between CE and DB.
Hence C = D = P and ABC is an equilateral triangle containing F with all its sides tangent to F. Since
A is arbitrary, F is contained within the intersection of all such triangles, namely the circle D with centre
O and radius 1/2, and every chord of the given circle tangent to F has length

3. If F were a proper subset
of D, there would be a point Q on the circumference of D outside F. and a tangent of F separating F from
Q. This tangent chord would intersect the interior of D and so be longer than

3, yielding a contradiction.
Hence F must be the circle D.
84. Let ABC be an acute-angled triangle, with a point H inside. Let U, V , W be respectively the reected
image of H with respect to axes BC, AC, AB. Prove that H is the orthocentre of ABC if and only
if U, V , W lie on the circumcircle of ABC,
Solution 1. Suppose that H is the orthocentre of ABC. Let P, Q, R be the respective feet of the
altitudes from A, B, C. Since BC right bisects HU, HBP UBP and so HBP = UBP. Thus
ACB = QCB = 90

QBC = 90

HBP
= 90

UBP = PUB = AUB ,

37
so that ABUC is concyclic and U lies on the circumcircle of ABC. Similarly V and W lie on the
circumcircle.
Now suppose that U, V, W lie on the circumcircle. Let C
1
, C
2
, C
3
be the respective reections of the
circumcircle about the axes BC, CA, AB. These three circles intersect in the point H. If H

is the
orthocentre of the triangle, then by the rst part of the solution, the reective image of H

about the three

axes lies on the circumcircle, so that H

belongs to C
1
, C
2
, C
3
and H = H

or else HH

is a common chord
of the three circles. But the latter does not hold, as the common chords AH, BH and CH of pairs of the
circles intersect only in H.
Solution 2. Let H be the orthocentre, and P, Q, R the pedal points as dened in the rst solution.
Since ARHQ is concyclic
BAC +BUC = BAC +BHC = RAQ+RHQ = 180

and so ABUC is concyclic. A similar argument holds for V and W.

[A. Lin] Suppose that U, V , W are on the circumcircle. From the reection about BC, BCU = BCH.
From the reections about BA and BC, we see that BW = BH = BU, and so, since the equal chords BW
and BU subtend equal angles at C, BCW = BCU. Hence BCW = BCH, with the result that
C, H, W are collinear and CW is an altitude. Similarly, AU and BV are altitudes that contain H, and so
their point H of intersection must be the orthocentre.
85. Find all pairs (a, b) of positive integers with a ,= b for which the system
cos ax + cos bx = 0
a sin ax +b sin bx = 0 .
Solution 1. Suppose that the system is solvable; note that x = 0 is not a solution. Then cos ax = cos bx
so that sin ax = sin bx where = 1. Hence (a + b) sin bx = 0. Since a and b are positive and unequal,
a +b ,= 0, so that sin bx = 0. Hence bx = n for some integer n. Also sin ax = 0, so that ax = m for some
integer m. Hence, we must have an = bm for some integers m and n. Since cos m = cos n, m and n
must have opposite parity.
Suppose that a = 2
u
p and b = 2
v
q with u and v unequal integers and p and q odd. Then x = 2
w
.
where w is the minimum of u and v satises the system of equations.
Solution 2. First, observe that x ,= 0 for any solution. If the system is satised, then
0 = cos ax + cos bx = 2 cos
1
2
(a +b)xcos
1
2
(a b)x
=cos
1
2
(a +b)x = 0 or cos
1
2
(a b)x = 0
=
1
2
(a +b)x = (2k + 1)

2
or
1
2
(a b)x = (2k + 1)

2
=ax bx = (2k + 1) for some integer k
=sin ax = sin(bx) = sin bx
=0 = a sin ax +b sin bx = (a b) sin bx .
Since a ,= b and a + b > 0, 0 = sin bx = sin ax, so that ax = m and bx = n for some integers m and n.
Since 0 = cos ax + cos bx = (1)
m
+ (1)
n
, the integers m and n must have dierent parity. Hence
x =
m
a
=
n
b
38
where m and n are integers not both even or both odd. Since x ,= 0, a/b = m/n, so a/b in lowest terms
must have numerator and denominator of dierent parities.
We now show that, for any pair a, b satisfying this condition, there is a solution. Wolog, let a = 2uw
and v = (2v + 1)w, where the greatest common divisor of 2u and 2v + 1 is 1, and w is an arbitrary positive
integer. Suppose that x = /w. Then
cos ax + cos bx = cos 2u + cos(2v + 1) = 1 1 = 0
and
a sin ax +b sin bx = a sin 2u +b sin(2v + 1) = 0 + 0 = 0
as desired.
Solution 3. Since cos
2
ax = cos
2
bx and a
2
sin
2
ax +b
2
sin
2
bx, then
a
2
cos
2
bx +b
2
sin
2
bx = a
2
=(b
2
a
2
) sin
2
bx = 0
so that bx = n for some integer. Similarly ax = m. The solution can be completed as before.
Comment. Note that there are two parts to the solution of this problem, and your write-up should
make sure that these are carefully delineated. First, assuming that there is a solution, you derive necessary
conditions on a and b that the two equations are consistent. Then, you assume these conditions on a and b,
and then display a solution to the two equations. A complete solution requires noting that suitable numbers
a and b actually do lead to a solution.
86. Let ABCD be a convex quadrilateral with AB = AD and CB = CD. Prove that
(a) it is possible to inscribe a circle in it;
(b) it is possible to circumscribe a circle about it if and only if AB BC;
(c) if AB BC and R and r are the respective radii of the circumscribed and inscribed circles, then
the distance between the centres of the two circles is equal to the square root of R
2
+r
2
r

r
2
+ 4R
2
.
Comment. Most students picked up the typo in part (c) in which AC was given instead of the intended
BC. I am sorry for the mistake. However, this does happen from time to time even on competitions, and
you should be alert. From the context of this problem, the intention was probably pretty clear (in fact, some
of you might not have realized that there was an error). The rule in such a situation is that, if you feel that
there is an error, make a reasonable nontrivial interpretation of the problem, state it clearly and solve it.
Solution 1. (a) Triangles ABC and ADC are congruent (SSS) with the congruence implemented by a
reection in AC. Hence AC bisects angles DAB and DCB. The angle bisectors of ADB and ABC are
reected images and intersect in I, a point on AC. Since I is equidistant from the four sides of the kite
ABCD, it is the centre of its incircle.
(b) If AB BC, then the circle with diameter AC passes through B. By symmetry about AC, it must
pass through D as well. Conversely, let C be the circumcircle of ABCD. The circle goes to itself under
reection in AC, so AC must be a diameter of C. Hence ABC = ADC = 90

.
(c) Let I be the incentre and O the circumcentre of ABCD; both lie on AC. Suppose that J and K
are the respective feet of the perpendiculars to AB and BC from I, and P and Q the respective feet of the
perpendiculars to AB and BC from O. Let x = [AB[ and y = [BC[. Then
x
y
=
x r
r
xy = r(x +y) .
Since [AO[ = [OC[ = R, 4R
2
= x
2
+y
2
. Noting that x and y both exceed r, we have that
39
(x +y)
2
= x
2
+y
2
+ 2xy = 4R
2
+ 2r(x +y)
(x +y r)
2
= r
2
+ 4R
2
x +y = r +
_
r
2
+ 4R
2
.
Now
[IO[
2
= [JP[
2
+[KQ[
2
= ([JB[
1
2
[AB[)
2
+ ([KB[
1
2
[BC[)
2
= 2r
2
r(x +y) +
1
4
(x
2
+y
2
) = r
2
r
_
r
2
+ 4R
2
+R
2
,
yielding the desired result.
Solution 2. (a) Since triangles ADB and CDB are isosceles, the angle bisectors of A and C right bisect
the base BD and so they coincide. The line AC is an axis of reective symmetry that interchanges B and
D, and also interchanges the angle bisectors of B and D. The point P where one of the bisectors intersects
the axis AC is xed by the reection and so lies on the other bisector. Hence, P is common to all four angle
bisectors, and so is equidistant from the four sides of the quadrilateral. Thus, we can inscribe a circle inside
ABCD with centre P.
(b) Since AC is a line of symmetry, B = D. Note that, ABCD has a circumcircle pairs of opposite
angles sum to 180

B +D = 180

B = D = 90

. This establishes the result.

(c) [R. Barrington Leigh] Let a, b and c be the respective lengths of the segments BC, AC and AB.
Let O and I be, respectively, the circumcentre and the incentre for the quadrilateral. Note that both points
lie on the diagonal AC. Wolog, we may take a c.
We observe that ABI = 45

and that BI is the hypotenuse of an isosceles right triangle with arms of

length r. We have, by the Law of Cosines,
d
2
= R
2
+ 2r
2
2

2Rr cos IBO

= R
2
+ 2r
2
2

2Rr
_
cos
_
ABO

4
__
= R
2
+ 2r
2
2

2Rr[cos ABO(1/

2) + sin ABO(1/

2)]
= R
2
+ 2r
2
2Rr[cos ABO + cos CBO]
= R
2
+ 2r
2
2Rr[cos BAC + cos BCA]
= R
2
+ 2r
2
2Rr
_
a +c
b
_
= R
2
+ 2r
2
r(a +c) ,
since b = 2R and both triangle AOB and COB are isosceles with arms of length R.
By looking at the area of ABC in two ways, we have that ac = r(a +c). Now
(a +c r)
2
= a
2
+c
2
+r
2
+ 2[ac r(a +c)] = a
2
+c
2
+r
2
= 4R
2
+r
2
,
so that a +c = r +

4R
2
+r
2
. (The positive root is selected as a and c both exceed r.) Hence
d
2
= R
2
+ 2r
2
r[r +
_
4R
2
+r
2
]
= R
2
+r
2
r
_
r
2
+ 4R
2
.
87. Prove that, if the real numbers a, b, c, satisfy the equation
na| +nb| = nc|
40
for each positive integer n, then at least one of a and b is an integer.
Solution. We rst show that a+b = c. Suppose, if possible, that c > a+b. Let n (c ab)
1
. Then
nc| > nc 1 > n(a +b) > na| +nb|
yielding a contradiction. Similarly, if c < a +b and n 2(a +b c)
1
, then
nc| nc na 1 +nb 1 < na| +nb|
again yielding a contradiction. Hence a +b = c.
Let a = a| + , b = b| + and c = c| + . From the condition for n = 1, we have a| + b| = c|.
Then, na| = na| + n| = na| + n| with similar equations for b and c. Putting this together gives
that n| + n| = n|, for all n 1. As in the rst part of the solution, we have that + = , from
which n +n = n for all n 1, where x denotes the fractional part x x| of x.
We rst show that , and cannot all be positive and rational. For, if they were rational, then
for some positive integers i, j, k with k 2, we would have = i/k, = j/k and = (i + j)/k. Then
k| = i = (k 1)| + 1, with similar relations for and . Thus,
k| +k| k| [(k 1)| +(k 1)| (k 1)|] = 1
so that n| +n| = n| must fail for either n = k or n = k 1.
Wolog, suppose that all of , , are positive with irrational. Let p be a nonnegative integer for
which + p < 1 + (p + 1) and suppose that = 1 ( + p). Since + = < 1, it follows that
p 1.
We show that there is a positive integer m 2 for which + p < m. Let t = 1/| and consider
the intervals [i/t, (i + 1)/t) where 0 i t 1. By the Pigeonhole Principle, one of these intervals
must contain two of the numbers 2, 4, , 2(t + 1), say q and r with q r + 2. Thus,
[q r[ < 1/t . Since
q r = (q r) q| +r| = (q r) I
for some integer I, either (q r) < or (q r) > 1 .
In the rst case, we can nd a positive integer s for which 1 > s(q r) > 1 . Since
s(q r) = s(q r)| +s(q r) ,
it follows that
s(q r) = s(q r) > 1 .
Thus, in either case, we can nd m 2 for which +p = 1 < m.
Now, m > ,
m = m +m m > +p + =
and
m = m m < 1 ( +p) = 1 [ + (p + 1) ] 1 (1 ) = .
Hence,
m| = m m = (m1) (m ) < (m1)
so that (m1)| = m|;
m| = m m = (m1) (m ) < (m1)
41
so that (m1)| = m|; and m| = mm > (m1) (m1)|, so that (m1)|+1 = m|.
Hence n| +n| = n| must fail for either n = m or n = m1.
The only remaining possibility is that either or vanishes, i.e., that a or b is an integer. This
possibility is feasible when the other two variables have the same fractional part.
88. Let I be a real interval of length 1/n. Prove that I contains no more than
1
2
(n+1) irreducible fractions
of the form p/q with p and q positive integers, 1 q n and the greatest common divisor of p and q
equal to 1.
Comment. The statement of the problem needs a slight correction. The result does not apply for closed
intervals of length 1/n whose endpoints are consecutive fractions with denominator n. The interval [1/3, 2/3]
is a counterexample. So we need to strengthen the hypothesis to exclude this case, say by requiring that
the interval be open (i.e., not include its endpoints), or by supposing that not both endpoints are rational.
Alternatively, we could change the bound to
1
2
(n + 3) and ask under what circumstances this bound is
achieved.
Solution 1. We rst establish a lemma: Let 1 q n. Then there exists a positive integer m for which
1
2
(n + 1) mq n. For, let m = n/q|. If q > n/2, then m = 1 and clearly
1
2
(n + 1) mq = q n. If
q n/2, then (n/q) 1 < m (n/q), so that
n
2
n q < mq n
and
1
2
(n + 1) mq n.
Let p/q and p

/q

be two irreducible fractions in I with m and m

corresponding integers as determined

by the lemma. Suppose, if possible, that mq = m

. Then

p
q

p

mp
mq

m

mq

1
mq

1
n
,
contradicting the fact that no two fractions in I can be distant at least
1
n
.
It follows that the mapping p/q mq from the set of irreducible fractions in I into the set of integers in
the interval [(n+1)/2, n] is one-one. But the latter set has at most n((n+1)/2) +1 = (n+1)/2 elements,
and the result follows.
Solution 2. [M. Zaharia] For 1 i
1
2
(n + 1), dene
S
i
= 2
j
(2i 1) : j = 0, 1, 2, .
(Thus, S
1
= 1, 2, 4, 8, , S
3
= 3, 6, 12, 24, and S
5
= 5, 10, 20, 40, , for example.) We show that
each S
i
contains at most one denominator not exceeding n among the irreducible fractions in I. For suppose
a
2
u
(2i 1)
and
b
2
v
(2i 1)
are distinct irreducible fractions in I, with u v. Then

a
2
u
(2i 1)

b
2
v
(2i 1)

2
vu
a b
2
v
(2i 1)

1
2
v
(2i 1)

1
n
.
But I cannot contain two fractions separated by a distance of 1/n or larger. Thus, we get a contradiction,
and it follows that there cannot be more than one fraction with a denominator in each of the at most (n+1)/2
sets S
i
. The result follows.
42
89. Prove that there is only one triple of positive integers, each exceeding 1, for which the product of any
two of the numbers plus one is divisible by the third.
Solution 1. Let a, b, c be three numbers with the desired property; wolog, suppose that 2 a b c.
Since a[(bc + 1), a has greatest common divisor 1 with each of b and c. Similarly, the greatest common
divisor of b and c is 1. Since ab +bc +ca + 1 is a multiple of each of a, b, c, it follows that ab +bc +ca + 1
is a multiple of abc. Therefore, abc ab +bc +ca + 1.
Since a, b, c are distinct and so 2 a < b < c, we must have a 2 and b 3. Suppose, if possible that
b 4, so that c 5. Then abc 40 and
ab +bc +ca + 1
abc
5
+
abc
2
+
abc
4
+ 1
19abc
20
+
abc
40
< abc ,
a contradiction. Hence b must equal 3 and a must equal 2. Since c[(ab + 1), c must equal 7. The triple
(a, b, c) = (2, 3, 7) satises the desired condition and is the only triple that does so.
Solution 2. As in Solution 1, we show that abc ab +bc +ca + 1, so that
1
1
a
+
1
b
+
1
c
+
1
abc
.
However, if a 3, the right ride of the inequality cannot exceed (1/3) + (1/4) + (1/5) + (1/60) = 4/5 < 1.
Hence a = 2. If a = 2 and b 4, then b 5 (why?) and the right side cannot exceed (1/2) +(1/5) +(1/7) +
(1/70) = 6/7 < 1. Hence (a, b) = (2, 3). If now c exceeds 7, then c 11 and the right side of the inequality
cannot exceed (1/2) +(1/3) +(1/11) +(1/66) = 31/33 < 1. Hence c 7, and we are now led to the solution.
Solution 3. [P. Du] As in Solution 1, we show that a, b, c are pairwise coprime and that ab +bc +ca +1
is a multiple of abc. Assume 2 a < b < c. Then abc > ac and bc(a 1) bc > ac a(b + 1) > ab + 1,
whence, adding these, we get 2abc bc > ac +ab + 1, so that 2abc > ab +bc +ca + 1. Hence,
abc = ab +bc +ca + 1 = bc (c a)b +bc +bc (b a)c + 1 = 3bc (c a)b (c b)a + 1 < 3bc
so that a < 3. Hence a = 2. Plugging this into the equation yields
bc = 2b + 2c + 1 = 4c 2(c b) + 1 < 4c
so that b < 4. Hence b = 3, and we nd that 6c = 6 + 5c + 1 or c = 7.
Solution 4. [O. Ivrii] As before, we show that a, b and c are pairwise coprime, and take 2 a < b < c.
Then bc[ab+ac+1. Since bc > ac+1 and bc > ab+1, we have that 2bc > ab+ac+1. Hence bc = ab+ac+1,
so that (bc + 1) +ab = 2(ab + 1) +ac. Since a divides each of bc + 1, ab and ac, but is coprime with ab + 1,
it follows that a divides 2. Hence a = 2 and
bc = 2(b +c) + 1 =(b 2)(c 2) = 5 =(b, c) = (3, 7) .
Solution 5. As above, we can take 2 a < b < c. Since
(ab + 1)
c

(ca + 1)
b
= a
2
+
a
c
+
a
b
+
1
bc
,
we see that (a/c) + (a/b) + (1/(bc)) is a positive integer less than 3.
Suppose, if possible, that (a/c)+(a/b)+(1/(bc)) = 2. Then ab+ac+1 = 2bc, whence b(ca)+c(ba) = 1,
an impossibility. Hence a(b +c) + 1 = bc, so that
2 = (bc + 1) a(b +c) .
43
Since both terms on the right are divisible by a, 2 must be a multiple of a. Hence a = 2, and we obtain
(b 2)(c 2) = 5, so that (b, c) = (3, 7).
90. Let m be a positive integer, and let f(m) be the smallest value of n for which the following statement
is true:
given any set of n integers, it is always possible to nd a subset of m integers whose sum is divisible by
m
Determine f(m).
Solution. [N. Sato] The value of f(m) is 2m1. The set of 2m2 numbers consisting of m1 zeros
and m1 ones does not satisfy the property; from this we can see that n cannot be less than 2m1.
We rst establish that, if f(u) = 2u1 and f(v) = 2v 1, then f(uv) = 2uv 1. Suppose that 2uv 1
numbers are given. Select any 2u 1 at random. By hypothesis, there exists a usubset whose sum is
divisible by u; remove these u elements. Continue removing usubsets in this manner until there are fewer
than u numbers remaining. Since 2uv 1 = (2v 1)u + (u 1), we will have 2v 1 sets of u numbers
summing to a multiple of u. For 1 i 2v 1, let ua
i
be the sum of the ith of these 2v 1 sets. We can
choose exactly v of the a
i
whose sum is divisible by v. The v usets corresponding to these form the desired
uv elements whose sum is divisible by uv. Thus, if we can show that f(p) = 2p 1 for each prime p, we can
use the fact that each number is a product of primes to show that f(m) = 2m1 for each positive integer
m.
Let x
1
, x
2
, , x
2p1
be 2p 1 integers. Wolog, we can assume that the x
i
have been reduced to their
least non-negative residue modulo p and that they are in increasing order. For 1 i p1, let y
i
= x
p+i
x
i
;
we have that y
i
0. If y
i
= 0 for some i, then x
i+1
= = x
p+i
, in which case x
i+1
+ +x
p+i
is a multiple
of p and we have achieved our goal. Henceforth, assume that y
i
> 0 for all i
Let s = x
1
+ x
2
+ + x
p
. Replacing x
i
by x
p+i
in this sum is equivalent to adding y
i
. We wish to
show that there is a set of the y
i
whose sum is congruent to s modulo p; this would indicate which of the
rst p x
i
to replace to get a sum which is a multiple of p.
Suppose that A
0
= 0, and, for k 1, that A
k
is the set of distinct numbers i with 0 i p 1
which either lie in A
k1
or are congruent to a + y
k
for some a in A
k1
. Note that the elements of each A
k
is equal to 0 or congruent (modulo p) to a sum of distinct y
i
. We claim that the number of elements in A
k
must increase by at least one for every k until A
k
is equal to 0, 1, , p 1.
Suppose that going from A
j1
to A
j
yields no new elements. Since 0 A
j1
, y
j
A
j
, which means
that y
j
A
j1
. Then 2y
j
= y
j
+ y
j
A
j
= A
j1
, 3y
j
= 2y
j
+ y
j
A
j
= A
j1
, and so on. Thus, all
multiples of y
j
(modulo p) are in A
j1
. As p is prime, we nd that A
j1
must contain 0, 1, , p 1. We
deduce that some sum of the y
i
is congruent to s modulo p and obtain the desired result.
Comment. This turned out to be a hard problem. Here is a partial solution that was originally obtained.
Let m be any positive integer. Note that the any set of 2(m1) integers with m1 of them congruent to
0, modulo m, and the other m1 of them congruent to 1, modulo m, does not have a subset of m integers
whose sum is divisible by m. Therefore, f(m) 2m1.
Let a and b be two positive integers. We establish that
f(ab) f(a) + (f(b) 1)a . (1)
Suppose that we have any set of at least f(a) + (f(b) 1)a integers. Since the number of elements in the
set exceeds f(a), we can nd a set T
1
of a integers whose sum is divisible by a; let this sum be as
1
. Remove
these a integers from the original set to leave f(a) + (f(b) 2)a integers. We can nd a new set T
2
of a
integers whose sum is of the form as
2
for some integer s
2
. After doing this f(b) 1 times, we are left with
a residue of at least f(a) integers and f(b) 1 sets T
i
(1 i f(b) 1) whose elements add up to as
i
44
respectively. Finally, we can nd a set T
f(b
of a integers from the nal f(a) numbers for which the sum is
as
f(b)
for some integer s
f(b
.
Now consider the set
s
1
, s
2
, , s
f(b)
.
By the denition of f(b), we can nd b of them whose sum is divisible by b, say s
j
where j belongs to a set
U. Then

as
j
: j U is divisible by ab. There are b summands and each of them is a sum of a elements
of our original set, so we there are ab numbers in the original set whose sum is divisible by ab.
Let W = m; f(m) = 2m 1. The set W is nonvoid, as it contains the number 1. Also, the product
of any two numbers in W also lies inside W. For suppose that f(a) = 2a 1 and f(b) = 2b 1. Then
f(ab) f(a) + (f(b) 1)a = (2a 1) + (2b 2)a = 2ab 1 .
But, we know that f(ab) 2ab 1, from our initial observation. Hence f(ab) = 2ab 1. Thus, to complete
the problem and show that f(m) = 2m1 for all m, we just have to deal with the case that m is prime.
91. A square and a regular pentagon are inscribed in a circle. The nine vertices are all distinct and divide the
circumference into nine arcs. Prove that at least one of them does not exceed 1/40 of the circumference
of the circle.
Solution 1. Let the four points of the square be at A, B, C, D. We can partition the circumference into
eight arcs as follows: (1) four closed arcs (containing endpoints), each of length 1/20 of the circumference
centered at A, B, C and D; call these the shorter arcs: (2) four open arcs (not containing endpoints), each
of length 1/5 of the circumference and interpolated between two of the arcs centred at the vertices of the
square; call these the longer arcs.
Suppose a regular pentagon is inscribed in a circle. Since any pair of adjacent vertices terminate a closed
arc whose length is 1/5 of the circumference, no two vertices of the pentagon can belong to the same longer
arc. Since there are only four longer arcs, at least one vertex of the pentagon must lie inside a shorter arc
and so be no more distant that
1
2

1
20
=
1
40
from a vertex of the square.
Solution 2. By the Pigeonhole Principle, two vertices of the pentagon must be on the arc joining two
adjacent vertices of the square. Let the two vertices of the square be A and D and let the two vertices of
the pentagon lying between them be B and C, If the order is ABCD, then arc AB+ arc CD =
1
4

1
5
=
1
20
of the circumference. It is not possible for both the arcs AB and CD to exceed 1/40 of the circumference
and the result follows.
92. Consider the sequence 200125, 2000125, 20000125, , 200 00125, (in which the nth number has
n + 1 digits equal to zero). Prove that none of these numbers is the square, cube or fth power of an
integer.
Solution 1. Each number has the form 2 10
n+1
+ 125 where n 4. Since both 10
n
and 120 are
multiples of 8, each number in the sequence is congruent to 5, modulo 8, and so cannot be square.
Observe that 10
n+1
= 10
n2
8 125, so that
2 10
n+1
+ 125 = 125(16 10
n2
+ 1) = 5
3
(16 10
n2
+ 1) .
If such a number is a kth power, it must be divisible by 5
k
. Since 16 10
n2
+ 1 is not a multiple of 5, no
number in the sequence can be a kth power for k 4.
Let u
n
= 16 10
n2
+ 1, for n 5. Suppose that (10x
n
+ 1)
3
= u
n
. Then
1000x
3
n
+ 300x
2
n
+ 30x
n
= 16 10
n2
so that x
n
= 10
n3
y
n
for some y
n
and we nd that
16 = 10
3n6
y
3
n
+ 3 10
2n4
y
2
n
+ 3y
n
y
2
n
+ 3y
n
45
so that y
n
= 1 or 2. It is straightfoward to check that neither works, so that u
n
can never be a cube. Hence
no number in the given sequence can be a cube.
Solution 2. The nth number is equal to 5
3
16 10
n1
+ 1, from which it is seen that 5 divides it to
an odd power. Hence it cannot be square.
Suppose the number is the cube of some natural number k. Then k = 10b +5 for some natural number
b. Hence
(10b + 5)
3
= 2 10
n+1
+ 125 .
This reduces to b(4b
2
+ 6b + 3) = 2
i
5
j
for some natural numbers i and j exceeding 4. Since the factor
in brackets on the left is odd, 2
i
divides b. Checking, modulo 5, we see that the factor in brackets is never
divisible by 5, so 5
j
must divide b. Hence 4b
2
+6b +3 = 1, which is impossible, since b is a natural number.
The desired result follows.
As before, it is straightforward by checking divisibility by 5 that the numbers cannot be higher powers.
93. For any natural number n, prove the following inequalities:
2
(n1)/(2
n2
)

2
4

4
8

8
2
n

2
n
< 4 .
Solution. The middle member of the inequality is 2 raised to the power s
1
2
+
2
4
+ +
n
2
n
. Note that
s
1
2
s =
1
2
+
1
4
+ +
1
2
n

n
2
n+1
= 1
1
2
n

n
2
n+1
= 1
n + 2
2
n+1
whence s = 2 (n + 2)2
n
. Clearly, s < 2.
On the other hand,
s
n 1
2
n2
=
2
n+1
(n + 2) 4(n 1)
2
n
=
2
n+1
(5n 2)
2
n
.
When n = 1, 2
n+1
(5n 2) = 1 > 0; when n = 2, 2
n+1
(5n 2) = 0, and when n = 3, 2
n+1
(5n 2) =
3 > 0. Suppose, as an induction hypothesis, that 2
k+1
> 5k 2 for some k 3. Then
2
k+2
> 10k 4 = 5(k + 1) 2 + (5k 7) > 5(k + 1) 2 ,
so that, for each positive integer n, 2
n+1
5n 2, with equality if and only if n = 2. The desired result
follows.
Comment. Solvers approached the proof of 2
n+1
5n 2 in two ways. Some used induction. The
inequality holds for n = 1, 2, 3. Suppose that it holds for n = k > 2, Then, using this fact, we nd that
2
k+1
= 2
k+1
+ 2
k+1
5k 2 + 5 = 5(k + 1) 2 ,
from which a proof by induction can be constructed.
Another approach is to note that both sides are equal for n = 2 and then argue that the left increases
more rapidly than the right with increase of n. One might note, for example, that for each n 2, 5(n+1)2 <
2(5n 2).
94. ABC is a right triangle with arms a and b and hypotenuse c = [AB[; the area of the triangle is s square
units and its perimeter is 2p units. The numbers a, b and c are positive integers. Prove that s and p
are also positive integers and that s is a multiple of p.
Solution. Since a
2
+b
2
= c
2
and squares are congruent to 0 or 1, modulo 4, it is not possible for a and
b to be both odd. Since, at least one of them is even, s =
1
2
ab is an integer. Also, since either two or none
46
of a, b, c are odd, p =
1
2
(a + b + c) is an integer. Let r be the inradius of the triangle, so that s = rp. It
remains to nd r and show that it is an integer. In any triangle with sides a, b, c, the length of the tangents
from vector to incircle are
1
2
(a +b c),
1
2
(b +c a) and
1
2
(b +c a). For a right triangle with hypotenuse
c, one of the lengths is r, namely r =
1
2
(a +b c). Since one of the legs of the triangle is even, the other leg
and the hypotenuse must have the same parity, so that a +b c is even and r is an integer.
Comment. T. Chao noted that it suces to show the result for primitive right triangles, for which
(a, b, c) = (m
2
n
2
, 2mn, m
2
+ n
2
) for some coprime pair (m, n) of integers. (Prove this.) Then, it turns
out that s = (m
2
n
2
)mn and p = m(m + n), from which the result follows. A lot of students used the
representation in their proofs without proving it. Since this is not part of the regular curriculum, it is
prudent to provide a proof. There were several solutions to this problem in which this well-known fact
was improperly used and yielded a particular rather than a general solution. Some studenets thought that
the above form gave a general representation of all pythagorean triples; but (15, 36, 39) for example cannot
be so represented. How should the form be modied to embrace such examples?
95. The triangle ABC is isosceles is isosceles with equal sides AC and BC. Two of its angles measure 40

.
The interior point M is such that MAB = 10

and MBA = 20

. Determine the measure of CMB.

Solution 1. Let BM be produced to meet AC at N. Since AMB = 150

, we have that NMA =

30

= NAM so that NA = NM. Let a = [BC[ = [AC[, c = [AB[, u = [CN[ and v = [NA[ = [NM[.
Since BN bisects angle CBA, we have that v/u = c/a.
By the Law of Sines,
c
a
=
sin 100

sin 40

=
sin 80

sin 40

= 2 cos 40

and
v
u
=
sin( 60

)
sin
where = CMB. Hence
sin( 60

) = 2 sin cos 40

= sin( + 40

) + sin( 40

)
whence
2 cos( 50

) sin 10

= sin( 60

) sin( 40

) = sin( + 40
c
irc
) .
Since +40

= (50

) +90

, sin(+40

) = cos(50

). Therefore, we nd that 2 cos(50

) sin 10

=
cos( 50

). Since sin 10

,=
1
2
, we have that cos( 50

) = 0 and = 140

.
Solution 2. [R. Mong] Let A

be on BC produced so that A

B = AB. The triangle A

BM and ABM
are congruent (SAS), so A

M = AM, and BA

M = BAM = 10

. Triangle A

AB is isosceles, with vertex

angle B = 40

, so A

AB = AA

B = (180

40

)/2 = 70

. Then MA

A = BA

A BA

M = 60

.
Similarly, MAA

= 60

. Therefore, the triangle MA

A is equilateral.
CAM = CAB MAB = 40

10

= 30

, so CA is the angle bisector in the triangle MA

A.
It follows that CA is the perpendicular bisector of MA

, and A

C = CM. Applying the Exterior Angle

Theorem for the triangle C

AM, MCB = 2MA

B = 20

, and CMB = 180

MBC MCB =
180

20

20

= 140

.
96. Find all prime numbers p for which all three of the numbers p
2
2, 2p
2
1 and 3p
2
+4 are also prime.
Solution. Modulo 7, we nd that p
2
2 0 when p 3, 4, 2p
2
1 0 when p 2, 5 and 3p
2
+ 4 0
when p 1, 6. Thus, when p > 7, at least one of the four numbers is a proper multiple of 7. The only primes
p for which all numbers are prime at 3 and 7, and we get the quadruples (3, 7, 17, 31) and (7, 47, 97, 151).
Notes. A rectangular hyperbola is an hyperbola whose asymptotes are at right angles.
47
97. A triangle has its three vertices on a rectangular hyperbola. Prove that its orthocentre also lies on the
hyperbola.
Solution 1. A rectangular hyperbola can be represented as the locus of the equation xy = 1. Let the
three vertices of the triangle be at (a, 1/a), (b, 1/b), (c, 1/c). The altitude to the points (c, 1/c) has slope
(a b)/(a
1
b
1
) = ab and its equation is y = abx + (1/c) abc. The altitude to the point (a, 1/a) has
equation y = bcx +(1/a) abc. These two lines intersect in the point (1/abc, abc) and the result follows.
Solution 2. [R. Barrington Leigh] Suppose that the equation of the rectangular hyperbola is xy = 1.
Let the three vertices be at (x
i
, y
i
) (i = 1, 2, 3), and let the orthocentre be at (x
0
, y
0
). Then
(x
1
x
2
)(x
0
x
3
) = (y
1
y
2
)(y
0
y
3
)
and
(x
1
x
3
)(x
0
x
2
) = (y
1
y
3
)(y
0
y
2
) .
Cross-multiplying these equations yields that
(x
1
x
2
)(y
1
y
3
)(x
0
x
3
)(y
0
y
2
) = (x
1
x
3
)(y
1
y
2
)(x
0
x
2
)(y
0
y
3
) ,
whence
(1 x
1
y
3
x
2
y
1
+x
2
y
3
)(x
0
y
0
x
0
y
2
x
3
y
0
+x
3
y
2
) = (1 x
1
y
2
x
3
y
1
+x
3
y
2
)(x
0
y
0
x
0
y
3
x
2
y
0
+x
2
y
3
) .
Collecting up the terms in x
0
y
0
, x
0
, y
0
, and the rest, and simplifying, yields that x
0
y
0
= 1, as desired.
98. Let a
1
, a
2
, , a
n+1
, b
1
, b
2
, , b
n
be nonnegative real numbers for which
(i) a
1
a
2
a
n+1
= 0,
(ii) 0 b
k
1 for k = 1, 2, , n.
Suppose that m = b
1
+b
2
+ +b
n
| + 1. Prove that
n

k=1
a
k
b
k

m

k=1
a
k
.
Solution. Note that m1 b
1
+b
2
+ +b
m
< m. We have that
a
1
b
1
+a
2
b
2
+ +a
m
b
m
+a
m+1
b
m+1
+ +a
n
b
n
a
1
b
1
+a
2
b
2
+ +a
m
b
m
+a
m
(b
m+1
+b
m+2
+ +b
n
)
< a
1
b
1
+a
2
b
2
+ +a
m
b
m
+a
m
(mb
1
b
2
b
m
)
= a
1
b
1
+a
2
b
2
+ +a
m
b
m
+a
m
(1 b
1
) +a
m
(1 b
2
) + +a
m
(1 b
m
)
a
1
b
1
+a
2
b
2
+ +a
m
b
m
+a
1
(1 b
1
) +a
2
(1 b
2
) + +a
m
(1 b
m
)
= a
1
+a
2
+ +a
m
.
99. Let E and F be respective points on sides AB and BC of a triangle ABC for which AE = CF. The
circle passing through the points B, C, E and the circle passing through the points A, B, F intersect at
B and D. Prove that BD is the bisector of angle ABC.
Solution 1. Because of the concyclic quadrilaterals, DEA = 180

BED = DCF and DFC =

180

DFB = DAB . Since, also, AE = CF, DAE DFC (ASA) so that AD = DF. In the circle
through ABFD, the equal chords AD and DF subtend equal angles ABD and FBD at the circumference.
The result follows.
48
Solution 2. CDF = CDE FDE = 180

ABC FDE = FDA FDE = EDA and

AED = 180

BED = BCD = FCD. Since AE = CF, EAD CFD (ASA). The altitude
from D to AE is equal to the altitude from D to FC, and so D must be on the bisector of ABC.
Solution 3. Let B be the point (0, 1) and D the point (0, 1). The centres of both circles are on the
right bisector of BD, namely the xaxis. Let the two circles have equations (x a)
2
+ y
2
= a
2
+ 1 and
(xb)
2
+y
2
= b
2
+1. Suppose that y = mx1 is a line through B; this line intersects the circle of equation
(x a)
2
+y
2
= a
2
+ 1 in the point
_
2(m+a)
m
2
+ 1
,
m
2
+ 2am1
m
2
+ 1
_
and the circle of equation (x b)
2
+y
2
= b
2
+ 1 in the point
_
2(m+b)
m
2
+ 1
,
m
2
+ 2bm1
m
2
+ 1
_
The distance between these two points is the square root of
_
2(a b)
m
2
+ 1
_
2
+
_
2m(a b)
m
2
+ 1
_
2
=
4(a b)
2
(1 +m
2
)
(m
2
+ 1)
2
=
4(a b)
2
m
2
+ 1
.
Now suppose that the side AB of the triangle has equation y = m
1
x 1 and the side BC the equation
y = m
2
x 1, so that (A, E) and (C, F) are the pairs of points where the lines intersect the circles. Then,
from the foregoing paragraph, we must have m
2
1
+ 1 = m
2
2
+ 1 or 0 = (m
1
m
2
)(m
1
+m
2
). Since the sides
are distinct, it follows that m
1
= m
2
and so BD bisects ABC.
100. If 10 equally spaced points around a circle are joined consecutively, a convex regular inscribed decagon
P is obtained; if every third point is joined, a self-intersecting regular decagon Q is formed. Prove that
the dierence between the length of a side of Q and the length of a side of P is equal to the radius of
the circle. [With thanks to Ross Honsberger.]
Solution 1. Let the decagon be ABCDEFGHIJ. Let BE and DI intersect at K and let AF and DI
intersect at L. Observe that AB|DI|EH and BE|AF|HI, so that ABKL and KIHE are parallelograms.
Now AB is a side of P and HE is a side of Q, and the length of the segment IL is the dierence of the
lengths of EH = IK and AB = KL. Since L, being the intersection of the diameters AF and DI, is the
centre of the circle, the result follows.
Solution 2. [R. Barrington Leigh] Use the same notation as in Solution 1. Let O be the centre of
P. Now, AB is an edge of P, AD is an edge of Q, DO is a radius of the circle and BG a diameter. Let
AD and BO intersect at U. Identify in turn the angles DOU = 72

, DAB = 36

, ABU = 72

,
DUO = BUA = 72

, whence AU = AB, DU = DO and AD AB = AD AX = DX = DO, as

desired.
Solution 3. Label the vertices of P as in Solution 1. Let O be the centre of P, and V be a point
on EB for which EV = OE. We have that AOB = 36

, DOB = OBA = 72

, BOE = 108

and OEB = OBE = 36

. Also, EOV = EV O = 72

and OE = EV = OA = OB. Hence,

DAB = EV O (SAS), so that OV = AB. Since BV O = 108

and BOV = 36

, OBV = 36

, and so
BV = OV = AB. Hence BE AB = EV +BV AB = EV = OE, the radius.
Solution 4. Let the circumcircle of P and Q have radius 1. A side of P is the base of an isosceles
triangle with equal sides 1 and apex angle 36

, so its length is 2 sin 18

. Likewise, the length of a side of Q

is 2 sin 54

. The dierence between these is

2 sin 54

2 sin 18

= 2 cos 36

2 cos 72

= 2t 2(2t
2
1) = 2 + 2t 4t
2
49
where t = cos 36

. Now
t = cos 36

= cos 144

= 1 2 cos
2
72

= 1 2(2t
2
1)
2
= 8t
4
+ 8t
2
1 ,
so that
0 = 8t
4
8t
2
+t + 1 = (t + 1)(8t
3
8t
2
+ 1)
= (t + 1)(2t 1)(4t
2
2t 1) .
Since t is equal to neither 1 nor
1
2
, we must have that 4t
2
2t = 1. Hence
2 sin 54

2 sin 18

= 2 (4t
2
2t) = 1 ,
the radius of the circle.
101. Let a, b, u, v be nonnegative. Suppose that a
5
+b
5
1 and u
5
+v
5
1. Prove that
a
2
u
3
+b
2
v
3
1 .
[With thanks to Ross Honsberger.]
Solution. By the arithmetic-geometric means inequality, we have that
2a
5
+ 3u
5
5
=
a
5
+a
5
+u
5
+u
5
+u
5
5

5

a
10
u
15
= a
2
u
3
and, similarly,
2b
5
+ 3v
5
5
b
2
v
3
.
Adding these two inequalities yields the result.
102. Prove that there exists a tetrahedron ABCD, all of whose faces are similar right triangles, each face
having acute angles at A and B. Determine which of the edges of the tetrahedron is largest and which
is smallest, and nd the ratio of their lengths.
Solution 1. Begin with AB, a side of length 1. Now construct a rectangle ACBD with diagonal AB, so
that [AC[ = [BD[ = s < t = [AD[ = [BC[. The requisite values of s and t will be determined in due course.
We want to show that we can fold up D and C from the plane in which AB lies (like folding up the wings
of a buttery) in such a way that we can obtain the desired tetrahedron.
When the triangles ADB and ACB lie at, we see that C and D are distance 1 apart. Suppose that,
when we have folded up C and D to get the required tetrahedron, they are distance r apart. Then ACD
should be a right triangle similar to ABC. The hypotenuse of ACD cannot be AC as AC < AD. Nor can
it be CD, for then, we would have AD = BC, AC = AC, and CD would have to have length 1, possible
only when ABCD is coplanar. So the hypotenuse must be AD. The similarity of ADC and ABC would
require that
1 : t : s = t : s : r
where r = [CD[. Thus, 1/t = t/s or s = t
2
and t/s = s/r or r = s
2
/t = t
3
. So we must fold C and D until
they are distance t
3
apart.
Is this possible? Since ACB is right, 1 = t
2
+ s
2
= t
2
+ t
4
, whence s = t
2
=
1
2
(1 +

5) < 1. Hence
r < 1. To arrange that we can make the distance between C and D equal to r, we must show that r exceeds
the minimum possible distance between C and D, which occurs when ADB is folded at partially covering
ACB. Suppose this has been done, with ABCD coplanar and C, D both on the same side of AB. Let P
and Q be the respective feet of the perpendiculars to AB from C and D. Then
[CP[ = [DQ[ = t
3
, [AP[ = [QB[ = t
4
, [AQ[ = [PB[ = t
2
,
50
and
[CD[ = [PQ[ = t
2
t
4
= (t
4
+t
6
) t
4
= t
6
< t
3
.
When C and D are located, we have [AB[ = 1, [AD[ = [BC[ = t, [AC[ = [BD[ = t
2
and [CD[ = t
3
.
Since all faces of the tetrahedron ABCD have sides in the ratio 1 : t : t
2
, all are similar right triangles and
AB : CD = 1 : t
3
.
Solution 2. Let = CAB and [AB[ = 1. By the condition on the acute angles of triangles ACB
and ACD, ACB = ADB = 90

, so that the triangles ACD and ADB, being similar and sharing a
hypotenuse, are congruent.
Suppose, if possible, that BAD = . Then AC = AD and so ACD must be isosceles with its right
angle at A, contrary to hypothesis. So, ABD = and [BD[ = [AC[ = cos , [AD[ = [BC[ = sin .
Consider ACD. Suppose that ACD = 90

. If DAC = , then ABC ADC and 1 =

[AB[ = [AD[ = sin , yielding a contradiction. Hence ADC = , [AD[ = [AC[/ sin = cos / sin and
[CD[ = [AC[ cot = cos
2
/ sin . Hence, looking at [AD[, we have that
cos
sin
= sin =0 = cos sin
2
= cos
2
+ cos 1 .
Therefore, cos =
1
2
(

5 1) and sin
2
= cos .
Observe that [BC[ sin = sin
2
= cos = [BD[ and [BC[ cos = sin cos = cos
2
/ sin = [CD[,
so that triangle BCD is right with CDB = 90

and similar to the other three faces.

We need to check that this set-up is feasible. Using spatial coordinates, take
C (0, 0, 0) A (0, cos , 0) B (sin , 0, 0) .
Since ACD = 90

, D lies in the plane y = 0 and so has coordinates of the form (x, 0, z). Since CDB = 90

,
CD DB, so that
0 = (x, 0, z) (x sin , 0, z) x
2
+z
2
xsin ,
Now [CD[ = cos sin forces cos
2
sin
2
= x
2
+z
2
. Hence
xsin = cos
2
sin
2
=x = cos
2
sin .
Therefore
z
2
= (cos
2
cos
4
) sin
2
= cos
2
sin
4
=z = cos sin
2
,
Hence D (cos
2
sin , 0, cos sin
2
).
Thus, letting sin = t =
1
2
(

5 1), we have A (0, t

2
, 0), B (t, 0, 0), C (0, 0, 0), D (t
5
, 0, t
4
)
with t
4
+ t
2
1 = 0, and [AB[ = 1, [AD[ = [BC[ = t, [BD[ = [AC[ = t
2
and [CD[ = t
3
. [Exercise: Check
that the coordinates give the required distances and similar right triangles.] The ratio of largest to smallest
edges is 1 : t
3
= 1 : [
1
2
(

5 1)]
3/2
= 1 :
_
2 +

5.
We need to dispose of the other possibilities for ACD. By the given condition, DAC ,= 90

. If
ADC = 90

, then we have essentially the same situation as before with the roles of and its complement,
and of C and D switched.
Comment. Another way in that was used by several solvers was to note that there are four right angles
involved among the four sides, and that at most three angles can occur at a given vertex of the tetrahedron.
It is straightforward to argue that it is not possible to have three of the right angles at either C or D. Since
all right angles occur at these two vertices, then there must be two at each. As an exercise, you might want
to complete the argument from this beginning.
51
103. Determine a value of the parameter so that
f(x) cos
2
x + cos
2
(x +) cos xcos(x +)
is a constant function of x.
Solution 1.
f(x) = cos
2
x + (cos xcos sin xsin )
2
cos x(cos xcos sin xsin )
= cos
2
x(1 + cos
2
cos ) + (1 cos
2
x)(sin
2
) sin xcos xsin (2 cos 1)
= sin
2
+ cos
2
x(1 + cos
2
cos 1 + cos
2
)
1
2
sin 2xsin (2 cos 1)
= sin
2
+ (2 cos 1)(cos
2
xcos sin 2xsin ) .
The function f(x) is constant when 2 cos 1 = 0, or when = /3, and its constant value in this case is
3/4.
Solution 2.
f(x) =
1 + cos 2x
2
+
1 + cos 2(x +)
2

1
2
(cos(2x +) cos )
=
1
2
[2 cos + cos 2x(1 + cos 2 cos ) + sin 2x(sin sin 2)]
=
1
2
[2 cos + (2 cos 1)(cos 2xcos + sin 2xsin ] .
When = /3, cos = 1/2 and the function is the constant 3/4.
Solution 3. First, note the identity
cos
2
A+ cos
2
B = 1 +
1
2
(cos 2A+ cos 2B) = 1 + cos(A+B) cos(AB) .
Applying this yields
f(x) = 1 + cos(2x +) cos
1
2
(cos(2x +) + cos )
=
_
1
1
2
cos
_
+ cos(2x +)
_
cos
1
2
_
.
Hence, f(x) is the constant 3/4 when = /3.
Solution 4. We have that
f(x) =
3
4
cos
2
x + [cos(x +)
1
2
cos x]
2
.
The function f(x) can be made to take the constant value 3/4 if we can nd a parameter for which
[cos(x +)
1
2
cos x]
2
=
3
4
sin
2
x
for all x. This is equivalent to
cos(x +) =
1
2
cos x

3
2
sin x = cos(x

3
)
for all x. Thus, if = /3, then f(x) is constantly equal to
3
4
.
52
Comment. Some students started by showing that f(0) = f(

2
) implies that 1 + cos
2
cos =
cos
2
(

2
+ ) = 1 cos
2
, or 0 = 2 cos
2
cos = cos (2 cos 1). This tells us that

2
(mod ) and

3
(mod 2) are the only possibilities. However, the rst of these turns out to be extraneous. It yields
f(x) = 1
1
2
sin 2x, which is not constant.
104. Prove that there exists exactly one sequence x
n
of positive integers for which
x
1
= 1 , x
2
> 1 , x
3
n+1
+ 1 = x
n
x
n+2
for n 1.
Solution. Let x
2
= u. Then the rst four terms of the sequence are
1, u, u
3
+ 1, u
8
+ 3u
5
+ 3u
2
+ (2/u),
so for the whole sequence to consist of positive integers, we must have that u = 2. Now for any n 3,
x
n
=
x
3
n1
+ 1
x
n2
=
x
9
n2
+ 3x
6
n2
+ 3x
3
n2
+ 1 +x
3
n3
x
n2
x
3
n3
(1).
From the given condition, it can be seen that any consecutive pairs of terms in the sequence, if integers, are
coprime. We know that x
1
, x
2
, x
3
are integers. Let n 4. Suppose that it has been shown that x
m
is an
integer for 1 m n 1. Then (x
3
n3
+ 1)/x
n2
= x
n4
is an integer, as is (x
3
n2
+ 1)/x
n3
= x
n1
and
its cube. Since the numerator of (1) is a multiple of each of x
n2
and x
3
n3
separately, and since these two
divisors are coprime, x
n
must be an integer. The result follows by induction.
Solution 2. [M. Mika] As before, we see that x
2
must be 2. It can be checked that x
3
and x
4
are integers.
For any integer n 4, we have that
x
3
n
+ 1 =
(x
3
n1
+ 1)
3
x
3
n2
+ 1
=
(x
3
n1
+ 1)
3
x
n1
x
n3
1
+ 1
=
x
n1
(x
8
n1
+ 3x
5
n1
+ 3x
2
n1
+x
n3
)
x
n1
x
n3
1
.
Therefore
(x
3
n
+ 1)(x
n1
x
n3
1) = x
n1
(x
8
n1
+ 3x
5
n1
+ 3x
2
n1
+x
n3
) .
Supposing, as an induction hypothesis,that x
1
, , x
n
are integers, we see that x
n1
and x
n1
x
n3
1 are
coprime, so we must have that x
n1
divides x
3
n
+ 1. Thus, x
n+1
is an integer.
105. Prove that within a unit cube, one can place two regular unit tetrahedra that have no common point.
Solution 1. Let ABCDEFGH be the cube, with ABCD the top face, EFGH the lower face and AE,
BF, CG, DH edges. Let O be the centre of the cube, and let P, Q, R be the midpoints of AB, DH, FG
respectively.
The centre O lies on the diagonal CE, which is the axis of a rotation that takes B D G,
A H F, P Q R, so PQR is equilateral with centre O and CE PQR.
Using Pythagoras Theorem, we calculate some lengths:
[CP[ = [CQ[ = [CR[ = [RB[ = [RH[ =
_
1 + (1/4) = (

5)/2 ,
[PQ[ = [PR[ = [QR[ =
_
(5/4) + (1/4) =
_
3/2 ,
53
[CO[ = (

3)/2 .
[As a check that O is the centre of PQR, we can compute [PO[ = [QO[ = [RO[ = 1/

2 = [1/

3][PQ[.]
Since the height of a regular tetrahedron with side s is s
_
2/3, we can construct a regular tetrahedron
CUV W with apex C, base UV W homothetic to PQR with centre O, height (

3)/2, and side length

[(

3)/2][
_
3/2] = 3/(2

2) > 1. Since 3/(2

2) =
_
9/8 <
_
3/2, triangle UV W lies within triangle PQR,
and so the tetrahedron lies within the cube. Shrink the tetrahedron by a homothety with factor
_
8/9 about
its centre to get one of the desired tetrahedra.
The second tetrahedra can be found in a similar way from EUV W (which is congruent to CUV W).
The two tetrahedra are strictly separated by the plane of PQR.
Solution 2. Let the cube have vertices at the eight points (, , ) where , , = 0, 1. The plane of
equation x + y + z = 3/2 passes through (0, 1,
1
2
), (
1
2
, 1, 0), (1,
1
2
, 0), (1, 0,
1
2
), (
1
2
, 0, 1) and (0,
1
2
, 1) at the
middle of various edges of the cube, and bisects the cube into two congruent halves. Consider the cube
reduced by a homothety of factor 1/

2 about the origin. Four of its vertices, (0, 0, 0), (0, 1/

2, 1/

2),
(1/

2, 1/

2, 0), (1/

2, 0, 1/

2), constitute the four vertices of a regular unit tetrahedron contained in the
original cube. Since the sum of the coordinates of all of these points is less than 3/2, they all lie on the same
side of the plane bisecting the cube, as does the whole tetrahedron. Its image reected in the centre of the
cube is a second tetrahedron contained in the upper portion of the cube.
Solution 3. [D. Tseng] Consider unit tetrahedra CPQR and EUV W, each sharing a vertex and a
face with the cube and directed inwards with the face diagonal AC intersecting PQ in its midpoint S
and face diagonal EG intersecting UV in its midpoint X. (Each tetrahedron is carried into the other by
a reection in the centre of the cube.) Planes PQR and UV W are parallel. These tetrahedra intersect
the internal plane ACGE in two triangles EXW and CSR. Let SR produced meet EG in M, and let T
and N be be points on AC for which RT AC and MN AC. Observe that [RS[ = [CS[ =

3/2,
[ST[ = 1/(2

3), [TC[ = 1/

3 and [RT[ =
_
(2/3). Since ST : SN = RT : MN, [SN[ = 1/(2

2) and
[MG[ = [NC[ = ((

3)/2) (1/(2

2)). Hence [EX[ + [MG[ =

3 1/(2

2) <

2 = [EG[. This means

that the parallel lines WX and RS have a region of ACGE between them that do not intersect triangles
EXW and CSR, and so the two tetrahedra are separated by the slab between the parallel planes PQR and
UV W that passes through the centre of the cube.
106. Find all pairs (x, y) of positive real numbers for which the least value of the function
f(x, y) =
x
4
y
4
+
y
4
x
4

x
2
y
2

y
2
x
2
+
x
y
+
y
x
is attained. Determine that minimum value.
Solution 1. Observe that
f(x, y) 2 =
_
x
2
y
2
1
_
2
+
_
y
2
x
2
1
_
2
+
_
x
y

y
x
_
2
+
_
x
y
2 +
y
x
_

(x y)
2
xy
0
with equality if and only if x = y. The required minimum is 2.
Solution 2. Let u = (x
2
/y
2
) + (y
2
/x
2
) and v = (x/y) + (y/x) Note that u, v 2 with equality if and
only if x = y. Then f(x, y) = u
2
u 2 +v = (u 2)(u +1) +v 2 with equality if and only if x = y. The
desired minimum is 2.
Solution 3. Let v = (x/y) + (y/x). Then
f(x, y) = [v
2
2]
2
2 [v
2
2] +v = v
4
5v
2
+v + 4 = (v 2)(v
3
+ 2v
2
v 1) + 2 .
54
Note that v 2 and so v
3
+ 2v
2
v 1 = (v
3
v) + (2v
2
1) > 0. The desired result now follows.
Comment. Several solvers did this problem by calculus. The most important thing you need to know
about calculus is when not to use it. Calculus provides very general algorithms for doing optimization
problems, and such algorithms often have two undesirable characteristics: (1) they may not provide the
quickest and most convenient approach in particular cases; (2) they tend to operate as black boxes,
preventing the solver from appreciating the essence of the problem or the signicance of the answer. When
you have a problem of this type, you should check to see whether it can be handled without calculus, and
use calculus only as a last resort, or at least when it is clear that every other approach is messier.
107. Given positive numbers a
i
with a
1
< a
2
< < a
n
, for which permutation (b
1
, b
2
, , b
n
) of these
numbers is the product
n

i=1
_
a
i
+
1
b
i
_
maximized?
Solution 1. By the arithmetic-geometric means inequality, we have that, for each i, 2a
i
b
i
a
2
i
+ b
2
i
, so
that
(a
i
b
i
+ 1)
2
= a
2
i
b
2
i
+ 2a
i
b
i
+ 1 a
2
i
b
2
i
+a
2
i
+b
2
i
+ 1 = (a
2
i
+ 1)(b
2
i
+ 1) .
Hence
n

i=1
(a
i
b
i
+ 1)

_
n

i=1
(a
2
i
+ 1)
n

i=1
(b
2
i
+ 1) =
n

i=1
(a
2
i
+ 1) .
Equality occurs if and only if b
i
= a
i
for each i.
Now
n

i=1
_
a
i
+
1
b
i
_
=

n
i=1
(a
i
b
i
+ 1)

n
i=1
b
i
=

n
i=1
(a
i
b
i
+ 1)

n
i=1
a
i
.
Thus, the given expression is maximized

n
i=1
(a
i
b
i
+1) is maximized a
i
= b
i
for each i (b
1
, b
2
, , b
n
)
is obtained from (a
1
, a
2
, , a
n
) by the identity permutation.
Solution 2. There are nitely many permutations of the numbers, so that there must be a permutation
which maximizes the value of the given expression. We show that it is the identity permutation, by showing
that, for any other permutation, we can nd a permutation that yields a larger value.
Suppose that (b
1
, b
2
, , b
n
) is a permutation for which there is a pair i, j of indices for which a
i
< a
j
while b
i
> b
j
. Then
_
a
i
+
1
b
j
__
a
j
+
1
b
i
_

_
a
i
+
1
b
i
__
a
j
+
1
b
j
_
= (a
j
a
i
)
_
1
b
j

1
b
i
_
> 0 .
with the result that the product can be made larger by interchanging the positions of b
i
and b
j
. The result
follows.
108. Determine all real-valued functions f(x) of a real variable x for which
f(xy) =
f(x) +f(y)
x +y
for all real x and y for which x +y ,= 0.
55
Solution 1. Setting y = 1 yields that (x + 1)f(x) = f(x) + f(1) so that xf(x) = f(1) for x ,= 1. Set
x = 0 to obtain f(1) = 0, so that, for x ,= 0, (x + 1)f(x) = f(x). From this, we deduce that, as long as
x ,= 0, 1, we have that f(x) = 0.
For each nonzero value of x, xf(0) = f(x) + f(0), so that (x 1)f(0) = f(x). Taking x = 2 gives
f(0) = f(2) = 0. Finally, 2f(1) = 2f(1) = 0, so f(1) = 0. Hence, f(x) must be indentically equal to 0.
Solution 2. [S.E. Lu] For all nonzero x, we have that f(x) = (x 1)f(0). The equality f(x) + f(y) =
(x+y)f(xy) leads to either f(0) = 0 or x+y2 = (xy1)(x+y). The latter simplies to (x+y)(2xy) = 2
for all nonzero x, y, which is patently false. Hence f(0) = 0, so f(x) 0.
Solution 3. Taking y = 0 leads to (x 1)f(0) = f(x) for all x ,= 0. Taking y = 1 leads to xf(x) = f(1)
for all x ,= 1. Hence, for x ,= 0, 1, we have that x(x 1)f(0) = f(1). This holds for innitely many x if
and only if f(0) = f(1) = 0. It follows that f(x) = 0 for all real x.
Comment. Suppose that the given condition is weakened to hold only when both x and y are nonzero.
Then we get xf(x) = f(1) so that f(x) = f(1)/x for all nonzero x. it can be checked that, for any constant
c, f(x) = c/x for is a solution for x ,= 0.
109. Suppose that
x
2
+y
2
x
2
y
2
+
x
2
y
2
x
2
+y
2
= k .
Find, in terms of k, the value of the expression
x
8
+y
8
x
8
y
8
+
x
8
y
8
x
8
+y
8
.
Solution 1. Simplifying, we obtain that
k =
2(x
4
+y
4
)
x
4
y
4
,
and, by extension, that
k
2
+ 4
2k
=
k
2
+
2
k
=
x
4
+y
4
x
4
y
4
+
x
4
y
4
x
4
+y
4
=
2(x
8
+y
8
)
x
8
y
8
.
Continuing on, we nd that
x
8
+y
8
x
8
y
8
+
x
8
y
8
x
8
+y
8
=
2(x
16
+y
16
)
x
16
y
16
=
k
2
+ 4
4k
+
4k
k
2
+ 4
=
k
4
+ 24k
2
+ 16
4k(k
2
+ 4)
.
Comment. R. Barrington Leigh dened a formula
R =
a +b
a b
+
a b
a +b
= 2
a
2
+b
2
a
2
b
2
for a ,= b which he then applied to (a, b) = (x
2
, y
2
), (x
4
, y
4
).
110. Given a triangle ABC with an area of 1. Let n > 1 be a natural number. Suppose that M is a point on
the side AB with AB = nAM, N is a point on the side BC with BC = nBN, and Q is a point on the
side CA with CA = nCQ. Suppose also that T = AN CM, R = BQAN and S = CMBQ,
where signies that the singleton is the intersection of the indicated segments. Find the area of the
triangle TRS in terms of n.
56
Solution 1. [R. Furmaniak, Y. Ren] The area of a triangle XY Z will be denoted by [XY Z]. Consider
the triangle ABQ and the line MC that intersects AB at M, BQ at S and AQ at the external point C. By
Menelaus Theorem for the triangle ABQ and transversal MC,
1 =
BM
MA

AC
QC

QS
SB
= (n 1)n
QS
SB
=
SB
QS
= (n 1)n .
Observe the triangles BSC and QSC. Since the heights from C to the opposite sides SB and QS coincide,
then
[BSC]
[QSC]
=
SB
QS
= (n 1)n =[BSC] = (n 1)n[QSC] .
Examining triangles QSC and QBC, we similarly nd that
[QSC]
[QBC]
=
QS
QB
=
QS
QS +SB
=
1
(n 1)n + 1
=
1
n
2
n + 1
=[QSC] =
1
n
2
n + 1
[QBC] .
Since the heights of triangles QBC and ABC from B to QC and AC coincide, it follows that
[QBC]
[ABC]
=
QC
AB
=
1
n
=[QBC] =
1
n
[ABC] =
1
n
=[QSC] =
1
n
2
n + 1

1
n
=
1
n(n
2
n + 1)
=[BSC] =
(n 1)n
n(n
2
n + 1)
=
n 1
n
2
n + 1
.
Similarly,
[TAC] = [RBA] =
n 1
n
2
n + 1
.
Now
[TSR] = [ABC] [BSC] [TAC] [RBA] = 1
3(n 1)
n
2
n + 1
=
(n 2)
2
n
2
n + 1
.
Solution 2. [M. Butler] Using Menelaus Theorem with triangle BQC and transversal ARN, we nd
that
BR
RQ

QA
AC

CN
NB
= 1
so that
BR
RQ

1 n
n

n 1
1
= 1
=BR =
n
(n 1)
2
RQ .
Thus,
n 1
n
= [ABQ] = [ARB] + [ARQ]
=
_
1 +
(n 1)
2
n
_
[ARB]
=
_
n
2
n + 1
n
_
[ARB]
whence
[ARB] =
n 1
n
2
n + 1
.
57
Therefore
[RST] = 1
3(n 1)
n
2
n + 1
=
(n 2)
2
n
2
n + 1
.
Solution 3. Let a = [AMT], b = [BNR], c = [CQS], x = [BRT], y = [CSR], z = [ATS] and d = [RST].
Then using BM = (n 1)AM, [BRM] = (n 1)a,
x +d = [BTS] = (n 1)[ATS] = (n 1)z
and
nb +y = [BRC] + [CSR] = [BSC] = (n 1)[ASC] = (n 1)nc .
Analogously, from CN = (n 1)BN and AQ = (n 1)CQ, we get
x +d = (n 1)z, y +d = (n 1)x, z +d = (n 1)y
and
nb +y = (n
2
n)c, nc +z = (n
2
n)a, na +x = (n
2
n)b ,
whence
x +y +x + 3d = (n 1)(x +y +z) or 3d = (n 2)(x +y +z)
and
n(a +b +c) + (x +y +z) = (n
2
n)(a +b +c) or x +y +z = (n
2
2n)(a +b +c) .
From 1 = n[na +x +b] = n[nb +y +c] = n[nc +z +a], we nd that
3 = n
2
(a +b +c) +n(x +y +z) +n(a +b +c)
= n(n + 1)(a +b +c) +n(x +y +z)
=
_
n + 1
n 2
+n
_
(x +y +z)
=
_
n
2
n + 1
n 2
_
(x +y +z) ,
whence
d =
(n 2)
2
n
2
n + 1
.
Solution 4. Since the ratio of areas remains invariant under shear transformations and dilations, we
may assume that the triangle is right isosceles. Assign coordinates: A (0, 0), B (0, 1), C = (1, 0),
M (0, 1/n),
N
_
1
n
,
n 1
n
_
Q
_
n 1
n
, 0
_
.
Then
R
_
n 1
n
2
n + 1
,
(n 1)
2
n
2
n + 1
_
S
_
(n 1)
2
n
2
n + 1
,
1
n
2
n + 1
_
and
T
_
1
n
2
n + 1
,
n 1
n
2
n + 1
_
.
58
A computation of the area of RST now yields the result.
Comment. Considering how reasonable the result it, H. Lee noted that when n > 1, then (n 2)
2
<
n
2
n + 1, so that [TSR] < 1 as expected, and also noted that when n = 2, we get the special case of the
medians that intersect in a common point and yield [TSR] = 0.
111. (a) Are there four dierent numbers, not exceeding 10, for which the sum of any three is a prime number?
(b) Are there ve dierent natural numbers such that the sum of every three of them is a prime number?
Solution. [R. Barrington Leigh] (a) Yes, there are four such numbers. The three-member sums of the
set 1, 3, 7, 9 are the primes 11, 13, 17, 19.
(b) No. We prove the statement by contradiction. Suppose that there are ve dierent natural numbers
for which every sum of three is prime. As the numbers are distinct and positive, each such sum must be at
least 1+2+3 = 6, and so cannot be a multiple of 3. Consider the ve numbers, modulo 3. If there are three
in the same congruent class, their sum is a multiple of 3. If there is one each congruent to 0, 1, 2 modulo 3,
then the sum of these three is a multiple of 3. Otherwise, there are only two congruence classes represented
with at most two numbers in each, an impossibility. Hence in all cases, there must be three who sum to a
multiple of 3.
Comment. Part (b) need not be framed as a contradiction. One could formulate it as follows: Let ve
positive integers be given. Argue that either each congruent class modulo 3 is represented or that some class
is represented by at least three of the numbers. Then note that therefore some three must sum to a multiple
of 3. Observe that 3 itself is not a possible sum. Hence, among every ve positive integers, there are three
who add to a nonprime multiple of 3, and simply say that the answer to the question is no.
112. Suppose that the measure of angle BAC in the triangle ABC is equal to . A line passing through the
vertex A is perpendicular to the angle bisector of BAC and intersects the line BC at the point M.
Find the other two angles of the triangle ABC in terms of , if it is known that BM = BA+AC.
Solution. Let q be the line through A perpendicular to the bisector of angle BAC; this line bisects the
external angle at A. The possibility that q is parallel to BC is precluded by the condition that it intersects
BC at M. Let ABC = and ACB = , Since p is not parallel to BC, is not equal to .
Case i. Suppose that > . Then M intersects BC so that B lies between M and C. Let BA be
produced to D so that AC = AD. Since MB = BA + AC = BA + AD = BD, DMB = MDB and so
MDB =
1
2
DBC =
1
2
(exterior angle). Since AD = AC, ADC = ACD =
1
2
BAC =
1
2
. Since MA
produced bisects DAC, MA produced right bisects DC and so MD = MC. Therefore
+

2
= MCD = MDC =

2
+

2
,
whence = 2. Therefore, 180

= + + = + 3 and
=
180

3
and =
360

2
3
.
Case ii. Supppose that < . Then M intersects BC so that C lies between B and M. Let BA
be produced to D so that AD = AC. Since AM bisects DAC, it right bisects CD and so triangle
MDC is isosceles. Then ADM = ADC + MDC = ACD + MCD = ACM. Since BM =
BA + AC = BD, ACM = ADM = BDM = BMD. Since ACM = + (exterior angle),
180

= DBM+2BMD = +2(+), so that =

1
3
(180

2) and = 180

ACM = 180

(+) =
120

1
3
= (360

)/3.
Question. Why cannot you just say the second case can be handled as the rst case, by symmetry?
59
113. Find a function that satises all of the following conditions:
(a) f is dened for every positive integer n;
(b) f takes only positive values;
(c) f(4) = 4;
(d)
1
f(1)f(2)
+
1
f(2)f(3)
+ +
1
f(n)f(n + 1)
=
f(n)
f(n + 1)
.
Solution. [R. Barrington Leigh] The function for which f(n) = n for every positive integer n satises the
condition. [Exercise: establish this by induction.] We now show that this is the only example. Substituting
n = 1 into (d) and noting that f(2) ,= 0, we nd that f(1)
2
= 1, whence f(1) = 1. Applying (d) to two
consecutive values of the argument yields that
f(n)
f(n + 1)

f(n 1)
f(n)
=
1
f(n)f(n + 1)
,
whence
[f(n)]
2
1 = f(n 1)f(n + 1) .
Substituting n = 2 and n = 3 into this and noting that f(1) = 1 and f(4) = 4, we nd that
[f(2)]
2
1 = f(3)
and
[f(3)]
2
1 = 4f(2) ,
whence
0 = [f(2)]
4
2[f(2)]
2
4f(2) = f(2)[f(2) 2]([f(2)]
2
+ 2f(2) + 2) .
Since the rst and third factors are positive for all postive possibilities for f(2), we must have f(2) = 2. As
f(n + 1) =
[f(n)]
2
1
f(n 1)
,
we can prove by induction that f(n) = n for all positive integers n.
114. A natural number is a multiple of 17. Its binary representation (i.e., when written to base 2) contains
exactly three digits equal to 1 and some zeros.
(a) Prove that there are at least six digits equal to 0 in its binary representation.
(b) Prove that, if there are exactly seven digits equal to 0 and three digits equal to 1, then the number
must be even.
Solution 1. (a) If there are fewer than six digits equal to 0 in its binary representation, then the number
must have at most eight digits and be of the form 2
a
+ 2
b
+ 2
c
where 0 a < b < c 7. The rst eight
powers of 2 with nonnegative exponent are congruent to 1, 2, 4, 8, 1, 2, 4, 8 modulo 17, and the sum of
any three of these cannot equal to zero and must lie between 14 and 14. Hence it is not possible for three
powers of 2 among the rst eight to sum to a multiple of 17. Hence, the number must have at least nine
digits, including three zeros.
(b) Suppose that the number is equal to 2
a
+2
b
+2
c
where 0 a < b < c 9. If this number has exactly
10 digits and is odd, then a = 0 and c = 9, so that the number is equal to 1+2
b
+2
9
= 513+2
b
3+2
b
(mod
17). But there is no value of b that will make this vanish, modulo 17. Hence, a 10-digit number divisible by
17 must be even. An example is 2 17
2
= 2 (1 + 2
5
+ 2
8
) = (1001000010)
2
.
60
Solution 2. [R. Furmaniak] (a) Since 17
10
= 10001
2
, any binary number abcd
2
with four or fewer digits
multiplied by 17 will yield abcdabcd
2
. Since the rst and last four digits are the same, there must be an
even number of 1s. Thus, any multiple of 17 with exactly three binary digits must be a product of 17 and
a number that has at least 5 binary digits. Every such product must have at least 9 digits, and so at least
three digits equal to 0.
(b) As in Solution 1.
115. Let U be a set of n distinct real numbers and let V be the set of all sums of distinct pairs of them, i.e.,
V = x +y : x, y U, x ,= y .
What is the smallest possible number of distinct elements that V can contain?
Solution. Let U = x
i
: 1 i n and x
1
< x
2
< < x
n
. Then
x
1
+x
2
< x
1
+x
3
< < x
1
+x
n
< x
2
+x
n
< < x
n1
+x
n
so that the 2n 3 sums x
1
+x
j
with 2 j n and x
i
+x
n
with 2 i n 1 have distinct values. On the
other hand, the set 1, 2, 3, 4, , n has the smallest pairwise sum 3 = 1 + 2 and the largest pairwise sum
2n 1 = (n 1) +n, so there are at most 2n 3 pairwise sums. Hence V can have as few as, but no fewer
than, 2n 3 elements.
Comment. This problem was not well done. A set is assumed to be given, and so you must deal with it.
Many of you tried to vary the elements in the set, and say that if we ddle with them to get an arithmetic
progression we minimize the number of sums. This is vague and intuitive, does not deal with the given set
and needs to be sharpened. To avoid this, the best strategy is to take the given set and try to determine
pairwise sums that are sure to be distinct, regardless of what the set is; this suggests that you should look
at extreme elements - the largest and the smallest. To make the exposition straightforward, assume with no
loss of generality that the elements are in increasing or decreasing order. You want to avoid a proliferation
of possibilities.
Secondly, in setting out the proof, note that it should divide cleanly into two parts. First show that,
whatever the set, at least 2n3 distinct sums occur. Then, by an example, demonstrate that exactly 2n3
sums are possible. A lot of solvers got into hot water by combining these two steps.
116. Prove that the equation
x
4
+ 5x
3
+ 6x
2
4x 16 = 0
has exactly two real solutions.
Solution. In what follows, we denote the given polynomial by p(x).
Solution 1.
p(x) = (x
2
+ 3x + 4)(x
2
+ 2x 4) =
__
x +
3
2
_
2
+
7
4
__
(x + 1)
2
5
_
.
The rst quadratic factor has nonreal roots, and the second two real roots, and the result follows.
Solution 2. Since p(1) = p(2) = 8, the polynomial p(x) + 8 is divisible by x + 2 and x 1. We nd
that
p(x) = (x + 2)
3
(x 1) 8 .
When x > 1, the linear factors are strictly increasing, so p(x) strictly increases from 8 unboundedly, and
so vanishes exactly once in the interval (1, ). When x < 2, the two linear factors are both negative and
increasing, so that p(x) strictly decreases from positive values to 8. Thus, it vanishes exactly once in the
61
interval (, 2). When 2 < x < 1, the two linear factors have opposite signs, so that (x+2)
3
(x1) < 0
and p(x) < 8 < 0. The result follows.
Solution 3. [R. Mong] We have that p(x) = x
4
+ 5x
3
+ 6x
2
4x 16 = (x 1)(x + 2)
3
8. Let
q(x) = f((x + 2)) = (x 3)(x)
3
8 = x
4
+ 3x
3
8. By Descartes Rule of Signs, p(x) and q(x) each
have exactly one positive root. (The rule says that the number of positive roots of a real polynomial has
the same parity as and no more than the number of sign changes in the coecients as read in descending
order.) It follows that p(x) has exactly one root in each interval (, 2) and (0, ). Since p(x) 8 for
2 x 0, the desired result follows.
Solution 4. Since the derivative p

(x) = (x + 2)
2
(4x 1), we deduce that p

(x) < 0 for x <

1
4
and
p

(x) > 0 for x >

1
4
. It follows that p(x) is strictly decreasing on (,
1
4
) and strictly increasing on (
1
4
, ).
Since the leading coecient is positive and p(
1
4
) < 0, p(x) has exactly one root in each of the two intervals.
117. Let a be a real number. Solve the equation
(a 1)
_
1
sin x
+
1
cos x
+
1
sin xcos x
_
= 2 .
Solution. First step. When a = 1, the equation is always false and there is no solution. Also, the
left side is undened when x is a multiple of /2, so we exclude this possibility. Thus, in what follows, we
suppose that a ,= 1 and that sin xcos x ,= 0. [Comment. This initial clearing away the underbrush avoids
nuisance situations later and makes the exposition of the core of the solution go easier.]
Solution 1. Let u = sin x + cos x. Then u
2
1 = 2 sin xcos x, so that
(a 1)(u + 1) = u
2
1
0 = u
2
(a 1)u a = (u + 1)(u a) .
Since sin xcos x ,= 0, u + 1 ,= 0. Thus, u = a, and sin x, cos x are the roots of the quadratic equation
t
2
at +
a
2
1
2
= 0 .
Hence
(sin x, cos x) =
_
1
2
(a
_
2 a
2
),
1
2
(a
_
2 a
2
)
_
.
For this to be viable, we require that [a[

2 and a ,= 1.
Solution 2. The given equation (since sin xcos x ,= 0) is equivalent to
(a 1)(sin x + cos x + 1) = 2 sin xcos x
=(a 1)
2
(2 + 2 sin x + 2 cos x + 2 sin xcos x) = 4 sin
2
xcos
2
x
4(a 1)(sin xcos x) + 2(a 1)
2
(sin xcos x) = 4 sin
2
xcos
2
x
2(a 1) + (a 1)
2
= sin 2x
sin 2x = a
2
1 .
For this to be viable, we require that [a[

2.
For all values of x, we have that
2(1 + sin x + cos x) + 2 sin xcos x = (sin x + cos x + 1)
2
,
62
so that
(sin x + cos x + 1 1)
2
= 1 + 2 sin xcos x = a
2
,
whence
sin x + cos x = a .
Since we squared the given equation, we may have introduced extraneous roots, so we need to check the
solution. Taking sin x + cos x = a, we nd that
(a 1)(sin x + cos x + 1) = (a 1)(a + 1) = a
2
1 = 2 sin xcos x
as desired. Taking sin x + cos x = a, we nd that
(a 1)(sin x + cos x + 1) = (a 1)(1 a) = (a 1)
2
,= a
2
1 = 2 sin xcos x
so this does not work. Hence the equation is solvable when [a[

2, a ,= 1, and the solution is given by

x =
1
2
where sin = a
2
1 and sin x + cos x = a.
Solution 3. We have that
(a 1)
_

2 cos
_
x

4
_
+ 1
_
= (a 1)(sin x + cos x + 1)
= 2 sin xcos x = sin 2x
= cos
_

2
2x
_
= cos 2
_
x

4
_
= 2 cos
2
_
x

4
_
1 .
Let t = cos(x /4). Then
0 = 2t
2

2(a 1)t a
= (

2t a)(

2t + 1) .
Since x cannot be a multiple of /2, t cannot equal 1/

2. Hence cos(x +

4
) = t = a/

2, so that x =

4
+
where cos = a/

2. Since the equation at the beginning of this solution is equivalent to the given equation
and the quadratic in t, this solution is valid, subject to [a[

2 and a ,= 1.
Solution 4. Note that sin x + cos x = 1 implies that 2 sin xcos x = 0. Since we are assuming that
sin x + cos x ,= 0, we multiply the equation (a 1)(sin x + cos x + 1) = 2 sin xcos x by sin x + cos x 1 to
obtain the equivalent equation
(a 1)[(sin x + cos x)
2
1] = 2 sin xcos x(sin x + cos x 1)
(a 1)2 sin xcos x = 2 sin xcos x(sin x + cos x 1)
sin x + cos x = a
sin
_
x +

4
_
=
1

a
x =

4
where sin = a/

2. We have the same conditions on a as before.

63
Solution 5. The equation is equivalent to
(a 1)(sin x + 1) = cos x(2 sin x + 1 a) .
Squaring, we obtain
(a 1)
2
(sin x + 1)
2
= (1 sin
2
x)[4 sin
2
x + 4(1 a) sin x + (1 a)
2
] .
Dividing by sin x + 1 yields
2 sin
2
x 2a sin x + (a
2
1) = 0 =sin x =
1
2
(a
_
2 a
2
) .
[Note that the equation cos x = a sin x in Solution 3 leads to the equation here.] Thus
sin
2
x =
1 a

2 a
2
2
and cos
2
x =
1 a

2 a
2
2
.
Thus
(sin x, cos x) =
_
1
2
(a
_
2 a
2
),
1
2
(a
_
2 a
2
)
_
.
Note that 0 sin
2
x 1 requires 0 1 a

2 a
2
2, or equivalently [a[

2 and a
2
(2 a
2
) 1
[a[

2 and (a
2
1)
2
0 [a[

2.
We need to check for extraneous roots. If
(sin x, cos x) = ((1/2)(a
_
2 a
2
), (1/2)(a
_
2 a
2
) ,
then
(a 1)(sin x + cos x + 1) = (a 1)(a + 1) = a
2
1 = (1/2)[a
2
(2 a
2
)] = 2 sin xcos x
as desired. On the other hand, if
(sin x, cos x) = ((1/2)(a
_
2 a
2
), (1/2)(a
_
2 a
2
) ,
then
(a 1)(sin x + cos x + 1) = (a 1)(
_
2 a
2
+ 1)
while
2 sin xcos x = (1/2)[a
2
(2 a
2
)] = (a
2
1) .
These are not equal when a ,= 1. Hence
(sin x, cos x) = ((1/2)(a
_
2 a
2
), (1/2)(a
_
2 a
2
) .
Solution 6. Let u = sin x + cos x, so that u
2
= 1 + 2 sin xcos x. Then the equation is equivalent to
(a 1)(u + 1) = u
2
1, whence u = 1 or u = a. We reject u = 1, so that u = a and we can nish as in
Solution 3.
Solution 7. [O. Bormashenko] Since
1
sin x
+
1
cos x
+
1
sin xcos x
=
2
a 1
,
we have that
_
1
sin x
+
1
cos x
_
2
=
_
2
a 1

1
sin xcos x
_
2
64

1
sin
2
xcos
2
x
+
2
sin xcos x
=
4
(a 1)
2

4
(a 1) sin xcos x
+
1
sin
2
xcos
2
x

1
sin xcos x
_
2 +
4
a 1
_
=
4
(a 1)
2
2 sin xcos x = a
2
1 sin 2x = a
2
1 .
We check this solution as in Solution 2.
Solution 8. [S. Patel] Let z = cos x +i sin x. Note that z ,= 0, 1, i. Then
sin x =
1
2i
_
z
1
z
_
=
z
2
1
2iz
and
cos x =
1
2
_
z +
1
z
_
=
z
2
+ 1
2z
.
The given equation is equivalent to
1 = (a 1)
_
iz
z
2
1
+
z
z
2
+ 1
+
2iz
2
z
4
1
_
= (a 1)
_
iz
z
2
1
+
z
z
2
+ 1
+
i
z
2
1
+
i
z
2
+ 1
_
= (a 1)
_
i(z + 1)
z
2
1
+
z +i
z
2
+ 1
_
= (a 1)
_
i
z 1
+
1
z i
_
= (a 1)
_
(i + 1)z
z
2
(1 +i)z +i
_
.
This is equivalent to
z
2
(1 +i)z +i = (a 1)[(1 +i)z] z
2
(1 +i)az +i = 0 .
Hence
z =
(1 +i)a

2ia
2
4i
2
=
(1 +i)a

2i

a
2
2
2
=
_
1 +i
2
_
(a
_
a
2
2) .
Suppose that a
2
> 2. Then [z[
2
=
1
2
[a

a
2
2]
2
= (a
2
1) a

a
2
2. Since [z[ = 1, we must have
a
2
2 = a

a
2
2, whence a
4
4a
2
+4 = a
4
2a
2
or a
2
= 2, which we do not have. Hence, we must have
a
2
2, so that
z =
_
1 +i
2
_
(a
_
a
2
2) .
Therefore
cos x = Rez =
a

2 a
2
2
and
sin x = Imz =
a

2 a
2
2
.
65
Comment. R. Barrington Leigh had an interesting approach for solutions with positive values of sin x
and cos x. Consider a right triangle with legs sin x and cos x, inradius r, semiperimeter s and area . Then
1
r
=
s

=
1 + sin x + cos x
sin xcos x
=
2
a 1
so that 1 a. We need to determine right triangles whose inradius is
1
2
(a 1). Using the formula r =
(s c) tan(C/2) with c = 1 and C = 90

, we have that
r = (s 1) tan 45

= s 1
whence
a 1
2
=
1
2
(sin x + cos x 1) sin x + cos x = a .
118. Let a, b, c be nonnegative real numbers. Prove that
a
2
(b +c a) +b
2
(c +a b) +c
2
(a +b c) 3abc .
When does equality hold?
Solution 1. Observe that
3abc [a
2
(b +c a) +b
2
(c +a b) +c
2
(a +b c)] = abc (b +c a)(c +a b)(a +b c) . ()
Now
2a = (c +a b) + (a +b c)
with similar equations for b and c. These equations assure us that at most one of b + c a, c + a b and
a +b c can be negative. If exactly one of these three quantities is negative, than (*) is clearly nonnegative,
and is equal to zero if and only if at least one of a, b and c vanishes, and the other two are equal. If all the
three quantities are nonnegative, then an application of the arithmetic-geometric means inequality yields
that
2a 2
_
(c +a b)(a +b c)
with similar inequalities for b and c. It follows from this that () is nonnegative and vanishes if and only if
a = b = c, or one of a, b, c vanishes and the other two are equal.
Solution 2. Wolog, suppose that a b c. Then
3abc [a
2
(b +c a) +b
2
(c +a b) +c
2
(a +b c)]
= a(bc ab ac +a
2
) +b(ac bc ab +b
2
) +c(ab ac bc +c
2
)
= a(b a)(c a) b(c b)(b a) c(c a)(c b)
= a(b a)(c a) + (c b)[ab b
2
+c
2
ca]
= a(b a)(c a) + (c b)
2
(c +b a) 0 .
Equality occurs if and only if a = b = c or if a = 0 and b = c.
Solution 3. [S.-E. Lu] The inequality is equivalent to
(a +b c)(b +c a)(c +a b) abc .
At most one of the three factors on the left side can be negative. If one of them is negative, then the
inequality is satised, and equality occurs if and only if both sides vanish (i.e., one of the three variables
vanishes and the others are equal).
66
Otherwise, we can square both sides to get the equivalent inequality:
[a
2
(b c)
2
][b
2
(a c)
2
][c
2
(a b)
2
] a
2
b
2
c
2
.
Since b a +c and c a +b, we nd that [b c[ a, whence (b c)
2
a
2
. Thus, a
2
(b c)
2
a
2
, with
similar inequalties for the other two factors on the left. It follows that the inequality holds with equality
when a = b = c or one variable vanishes and the other two are equal.
Solution 4. [R. Mong] Let

f(a, b, c) denote the cyclic sum f(a, b, c) + f(b, c, a) + f(c, a, b). Suppose
that u = a
3
+b
3
+c
3
=

a
3
and v =

(b c)a
2
. Then
u +v =

a
3
+ (b c)a
2
=

a
2
(a +b c)
and
u v =

a
3
(b c)a
2
=

a
2
(a b +c) =

a
2
(c +a b) =

b
2
(a +b c) .
Then

a
2
(a +b c)

b
2
(a +b c) = u
2
v
2
u
2
.
By the Cauchy-Schwarz Inequality,

ab(a +b c)
_
u
2
v
2
a
3
+b
3
+c
3
.
(Note that the left side turns out to be positive; however, the result would hold anyway even if it were
negative, since a
3
+b
3
+c
3
is nonnegative.)
Then
a
2
b +ab
2
abc +b
2
c +bc
2
abc +a
2
c +ac
2
abc a
3
+b
3
+c
3
=a
2
(b +c a) +b
2
(c +a b) +c
2
(a +b c) 3abc
as desired.
Equality holds if and only if
a
2
(a +b c) : b
2
(b +c a) : c
2
(c +a b) = b
2
(a +b c) : c
2
(b +c a) : a
2
(c +a b) .
Suppose, if possible that a +b = c, say. Then b +c a = 2b, c +a b = 2a, so that b
3
: c
2
a = c
2
b : a
3
and
c
2
= ab. This is possible if and only if a = b = 0. Otherwise, all terms in brackets are nonzero, and we nd
that a
2
: b
2
: c
2
= b
2
: c
2
: a
2
so that a = b = c.
Solution 5. [A. Chan] Wolog, let a b c, so that b = a + x and c = a + x + y, where x, y 0. The
left side of the inequality is equal to
3a
3
+ 3(2x +y)a
2
+ (2x
2
+ 2xy y
2
)a (y
3
+ 2xy
2
)
and the right side is equal to
3a
3
+ 3(2x +y)a
2
+ (3x
2
+ 3xy)a .
The right side minus the left side is equal to
(x
2
+xy +y
2
)a + (y
3
+ 2xy
2
) .
Since each of a, x, y is nonnegative, this expression is nonnegative, and it vanishes if and only if each term
vanishes. Hence, the desired inequality holds, with equality, if and only if y = 0 and either a = 0 or x = 0,
if and only if either (a = 0 and b = c) or (a = b = c).
67
119. The medians of a triangle ABC intersect in G. Prove that
[AB[
2
+[BC[
2
+[CA[
2
= 3([GA[
2
+[GB[
2
+[GC[
2
) .
Solution 1. Let the respective lengths of BC, CA, AB, AG, BG and CG be a, b, c, u, v, w. If M is the
midpoint of BC, then A, G, M are collinear with AM = (3/2)AG. Let = AMB. By the law of cosines,
we have that
c
2
=
9
4
u
2
+
1
4
a
2

3
2
aucos
b
2
=
9
4
u
2
+
1
4
a
2
+
3
2
aucos
whence
b
2
+c
2
=
9
2
u
2
+
1
2
a
2
.
Combining this with two similar equations for the other vertices and opposite sides, we nd that
2(a
2
+b
2
+c
2
) =
9
2
(u
2
+v
2
+w
2
) +
1
2
(a
2
+b
2
+c
2
)
which simplies to a
2
+b
2
+c
2
= 3(u
2
+v
2
+w
2
), as desired.
Solution 2. We have that

AG =
1
3
(

AB +

AC) .
Hence
[

AG[
2
=
1
9
[[

AB[
2
+[

AC[
2
+ 2(

AB

AC)] .
Similarly
[

BG[
2
=
1
9
[[

BA[
2
+[

BC[
2
+ 2(

BA

BC)] ,
and
[

CG[
2
=
1
9
[[

CA[
2
+[

CB[
2
+ 2(

CA

CB)] .
Therefore
9[[

AG[
2
+[

BG[
2
+[

CG[
2
]
= 2[[

AB[
2
+[

BC[
2
+[

CA[
2
] +

AB (

AC +

CB) +

AC (

AB +

BC) +

BC (

BA+

AC)
= 3[[

AB[
2
+[

BC[
2
+[

CA[
2
,
as desired.
120. Determine all pairs of nonnull vectors x, y for which the following sequence a
n
: n = 1, 2, is (a)
increasing, (b) decreasing, where
a
n
= [x ny[ .
Solution 1. By the triangle inequality, we obtain that
[x ny[ +[x (n 2)y[ 2[x (n 1)y[ ,
whence
[x ny[ [x (n 1)y[ [x (n 1)y[ [x (n 2)y[ ,
68
for n 3. This establishes that the sequence is never decreasing, and will increase if and only if
[x 2y[ [x y[ 0 .
This condition is equivalent to
x x 4x y + 4y y x x 2x y +y y
or 3[y[
2
2x y.
Solution 2.
a
2
n
= [x[
2
2n(x y) +n
2
[y[
2
= [y[
2
__
n
x y
[y[
2
_
2
_
+
_
[x[
2

(x y)
2
[y[
4
_
.
This is a quadratic whose nonconstant part involves the form (n c)
2
. This is an increasing function of n,
for positive integers n, if and only if c 3/2. Hence, the sequence increases if and only if
x y
[y[
2

3
2
.
121. Let n be an integer exceeding 1. Let a
1
, a
2
, , a
n
be posive real numbers and b
1
, b
2
, , b
n
be arbitrary
real numbers for which

i=j
a
i
b
j
= 0 .
Prove that

i=j
b
i
b
j
< 0 .
Solution 1. For the result to hold, we need to assume that at least one of the b
i
is nonzero. The condition
is that
(a
1
+a
2
+ +a
n
)(b
1
+b
2
+ +b
n
) = a
1
b
1
+a
2
b
2
+ +a
n
b
n
.
Now
2

i=j
b
i
b
j
= (b
1
+b
2
+ +b
n
)
2
(b
2
1
+b
2
2
+ +b
2
n
)
=
(a
1
b
1
+ +a
n
b
n
)
2
(a
1
+ +a
n
)
2
(b
2
1
+ +b
2
n
)

(a
2
1
+ +a
2
n
)(b
2
1
+ +b
2
n
)
(a
1
+ +a
n
)
2
(b
2
1
+ +b
2
n
)
=
(b
2
1
+ +b
2
n
)
(a
1
+ +a
n
)
2
[(a
2
1
+ +a
2
n
) (a
1
+ +a
n
)
2
] < 0 ,
from which the desired result follows. The inequality is due to the Cauchy-Schwarz Inequality.
Solution 2. [R. Barrington Leigh] Suppose that not all the b
i
vanish and that b
1
b
2
b
n
(wolog).
Since

i=j
a
i
b
j
= 0, not all the b
i
have the same sign, and so b
1
> 0 > b
n
. Wolog, we may assume that
B b
1
+b
2
+ +b
n
0. (If B < 0, we can change the signs of all the b
i
which alters neither the hypothesis
nor the conclusion.) We have that
0 = a
1
(b
1
B) +a
2
(b
2
B) + +a
n
(b
n
B) < (a
1
+a
2
+ +a
n
)(b
1
B) ,
so that b
1
> B. Hence
2

i=j
b
i
b
j
= B
2

b
2
i
< B
2
b
2
1
< 0 ,
69
as desired.
122. Determine all functions f from the real numbers to the real numbers that satisfy
f(f(x) +y) = f(x
2
y) + 4f(x)y
for any real numbers x, y.
Solution 1. Let y =
1
2
(x
2
f(x)). Then
f
_
f(x) +x
2
2
_
= f
_
f(x) +x
2
2
_
+ 2f(x)[x
2
f(x)] ,
from which it follows that, for each x, either f(x) = 0 or f(x) = x
2
. [Note: this does not imply yet that the
same option holds for all x.] In particular, f(0) = 0, so that f(y) = f(y) for all y.
Suppose that f(c) = 0. Then, for each real y, f(y) = f(c
2
y), whence f(c
2
) = f(0) = 0. Thus, for
each real y, f(y) = f(c
4
y). Suppose that f(y) ,= 0. Then
f(y) = y
2
=y
2
= (c
2
y)
2
= (c
4
y)
2
=0 = c
2
(c
2
2y) = c
4
(c
4
2y) .
If c were nonzero, then we would have c
2
/2 = y = c
4
/2, so c = 1 and y =
1
2
. But then f(y) = f(y) =
f(1 y); substituting y =
1
2
yields
1
4
= f(
1
2
) = f(
3
2
), which is false. Hence c = 0. It follows that, either
f(x) 0 (for all x) or else that f(x) x
2
(for all x). These solutions can (and should be) checked.
Solution 2. Let y = x
2
f(x). Then
f(x
2
) = f(f(x) +x
2
f(x)) = f(f(x)) + 4f(x)[x
2
f(x)] .
Taking y = 0, we see that f(f(x)) = f(x
2
), so that 4f(x)[x
2
f(x)] = 0. Hence, for each x, either f(x) = 0
or f(x) = x
2
.
Suppose, if possible, that there are two nonzero reals u and v for which f(u) = 0 and f(v) = v
2
. Setting
(x, y) = (u, v) yields that v
2
= f(u
2
v). Since v ,= 0, we must have that
v
2
= f(u
2
v) = u
4
2u
2
v +v
2
0 = u
2
(u
2
2v) v =
1
2
u
2
.
This would mean that we could nd only one such pair (u, v), which is false. Hence this case is not possible,
so that, either f(x) = 0 for all x or else that f(x) = x
2
for all x.
Solution 3. From (x, y) = (0, 0), we have that f(f(0)) = f(0). From (x, y) = (0, f(0)), we have that
f(0) = f(f(0)) 4f(0)
2
, whence f(0) = 0. From x = 0, we have that f(y) = f(y) for all y. Finally, taking
y = x
2
and y = f(x), we get
f(x
2
+f(x)) = f(0) + 4f(x)x
2
= f(x
2
+f(x)) 4f(x)
2
+ 4f(x)x
2
.
so that 0 = 4f(x)[x
2
f(x)]. We can nish as in the other solutions.
Solution 4. [R. Barrington Leigh] Taking y = x f(x) and then y = x
2
x yields that
f(x) = f(f(x) +x f(x)) = f(x
2
x +f(x)) + 4f(x)(x f(x))
= f(x
2
(x
2
x)) + 4f(x)(x
2
x) + 4f(x)(x f(x))
= f(x)[1 + 4x
2
4x + 4x 4f(x)] = f(x) + 4f(x)[x
2
f(x)] ,
so that for each x, either f(x) = 0 or f(x) = x
2
. The solution can be completed as before.
70
123. Let a and b be the lengths of two opposite edges of a tetrahedron which are mutually perpendicular and
distant d apart. Determine the volume of the tetrahedron.
Solution 1. Construct parallel planes distant d apart that contain the edges of lengths a and b. In the
planes, congruent parallelograms can be constructed whose diagonals are of lengths a and b and right bisect
each other, and each of which has an edge of the tetrahedron as a diagonal. Each parallelogram can be
obtained from the other by a translation relating their centres, so the two parallelograms bound a prism
with opposite faces distant d apart. The volume of this prism is
1
2
abd.
The prism is the disjoint union of the given tetrahedron and four tetrahedra, all of height d, two having
as base a triangle with base a and height
1
2
b and two having as base a triangle with base b and height
1
2
a. Each of these latter four tetrahedra have volume
1
3
(
1
2

ab
2
)d =
abd
12
. Hence, the volume of the given
tetrahedron is
abd
2
4
_
abd
12
_
=
1
6
(abd) .
Solution 2. Suppose that ABCD is the tetrahedron with opposite edges AB of length a and CD of
length b orthogonal and at distance d from each other.
Case (i). Suppose that AB and CD are oriented so that there are points E and F on AB and CD
respectively for which EF is perpendicular to both AB and CD. Then [EF[ = d and [ABF] =
1
2
ad. The
tetrahedron ABCD is the union of the nonoverlapping tetrahedra ABFC and ABFD, each with ABF as
base and perpendicular height along CD. Hence the volume of ABCD is equal to
1
3
[ABF]([FC[ +[FD[) =
1
3
_
1
2
ad
_
[CD[ =
1
6
abd .
Case (ii). Suppose that E and F are on AB possibly produced and on CD produced, say, with EF
perpendicular to AB and CD. Then we can argue in a way similar to that in Case (i) that the volume of
ABCD is equal to the volume of ABFC less the volume of ABFD to obtain the answer (1/6)abd.
Solution 3. [C. Lau; H. Lee] Let ABCD be the given tetrahedron with [BC[ = a and [AD[ = b.
Suppose E lies on BC, possibly produced, with AE BC. Then AD must lie in the plane containing AE
and perpendicular to BC. Let F lie on AD produced with EF AD. Note that [EF[ = d. Let G be the
foot of the perpendicular from D to AE produced. Then
[ADE] =
1
2
[AD[[EF[ =
1
2
bd =
1
2
[AE[[GD[ .
It follows that the volume of ABCD is equal to
1
3
[ABC][GD[ =
1
6
[AE[[BC[[GD[ =
1
6
abd .
124. Prove that
(1
4
+
1
4
)(3
4
+
1
4
)(5
4
+
1
4
) (11
4
+
1
4
)
(2
4
+
1
4
)(4
4
+
1
4
)(6
4
+
1
4
) (12
4
+
1
4
)
=
1
313
.
Solution. The left side can be written as

4x
4
+ 1 : x odd, 1 x 11

4x
4
+ 1 : x even, 2 x 12 .
Now
4x
4
+ 1 = 4x
4
+ 4x
2
+ 1 4x
2
= (2x
2
+ 1)
2
(2x)
2
= (2x
2
2x + 1)(2x
2
+ 2x + 1) = [(x 1)
2
+x
2
][x
2
+ (x + 1)
2
] .
71
From this, we see that the left side is equal to
[1
2
(1
2
+ 2
2
)][(2
2
+ 3
2
)(3
2
+ 4
2
)] [(10
2
+ 11
2
)(11
2
+ 12
2
)]
[(1
2
+ 2
2
)(2
2
+ 3
2
)][(3
2
+ 4
2
)(4
2
+ 5
2
)] [(11
2
+ 12
2
)(12
2
+ 13
2
)]
=
1
2
12
2
+ 13
2
=
1
313
.
Comment. In searching for factors, note that any common divisor of 4n
4
+ 1 and 4(n + 1)
4
+ 1 must
divide the dierence
[(n
4
+ 1)
4
n
4
] = [(n + 1)
2
n
2
][(n + 1)
2
+n
2
] = (2n + 1)(2n
2
+ 2n + 1) ,
so that we can try either 2n + 1 (which does not work) or 2n
2
+ 2n + 1 to nd that 4n
4
+ 1 = (2n
2
+ 2n +
1)(2n
2
2n + 1) and
4(n + 1)
4
+ 1 = (2n
2
+ 2n + 1)(2n
2
+ 6n + 5) = (2n
2
+ 2n + 1)[2(n + 2)
2
2(n + 2) + 1] .
125. Determine the set of complex numbers z which satisfy
Im (z
4
) = (Re (z
2
))
2
,
and sketch this set in the complex plane. (Note: Im and Re refer respectively to the imaginary and real
parts.)
Solution 1. Let z = x + yi and z
2
= u + vi. Then u = x
2
y
2
, v = 2xy and z
4
= (u
2
v
2
) + 2uvi.
Im (z
4
) = (Re (z
2
))
2
implies that 2uv = u
2
. Thus, u = 0 or u = 2v. These reduce to x
2
= y
2
or
(x 2y)
2
= 5y
2
, so that the locus consists of the points z on the lines determined by the equations y = x,
y = x, y = (

5 2)x, y = (

5 2)x.
Solution 2. Let z = r(cos + i sin ); then z
2
= r
2
(cos 2 + i sin 2) and z
4
= r
4
(cos 4 + i sin 4). The
condition is equivalent to
r
4
sin 4 = (r
2
cos 2)
2
2 sin 2 cos 2 = cos
2
2 .
Hence cos 2 = 0 or tan 2 =
1
2
. The latter possibility leads to tan
2
+ 4 tan 1 = 0 or tan = 2

5.
This yields the same result as in Solution 1.
Solution 3. Let z = x+yi. Then z
2
= x
2
y
2
+2xyi and z
4
= (x
4
6x
2
y
2
+y
4
) +4xy(x
2
y
2
)i. Then
the condition in the problem is equivalent to
4xy(x
2
y
2
) = (x
2
y
2
)
2
,
which in turn is equivalent to y = x or y
2
+ 4xy x
2
= 0, i.e., y = (2

5)x.
126. Let n be a positive integer exceeding 1, and let n circles (i.e., circumferences) of radius 1 be given in the
plane such that no two of them are tangent and the subset of the plane formed by the union of them is
connected. Prove that the number of points that belong to at least two of these circles is at least n.
Solution. Let be the set of circles and S be the set of points belonging to at least two of them. For
C and s S C, dene f(s, C) = 1/k, where k is the number of circles passing through s, including C.
For C and s , C, dene f(s, C) = 0. Observe that, for each s S,

C
f(s, C) = 1 .
72
Let C ; select s S C for which f(s, C) = 1/k is minimum. Let C = C
1
, C
2
, , C
k
be the circles that
contain s. These circles (apart from C) meet C in distinct points, so that

sS
f(s, C)
1
k
+
k 1
k
= 1 .
Hence the number of points in S is equal to

sS

C
f(s, C) =

sS
f(s, C) n .
Comment. The full force of the connectedness condition is not needed. It is required only that each
circle intersect with at least one other circle.
73