Canadian MO 1969-2017 (Solutions From 1994 - 2017)
Canadian MO 1969-2017 (Solutions From 1994 - 2017)
Canadian MO 1969-2017 (Solutions From 1994 - 2017)
1969
PROBLEM 1
Show that if a1 =b1 = a2 =b2 = a3 =b3 and p1 , p2 , p3 are not all zero, then
n p an + p an + p an
a1 = 1 1 2 2 3 3
b1 p1bn1 + p2 bn2 + p3 bn3
for every positive integer n.
PROBLEM 2
p p p p
Determine which of the two numbers c + 1 , c, c , c , 1 is greater for any
c 1.
PROBLEM 3
Let c be the length of the hypotenuse of a right
p angle triangle whose other two sides
have lengths a and b. Prove that a + b 2c. When does the equality hold?
PROBLEM 4
Let ABC be an equilateral triangle, and P be an arbitrary point within the triangle.
Perpendiculars PD, PE , PF are drawn to the three sides of the triangle. Show
that, no matter where P is chosen,
PD + PE + PF = p1 :
AB + BC + CA 2 3
PROBLEM 5
Let ABC be a triangle with sides of lengths a, b and c. Let the bisector of the
angle C cut AB in D. Prove that the length of CD is
2ab cos C2
a+b :
PROBLEM 6
Find the sum of 1 1! + 2 2! + 3 3! + + (n , 1)(n , 1)! + n n!, where n! =
n(n , 1)(n , 2) 2 1.
PROBLEM 7
Show that there are no integers a, b, c for which a2 + b2 , 8c = 6.
{1{
PAGE 2 1969
PROBLEM 8
Let f be a function with the following properties:
1) f (n) is dened for every positive integer n;
2) f (n) is an integer;
3) f (2) = 2;
4) f (mn) = f (m)f (n) for all m and n;
5) f (m) > f (n) whenever m > n.
Prove that f (n) = n.
PROBLEM 9
Show that for any quadrilateral inscribed
p in a circle of radius 1, the length of the
shortest side is less than or equal to 2.
PROBLEM 10 A
Let ABC be the right-angled isosceles triangle
whose equal sides have length 1. P is a point on
the hypotenuse, and the feet of the perpendiculars
from P to the other sides are Q and R. Consider
the areas of the triangles APQ and PBR, and the
area of the rectangle QCRP . Prove that regard- P Q
less of how P is chosen, the largest of these three
areas is at least 2=9.
B R C
Canadian Mathematical Olympiad
1970
PROBLEM 1
Find all number triples (x; y; z) such that when any one of these numbers is added
to the product of the other two, the result is 2.
D
PROBLEM 2 A
Given a triangle ABC with angle A obtuse and
with altitudes of length h and k as shown in the
k
b
diagram, prove that a + h b + k. Find under h
what conditions a + h = b + k. C
E
B
a
PROBLEM 3
A set of balls is given. Each ball is coloured red or blue, and there is at least one of
each colour. Each ball weighs either 1 pound or 2 pounds, and there is at least one
of each weight. Prove that there are 2 balls having dierent weights and dierent
colours.
PROBLEM 4
a) Find all positive integers with initial digit 6 such that the integer formed by
deleting this 6 is 1=25 of the original integer.
b) Show that there is no integer such that deletion of the rst digit produces a
result which is 1=35 of the original integer.
PROBLEM 5
A quadrilateral has one vertex on each side of a square of side-length 1. Show that
the lengths a, b, c and d of the sides of the quadrilateral satisfy the inequalities
2 a2 + b2 + c2 + d2 4:
PROBLEM 6
Given three non-collinear points A, B , C , construct a circle with centre C such
that the tangents from A and B to the circle are parallel.
PROBLEM 7
Show that from any ve integers, not necessarily distinct, one can always choose
three of these integers whose sum is divisible by 3.
PROBLEM 8
Consider all line segments of length 4 with one end-point on the line y = x and the
other end-point on the line y = 2x. Find the equation of the locus of the midpoints
of these line segments.
{1{
PAGE 2 1970
PROBLEM 9
Let f (n) be the sum of the rst n terms of the sequence
0; 1; 1; 2; 2; 3; 3; 4; 4; 5; 5; 6; 6; : : : :
a) Give a formula for f (n).
b) Prove that f (s + t) , f (s , t) = st where s and t are positive integers and
s > t.
PROBLEM 10
Given the polynomial
f (x) = xn + a1 xn,1 + a2 xn,2 + + an,1 x + an
with integral coecients a1 ; a2 ; : : : ; an , and given also that there exist four distinct
integers a, b, c and d such that
f (a) = f (b) = f (c) = f (d) = 5;
show that there is no integer k such that f (k) = 8.
Canadian Mathematical Olympiad
1971
PROBLEM 1
B C
DEB is a chord of a circle such that DE = 3 and E
EB = 5. Let O be the centre of the circle. Join D
OE and extend OE to cut the circle at C . (See
diagram). Given EC = 1, nd the radius of the O
circle.
PROBLEM 2
Let x and y be positive real numbers such that x + y = 1. Show that
1 + x1 1 + 1y 9:
PROBLEM 3
ABCD is a quadrilateral with AD = BC . If 6 ADC is greater than 6 BCD, prove
that AC > BD.
PROBLEM 4
Determine all real numbers a such that the two polynomials x2 +ax+1 and x2 +x+a
have at least one root in common.
PROBLEM 5
Let
p(x) = a0 x + a1 x ,1 + + a ,1 x + a ;
n n
n n
where the coecients a are integers. If p(0) and p(1) are both odd, show that p(x)
i
has no integral roots.
PROBLEM 6
Show that, for all integers n, n2 + 2n + 12 is not a multiple of 121.
PROBLEM 7
Let n be a ve digit number (whose rst digit is non-zero) and let m be the four
digit number formed from n by deleting its middle digit. Determine all n such that
n=m is an integer.
PROBLEM 8
A regular pentagon is inscribed in a circle of radius r. P is any point inside the
pentagon. Perpendiculars are dropped from P to the sides, or the sides produced,
of the pentagon.
{1{
PAGE 2 1971
a) Prove that the sum of the lengths of these perpendiculars is constant.
b) Express this constant in terms of the radius r.
PROBLEM 9
Two
ag poles of heights h and k are situated 2a units apart on a level surface.
Find the set of all points on the surface which are so situated that the angles of
elevation of the tops of the poles are equal.
PROBLEM 10
Suppose that n people each know exactly one piece of information, and all n pieces
are dierent. Every time person A phones person B, A tells B everything that
A knows, while B tells A nothing. What is the minimum number of phone calls
between pairs of people needed for everyone to know everything? Prove your answer
is a minimum.
Canadian Mathematical Olympiad
1972
PROBLEM 1
Given three distinct unit circles, each of which is tangent to the other two, nd the
radii of the circles which are tangent to all three circles.
PROBLEM 2
Let a1 ; a2 ; : : : ; a be non-negative real numbers. Dene M to be the sum of all
n
products of pairs a a (i < j ), i.e.,
i j
M = a1 (a2 + a3 + + a ) + a2 (a3 + a4 + + a ) + + a ,1 a :
n n n n
Prove that the square of at least one of the numbers a1 ; a2 ; : : : ; a does not exceed
n
2M=n(n , 1).
PROBLEM 3
a) Prove that 10201 is composite in any base greater than 2.
b) Prove that 10101 is composite in any base.
PROBLEM 4
Describe a construction of a quadrilateral ABCD given:
(i) the lengths of all four sides;
(ii) that AB and CD are parallel;
(iii) that BC and DA do not intersect.
PROBLEM 5
Prove that the equation x3 + 113 = y3 has no solution in positive integers x and y.
PROBLEM 6
Let a and b be distinct real numbers. Prove that there exist integers m and n such
that am + bn < 0, bm + an > 0.
PROBLEM 7
a) Prove that the values of x for which x = (x2 + 1)=198 lie between 1=198 and
197:99494949 . p
b) Use the result pof a) to prove that 2 < 1:41421356.
c) Is it true that 2 < 1:41421356?
PROBLEM 8
During a certain election campaign, p dierent kinds of promises are made by the
various political parties (p > 0). While several parties may make the same promise,
any two parties have at least one promise in common; no two parties have exactly
the same set of promises. Prove that there are no more than 2 ,1 parties.
p
{1{
PAGE 2 1972
PROBLEM 9
Four distinct lines L1, L2, L3, L4 are given in the plane: L1 and L2 are respectively
parallel to L3 and L4. Find the locus of a point moving so that the sum of its
perpendicular distances from the four lines is constant.
PROBLEM 10
What is the maximum number of terms in a geometric progression with common
ratio greater than 1 whose entries all come from the set of integers between 100
and 1000 inclusive?
Canadian Mathematical Olympiad
1973
PROBLEM 1
(i) Solve the simultaneous inequalities, x < 41 and x < 0; i.e., nd a single
x
inequality equivalent to the two given simultaneous inequalities.
(ii) What is the greatest integer which satises both inequalities 4x + 13 < 0 and
x2 + 3x > 16?
(iii) Give a rational number between 11=24 and 6=13.
(iv) Express 100000 as a product of two integers neither of which is an integral
multiple of 10.
(v) Without the use of logarithm tables evaluate
1 1
log2 36 + log3 36 :
PROBLEM 2
Find all the real numbers which satisfy the equation jx +3j,jx , 1j = x +1. (Note:
jaj = a if a 0; jaj = ,a if a < 0.)
PROBLEM 3
Prove that if p and p + 2 are both prime integers greater than 3, then 6 is a factor
of p + 1.
PROBLEM 4
The gure shows a (convex) polygon with nine ver- P0 P8
tices. The six diagonals which have been drawn P1 P7
dissect the polygon into the seven triangles:
P0 P1P3 , P0 P3P6, P0P6 P7, P0P7 P8, P1P2P3 , P6
P3 P4P6 , P4 P5P6. In how many ways can these P2
triangles be labelled with the names 41, 42, 43,
44 , 45, 46, 47 so that P is a vertex of triangle P5
i
4 for i = 1; 2; 3; 4; 5; 6; 7? Justify your answer.
i
P3 P 4
PROBLEM 5
For every positive integer n, let
h(n) = 1 + 12 + 13 + + n1 :
For example, h(1) = 1, h(2) = 1+ 21 , h(3) = 1+ 21 + 13 . Prove that for n = 2; 3; 4; : : :
n + h(1) + h(2) + h(3) + + h(n , 1) = nh(n):
{1{
PAGE 2 1973
PROBLEM 6
If A and B are xed points on a given circle not collinear with centre O of the
circle, and if XY is a variable diameter, nd the locus of P (the intersection of the
line through A and X and the line through B and Y ).
PROBLEM 7
Observe that
1 = 1 + 1; 1 = 1 + 1; 1 = 1 + 1 ; 1 = 1 + 1 :
1 2 2 2 3 6 3 4 12 4 5 20
State a general law suggested by these examples, and prove it.
Prove that for any integer n greater than 1 there exist positive integers i and j such
that
1 1 1 1 1
n = i(i + 1) + (i + 1)(i + 2) + (i + 2)(i + 3) + + j (j + 1) :
Canadian Mathematical Olympiad
1974
PART A
PROBLEM 1
i) If x = (1 + n1 )n and y = (1 + n1 )n+1 , show that yx = xy .
ii) Show that, for all positive integers n,
12 , 22 + 32 , 42 + + (,1)n(n , 1)2 + (,1)n+1n2 = (,1)n+1(1 + 2 + + n):
PROBLEM 2
Let ABCD be a rectangle with BC = 3AB . Show that if P , Q are the points on
side BC with BP = PQ = QC , then
6 DBC + 6 DPC = 6 DQC:
PART B
PROBLEM 3
Let
f (x) = a0 + a1 x + a2 x2 + + an xn
be a polynomial with coecients satisfying the conditions:
0 ai a0 ; i = 1; 2; : : : ; n:
Let b0; b1 ; : : : ; b2n be the coecients of the polynomial
f (x) 2 = (a0 + a1 x + a2 x2 + + an xn )2
,
PROBLEM 4
Let n be a xed positive integer. To any choice of n real numbers satisfying
0 xi 1; i = 1; 2; : : : ; n;
{1{
PAGE 2 1974
there corresponds the sum
() X
jxi , xj j
1i<jn
= jx1 , x2j + jx1 , x3j + jx1 , x4j + + jx1 , xn,1j + jx1 , xn j
+ jx2 , x3 j + jx2 , x4 j + + jx2 , xn,1j + jx2 , xn j
+ jx3 , x4 j + + jx3 , xn,1j + jx3 , xn j
+ + jxn,2 , xn,1j + jxn,2 , xn j
+ jxn,1 , xn j:
Let S (n) denote the largest possible value of the sum (). Find S (n).
PROBLEM 5 Y
Given a circle with diameter AB and a point X
on the circle dierent from A and B , let ta , tb and
tx be the tangents to the circle at A, B and X ta tb
respectively. Let Z be the point where line AX
meets tb and Y the point where line BX meets Z
ta . Show that the three lines Y Z , tx and AB are X
either concurrent (i.e., all pass through the same tx
point) or parallel.
PROBLEM 6 A B
An unlimited supply of 8-cent and 15-cent stamps is available. Some amounts of
postage cannot be made up exactly, e.g., 7 cents, 29 cents. What is the largest
unattainable amount, i.e., the amount, say n, of postage which is unattainable
while all amounts larger than n are attainable? (Justify your answer.)
PROBLEM 7
A bus route consists of a circular road of circum-
ference 10 miles and a straight road of length 1 P
mile which runs from a terminus to the point Q
on the circular road (see diagram). It is served by
two buses, each of which requires 20 minutes for
the round trip. Bus No. 1, upon leaving the termi- x
nus, travels along the straight road, once around Q
PROBLEM 3
Two grade seven students were allowed to enter a chess tournament otherwise com-
posed of grade eight students. Each contestant played once with each other con-
testant and received one point for a win, one half point for a tie and zero for a
loss. The two grade seven students together gained a total of eight points and each
grade eight student scored the same number of points as his classmates. How many
students from grade eight participated in the chess tournament? Is the solution
unique?
PROBLEM 4
Let AB be a diameter of a circle, C be any xed point between A and B on this
diameter, and Q be a variable point on the circumference of the circle. Let P be
the point on the line determined by Q and C for which CB AC = QC . Describe, with
CP
proof, the locus of the point P .
PROBLEM 5
Prove that a positive integer is a sum of at least two consecutive positive integers
if and only if it is not a power of two.
PROBLEM 6
If A, B , C , D are four points in space, such that
6 ABC = 6 BCD = 6 CDA = 6 DAB = =2;
PROBLEM 3
N is an integer whose representation in base b is 777. Find the smallest positive
integer b for which N is the fourth power of an integer.
PROBLEM 4
Let
p(x) = an xn + an,1 xn,1 + + a1 x + a0
and
q(x) = bm xm + bm,1 xm,1 + + b1 x + b0
be two polynomials with integer coecients. Suppose that all the coecients of
the product p(x) q(x) are even but not all of them are divisible by 4. Show that
one of p(x) and q(x) has all even coecients and the other has at least one odd
coecient.
PROBLEM 5
A right circular cone of base radius 1 cm and slant height 3 cm is given. P is a
point on the circumference of the base and the shortest path from P around the
cone and back to P is drawn (see diagram). What is the minimum distance from
{1{
PAGE 2 1977
the vertex V to this path?
V
3 cm
P 1 cm
PROBLEM 6
Let 0 < u < 1 and dene
u1 = 1 + u; u2 = u1 + u; : : : ; un+1 = u1 + u; n 1:
1 n
Show that un > 1 for all values of n = 1; 2; 3; : : : .
PROBLEM 7
A rectangular city is exactly m blocks long and n blocks wide (see diagram). A
woman lives in the southwest corner of the city and works in the northeast corner.
She walks to work each day but, on any given trip, she makes sure that her path
does not include any intersection twice. Show that the number f (m; n) of dierent
paths she can take to work satises f (m; n) 2mn .
9
>>
>=
>> n blocks
>;
| {z }
m blocks
Canadian Mathematical Olympiad
1978
PROBLEM 1
Let n be an integer. If the tens digit of n2 is 7, what is the units digit of n2 ?
PROBLEM 2
Find all pairs a, b of positive integers satisfying the equation 2a2 = 3b3.
PROBLEM 3
Determine the largest real number z such that
x+y+z = 5
xy + yz + xz = 3
and x, y are also real.
PROBLEM 4
The sides AD and BC of a convex quadrilateral ABCD are extended to meet at
E . Let H and G be the midpoints of BD and AC , respectively. Find the ratio of
the area of the triangle EHG to that of the quadrilateral ABCD.
PROBLEM 5
Eve and Odette play a game on a 3 3 checkerboard, with black checkers and white
checkers. The rules are as follows:
I. They play alternately.
II. A turn consists of placing one checker on an unoccupied square of the board.
III. In her turn, a player may select either a white checker or a black checker and
need not always use the same colour.
IV. When the board is full, Eve obtains one point for every row, column or diagonal
that has an even number of black checkers, and Odette obtains one point for
every row, column or diagonal that has an odd number of black checkers.
V. The player obtaining at least ve of the eight points WINS.
(a) Is a 4{4 tie possible? Explain.
(b) Describe a winning strategy for the girl who is rst to play.
PROBLEM 6
Sketch the graph of x3 + xy + y3 = 3.
{1{
Canadian Mathematical Olympiad
1979
PROBLEM 1
Given: (i) a; b > 0; (ii) a, A1, A2, b is an arithmetic progression; (iii) a, G1, G2, b
is a geometric progression. Show that
A1A2 G1G2
PROBLEM 2
It is known in Euclidean geometry that the sum of the angles of a triangle is
constant. Prove, however, that the sum of the dihedral angles of a tetrahedron is
not constant.
PROBLEM 3
Let a, b, c, d, e be integers such that 1 a < b < c < d < e. Prove that
1 1 1 1 15
[a; b] + [b; c] + [c; d] + [d; e] 16 ;
where [m; n] denotes the least common multiple of m and n (e.g. [4; 6] = 12).
PROBLEM 4
A dog standing at the centre of a circular arena sees a rabbit at the wall. The
rabbit runs around the wall and the dog pursues it along a unique path which is
determined by running at the same speed and staying on the radial line joining the
centre of the arena to the rabbit. Show that the dog overtakes the rabbit just as it
reaches a point one-quarter of the way around the arena.
PROBLEM 5
A walk consists of a sequence of steps of length 1 taken in directions north, south,
east or west. A walk is self-avoiding if it never passes through the same point twice.
Let f (n) denote the number of n-step self-avoiding walks which begin at the origin.
Compute f (1), f (2), f (3), f (4), and show that
2n < f (n) 4 3n,1:
{1{
Canadian Mathematical Olympiad
1980
PROBLEM 1
If a679b is a ve digit number (in base 10) which is divisible by 72, determine a
and b.
PROBLEM 2
The numbers from 1 to 50 are printed on cards. The cards are shued and then laid
out face up in 5 rows of 10 cards each. The cards in each row are rearranged to make
them increase from left to right. The cards in each column are then rearranged to
make them increase from top to bottom. In the nal arrangement, do the cards in
the rows still increase from left to right?
PROBLEM 3
Among all triangles having (i) a xed angle A and (ii) an inscribed circle of xed
radius r, determine which triangle has the least perimeter.
PROBLEM 4
A gambling student tosses a fair coin and scores one point for each head that turns
up and two points for each tail. Prove that the probability of the student scoring
exactly n points is 13 [2 + (, 21 )n ].
PROBLEM 5
A parallelepiped has the property that all cross sections which are parallel to any
xed face F , have the same perimeter as F . Determine whether or not any other
polyhedron has this property.
{1{
Canadian Mathematical Olympiad
1981
PROBLEM 1
For any real number t, denote by [t] the greatest integer which is less than or equal
to t. For example: [8] = 8, [] = 3 and [,5=2] = ,3. Show that the equation
[x] + [2x] + [4x] + [8x] + [16x] + [32x] = 12345
has no real solution.
PROBLEM 2
Given a circle of radius r and a tangent line ` to the circle through a given point P
on the circle. From a variable point R on the circle, a perpendicular RQ is drawn
to ` with Q on `. Determine the maximum of the area of triangle P QR.
PROBLEM 3
Given a nite collection of lines in a plane P , show that it is possible to draw an
arbitrarily large circle in P which does not meet any of them. On the other hand,
show that it is possible to arrange an innite sequence of lines (rst line, second
line, third line, etc.) in P so that every circle in P meets at least one of the lines.
(A point is not considered to be a circle.)
PROBLEM 4 , ,
P (x) and Q(x) are two polynomials that satisfy the identity P Q(x) Q P (x)
for real numbers , x. If the ,equation
P (x) = Q(x) has no real solution, show that
the equation P P (x) = Q Q(x) also has no real solution.
PROBLEM 5
Eleven theatrical groups participated in a festival. Each day, some of the groups
were scheduled to perform while the remaining groups joined the general audience.
At the conclusion of the festival, each group had seen, during its days o, at least
one performance of every other group. At least how many days did the festival
last?
{1{
Canadian Mathematical Olympiad
1982
PROBLEM 1
In the diagram, OBi is parallel and equal in length to AiAi+1 for i = 1; 2; 3 and
4(A5 = A1). Show that the area of B1 B2 B3 B4 is twice that of A1 A2A3A4 .
B1
B2 A3
A4 A2
O
B3
B4
A1
PROBLEM 2
If a, b and c are the roots of the equation x3 , x2 , x , 1 = 0,
(i) show that a, b and c are distinct:
(ii) show that
a1982 , b1982 + b1982 , c1982 + c1982 , a1982
a,b b,c c,a
is an integer.
PROBLEM 3
Let Rn be the n-dimensional Euclidean space. Determine the smallest number g(n)
of points of a set in Rn such that every point in Rn is at irrational distance from
at least one point in that set.
PROBLEM 4
Let p be a permutation of the set Sn = f1; 2; : : : ; ng. An element j 2 Sn is called a
xed point of p if p(j ) = j . Let fn be the number of permutations having no xed
points, and gn be the number with exactly one xed point. Show that jfn , gn j = 1.
PROBLEM 5
The altitudes of a tetrahedron ABCD are extended externally to points A , B , 0 0
{1{
PAGE 2 1982
k=hd. Here, k is a constant and ha denotes the length of the altitude of ABCD
from vertex A, etc. Prove that the centroid of the tetrahedron A B C D coincides
0 0 0 0
PROBLEM 2
For each real number let r be the transformation of the plane that takes the
r T
point ( ) into the point (2r 2r + 2r ). Let be the family of all such trans-
x; y x; r x y F
PROBLEM 3
The area of a triangle is determined by the lengths of its sides. Is the volume of a
tetrahedron determined by the areas of its faces?
PROBLEM 4
Prove that for every prime number , there are innitely many positive integers
p n
PROBLEM 5
The geometric mean (G.M.) of a positive numbers 1 2
k k is dened to be
a ;a ;:::;a
the (positive) -th root of their product. For example, the G.M. of 3, 4, 18 is 6.
k
Show that the G.M. of a set of positive numbers is equal to the G.M. of the
S n
{1{
Canadian Mathematical Olympiad
1984
PROBLEM 1
Prove that the sum of the squares of 1984 consecutive positive integers cannot be
the square of an integer.
PROBLEM 2
Alice and Bob are in a hardware store. The store sells coloured sleeves that t over
keys to distinguish them. The following conversation takes place:
Alice: Are you going to cover your keys?
Bob: I would like to, but there are only 7 colours and I have 8 keys.
Alice: Yes, but you could always distinguish a key by noticing that the red key
next to the green key was dierent from the red key next to the blue
key.
Bob: You must be careful what you mean by \next to" or \three keys over
from" since you can turn the key ring over and the keys are arranged
in a circle.
Alice: Even so, you don't need 8 colours.
Problem: What is the smallest number of colours needed to distinguish keys if
n
0 1 +, p1
x y
3
:
xy
{1{
Canadian Mathematical Olympiad
1985
PROBLEM 1
The lengths of the sides of a triangle are 6, 8 and 10 units. Prove that there is
exactly one straight line which simultaneously bisects the area and perimeter of the
triangle.
PROBLEM 2
Prove or disprove that there exists an integer which is doubled when the initial
digit is transferred to the end.
PROBLEM 3
Let P1 and P2 be regular polygons of 1985 sides and perimeters x and y respectively.
Each side of P1 is tangent to a given circle of circumference c and this circle passes
through each vertex of P2 . Prove x + y 2c. (You may assume that tan for
0 < 2 ).
PROBLEM 4
Prove that 2n,1 divides n! if and only if n = 2k,1 for some positive integer k.
PROBLEM 5
Let 1 < x1 <p2 and, for n = 1; 2; : : : , dene xn+1 = 1 + xn , 21 x2n . Prove that, for
n 3, jxn , 2j < 2,n .
{1{
Canadian Mathematical Olympiad
1986
PROBLEM 1
In the diagram line segments AB and CD are of length 1 while angles ABC and
CBD are 90 and 30 respectively. Find AC .
A
90
30
B D
PROBLEM 2
A Mathlon is a competition in which there are M athletic events. Such a competi-
tion was held in which only A, B , and C participated. In each event p1 points were
awarded for rst place, p2 for second and p3 for third, where p1 > p2 > p3 > 0 and
p1 , p2 , p3 are integers. The nal score for A was 22, for B was 9 and for C was also
9. B won the 100 metres. What is the value of M and who was second in the high
jump?
PROBLEM 3
A chord ST of constant length slides around a semicircle with diameter AB . M is
the mid-point of ST and P is the foot of the perpendicular from S to AB . Prove
that angle SPM is constant for all positions of ST .
PROBLEM 4
P
For positive integers n and k, dene F (n; k) = nr=1 r2k,1. Prove that F (n; 1)
divides F (n; k).
PROBLEM 5
Let u1; u2 ; u3 ; : : : be a sequence of integers satisfying the recurrence relation un+2 =
u2n+1 , un . Suppose u1 = 39 and u2 = 45. Prove that 1986 divides innitely many
terms of the sequence.
{1{
Canadian Mathematical Olympiad
1987
PROBLEM 1
Find all solutions of a2 + b2 = n! for positive integers a, b, n with a b and n < 14.
PROBLEM 2
The number 1987 can be written as a three digit number xyz in some base b. If
x + y + z = 1 + 9 + 8 + 7, determine all possible values of x, y, z, b.
PROBLEM 3
Suppose ABCD is a parallelogram and E is a point between B and C on the line
BC . If the triangles DEC , BED and BAD are isosceles what are the possible
values for the angle DAB ?
PROBLEM 4
On a large,
at eld n people are positioned so that for each person the distances to
all the other people are dierent. Each person holds a water pistol and at a given
signal res and hits the person who is closest. When n is odd show that there is at
least one person left dry. Is this always true when n is even?
PROBLEM 5
For every positive integer n show that
p p p p
[ n + n + 1] = [ 4n + 1] = [ 4n + 2] = [ 4n + 3]
p
where [x] is the greatest integer less than or equal to x (for example [2:3] = 2,
[] = 3, [5] = 5).
{1{
Canadian Mathematical Olympiad
1988
PROBLEM 1
For what values of b do the equations: 1988x2 + bx + 8891 = 0 and 8891x2 + bx +
1988 = 0 have a common root?
PROBLEM 2
A house is in the shape of a triangle, perimeter P metres and area A square metres.
The garden consists of all the land within 5 metres of the house. How much land
do the garden and house together occupy?
PROBLEM 3
Suppose that S is a nite set of at least ve points in the plane; some are coloured
red, the others are coloured blue. No subset of three or more similarly coloured
points is collinear. Show that there is a triangle
(i) whose vertices are all the same colour, and
(ii) at least one side of the triangle does not contain a point of the opposite colour.
PROBLEM 4
Let xn+1 = 4xn , xn,1, x0 = 0, x1 = 1, and yn+1 = 4yn , yn,1 , y0 = 1, y1 = 2.
Show for all n 0 that yn2 = 3x2n + 1.
PROBLEM 5
Let S = fa1; a2 ; : : : ; ar g denote a sequence of integers. For each non-empty subse-
quence A of S , we dene p(A) to be the product of all the integers in A. Let m(S )
be the arithmetic average of p(A) over all non-empty subsets A of S . If m(S ) = 13
and if m(S [ far+1 g) = 49 for some positive integer ar+1 , determine the values of
a1 ; a2 ; : : : ; ar and ar+1 .
{1{
Canadian Mathematical Olympiad
1989
PROBLEM 1
The integers 1; 2; : : : ; n are placed in order so that each value is either strictly bigger
than all the preceding values or is strictly smaller than all preceding values. In how
many ways can this be done?
PROBLEM 2
Let ABC be a right angled triangle of area 1. Let A0B 0C 0 be the points obtained by
re
ecting A, B , C respectively, in their opposite sides. Find the area of A0B 0C 0.
4
PROBLEM 3
Dene an n=1 as follows: a1 = 19891989; an , n > 1, is the sum of the digits of
f g
{1{
Canadian Mathematical Olympiad
1990
PROBLEM 1
A competition involving n 2 players was held over k days. On each day, the
players received scores of 1; 2; 3; : : : ; n points with no two players receiving the
same score. At the end of the k days, it was found that each player had exactly
26 points in total. Determine all pairs (n; k) for which this is possible.
PROBLEM 2
A set of 12 n(n + 1) distinct numbers is arranged at random in a triangular array:
.. .. ..
. . .
Let Mk be the largest number in the k-th row from the top. Find the probability
that
M1 < M2 < M3 < < Mn :
PROBLEM 3
Let ABCD be a convex quadrilateral inscribed in a circle, and let diagonals AC
and BD meet at X . The perpendiculars from X meet the sides AB , BC , CD, DA
at A , B , C , D respectively. Prove that
0 0 0 0
jA B j + jC D j = jA D j + jB C j:
0 0 0 0 0 0 0 0
PROBLEM 4
A particle can travel at speeds up to 2 metres per second along the x-axis, and up
to 1 metre per second elsewhere in the plane. Provide a labelled sketch of the region
which can be reached within one second by the particle starting at the origin.
PROBLEM 5
Suppose that a function f dened on the positive integers satises
,
f (1) = 1; f (2),= 2;
f (n + 2) = f n + 2 , f (n + 1) + f n + 1 , f (n) (n 1):
(a) Show that
(i) 0 f (n + 1) , f (n) 1
(ii) if f (n) is odd, then f (n + 1) = f (n) + 1.
(b) Determine, with justication, all values of n for which
f (n) = 210 + 1:
{1{
Canadian Mathematical Olympiad
1991
PROBLEM 1
Show that the equation 2 + 5 = 3 has innitely many solutions in integers , ,
x y z x y
following property: In base 2, it has exactly 2 digits consisting of 1's and 0's.
n n n
intersects determines a chord of . Show that the midpoints of these chords lie
C C
on a circle.
PROBLEM 4
Ten distinct numbers from the set f0 1 2; ; 13 14g are to be chosen to ll in the
;:::; ;
ten circles in the diagram. The absolute values of the dierences of the two numbers
joined by each segment must be dierent from the values for all other segments. Is
it possible to do this? Justify your answer.
PROBLEM 5
In the gure, the side length of the large equilateral triangle is 3 and (3), the
f
number of parallelograms bounded by sides in the grid, is 15. For the general
analogous situation, nd a formula for ( ), the number of parallelograms, for a
f n
{1{
Canadian Mathematical Olympiad
1992
PROBLEM 1
Prove that the product of the rst n natural numbers is divisible by the sum of the
rst n natural numbers if and only if n + 1 is not an odd prime.
PROBLEM 2
For x; y; z 0, establish the inequality
x(x , z)2 + y(y , z)2 (x , z)(y , z)(x + y , z)
and determine when equality holds.
PROBLEM 3
In the diagram, ABCD is a square, with U and V interior points of the sides AB
and CD respectively. Determine all the possible ways of selecting U and V so as
to maximize the area of the quadrilateral PUQV .
A D
P
U
V
Q
B C
PROBLEM 4
Solve the equation
x2 + x2 = 3:
(x + 1)2
PROBLEM 5
A deck of 2n + 1 cards consists of a joker and, for each number between 1 and
n inclusive, two cards marked with that number. The 2n + 1 cards are placed in
a row, with the joker in the middle. For each k with 1 k n, the two cards
numbered k have exactly k , 1 cards between them. Determine all the values of n
not exceeding 10 for which this arrangement is possible. For which values of n is it
impossible?
{1{
Canadian Mathematical Olympiad
1993
PROBLEM 1
Determine a triangle for which the three sides and an altitude are four consecutive
integers and for which this altitude partitions the triangle into two right triangles
with integer sides. Show that there is only one such triangle.
PROBLEM 2
Show that the number x is rational if and only if three distinct terms that form a
geometric progression can be chosen from the sequence
x; x + 1; x + 2; x + 3; : : :
PROBLEM 3
In triangle ABC , the medians to the sides AB and AC are perpendicular. Prove
that cot B + cot C 23 .
PROBLEM 4
A number of schools took part in a tennis tournament. No two players from the same
school played against each other. Every two players from dierent schools played
exactly one match against each other. A match between two boys or between two
girls was called a single and that between a boy and a girl was called a mixed single.
The total number of boys diered from the total number of girls by at most 1. The
total number of singles diered from the total number of mixed singles by at most
1. At most how many schools were represented by an odd number of players?
PROBLEM 5
Let y1; y2 ; y3 ; : : : be a sequence such that y1 = 1 and, for k > 0, is dened by the
relationship:
y2k = 22yykk + 1 ifif kk isis even
odd
y2k+1 = 22yykk + 1 ifif kk isis odd
even
Show that the sequence y1 ; y2 ; y3 ; : : : takes on every positive integer value exactly
once.
{1{
Canadian Mathematical Olympiad
1994
PROBLEM 1
Evaluate the sum
X(,1) n + n + 1 :
1994
n
2
n=1
n!
PROBLEM 2 p
Show that every positive integralppower of 2 , 1pis of pthe form
pm , pm , 1 for
p
some positive integer m. (e.g. ( 2 , 1)2 = 3 , 2 2 = 9 , 8).
PROBLEM 3
Twenty-ve men sit around a circular table. Every hour there is a vote, and each
must respond yes or no. Each man behaves as follows: on the nth vote, if his
response is the same as the response of at least one of the two people he sits
between, then he will respond the same way on the (n + 1)th vote as on the nth
vote; but if his response is dierent from that of both his neighbours on the n-th
vote, then his response on the (n + 1)-th vote will be dierent from his response
on the nth vote. Prove that, however everybody responded on the rst vote, there
will be a time after which nobody's response will ever change.
PROBLEM 4
Let AB be a diameter of a circle
and P be any point not on the line through A
and B . Suppose the line through P and A cuts
again in U , and the line through
P and B cuts
again in V . (Note that in case of tangency U may coincide with
A or V may coincide with B . Also, if P is on
then P = U = V .) Suppose
that jPU j = sjPAj and jPV j = tjPB j for some nonnegative real numbers s and t.
Determine the cosine of the angle APB in terms of s and t.
PROBLEM 5
Let ABC be an acute angled triangle. Let AD be the altitude on BC , and let H
be any interior point on AD. Lines BH and CH , when extended, intersect AC
and AB at E and F , respectively. Prove that EDH = FDH .
6 6
{1{
Canadian Mathematical Olympiad
1995
PROBLEM 1
Let ( ) = 9x9+3
f x
x
. Evaluate the sum
1 ) + ( 2 ) + ( 3 ) + + ( 1995 )
( 1996
f
1996f
1996 f
1996 f
PROBLEM 2
Let , , and be positive real numbers. Prove that
a b c
a b c
a b c ( ) a+3b+c
abc :
PROBLEM 3
Dene a boomerang as a quadrilateral whose op-
posite sides do not intersect and one of whose in-
ternal angles is greater than 180 degrees. (See
Figure displayed.) Let be a convex polygon
C
PROBLEM 4
Let be a xed positive integer. Show that for only nonnegative integers , the
n k
diophantine equation
3 + 3 + + 3 = 3k+2
1 2 x x n x y
PROBLEM 5
Suppose that is a real parameter with 0
u 1. Dene
< u <
(
0 if 0
( ) = 1 , p + p(1 , )(1 , )2 if 1
x u
f x
ux u x u x
PROBLEM 2
Find all real solutions to the following system of equations. Carefully justify your
answer. 8 4x2
>>
>< 1 +4y42x2 = y
>> 1 + 42y2 = z
>: 4z = x
1 + 4z 2
PROBLEM 3
We denote an arbitrary permutation of the integers 1; : : : ; n by a1 ; : : : ; an . Let f (n)
be the number of these permutations such that
(i) a1 = 1;
(ii) jai , ai+1 j 2; i = 1; : : : ; n , 1.
Determine whether f (1996) is divisible by 3.
PROBLEM 4
Let 4ABC be an isosceles triangle with AB = AC . Suppose that the angle bisector
of B meets AC at D and that BC = BD + AD. Determine A.
6 6
PROBLEM 5
Letm r1 ; r2 ; : : : ; rm be a given set of m positive rational
P Pm [r numbers such that
r
k=1 k = 1. Dene the function f by f ( n ) = n , k=1 k n ] for each positive
integer n. Determine the minimum and maximum values of f (n). Here [x] denotes
the greatest integer less than or equal to x
{1{
Canadian Mathematical Olympiad
1997
PROBLEM 1
How many pairs of positive integers x; y are there, with x y, and such that
gcd(x; y) = 5! and lcd(x; y) = 50!.
NOTE. gcd(x; y) denotes the greatest common divisor of x and y, lcd(x; y) denotes
the least common multiple of x and y, and n! = n (n , 1) 2 1.
PROBLEM 2
The closed interval A = [0; 50] is the union of a nite number of closed intervals,
each of length 1. Prove that some of the intervals can be removed so that those
remaining are mutually disjoint and have total length 25.
NOTE. For a b, the closed interval [a; b] := fx 2 R : a x bg has length b , a;
disjoint intervals have empty intersection.
PROBLEM 3
Prove that
1 1 3 5 1997 1
1999 < 2 4 6 1998 < 44 :
PROBLEM 4
The point O is situated inside the parallelogram ABCD so that
6 AOB + 6 COD = 180:
Prove that 6 OBC = 6 ODC .
PROBLEM 5
Write the sum
,
n
X (,1)k nk
k=0
k3 + 9k2 + 26k + 24
in the form p(n)
q(n) , where p and q are polynomials with integer coecients.
{1{
THE 1998 CANADIAN MATHEMATICAL
OLYMPIAD
Here, if x is a real number, then [ x ] denotes the greatest integer that is less than or
equal to x.
4. Let ABC be a triangle with ∠BAC = 40◦ and ∠ABC = 60◦ . Let D and E be
the points lying on the sides AC and AB, respectively, such that ∠CBD = 40◦ and
∠BCE = 70◦ . Let F be the point of intersection of the lines BD and CE. Show that
the line AF is perpendicular to the line BC.
a2 + b2
= m2
ab + 1
if and only if (a, b) is of the form (an , an+1 ) for some n ≥ 0.
THE 1999 CANADIAN MATHEMATICAL
OLYMPIAD
3. Determine all positive integers n with the property that n = (d(n))2 . Here d(n)
denotes the number of positive divisors of n.
4. Suppose a1 , a2 , . . . , a8 are eight distinct integers from {1, 2, . . . , 16, 17}. Show
that there is an integer k > 0 such that the equation ai − aj = k has at least
three different solutions. Also, find a specific set of 7 distinct integers from
{1, 2, . . . , 16, 17} such that the equation ai − aj = k does not have three distinct
solutions for any k > 0.
1. At 12:00 noon, Anne, Beth and Carmen begin running laps around a circular
track of length three hundred meters, all starting from the same point on the
track. Each jogger maintains a constant speed in one of the two possible di-
rections for an indefinite period of time. Show that if Anne’s speed is different
from the other two speeds, then at some later time Anne will be at least one
hundred meters from each of the other runners. (Here, distance is measured
along the shorter of the two arcs separating two runners.)
s1 = a1 , s2 = a1 + a2 , s3 = a1 + a2 + a3 , . . . , s100 = a1 + a2 + · · · + a100 .
How many of these permutations will have no terms of the sequence s1 , . . . , s100
divisible by three?
6 CBD = 26 ADB,
6 ABD = 26 CDB
and AB = CB.
a1 ≥ a2 ≥ · · · ≥ a100 ≥ 0,
a1 + a2 ≤ 100
and a3 + a4 + · · · + a100 ≤ 100.
Determine the maximum possible value of a21 + a22 + · · · + a2100 , and find all
possible sequences a1 , a2 , . . . , a100 which achieve this maximum.
THE 2001 CANADIAN MATHEMATICAL OLYMPIAD
1. Randy: “Hi Rachel, that’s an interesting quadratic equation you have written down. What
are its roots?”
Rachel: “The roots are two positive integers. One of the roots is my age, and the other root
is the age of my younger brother, Jimmy.”
Randy: “That is very neat! Let me see if I can figure out how old you and Jimmy are. That
shouldn’t be too difficult since all of your coefficients are integers. By the way, I notice that
the sum of the three coefficients is a prime number.”
Rachel: “Interesting. Now figure out how old I am.”
Randy: “Instead, I will guess your age and substitute it for x in your quadratic equation
. . . darn, that gives me −55, and not 0.”
Rachel: “Oh, leave me alone!”
(a) Prove that Jimmy is two years old.
(b) Determine Rachel’s age.
2. There is a board numbered −10 to 10 as shown. Each square is coloured either red or white,
and the sum of the numbers on the red squares is n. Maureen starts with a token on the square
labeled 0. She then tosses a fair coin ten times. Every time she flips heads, she moves the token
one square to the right. Every time she flips tails, she moves the token one square to the left.
At the end of the ten flips, the probability that the token finishes on a red square is a rational
number of the form ab . Given that a + b = 2001, determine the largest possible value for n.
-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
3. Let ABC be a triangle with AC > AB. Let P be the intersection point of the perpen-
dicular bisector of BC and the internal angle bisector of 6 A. Construct points X on AB
(extended) and Y on AC such that P X is perpendicular to AB and P Y is perpendicular
to AC. Let Z be the intersection point of XY and BC. Determine the value of BZ/ZC.
C
M
P
A X
B
4. Let n be a positive integer. Nancy is given a rectangular table in which each entry is a positive
integer. She is permitted to make either of the following two moves:
(a) select a row and multiply each entry in this row by n.
(b) select a column and subtract n from each entry in this column.
Find all possible values of n for which the following statement is true:
Given any rectangular table, it is possible for Nancy to perform a finite sequence of
moves to create a table in which each entry is 0.
1. Let S be a subset of {1, 2, . . . , 9}, such that the sums formed by adding each unordered pair of
distinct numbers from S are all different. For example, the subset {1, 2, 3, 5} has this property,
but {1, 2, 3, 4, 5} does not, since the pairs {1, 4} and {2, 3} have the same sum, namely 5.
What is the maximum number of elements that S can contain?
2. Call a positive integer n practical if every positive integer less than or equal to n can be
written as the sum of distinct divisors of n.
For example, the divisors of 6 are 1, 2, 3, and 6. Since
1=1, 2=2, 3=3, 4=1+3, 5=2+ 3, 6=6,
we see that 6 is practical.
Prove that the product of two practical numbers is also practical.
a3 b3 c3
+ + ≥ a + b + c,
bc ca ab
and determine when equality occurs.
√
4. Let Γ be a circle with radius r. Let A and B be distinct points on Γ such that AB < 3r.
Let the circle with centre B and radius AB meet Γ again at C. Let P be the point inside Γ
such that triangle ABP is equilateral. Finally, let the line CP meet Γ again at Q.
Prove that P Q = r.
1. Consider a standard twelve-hour clock whose hour and minute hands move continu-
ously. Let m be an integer, with 1 ≤ m ≤ 720. At precisely m minutes after 12:00, the
angle made by the hour hand and minute hand is exactly 1◦ . Determine all possible
values of m.
2001
2. Find the last three digits of the number 20032002 .
x3 + y 3 + z 3 = x + y + z, and
x2 + y 2 + z 2 = xyz.
4. Prove that when three circles share the same chord AB, every line through A different
from AB determines the same ratio XY : Y Z, where X is an arbitrary point different
from B on the first circle while Y and Z are the points where AX intersects the other
two circles (labelled so that Y is between X and Z).
l
A
X
Y
Z
5. Let S be a set of n points in the plane such that any two points of S are at least 1
is a subset T of S with at least n/7 points such that any two
unit apart. Prove there √
points of T are at least 3 units apart.
36th Canadian Mathematical Olympiad
Wednesday, March 31, 2004
1. Find all ordered triples (x, y, z) of real numbers which satisfy the following system of
equations:
xy = z − x − y
xz = y − x − z
yz = x − y − z
5. Let T be the set of all positive integer divisors of 2004100 . What is the largest possible
number of elements that a subset S of T can have if no element of S is an integer
multiple of any other element of S?
37th Canadian Mathematical Olympiad
Wednesday, March 30, 2005
1. Consider an equilateral triangle of side length n, which is divided into unit triangles, as shown. Let
f (n) be the number of paths from the triangle in the top row to the middle triangle in the bottom
row, such that adjacent triangles in our path share a common edge and the path never travels up
(from a lower row to a higher row) or revisits a triangle. An example of one such path is illustrated
below for n = 5. Determine the value of f (2005).
a) Show that there are three distinct points a, b, c ∈ S and three distinct points A, B, C on the
circle such that a is (strictly) closer to A than any other point in S, b is closer to B than any
other point in S and c is closer to C than any other point in S.
b) Show that for no value of n can four such points in S (and corresponding points on the circle)
be guaranteed.
4. Let ABC be a triangle with circumradius R, perimeter P and area K. Determine the maximum
value of KP/R3 .
5. Let’s say that an ordered triple of positive integers (a, b, c) is n-powerful if a ≤ b ≤ c, gcd(a, b, c) = 1,
and an + bn + cn is divisible by a + b + c. For example, (1, 2, 2) is 5-powerful.
a) Determine all ordered triples (if any) which are n-powerful for all n ≥ 1.
b) Determine all ordered triples (if any) which are 2004-powerful and 2005-powerful, but not 2007-
powerful.
1. Let f (n; k ) be the number of ways of distributing k candies to n children so that each child receives at
most 2 candies. For example, if n = 3, then f (3; 7) = 0, f (3; 6) = 1 and f (3; 4) = 6.
E is on AC and both F and G are on BC . Describe the locus of (i.e., the curve occupied by) the
intersections of the diagonals of all possible rectangles DE F G.
3. In a rectangular array of nonnegative real numbers with m rows and n columns, each row and each
column contains at least one positive element. Moreover, if a row and a column intersect in a positive
element, then the sums of their elements are the same. Prove that m = n.
4. Consider a round-robin tournament with 2n + 1 teams, where each team plays each other team exactly
once. We say that three teams X, Y and Z, form a cycle triplet if X beats Y , Y beats Z, and Z
5. The vertices of a right triangle ABC inscribed in a circle divide the circumference into three arcs.
The right angle is at A, so that the opposite arc BC is a semicircle while arc AB and arc AC are
supplementary. To each of the three arcs, we draw a tangent such that its point of tangency is the
midpoint of that portion of the tangent intercepted by the extended lines AB and AC . More precisely,
the point D on arc BC is the midpoint of the segment joining the points D
0
and D
00
where the tangent
at D intersects the extended lines AB and AC . Similarly for E on arc AC and F on arc AB .
1. What is the maximum number of non-overlapping 2 × 1 dominoes that can be placed on a 8 × 9 checkerboard if six of
them are placed as shown? Each domino must be placed horizontally or vertically so as to cover two adjacent squares of
the board.
111
000
111
000
111
000
111
000
f (xy) + f (y − x) ≥ f (y + x)
1. ABCD is a convex quadrilateral for which AB is the longest side. Points M and N are located on
sides AB and BC respectively, so that each of the segments AN and CM divides the quadrilateral
into two parts of equal area. Prove that the segment M N bisects the diagonal BD.
2. Determine all functions f defined on the set of rational numbers that take rational values for which
4. Determine all functions f defined on the natural numbers that take values among the natural numbers
for which
(f (n))p ≡ n mod f (p)
for all n ∈ N and all prime numbers p.
5. A self-avoiding rook walk on a chessboard (a rectangular grid of unit squares) is a path traced by
a sequence of moves parallel to an edge of the board from one unit square to another, such that
each begins where the previous move ended and such that no move ever crosses a square that has
previously been crossed, i.e., the rook’s path is non-self-intersecting.
Let R(m, n) be the number of self-avoiding rook walks on an m × n (m rows, n columns) chessboard
which begin at the lower-left corner and end at the upper-left corner. For example, R(m, 1) = 1 for
all natural numbers m; R(2, 2) = 2; R(3, 2) = 4; R(3, 3) = 11. Find a formula for R(3, n) for each
natural number n.
41st Canadian Mathematical Olympiad
Wednesday, March 25, 2009
Problem 1. Given an m × n grid with squares coloured either black or white, we say
that a black square in the grid is stranded if there is some square to its left in the same
row that is white and there is some square above it in the same column that is white (see
Figure 1.).
Find a closed formula for the number of 2 × n grids with no stranded black squares.
Problem 2. Two circles of different radii are cut out of cardboard. Each circle is subdi-
vided into 200 equal sectors. On each circle 100 sectors are painted white and the other
100 are painted black. The smaller circle is then placed on top of the larger circle, so that
their centers coincide. Show that one can rotate the small circle so that the sectors on
the two circles line up and at least 100 sectors on the small circle lie over sectors of the
same color on the big circle.
Problem 3. Define
(xy + yz + zx)(x + y + z)
f (x, y, z) = .
(x + y)(x + z)(y + z)
Determine the set of real numbers r for which there exists a triplet (x, y, z) of positive
real numbers satisfying f (x, y, z) = r.
Problem 4. Find all ordered pairs (a, b) such that a and b are integers and 3a + 7b is a
perfect square.
Problem 5. A set of points is marked on the plane, with the property that any three
marked points can be covered with a disk of radius 1. Prove that the set of all marked
points can be covered with a disk of radius 1.
42nd Canadian Mathematical Olympiad
Wednesday, March 24, 2010
(1) For a positive integer n, an n-staircase is a figure consisting of unit squares, with one
square in the first row, two squares in the second row, and so on, up to n squares in
the nth row, such that all the left-most squares in each row are aligned vertically. For
example, the 5-staircase is shown below.
Let f (n) denote the minimum number of square tiles required to tile the n-staircase,
where the side lengths of the square tiles can be any positive integer. For example,
f (2) = 3 and f (4) = 7.
1
neighbours. Is it possible to change the colour of every vertex from black to white by a
sequence of operations of this type?
(A finite graph consists of a finite set of vertices and a finite set of edges between
vertices. If there is an edge between vertex A and vertex B, then B is called a neighbour
of A.)
(5) Let P (x) and Q(x) be polynomials with integer coefficients. Let an = n! + n. Show that
if P (an )/Q(an ) is an integer for every n, then P (n)/Q(n) is an integer for every integer
n such that Q(n) 6= 0.
2
43rd Canadian Mathematical Olympiad
Wednesday, March 23, 2011
(1) Consider 70-digit numbers n, with the property that each of the digits 1, 2, 3, . . . , 7
appears in the decimal expansion of n ten times (and 8, 9, and 0 do not appear).
Show that no number of this form can divide another number of this form.
(2) Let ABCD be a cyclic quadrilateral whose opposite sides are not parallel, X the
intersection of AB and CD, and Y the intersection of AD and BC. Let the
angle bisector of ∠AXD intersect AD, BC at E, F respectively and let the angle
bisector of ∠AY B intersect AB, CD at G, H respectively. Prove that EGF H is
a parallelogram.
(3) Amy has divided a square up into finitely many white and red rectangles, each
with sides parallel to the sides of the square. Within each white rectangle, she
writes down its width divided by its height. Within each red rectangle, she writes
down its height divided by its width. Finally, she calculates x, the sum of these
numbers. If the total area of the white rectangles equals the total area of the red
rectangles, what is the smallest possible value of x?
(4) Show that there exists a positive integer N such that for all integers a > N , there
exists a contiguous substring of the decimal expansion of a that is divisible by 2011.
(For instance, if a = 153204, then 15, 532, and 0 are all contiguous substrings of
a. Note that 0 is divisible by 2011.)
(5) Let d be a positive integer. Show that for every integer S, there exists an integer
n > 0 and a sequence ²1 , ²2 , . . . , ²n , where for any k, ²k = 1 or ²k = −1, such that
S = ²1 (1 + d)2 + ²2 (1 + 2d)2 + ²3 (1 + 3d)2 + · · · + ²n (1 + nd)2 .
1
44th CANADIAN MATHEMATICAL OLYMPIAD
44ème OLYMPIADE MATHÉMATIQUE DU CANADA
2. For any positive integers and , let , be the least common multiple of the consecutive integers
, 1, …., 1. Show that for any integer , there exist integers and such that
, 1, .
3. Let be a convex quadrilateral and let be the point of intersection of and . Suppose that
. Prove that the internal angle bisectors of , , and meet at a common point.
4. A number of robots are placed on the squares of a finite, rectangular grid of squares. A square can hold any number of
robots. Every edge of the grid is classified as either passable or impassable. All edges on the boundary of the grid are
impassable.
You can give any of the commands up, down, left, or right. All of the robots then simultaneously try to move in the
specified direction. If the edge adjacent to a robot in that direction is passable, the robot moves across the edge and
into the next square. Otherwise, the robot remains on its current square. You can then give another command of up,
down, left, or right, then another, for as long as you want.
Suppose that for any individual robot, and any square on the grid, there is a finite sequence of commands that will
move that robot to that square. Prove that you can also give a finite sequence of commands such that all of the robots
end up on the same square at the same time.
Un certain nombre de robots sont placés sur les carrés composant une grille rectangulaire de dimension finie. Chaque
carré peut contenir un nombre quelconque de robots. Les bords des carrés de la grille sont classés comme
franchissable ou infranchissable. Les côtés qui forment le pourtour de la grille sont infranchissables.
Vous pouvez donner n’importe laquelle des commandes suivantes : en haut, en bas, à gauche ou à droite. Tous les
robots tentent alors de se déplacer simultanément dans la direction précisée. Si le bord adjacent au carré vers lequel se
déplace un robot est franchissable, le robot le franchit et se place dans le carré suivant. Sinon, le robot reste dans le
carré où il se trouve. Vous pouvez ensuite lancer une autre commande de déplacement vers le haut, le bas, la gauche
ou la droite, et encore une autre, aussi longtemps que vous le désirez.
Supposons que pour chaque robot, et ce, pour n’importe quel carré, il existe une suite finie de commandes qui
amèneront ce robot au carré donné. Démontrez que vous pouvez aussi lancer une suite finie de commandes de sorte
que tous les robots finiront par se retrouver simultanément dans le même carré.
44th CANADIAN MATHEMATICAL OLYMPIAD
44ème OLYMPIADE MATHÉMATIQUE DU CANADA
5. A bookshelf contains n volumes, labelled 1 to in some order. The librarian wishes to put them in the correct order as
follows. The librarian selects a volume that is too far to the right, say the volume with label , takes it out, and inserts
it so that it is in the -th place. For example, if the bookshelf contains the volumes 1, 3, 2, 4 in that order, the
librarian could take out volume 2 and place it in the second position. The books will then be in the correct order
1, 2, 3, 4.
(a) Show that if this process is repeated, then, however the librarian makes the selections, all the volumes will
eventually be in the correct order.
(b) What is the largest number of steps that this process can take?
Une étagère contient n volumes étiquetés de 1 à , rangés dans un certain ordre. Le bibliothécaire souhaite les mettre
dans le bon ordre de la façon suivante : il choisit un volume qui se trouve trop à droite, par exemple le volume étiqueté
, le retire de son emplacement et l’insère à la –ième place. Par exemple, si les volumes sont rangés dans l’ordre
1, 3, 2, 4, le bibliothécaire peut prendre le volume 2 et le mettre à la deuxième place. Les livres sont alors rangés dans
le bon ordre, soit 1, 2, 3, 4.
a) Démontrez que si l’on répète ce processus, tous les volumes finiront par être dans le bon ordre, et ce, qu’elle que
soit la manière dont le bibliothécaire les range.
b) Quel est le plus grand nombre d’étapes que peut exiger un tel processus?
45th Canadian Mathematical Olympiad
Wednesday, March 27, 2013
1. Let a1 , a2 , . . . , an be positive real numbers whose product is 1. Show that the sum
a1 a2 a3 an
+ + +· · ·+
1 + a1 (1 + a1 )(1 + a2 ) (1 + a1 )(1 + a2 )(1 + a3 ) (1 + a1 )(1 + a2 ) · · · (1 + an )
n
2 −1
is greater than or equal to .
2n
2. Let m and n be odd positive integers. Each square of an m by n board is coloured
red or blue. A row is said to be red-dominated if there are more red squares than
blue squares in the row. A column is said to be blue-dominated if there are more
blue squares than red squares in the column. Determine the maximum possible value
of the number of red-dominated rows plus the number of blue-dominated columns.
Express your answer in terms of m and n.
3. Let p be a fixed odd prime. A p-tuple (a1 , a2 , a3 , . . . , ap ) of integers is said to be
good if
(i) 0 ≤ ai ≤ p − 1 for all i, and
(ii) a1 + a2 + a3 + · · · + ap is not divisible by p, and
(iii) a1 a2 + a2 a3 + a3 a4 + · · · + ap a1 is divisible by p.
Determine the number of good p-tuples.
4. The quadrilateral ABCD is inscribed in a circle. The point P lies in the interior
of ABCD, and ∠P AB = ∠P BC = ∠P CD = ∠P DA. The lines AD and BC meet
at Q, and the lines AB and CD meet at R. Prove that the lines P Q and P R form
the same angle as the diagonals of ABCD.
5. Fix positive integers n and k ≥ 2. A list of n integers is written in a row on a
blackboard. You can choose a contiguous block of integers, and I will either add 1 to
all of them or subtract 1 from all of them. You can repeat this step as often as you
like, possibly adapting your selections based on what I do. Prove that after a finite
number of steps, you can reach a state where at least n − k + 2 of the numbers on
the blackboard are all simultaneously divisible by k.
2015 Canadian Mathematical Olympiad
[version of January 28, 2015]
Notation: If V and W are two points, then V W denotes the line segment
with endpoints V and W as well as the length of this segment.
AB · AC + BC · BA + CA · CB
≤ 2.
AH · AD + BH · BE + CH · CF
5. Let p be a prime number for which p−1 2 is also prime, and let a,√b, c
be integers not divisible by p. Prove that there are at most 1 + 2p
positive integers n such that n < p and p divides an + bn + cn .
1
Problems for 2016 CMO – as of Feb 12, 2016
(a) Prove that there is a sequence of replacements that will make the
final number equal to 2.
(b) Prove that there is a sequence of replacements that will make the
final number equal to 1000.
6 vi2
vi = 1 + (i = 1, . . . , 10).
v12 + v22 + · · · + v10
2
Find all 10-tuples (v1 , v2 , . . . , v10 ) that are solutions of this system.
3. Find all polynomials P (x) with integer coefficients such that P (P (n)+
n) is a prime number for infinitely many integers n.
1
Prove that the smallest F for which the flea can jump over all the
intervals and avoid all the lava, regardless of what Lavaman does,
is F = (n − 1)A + B, where n is the positive integer such that
A A
≤B−A< .
n+1 n
2
CMO 2017 https://cms.math.ca/Competitions/CMO/ Problem Set
2017 Canadian
Mathematical Olympiad
1. Let a, b, and c be non-negative real numbers, no two of which are equal. Prove that
a2 b2 c2
2
+ 2
+ > 2.
(b − c) (c − a) (a − b)2
2. Let f be a function from the set of positive integers to itself such that, for every n, the
number of positive integer divisors of n is equal to f (f (n)). For example, f (f (6)) = 4 and
f (f (25)) = 3. Prove that if p is prime then f (p) is also prime.
3. Let n be a positive integer, and define Sn = {1, 2, . . . , n}. Consider a non-empty subset T of
Sn . We say that T is balanced if the median of T is equal to the average of T . For example,
for n = 9, each of the subsets {7}, {2, 5}, {2, 3, 4}, {5, 6, 8, 9}, and {1, 4, 5, 7, 8} is balanced;
however, the subsets {2, 4, 5} and {1, 2, 3, 5} are not balanced. For each n ≥ 1, prove that
the number of balanced subsets of Sn is odd.
(To define the median of a set of k numbers, first put the numbers in increasing order; then
the median is the middle number if k is odd, and the average of the two middle numbers if
k is even. For example, the median of {1, 3, 4, 8, 9} is 4, and the median of {1, 3, 4, 7, 8, 9} is
(4 + 7)/2 = 5.5.)
4. Points P and Q lie inside parallelogram ABCD and are such that triangles ABP and BCQ
are equilateral. Prove that the line through P perpendicular to DP and the line through Q
perpendicular to DQ meet on the altitude from B in triangle ABC.
5. One hundred circles of radius one are positioned in the plane so that the area of any triangle
formed by the centres of three of these circles is at most 2017. Prove that there is a line
intersecting at least three of these circles.
c 2017 Canadian Mathematical Society Page 1/ 1
CMO 1996
SOLUTIONS
QUESTION 1
Solution .
Then
1+α 1+β 1+γ N
S= + + =
1−α 1−β 1−γ (1 − α)(1 − β)(1 − γ)
Solution 1.
4t2
For any t, 0 ≤ 4t2 < 1 + 4t2 , so 0 ≤ < 1. Thus x, y and z must be non-negative and less
1 + 4t2
than 1.
If two of the variables are equal, say x = y, then the first equation becomes
4x2
= x.
1 + 4x2
1 1
This has the solution x = 0, which gives x = y = z = 0 and x = which gives x = y = z = .
2 2
Finally, assume that x, y and z are non-zero and distinct. Without loss of generality we may
assume that either 0 < x < y < z < 1 or 0 < x < z < y < 1. The two proofs are similar, so we do
only the first case.
4t2
We will need the fact that f (t) = is increasing on the interval (0, 1).
1 + 4t2
To prove this, if 0 < s < t < 1 then
4t2 4s2
f (t) − f (s) = −
1 + 4t2 1 + 4s2
4t2 − 4s2
=
(1 + 4s2 )(1 + 4t2 )
> 0.
Notice that x, y and z are non-negative. Adding the three equations gives
4z 2 4x2 4y 2
x+y+z = 2
+ 2
+ .
1 + 4z 1 + 4x 1 + 4y 2
1
Since each term is non-negative, each term must be 0, and hence each variable is either 0 or . The
2
1
original equations then show that x = y = z = 0 and x = y = z = are the only two solutions.
2
2
Solution 3.
Notice that x, y, and z are non-negative. Multiply both sides of the inequality
y
≥0
1 + 4y 2
4y 2
y− ≥ 0,
1 + 4y 2
and hence that y ≥ z. Similarly, z ≥ x, and x ≥ y. Hence, x = y = z and, as in Solution 1, the
two solutions follow.
Solution 4.
As for solution 1, note that x = y = z = 0 is a solution and any other solution will have each of
x, y and z positive.
1 + 4x2 √
The arithmetic-geometric mean inequality (or direct computation) shows that ≥ 1 · 4x2 = 2x
2
4x2 1
and hence x ≥ 2
= y, with equality if and only if 1 = 4x2 – that is, x = . Similarly, y ≥ z
1 + 4x 2
1 1
with equality if and only if y = and z ≥ x with equality if and only if z = . Adding x ≥ y, y ≥ z
2 2
1
and z ≥ x gives x+y +x ≥ x+y +z. Thus equality must occur in each inequality, so x = y = z = .
2
3
QUESTION 3
Solution.
A crucial observation, needed in Case II (b) is the following: If ak and ak+1 are consecutive integers
(i.e. ak+1 = ak ± 1), then the terms to the right of ak+1 (also to the left of ak ) are either all less
than both ak and ak+1 or all greater than both ak and ak+1 .
(b) Suppose a3 ≥ 4. If ak+1 is the first even number in the permutation then, because of (ii),
a1 , a2 , . . . , ak must be 1, 3, 5, . . . , 2k − 1 (in that order). Then ak+1 is either 2k or 2k − 2, so
that ak and ak+1 are consecutive integers. Applying the crucial observation made above, we
deduce that ak+2 , . . . , an are all either greater than or smaller than ak and ak+1 . But 2 must
be to the right of ak+1 . Hence ak+2 , . . . , an are the even integers less than ak+1 . The only
possibility then, is
1, 3, 5, . . . , ak−1 , ak , . . . , 6, 4, 2.
f (n) = f (n − 1) + f (n − 3) + 1, n ≥ 4. (∗)
Calculating a few more f (n)’s using (*) and mod 3 arithmetic, f (1) = 1, f (2) = 1, f (3) =
2, f (4) = 1, f (5) = 0, f (6) = 0, f (7) = 2, f (8) = 0, f (9) = 1, f (10) = 1, f (11) = 2. Since
f (1) = f (9), f (2) = f (10) and f (3) = f (11) mod 3, (*) shows that f (a) = f (a mod 8), mod 3, a ≥
1.
4
QUESTION 4
Solution 1.
D
4x
2x
x
x 4x 2x
B C
E
AB AD
By a standard theorem, = ; so in
CB DC
CE AD AB CA
= = = .
CD CD CB CB
Solution 2.
AD sin x AD BC sin 3x
= and 1+ = = .
BD sin 4x BD BD sin 2x
Now massage the resulting trigonometric equation with standard identities to get
5x − 90◦ = 90◦ − 4x ,
so that ∠A = 100◦ .
5
QUESTION 5
Solution.
Let m
X
f (n) = n − [rk n]
k=1
m
X m
X
=n rk − [rk n]
k=1 k=1
m
X
= {rk n − [rk n]}.
k=1
Letting n = b1 b2 . . . bn − 1, then
rk n = rk (b1 b2 . . . bm − 1)
= rk {(b1 b2 . . . bm − bk ) + bk − 1)}
= integer + rk (bk − 1).
This gives
rk n − [rk n] = rk (bk − 1) − [rk (bk − 1)]
· ¸
ak ak
= (bk − 1) − (bk − 1)
bk bk
µ ¶ · ¸
ak ak
= ak − − ak −
bk bk
µ ¶
ak
= ak − − (ak − 1)
bk
ak
=1− = 1 − rk .
bk
Pm
Hence f (n) = k=1 (1 − rk ) = m − 1.
6
1997
SOLUTIONS
Let p1 , . . . , p12 denote, in increasing order, the primes from 7 to 47. Then
and
Note that 24 , 32 , 52 , p1 , . . . , p12 all divide 50!, so all its prime powers differ from those of 5!
Since, by the above note, the prime powers for p12 and under differ in 5! and 50!, there are 215
choices for x, only half of which will be less than y. (Since for each choice of x, y is forced and
either x < y or y < x.) So the number of pairs is 215 /2 = 214 .
Problem 2 – Byung Kuy Chun, Harry Ainlay Composite High School, Edmonton, AB
Look at the first point of each given unit interval. This point uniquely defines the given unit
interval.
Lemma. In any interval [x, x + 1) there must be at least one of these first points (0 ≤ x ≤ 49).
Proof. Suppose the opposite. The last first point before x must be x − ε for some ε > 0. The
corresponding unit interval ends at x − ε + 1 < x + 1. However, the next given unit interval cannot
begin until at least x + 1.
Note that for two first points in intervals [x, x + 1) and [x + 2, x + 3) respectively, the corresponding
unit intervals are disjoint since the intervals are in the range [x, x + 2) and [x + 2, x + 4) respectively.
Since there are 25 of these intervals, we can find 25 points which correspond to 25 disjoint unit
intervals.
2
Problem 3 – Mihaela Enachescu, Dawson College, Montréal, PQ
1 3 1997 1 1 3 3
Let P = · · ... · . Then > because 2 < 3, > because 4 < 5, . . .,
2 4 1998 2 3 4 5
1997 1997
... > because 1998 < 1999 .
1998 1999
So
1 3 1997 1
P > · · ... · = . (1)
3 5 1999 1999
1 2 3 4
Also < because 1 · 3 < 2 · 2, < because 3 · 5 < 4 · 4, . . .
2 3 4 5
1997 1998
< because 1997 · 1999 = 19982 − 1 < 19982 .
1998 1999
µ ¶
2 4 1998 2 4 6 1998 1
So P < · · . . . · = · · · ... · .
3 5 1999 1 3 5 1997 1999
| {z }
1
P
1 1 1 1
Hence P 2 < < = 2 and P < . (2)
1999 1936 44 44
1 1
Then (1) and (2) give <P < (q.e.d.)
1999 44
A B
D C
Consider a translation which maps D to A. It will map 0 → 00 with OO0 = DA, and C will be
mapped to B because CB = DA.
∴ ∠ODC = ∠O 0 AB = ∠O 0 OB
∠O 0 OB = ∠OBC
∴ ∠ODC = ∠OBC.
3
Problem 4 – Adrian Chan, Upper Canada College, Toronto, ON
A B
θ
180−α α
Ο
180−θ
D C
Let ∠AOB = θ and ∠BOC = α. Then ∠COD = 180◦ − θ and ∠AOD = 180◦ − α.
Since AB = CD (parallelogram) and sin θ = sin(180◦ − θ), the sine law on 4OCD and 4OAB
gives
sin ∠CDO sin(180◦ − θ) sin θ sin ∠ABO
= = =
OC CD AB OA
so
OA sin ∠ABO
= . (1)
OC sin ∠CDO
Equations (1) and (2) show that sin ∠ABO · sin ∠CBO = sin ∠ADO · sin ∠CDO hence
1 1
[cos(∠ABO + ∠CBO)−cos(∠ABO − ∠CBO)] = [cos(∠ADO + ∠CDO)−cos(∠ADO − ∠CDO)].
2 2
Since ∠ADC = ∠ABC(parallelogram) and ∠ADO + ∠CDO = ∠ADC and ∠ABO + ∠CBO =
∠ABC it follows that cos(∠ABO − ∠CBO) = cos(∠ADO − ∠CDO).
Since ∠ABO + ∠CBO = ∠ADO + ∠CDO, subtracting gives 2 ∠CBO = 2 ∠CDO so ∠CBO =
∠CDO, and we are done.
Since we know that ∠ABO + ∠CBO = ∠CDO + ∠ADO, adding gives 2 ∠ABO = 2 ∠CDO so
∠ABO = ∠CDO and ∠CBO = ∠ADO.
Hence ∠BAD + ∠ADO + ∠ABO = 180◦ so ∠DOB = 180◦ and D, O, B are collinear.
4
A B
θ
O
180−θ
D C
Q.E.D.
5
Problem 5 – Sabin Cautis, Earl Haig Secondary School, North York, ON
Then
n
X (−1)k n!
S(n) =
k=0
k!(n − k)!(k + 2)(k + 3)(k + 4)
n
à ! µ ¶
X (−1)k (n + 4)! k+1
= × .
k=0
(k + 4)!(n − k)! (n + 1)(n + 2)(n + 3)(n + 4)
Let
n
à à ! !
X n+4
k
T (n) = (n + 1)(n + 2)(n + 3)(n + 4)S(n) = (−1) (k + 1) .
k+4
k=0
Now, for n ≥ 1,
n
à !
X n
i
(−1) =0 (∗)
i=0
i
since
à ! à ! à ! à !
n n n n n n
(1 − 1) = − + + . . . + (−1) = 0.
0 1 2 n
Also
n
à ! n
X n X i · n! 0 · n!
(−1)i i = (−1)i + (−1)0 ·
i=0
i i=1
i! · (n − i)! 0! · n!
n
X n!
= (−1)i
i=1
(i − 1)!(n − i)!
n
à !
X n−1
i
= (−1) n
i=1
i−1
n
à !
X n−1
= n (−1)i
i=1
i−1
n
à !
X n−1
i−1
= −n (−1) .
i=1
i−1
6
Substituting j = i − 1, (*) shows that
n
à ! n−1
à !
X n X n−1
i j
(−1) i = −n (−1) = 0. (∗∗)
i=0
i j=0
j
Hence
n
à !
X n+4
k
T (n) = (−1) (k + 1)
k+4
k=0
n
à !
X n+4
k+4
= (−1) (k + 1)
k+4
k=0
n
à ! à à !!
X n+4 n+4
k+4
= (−1) (k + 1) − −3 + 2(n + 4) − .
k+4 2
k=−4
Substituting j = k + 4,
n+4
à ! µ ¶
X n+4 (n + 4)(n + 3)
j
= (−1) (j − 3) − 2n + 8 − 3 −
j=0
j 2
n+4
à ! n+4
à !
X n+4 X n+4 1
j j
= (−1) j−3 (−1) − (4n + 10 − n2 − 7n − 12)
j=0
j j=0
j 2
The first two terms are zero because of results (*) and (**) so
n2 + 3n + 2
T (n) = .
2
Then
T (n)
S(n) =
(n + 1)(n + 2)(n + 3)(n + 4)
n2 + 3n + 2
=
2(n + 1)(n + 2)(n + 3)(n + 4)
(n + 1)(n + 2)
=
2(n + 1)(n + 2)(n + 3)(n + 4)
1
= .
2(n + 3)(n + 4)
à !
n
n (−1)k
X k 1
∴ =
k=0
k3 + 9k 2 + 26k + 24 2(n + 3)(n + 4)
7
1998
SOLUTIONS
The solutions to the problems of the 1998 CMO presented below are taken from students papers.
Some minor editing has been done - unnecesary steps have been eliminated and some wording has
been changed to make the proofs clearer. But for the most part, the proofs are as submitted.
Let a = 30k + r, where k is an integer and r is a real number between 0 and 29 inclusive.
· ¸ · ¸ · ¸ · ¸ · ¸ · ¸ · ¸
1 1 r 1 r 1 r
Then a = (30k + r) = 15k + . Similarly a = 10k + and a = 6k + .
2 2 2 3 3 5 5
· ¸ · ¸ · ¸ µ · ¸¶ µ · ¸¶ µ · ¸¶
1 1 1 r r r
Now, a + a + a = a, so 15k + + 10k + + 6k + = 30k + r and
2 3 5 2 3 5
· ¸ · ¸ · ¸
r r r
hence k = r − − − .
2 3 5
· ¸ · ¸ · ¸
r r r
Clearly, r has to be an integer, or r − − − will not be an integer, and therefore, cannot
2 3 5
equal k.
· ¸ · ¸ · ¸
r r r
On the other hand, if r is an integer, then r − − − will also be an integer, giving
2 3 5
exactly one solution for k.
For each r(0 ≤ r ≤ 29), a = 30k + r will have a different remainder mod 30, so no two different
values of r give the same result for a.
Since there are 30 possible values for r(0, 1, 2, . . . , 29), there are then 30 solutions for a.
1
Solution to Problem 2 – Jimmy Chui, Earl Haig S.S., North York, ON
µ ¶1/2 µ ¶1/2 µ ¶1/2 µ ¶1/2
1 1 1 1
Since x− ≥ 0 and 1− ≥ 0, then 0 ≤ x − + 1− =x.
x x x x
1
Note that x 6= 0. Else, would not be defined so x > 0.
x
Squaring both sides gives,
µ ¶ µ ¶ sµ ¶µ ¶
2 1 1 1 1
x = x− + 1− +2 x− 1−
x x x x
r
2 2 1 1
x = x + 1 − + 2 x − 1 − + 2.
x x x
x3 − x2 − x + 1 = 1
x(x2 − x − 1) = 0
x2 − x − 1 = 0 since x 6= 0.
√
1± 5
Thus x = . We must check to see if these are indeed solutions.
2
√ √
1+ 5 1− 5
Let α = , β= . Note that α + β = 1, αβ = −1 and α > 0 > β.
2 2
Since β < 0, β is not a solution.
Now, if x = α, then
µ ¶1/2 µ ¶1/2
1 1
α− + 1− = (α + β)1/2 + (1 + β)1/2 (since αβ − −1)
α α
= 11/2 + (β 2 )1/2 (since α + β = 1 and β 2 = β + 1)
= α (since α + β = 1).
2
Solution 1 to Problem 3 – Chen He, Columbia International Collegiate, Hamilton, ON
1 1 1 1 1 1 1
1+ + ... + = + + + + ... (1)
3 2n − 1 2 2 3 5 2n − 1
Since
1 1 1 1 1 1
> , > , ... , > ,
3 4 5 6 2n − 1 2n
(1) gives
µ ¶
1 1 1 1 1 1 1 1 1 1 1 1
1 + + ... + > + + + + ... + = + + + + ... + . (2)
3 2n − 1 2 2 4 6 2n 2 2 4 6 2n
Since
1 1 1 1 1 1 1 1
> , > , > , ... , >
2 4 2 6 2 8 2 2n
then
n 1 1 1 1 1 1 1 1
= + + + ... + > + + + ... +
2 |2 2 2{z 2} 2 4 6 2n
n
so µ ¶
1 1 1 1 1 1
> + + + ... + . (3)
2 n 2 4 6 2n
µ ¶ µ ¶
1 1 1 1 1 1 1
Therefore 1 + + ... + > + + ... + for all n ∈ N and n ≥ 2.
n+1 3 2n − 1 n 2 4 2n
3
Solution 2 to Problem 3 – Yin Lei, Vincent Massey S.S., Windsor, ON
µ ¶ µ ¶
1 1 1 1 1
n 1+ + ... + ≥ (n + 1) + + ... + .
3 2n − 1 2 4 2n
µ ¶ µ ¶
1 1 1 1 1
k 1+ + ... + > (k + 1) + + ... + . (1)
3 2k − 1 2 4 2k
We know
µ ¶ µ ¶
1 1 1 1 1
1+ + ... + − + + ... +
3 2k − 1 2 4 2k
µ ¶ µ ¶ µ ¶ µ ¶
1 1 1 1 1 1 1
= 1− + − + − + ... + −
2 3 4 5 6 2k − 1 2k
1 1 1 1
= + + + ... + .
1×2 3×4 5×6 (2k − 1)(2k)
Since
then
1 1 1 k
+ + ... + >
1×2 3×4 (2k − 1)(2k) (2k + 1)(2k + 2)
hence
1 1 1 1 1 k
1+ + ... + > + + ... + + . (2)
3 2k − 1 2 4 2k (2k + 1)(2k + 2)
Also
k+1 k+2 2k 2 + 2k + 2k + 2 − 2k 2 − 4k − k − 2 k
− = =−
2k + 1 2k + 2 (2k + 1)(2k + 2) (2k + 1)(2k + 2)
therefore
k+1 k+2 k
= − . (3)
2k + 1 2k + 2 (2k + 1)(2k + 2)
4
Adding 1, 2 and 3:
µ ¶ µ ¶
1 1 1 1 k+1
k 1+ + ... + + 1+ + ... + +
3 2k − 1 3 2k − 1 2k + 1
µ ¶ µ ¶
1 1 1 1 1 1 k k+2 k
> (k + 1) + + ... + + + + ... + + + −
2 4 2k 2 4 2k (2k + 1)(2k + 2) 2k + 2 (2k + 1)(2k + 2)
Rearrange both sides to get
µ ¶ µ ¶
1 1 1 1 1
(k + 1) 1 + + . . . + > (k + 2) + + ... + .
3 2k + 1 2 4 2k + 2
5
Solution 1 to Problem 4 – Keon Choi, A.Y. Jackson S.S., North York, ON
Suppose H is the foot of the perpendicular line from A to BC; construct equilateral 4ABG, with
C on BG. I will prove that if F is the point where AH meets BD, then 6 F CB = 70◦ . (Because
that means AH, and the given lines BD and CE meet at one point and that proves the question.)
Suppose BD extended meets AG at I.
A
E
I
F D
B H C G
6 F IG = 180◦ − 6 IF G − 6 IGF
= 180◦ − 80◦ − 20◦
= 80◦ .
GI = GF = BF. (1)
But 4BGI and 4ABC are congruent, since BG = AB, 6 GBI = 6 BAC, 6 BGI = 6 ABC.
Therefore
GI = BC. (2)
BC = BF.
So in 4BCF ,
Thus 6 F CB = 70◦ and that proves that the given lines CE and BD and the perpendicular line
AH meet at one point.
6
Solution 2 to Problem 4 – Adrian Birka, Lakeshore Catholic H.S., Port Colborne, ON
a2
c1 β1 β2
A’
C’
D
c2 a1
α2
γ1
α1 γ2
A b1 B’ b2 C
Proof: Let 6 BB 0 C = x, then 6 BB 0 A = 180◦ − x. Using the sine law in 4BB 0 C yields
b2 a
= . (1)
sin β2 sin x
b1 c c
= ◦
= . (2)
sin β1 sin(180 − x) sin x
Hence,
c sin β1
b1 : b2 = (3)
a sin β2
Similarly,
b sin α1 a sin γ1
a1 : a2 = , c1 : c 2 = . (4)
c sin α2 b sin γ2
By Ceva’s theorem, the necessary and sufficient condition for AA0 , BB 0 , CC 0 to intersect is:
(a1 : a2 ) · (b1 : b2 ) · (c1 : c2 ) = 1. Using (3), (4) on this yields:
7
so
Now, in our original question, give 6 BAC = 40◦ , 6 ABC = 60◦ . It follows that 6 ACB = 80◦ .
Since 6 CBD = 40◦ , 6 ABD = 6 ABC − 6 DBC = 20◦ . Similarly, 6 ECA = 20◦ .
B
E K
F
A D C
Now let us show that 6 F AD = 10◦ . Suppose otherwise. Let F 0 be such that F, F 0 are in the same
side of AC and 6 DAF 0 = 10◦ . Then 6 BAF 0 = 6 BAC − 6 DAF 0 = 30◦ .
Thus
sin 6 ABD sin 6 BCE sin 6 CAF 0 sin 20◦ sin 70◦ sin 10◦
· · = · ·
sin 6 DBC sin 6 ECA sin 6 F 0 AB sin 40◦ sin 10◦ sin 30◦
sin 20◦ cos 20◦
= ·
2 sin 20◦ cos 20◦ sin 30◦
1
= = 1.
2 sin 30◦
8
Solution to Problem 5 – Adrian Chan, Upper Canada College, Toronto, ON
a2n + a2n+1
Let us first prove by induction that = m2 for all n ≥ 0.
an · an+1 + 1
Proof:
a20 + a21 0 + m2
Base Case (n = 0) : = = m2 .
a0 · a1 + 1 0+1
Now, let us assume that it is true for n = k, k ≥ 0. Then,
a2k + a2k+1
= m2
ak · ak+1 + 1
a2k + a2k+1 = m2 · ak · ak+1 + m2
a2k+1 + m4 a2k+1 − 2m2 · ak · ak+1 + a2k = m2 + m4 a2k+1 − m2 · ak · ak+1
a2k+1 + (m2 ak+1 − ak )2 = m2 + m2 ak+1 (m2 ak+1 − ak )
a2k+1 + a2k+2 = m2 + m2 · ak+1 · ak+2 .
a2k+1 + a2k+2
So = m2 ,
ak+1 · ak+2 + 1
a2 + b2
proving the induction. Hence (an , an+1 ) is a solution to = m2 for all n ≥ 0.
ab + 1
a2 + b2
Now, consider the equation = m2 and suppose (a, b) = (x, y) is a solution with 0 ≤ x ≤ y.
ab + 1
Then
x2 + y 2
= m2 . (1)
xy + 1
If x = 0 then it is easily seen that y = m, so (x, y) = (a0 , a1 ). Since we are given x ≥ 0, suppose
now that x > 0.
x2 + (m2 x + k)2
= m2
(x)(m2 x + k) + 1
x2 + m4 x2 + 2m2 xk + k 2 = m4 x2 + m2 kx + m2
(x2 + k 2 ) + m2 (kx − 1) = 0.
9
Now substitute y = m2 x − x1 , where 0 ≤ x1 < m2 x, into (1).
We have
x2 + (m2 x − x1 )2
= m2
x(m2 x − x1 ) + 1
x2 + m4 x2 − 2m2 x · x1 + x21 = m4 x2 − m2 x · x1 + m2
x2 + x21 = m2 (x · x1 + 1)
x2 + x21
= m2 . (2)
x · x1 + 1
Continuing, we have (x1 , x) = (an−1 , an ) for some n. Then (x, y) = (an , an+1 ).
a2 + b2
Hence = m2 has solutions (a, b) if and only if (a, b) = (an , an+1 ) for some n.
ab + 1
10
GRADERS’ REPORT
Each question was worth a maximum of 7 marks. Every solution on every paper was graded by two
different markers. If the two marks differed by more than one point, the solution was reconsidered
until the difference resolved. If the two marks differed by one point, the average was used in
computing the total score.
The various grades assigned each solution are displayed below, as a percentage.
MARKS #1 #2 #3 #4 #5
PROBLEM 1
This question was well done. 47 students received 6 or 7 and only 6 students received no marks.
Many students came up with a proof similar to David Arthur’s proof. Another common approach
was to find bounds for a (either 0 ≤ a < 60 or 0 ≤ a < 90) and to then check which of these a
satisfy the equation.
PROBLEM 2
Although most students attempted this problem, there were only 6 perfect solutions. A further 6
solutions earned a mark of 6/7 and 13 solutions earned a mark of 5/7.
The most common approach was to square both sides of the equation, rearrange the terms to isolate
the radical, and to then square both sides again. This resulted in the polynomial x6 − 2x5 − x4 +
2x3 + x2 = 0. Many students were unable to factor this polynomial, and so earned only 2 or 3
points.
√ √
1+ 5 1− 5
The polynomial has three distinct roots: 0, , and . Most students recognized that
2 2 √
1− 5
0 is extraneous. One point was deducted for not finding that is extraneous, and a further
√ 2
1+ 5
point was deducted for not checking that is a solution. (It’s not obvious that the equation
2
has any solutions.) Failing to check for extraneous roots is considered to be a major error. The
graders should, perhaps, have deducted more points for this mistake.
The solution included here avoids the 6th degree polynomial, thus avoiding the difficult factoring.
11
However, the solutions must still be checked.
PROBLEM 3
There were 17 perfect solutions and eleven more contestants earned either 5 or 6 points.
1 1 1
The most elegant solution uses two simple observations: that 1 = + and that is greater than
2 2 2
1 1 1
the average of , , . . . , . A telescope argument also works, adding the first and last terms
2 4 2n
from each side, and so on. The key to a successful proof by induction is to be careful with algebra
and to avoid the temptation to use inequalities. For example, many students used the induction
hypothesis to deduce that
µ ¶ µ ¶
1 1 1 n+1 1 1 1
1 + + ... + > 1 + + ... + +
n+2 3 2n + 1 (n + 2)n 2 2n (n + 2)(2n + 1)
n+1 1
then used > , which is too sloppy for a successful induction proof.
(n + 2)n n+1
PROBLEM 4
Many contestants attempted this question, though few got beyond labeling the most apparent
angles. Nine students successfully completed the problem, while another six made a significant
attempt.
Most of these efforts employed trigonometry or coordinates to set up a trigonometric equation for
an unknown angle. This yields to an assault by identities. Adrian Birka produced a very clean
solution of this nature.
Only Keon Choi managed to complete a (very pretty) synthetic solution. One other contestant
made significant progress with the same idea.
PROBLEM 5
Many students were successful in finding the expression for the terms of the sequence {an } by a
variety of methods: producing an explicit formula, by means of a generating function and as a
sum of binomial coefficients involving parameter m. Unfortunately this does not help solving the
problem. Nevertheless seventeen contestants were able to prove by induction that the terms of the
sequence satisfy the required relation.
To prove the ”only if” part one should employ the method of descent which technically is the same
calculation as in the direct part of the problem. Three students succeeded in this, but only two
obtained a complete solution by showing that the sequence constructed by descent is decreasing
and must have m and 0 as the last two terms.
12
1999
SOLUTIONS
Most of the solutions to the problems of the 1999 CMO presented below are taken from students’
papers. Some minor editing has been done - unnecessary steps have been eliminated and some
wording has been changed to make the proofs clearer. But for the most part, the proofs are as
submitted.
Rearranging the equation we get 4x2 + 51 = 40[x]. It is known that x ≥ [x] > x − 1, so
Hence 3/2 ≤ x ≤ 17/2. Combining these inequalities gives 3/2 ≤ x < 7/2 or 13/2 < x ≤ 17/2 .
CASE 1: 3/2 ≤ x < 7/2.
For this case, the possible values for [x] are 1, 2 and 3.
If [x] = 1 then 4x2 + 51 = 40 · 1 so 4x2 = −11, which has no real solutions.
√ √ √ √
If [x] = 2 then 4x2 + 51 = 40 · 2 so 4x2 = 29 and x = 229 . Notice that 216 < 229 < 236 so
2 < x < 3 and [x] = 2.
√ √ √
If [x] = 3 then 4x2 + 51 = 40 · 3 and x = 69/2. But 269 > 264 = 4. So, this solution is rejected.
CASE 2: 13/2 < x ≤ 17/2.
For this case, the possible values for [x] are 6, 7 and 8.
√ √ √ √
189 144 189 196
If [x] = 6 then 4x2 + 51 = 40 · 6 so x = 2 . Notice that 2 < 2 < 2 so 6 < x < 7 and
[x] = 6.
√ √ √ √
229 196 229 256
If [x] = 7 then 4x2 + 51 = 40 · 7 so x = 2 . Notice that 2 < 2 < 2 so 7 < x < 8 and
[x] = 7.
√ √ √ √
If [x] = 8 then 4x2 + 51 = 40 · 8 so x = 269
2 . Notice that
256
2 < 269
2 < 324
2 so 8 < x < 9 and
[x] = 8.
√ √ √ √
29 189 229 269
The solutions are x = , , , .
2 2 2 2
(Editor: Adrian then checks these four solutions.)
1
Solution 1 to Problem 2 – Keon Choi, A.Y. Jackson S.S., North York, ON
E
Let D and E be the intersections of BC and extended
AC respectively with the circle.
Since CO||AB (because both the altitude and the ra-
dius are 1) 6 BCO = 60◦ and therefore 6 ECO =
C O
180◦ − 6 ACB − 6 BC0 = 60◦ .
Since a circle is always symmetric in its diameter and
line CE is reflection of line CB in CO, line segment
CE is reflection of line segment CB. D
Therefore CE = CD. A B
Therefore 4CED is an isosceles.
Therefore 6 CED = 6 CDE and 6 CED + 6 CDE = 6 ACB = 60◦ .
6 CED = 30◦ regardless of the position of centre 0. Since 6 CED is also the angle subtended from
the arc inside the triangle, if CED is constant, the arc length is also constant.
Editor’s Note: This proof has had no editing.
2
Solution 2 to Problem 2 – Jimmy Chui, Earl Haig S.S., North York, ON
³ ´
Place C at the origin, point A at √1 , 1 and y
³ ´ 3
point B at − √13 , 1 . Then 4ABC is equilateral B A
with altitude of length 1. A’
B’
Let O be the center of the circle. Because the
circle has radius 1, and since it touches line AB,
the locus of O is on the line through C parallel to
AB (since C is length 1 away from AB), i.e., the x
C O(a,0)
locus of O is on the x-axis.
Let point O be at (a, 0). Then − √13 ≤ a ≤ √1
3
since we have the restriction that the circle rolls
along AB.
Now, let A0 and 0
√ B be the intersection of the circle with
√ CA and CB respectively. The equation
of CA is y = 3 x, 0 ≤ x ≤ √13 , of CB is y = − 3 x, − √13 ≤ x ≤ 0, and of the circle is
(x − a)2 + y 2 = 1.
√
0
√ 2 2 a ± 4 − 3a2
We solve for A by substituting y = 3 x into (x − a) + y = 1 to get x = .
4
Visually, we can see that solutions represent the intersection of AC extended and the circle, but
we are only concerned with the greater x-value – this is the solution that is on AC, not on AC
extended. Therefore
√ Ã √ !
a+ 4 − 3a2 √ a+ 4 − 3a2
x= , y= 3 .
4 4
which is independent of a.
Consider the points 0, A0 and B 0 . 40A0 B 0 is an equilateral triangle (because A0 B 0 = 0A0 = 0B 0 = 1).
π
Therefore 6 A0 0B 0 = 3 and arc A0 B 0 = π3 , a constant.
3
Solution to Problem 3 – Masoud Kamgarpour, Carson S.S., North Vancouver, BC
Note that n = 1 is a solution. For n > 1 write n in the form n = P1α1 P2α2 ...Pm
αm where the P ’s,
i
1 ≤ i ≤ m, are distinct prime numbers and αi > 0. Since d(n) is an integer, n is a perfect square,
so αi = 2βi for integers βi > 0.
Using the formula for the number of divisors of n,
which is an odd number. Now because d(n) is odd, (d(n))2 is odd, therefore n is odd as well, so
Pi ≥ 3, 1 ≤ i ≤ m. We get
P1α1 · P2α2 . . . Pm
αm
= [(α1 + 1)(α2 + 1) . . . (αm + 1)]2
or using αi = 2βi
P1β1 P2β2 . . . Pm
βm
= (2β1 + 1)(2β2 + 1) . . . (2βm + 1).
4
Solution 2 to Problem 4 – The CMO committee
Consider all the consecutive differences (ie, di above) as well as the differences bi = ai+2 − ai , i =
1 . . . 6. Then the sum of these thirteen differences is 2·(a8 −a1 )+(a7 −a2 ) ≤ 2(17−1)+(16−2) = 46.
Now if no difference occurs more than twice, the smallest the sum of the thirteen differences can
be is 2 · (1 + 2 + 3 + 4 + 5 + 6) + 7 = 49, giving a contradiction.
f (x, y, z) − f (x, z, y) = x2 y + y 2 z + z 2 x − x2 z − z 2 y − y 2 x
= (y − z)(x − y)(x − z),
f (x + z, y, 0) − f (x, y, z) = (x + z)2 y − x2 y − y 2 z − z 2 x
= z 2 y + yz(x − y) + xz(y − z) ≥ 0,
so we may now assume z = 0. The rest follows from the arithmetic-geometric mean inequality:
µ ¶3
2x2 y 1 x + x + 2y 4
f (x, y, 0) = ≤ =
2 2 3 27
Equality occurs when x = 2y, hence at (x, y, z) = ( 23 , 13 , 0). (As well as (0, 23 , 13 ) and ( 13 , 0, 23 ).
5
GRADERS’ REPORT
Each question was worth a maximum of 7 marks. Every solution on every paper was graded by two
different markers. If the two marks differed by more than one point, the solution was reconsidered
until the difference resolved. If the two marks differed by one point, the average was used in
computing the total score.
The various grades assigned to each solution are displayed below, as a percentage.
MARKS #1 #2 #3 #4 #5
PROBLEM 1 The aim of the question was to give the competitors an encouraging start (it was
not a give away!). Over half of the students had good scores of 5, 6 or 7.
The general approach was to find bounds for x and then to find the exact value for x by substituting
in the resulting possible values of [x]. Depending on how the bounds were determined, this meant
checking 6 - 10 different cases.
Points were lost for not adequately verifying the bounds on x. For example, 2 points were deducted
for assuming, without proof, that 4x2 + 51 > 40[x] for x ≥ 9.
PROBLEM 2 Many competitors saw that the key here is to prove that the angle subtended by
the arc at its centre is constant, namely π/3. In all, 16 students managed a complete proof. Most
attempted an analytic solution – indeed, the problem is nearly routine if one chooses coordinates
wisely and later on notes that two such x-coordinates are roots of the same quadratic. A few
students used trigonometry, namely the law of sines on a couple of useful triangles. Two students
found essentially the same synthetic solution, which is very elegant.
PROBLEM 4
Many students found a specific set of seven integers such that the equation did not have three
different solutions. This earned two points. (One student found such a set with maximum value
14. A maximum value of 13 is not possible.)
6
Only eight competitors received high marks on the question (5, 6, or 7), and only one student scored
a perfect 7. All of the successful solvers considered differences of consecutive integers, showing that
they must be 1, 1, 2, 2, 3, 3, and 4, and then showed that every ordering of these differences led
to at least three repetitions of the same value. Most competitors recognized that the 1s could not
be together, nor could they be beside a 2. They then proceed by considering all such possible
arrangements, which often resulted in close to a dozen cases (depending on how the the cases were
handled.) David Nicholson was the most efficient at pruning the cases. (See Solution 1 to Problem
4.) Most students failed to consider one or two (easily dismissed) cases, hence lost 1 or 2 points.
A number of the contestants attempted to solve the problem by examining the odd-even character
of the set of eight integers, counting how many of the differences were odd or even, and using the
pigeon-hole principle. Although this approach looked promising, no one was able to handle the
case that 3 of the integers were of one parity, and 5 were of the other parity.
PROBLEM 5 No students received full marks for this problem. One student received 5 marks
for a proof that had minor errors. This proof was by Calculus. The committee was aware that
the problem could be solved using Calculus but (erroneously) thought it unlikely high school
students
³ would
´ ³ attempt´ such ³a solution.´ Many students received 1 point for “guessing” that
2 1 2 1 1 2
3 , 3 , 0 , 0, 3 , 3 and 3 , 0 , 3 are where equality occurred. Some students received
a further point for verifying the inequality on the boundary of the region.
7
2000 Canadian Mathematics Olympiad Solutions
Chair: Luis Goddyn, Simon Fraser University, goddyn@math.sfu.ca
The Year 2000 Canadian Mathematics Olympiad was written on Wednesday April 2, by 98 high
school students across Canada. A correct and well presented solution to any of the ve questions
was awarded seven points. This year’s exam was a somewhat harder than usual, with the mean
score being 8.37 out of 35. The top few scores were: 30, 28, 27, 22, 20, 20, 20. The rst, second and
third prizes are awarded to: Daniel Brox (Sentinel Secondary BC), David Arthur (Upper Canada
College ON), and David Pritchard (Woburn Collegiate Institute ON).
1. At 12:00 noon, Anne, Beth and Carmen begin running laps around a circular track of length
three hundred meters, all starting from the same point on the track. Each jogger maintains
a constant speed in one of the two possible directions for an indenite period of time. Show
that if Anne’s speed is dierent from the other two speeds, then at some later time Anne will
be at least one hundred meters from each of the other runners. (Here, distance is measured
along the shorter of the two arcs separating two runners.)
Comment: We were surprised by the difficulty of this question, having awarded an average
grade of 1.43 out of 7. We present two solutions; only the rst appeared among the graded
papers.
Solution 1: By rotating the frame of reference we may assume that Anne has speed zero, that
Beth runs at least as fast as Carmen, and that Carmen’s speed is positive. If Beth is no more
than twice as fast as Carmen, then both are at least 100 meters from Anne when Carmen has
run 100 meters. If Beth runs more that twice as fast as Carmen, then Beth runs a stretch of
more than 200 meters during the time Carmen runs between 100 and 200 meters. Some part
of this stretch lies more than 100 meters from Anne, at which time both Beth and Carmen
are at least (in fact, more than) 100 meters away from Anne.
Solution 2: By rotating the frame of reference we may assume Anne’s speed to equal zero,
and that the other two runners have non-zero speed. We may assume that Beth is running at
least as fast as Carmen. Suppose that it takes t seconds for Beth to run 200 meters. Then at
all times in the innite set T = {t, 2t, 4t, 8t, . . .}, Beth is exactly 100 meters from Anne. At
time t, Carmen has traveled exactly d meters where 0 < d 200. Let k be the least integer
such that 2k d 100. Then k 0 and 100 2k d 200, so at time 2k t ∈ T both Beth and
Carmen are at least 100 meters from Anne.
2. A permutation of the integers 1901, 1902, . . ., 2000 is a sequence a1, a2, . . . , a100 in which each
of those integers appears exactly once. Given such a permutation, we form the sequence of
partial sums
How many of these permutations will have no terms of the sequence s1 , . . ., s100 divisible by
three?
Comment: This question was the easiest and most straight forward, with an average grade of
3.07.
Solution: Let {1901, 1902, . . ., 2000} = R0 ∪ R1 ∪ R2 where each integer in Ri is congruent
to i modulo 3. We note that |R0| = |R1| = 33 and |R2| = 34. Each permutation S =
(a1, a2, . . . , a100) can be uniquely specied by describing a sequence S 0 = (a01, a02, . . . , a0100) of
residues modulo 3 (containing exactly 33 zeros, 33 ones and 34 twos), and three permutations
(one each of R0 , R1 , and R2). Note that the number of permutations of Ri is exactly |Ri|! =
1 2 |Ri|.
The condition on the partial sums of S depends only on the sequence of residues S 0 . In
order to avoid a partial sum divisible by three, the subsequence formed by the 67 ones and
twos in S 0 must equal either 1, 1, 2, 1, 2, . . . , 1, 2 or 2, 2, 1, 2, 1, . . ., 2, 1. Since |R2| = |R1| + 1,
only the second pattern is possible. The 33 zero entries
in S 0 may appear anywhere among
a01, a02, . . . , a0100 provided that a01 6= 0. There are 99 99!
33 = 33! 66! ways to choose which entries in
0 99 0
S equal zero. Thus there are exactly 33 sequences S whose partial sums are not divisible
by three. Therefore the total number of permutations S satisfying this requirement is exactly
!
99 99! 33! 34!
33! 33! 34! = .
33 66!
3. Let A = (a1, a2, . . . , a2000) be a sequence of integers each lying in the interval [−1000, 1000].
Suppose that the entries in A sum to 1. Show that some nonempty subsequence of A sums
to zero.
Comment: This students found this question to be the most difficult, with an average grade
of 0.51, and only one perfect solution among 100 papers.
Solution: We may assume no entry of A is zero, for otherwise we are done. We sort A into
a new list B = (b1, . . . , b2000) by selecting elements from A one at a time in such a way that
b1 > 0, b2 < 0 and, for each i = 2, 3, . . ., 2000, the sign of bi is opposite to that of the partial
sum
si−1 = b1 + b2 + + bi−1.
(We can assume that each si−i 6= 0 for otherwise we are done.) At each step of the selection
process a candidate for bi is guaranteed to exist, since the condition a1 + a2 + + a2000 = 1
implies that the sum of unselected entries in A is either zero or has sign opposite to si−1 .
From the way they were dened, each of s1 , s2, . . . , s2000 is one of the 1999 nonzero integers
in the interval [−999, 1000]. By the Pigeon Hole Principle, sj = sk for some j, k satisfying
1 j < k 2000. Thus bj+1 + bj+2 + + bk = 0 and we are done.
\CBD = 2\ADB,
\ABD = 2\CDB
and AB = CB.
2
so AP CD is a parallelogram. Now P D bisects AC so BD is an angle bisector of isosceles
triangle ABC. We have
1 1
\ADB = \CBD = \ABD = \CDB
2 2
so DB is the angle bisector of \ADC. As DB bisects the base of triangle ADC, this triangle
must be isosceles and AD = CD.
Solution 2: Let the bisector of \ABD meet AD at E. Let the bisector of \CBD meet CD
at F . Then \F BD = \BDE and \EBD = \BDF , which imply BE k F D and BF k ED.
Thus BEDF is a parallelogram whence
B B
A C A C
N
E F E M F
D D
Diagram for Solution 1 Diagram for Solution 2
a1 a2 a100 0
a1 + a2 100
a3 + a4 + + a100 100.
Determine the maximum possible value of a21 + a22 + + a2100 , and nd all possible sequences
a1, a2, . . . , a100 which achieve this maximum.
Comment: All of the correct solutions involved a sequence of adjustments to the variables,
each of which increase a21 + a22 + + a2100 while satisfying the constraints, eventually arriving
at the two optimal sequences: 100, 0, 0, . . ., 0 and 50, 50, 50, 50, 0, 0, . . . , 0. We present here a
sharper proof, which might be arrived at after guessing that the optimal value is 1002. Average
grade: 1.52 out of 7.
3
Solution: We have a1 + a2 + + a100 200, so
Since a1 a2 a100 0, none of the terms (ai − aj )ai is positive. Thus a21 + a22 + +
a2100 10, 000 with equality holding if and only if
equals zero. Since a1 a2 a3 a100 0, the last condition holds if and only if for
some i 1 we have a1 = a2 = = ai and ai+1 = = a100 = 0. If i = 1, then we get the
solution 100, 0, 0, . . ., 0. If i 2, then from a1 + a2 = 100, we get that i = 4 and the second
optimal solution 50, 50, 50, 50, 0, 0, . . ., 0.
4
2001
SOLUTIONS
Several solutions are edited versions of solutions submitted by the contestants whose names appear
in italics..
1. (Daniel Brox)
Let R be Rachel’s age, and let J be Jimmy’s age. Rachel’s quadratic is
for some number a. We are given that the coefficient a is an integer. The sum of the
coefficients is
a − a(R + J) + aRJ = a(R − 1)(J − 1).
Since this is a prime number, two of the three integers a, R − 1, J − 1 multiply to 1. We are
given that R > J > 0, so we must have that a = 1, J = 2, R − 1 is prime, and the quadratic
is
(x − R)(x − 2).
We are told that this quadratic takes the value −55 = −5 · 11 for some positive integer x.
Since R > 2, the first factor, (x − R), must be the negative one. We have four cases:
x − R = −55 and x − 2 = 1, which implies x = 3, R = 58.
x − R = −11 and x − 2 = 5, which implies x = 7, R = 18.
x − R = −5 and x − 2 = 11, which implies x = 13, R = 18.
x − R = −1 and x − 2 = 53, which implies x = 57, R = 58.
Since R − 1 is prime, the first and last cases are rejected, so R = 18 and J = 2.
2. (Lino Demasi )
After ten coin flips, the token finishes on the square numbered 2k − 10, where k is the number
¡ ¢
of heads obtained. Of the 210 = 1024 possible results of ten coin flips, there are exactly 10 k
ways to¡ obtain exactly k heads, so the probability of finishing on the square labeled 2k − 10
10¢
equals k /1024.
The probability of landing on a red square equals c/1024 where c is the sum of a selection of
the numbers from the list
à ! à ! à ! à !
10 10 10 10
, , ,..., = 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1. (1)
0 1 2 10
a/b = c/1024.
If we assume (as most contestants did!) that a and b are relatively prime, then the solution
proceeds as follows. Since 0 ≤ a/b ≤ 1 and a + b = 2001, we have 1001 ≤ b ≤ 2001. Also b
divides 1024, so we have b = 1024. Thus a = c = 2001 − 1024 = 977. There is only one way
to select terms from (1) so that the sum equals 977.
(This is easy to check, since the remaining terms in (1) must add to 1024 − 977 = 47, and
47 = 45 + 1 + 1 is the only possibility for this.)
1
In order to maximize n, we must colour the strip as¡ follows. Odd numbered squares are
10¢
red if positive, and white if negative. Since 252 = 5 is in the sum, the square labeled
¡ ¢
2 · 5 − 10 = 0 is red. For k = 0, 1, 2, 3, 4, if 10
k appears twice in the sum (2), then both 2k − 10
¡ ¢
and 10 − 2k are coloured red. If 10 does not appear in the sum, then both 2k − 10 and
¡10¢ k
10 − 2k are coloured white. If k appears once in the sum, then 10 − 2k is red and 2k − 10 is
white. Thus the maximum value of n is obtained when the red squares are those numbered
{1, 3, 5, 7, 9, −8, 8, −4, 4, −2, 2, 0, 6} giving n = 31.
(Alternatively) If we do not assume a and b are relatively prime, then there are several more
possibilities to consider. The greatest common divisor of a and b divides a + b = 2001, so
gcd(a, b) is one of
1, 3, 23, 29, 3 · 23, 3 · 29, 23 · 29, 3 · 23 · 29.
Since a/b = c/1024, dividing b by gcd(a, b) results in a power of 2. Thus the prime factoriza-
tion of b is one of the following, for some integer k.
2k , 3 · 2k , 23 · 2k , 29 · 2k , 69 · 2k , 87 · 2k , 667 · 2k , 2001.
Again we have 1001 ≤ b ≤ 2001, so b must be one of the following numbers.
1024, 3 · 512 = 1536, 23 · 64 = 1472, 29 · 64 = 1856, 69 · 16 = 1104, 87 · 16 = 1392, 667 · 2 = 1334, 2001.
After some (rather tedious) checking, one finds that only the following sums with terms from
(1) can add to a possible value of c.
Again only those terms appearing exactly once in a sum can affect maximum value of n. We
make the following table.
the red squares are {1, 3, 5, 7, 9, −6, 6, 2, 8}, the probability of landing on a red square is
a/b = 465/1536 = 310/1024 = 155/512, and n = 35.
2
3. Solution 1: (Daniel Brox)
Set O be the centre of the circumcircle of 4ABC. Let the angle bisector of 6 BAC meet this
circumcircle at R. We have
Thus BR = CR and R lies on the perpendicular bisector of BC. Thus R = P and ABCP
are concyclic. The points X, Y , M are the bases of the three perpendiculars dropped from P
onto the sides of 4ABC. Thus by Simson’s rule, X, Y, M are collinear. Thus we have M = Z
and BZ/ZC = BM/M C = 1.
Note: XY Z is called a Simson line, Wallace line or pedal line for 4ABC. To prove Simson’s
rule, we note that BM P X are concyclic, as are AY P X, thus
6 BXM = 6 BP M = 90 − 6 P BC = 90 − 6 P AC = 6 AP Y = 6 AXY
4. We shall # the only solution is n = 2. First we show that if n 6= 2, then the table
" see that
1
T0 = can not be changed into a table containing two zeros. For n = 1, this is
n−1
" #
a
very easy to see. Suppose n ≥ 3. For any table T = , let d(T ) be the quantity b − a
b
(mod n − 1). We shall show that neither of the two permitted moves can change the value of
d(T ). If we subtract n from both elements in T , then b − a does not change. If we multiply
the first row by n, then the element a changes to na, for a difference of (n − 1)a, which is
congruent to 0 (mod n − 1). Similarly, multiplying the second row by n does not change
d(T ). Since d(T0 ) = (n − 1) − 1 ≡ −1 (mod n − 1), we can never obtain the table with two
zeros by starting with T0 , because 0 − 0 is not congruent to −1 modulo n − 1.
For n = 2, and any table of positive integers, the following procedure will always result in a
table of zeros. We shall begin by converting the first column into a column of zeros as follows.
We repeatedly subtract 2 from all entries in the first column until at least one of the entries
equals either 1 or 2. Now we repeat the following sequence of three steps:
Each iteration of the three steps decreases the sum of those entries in the first column which
are greater than 2. Thus the first column eventually consists entirely of ones and twos, at
which time we apply (a) and (c) once again to obtain a column of zeros. We now repeat the
3
above procedure for each successive column of the table. The procedure does not affect any
column which has already been set to zero, so we eventually obtain a table with all entries
zero.
5. (Daniel Brox)
Let 6 P1 P3 P2 = 2α. As 4P1 P2 P3 is isosceles, we have that
t = P1 P2 = 2 sin α.
P3 P4 1 1
r= = = .
P1 P2 (2 sin α)(2 cos α) 2 sin(2α)
P3 P0
P2
P1
P5
P4
By the same argument, we see that each 6 Pi Pi+2 Pi+4 is a right angle with Pi+2 Pi+4 : Pi Pi+2 =
r. Thus the points P1 , P3 , P5 , . . . lie on a logarithmic spiral of ratio r and period four as shown
below. It follows that P1 , P5 , P9 , . . . are collinear, proving part (a).
4
P3
1
r
P1 P11
P9
P13
r3 P5
r2
P7
By the self-similarity of the spiral, we have that P1 P1001 = r500 P1001 P2001 , so
q
500
x/y = 1/r = 2 sin(2α).
This is an integer when sin(2α) ∈ p {0, ±1/2, ±1}. Since 0 < α < 90, this is equiva-
lent to α ∈ {15, 45, 75}. Thus 500 x/y is an integer exactly when t belongs to the set
{2 sin 15, 2 sin 45, 2 sin 75}. This answers part (b).
5
GRADERS’ REPORT
Eighty four of the eighty five eligible students submitted an examination paper. Each paper con-
tained proposed solutions the some or all of the five examination questions. Each correct and well
presented solution was awarded seven marks for a maximum total score of 35. The mean score was
10.8/35. The top three scores were 28, 27, and 22, thus special scrutiny was required to separate
the top two papers.
Each solution was independently marked by two graders. If the two marks differed, then the
solution was reconsidered until the difference was resolved. The top twenty papers were then
carefully regraded by the chair to ensure that nothing was amiss.
The grade distribution and average mark for each question appears in the following table. For
example, 13.1% of students were awarded 3 marks for question #1.
Marks #1 #2 #3 #4 #5
PROBLEM 1 Ninety five percent of students found the correct solution, although a surprising
number arrived at a solution through trial and error or by guessing and verifying a solution. Many
assumed without proof that the leading coefficient equals one, which resulted in a two-point penalty.
Another common error was not to consider all four possibilities for the pair (x − R), (x − 2).
PROBLEM 2 There was a flaw in question 2. The proposers intended that the integers a, b be
relatively prime. This was made explicit in an early draft, but somehow was lost with the ambiguous
phrase “of the form a/b.” Without this assumption, the problem is much more tedious to solve.
Remarkably, one student (Lino Demasi) considered more (but not all) possible values for gcd(a, b)
and obtained the correct solution n = 35. All other students assumed implicitly (and in two cases,
explicitly) that gcd(a, b) = 1. Solutions to both problems are presented in this publication.
PROBLEM 3 Most students either completely solved or were baffled by this basic geometry
problem. There were at least four types of solutions: one trigonometric, one using basic geometry,
and two which refer to standard theorems relating to the triangle. The first two tended to be
lengthy or cumbersome, and the last two are presented here. There were complaints from some
participants regarding the inaccurate angles appearing in the diagram supplied with the question.
The inaccuracy was intensional, since the key observation M = Z would have otherwise been given
6
away. Unfortunately, this caused some students to doubt their own proofs that BZ : ZC = 1; as
the ratio appears to be closer to 2 in the misleading diagram!
PROBLEM 4 This problem was left unanswered by about 60% of students. Several solutions
consisted only of a proof that n = 1 is not possible. About 25% described a procedure which works
when n = 2. Indeed the procedure for n = 2 seems to be unique. About 10% proved that for
no other value of n was possible, and all of the proofs explicitly or implicitly involved considering
residues modulo n − 1.
PROBLEM 5 This problem proved to be very difficult. Only two students completely answered
part (a), and no students correctly answered part (b). Of the students receiving more than 0 marks,
only two were were not among the top 15 This suggests that the question effectively resolved the
ranking of the strongest participants, which is arguably the purpose of Problem 5.
7
2002 Canadian Mathematical Olympiad
Solutions
1. Let S be a subset of {1, 2, . . . , 9}, such that the sums formed by adding each unordered pair of
distinct numbers from S are all different. For example, the subset {1, 2, 3, 5} has this property,
but {1, 2, 3, 4, 5} does not, since the pairs {1, 4} and {2, 3} have the same sum, namely 5.
What is the maximum number of elements that S can contain?
Solution 1
It can be checked that all the sums of pairs for the set {1, 2, 3, 5, 8} are different.
Suppose, for a contradiction, that S is a subset of {1, . . . , 9} containing 6 elements such that
all the sums of pairs are different. Now the smallest possible sum for two numbers from S is
1 + 2 = 3 and the
µ largest
¶ possible sum is 8 + 9 = 17. That gives 15 possible sums: 3, . . . , 17.
6
Also there are = 15 pairs from S. Thus, each of 3, . . . , 17 is the sum of exactly one
2
pair. The only pair from {1, . . . , 9} that adds to 3 is {1, 2} and to 17 is {8, 9}. Thus 1, 2, 8, 9
are in S. But then 1 + 9 = 2 + 8, giving a contradiction. It follows that the maximum number
of elements that S can contain is 5.
Solution 2.
It can be checked that all the sums of pairs for the set {1, 2, 3, 5, 8} are different.
Suppose, for a contradiction, that S is a subset of {1, . . . 9} such that all the sums of pairs
are different and that a1 < a2 < . . . < a6 are the members of S.
Since a1 + a6 6= a2 + a5 , it follows that a6 − a5 6= a2 − a1 . Similarly a6 − a5 6= a4 − a3 and
a4 − a3 6= a2 − a1 . These three differences must be distinct positive integers, so,
Similarly a3 − a2 6= a5 − a4 , so
(a3 − a2 ) + (a5 − a4 ) ≥ 1 + 2 = 3 .
a6 − a5 + a5 − a4 + a4 − a3 + a3 − a2 + a2 − a1 ≥ 6 + 3 = 9 ,
and hence a6 − a1 ≥ 9. This is impossible since the numbers in S are between 1 and 9.
2. Call a positive integer n practical if every positive integer less than or equal to n can be
written as the sum of distinct divisors of n.
For example, the divisors of 6 are 1, 2, 3, and 6 . Since
1=1, 2=2, 3=3, 4=1+3, 5=2+ 3, 6=6,
we see that 6 is practical.
Prove that the product of two practical numbers is also practical.
Solution
Let p and q be practical. For any k ≤ pq, we can write
k = aq + b with 0 ≤ a ≤ p, 0 ≤ b < q.
a = c 1 + . . . + cm , b = d 1 + . . . + d n
where the ci ’s are distinct divisors of p and the dj ’s are distinct divisors of q. Now
k = (c1 + . . . + cm )q + (d1 + . . . + dn )
= c1 q + . . . + cm q + d1 + . . . + dn .
Each of ci q and dj divides pq. Since dj < q ≤ ci q for any i, j, the ci q’s and dj ’s are all distinct,
and we conclude that pq is practical.
3. Prove that for all positive real numbers a, b, and c,
a3 b3 c3
+ + ≥ a + b + c,
bc ca ab
and determine when equality occurs.
Each of the inequalities used in the solutions below has the property that equality holds if
and only if a = b = c. Thus equality holds for the given inequality if and only if a = b = c.
Solution 1.
(a4 + b4 ) (b4 + c4 ) (c4 + a4 )
Note that a4 + b4 + c4 = + + . Applying the arithmetic-geometric
2 2 2
mean inequality to each term, we see that the right side is greater than or equal to
a2 b2 + b2 c2 + c2 a2 .
Solution 2.
Notice the inequality is homogeneous. That is, if a, b, c are replaced by ka, kb, kc, k > 0 we
get the original inequality. Thus we can assume, without loss of generality, that abc = 1.
Then
µ 3 ¶
a3 b3 c3 a b3 c3
+ + = abc + +
bc ca ab bc ca ab
= a4 + b4 + c4 .
So we need prove that a4 + b4 + c4 ≥ a + b + c.
By the Power Mean Inequality,
µ ¶4
a4 + b4 + c4 a+b+c
≥ ,
3 3
(a + b + c)3
so a4 + b4 + c4 ≥ (a + b + c) · .
27
a+b+c √ 3
By the arithmetic mean-geometric mean inequality, ≥ abc = 1, so a + b + c ≥ 3.
3
(a + b + c)3 33
Hence, a4 + b4 + c4 ≥ (a + b + c) · ≥ (a + b + c) = a + b + c.
27 27
Solution 3.
Rather than using the Power-Mean inequality to prove a4 + b4 + c4 ≥ a + b + c in Proof 2,
the Cauchy-Schwartz-Bunjakovsky inequality can be used twice:
(a4 + b4 + c4 )(12 + 12 + 12 ) ≥ (a2 + b2 + c2 )2
(a2 + b2 + c2 )(12 + 12 + 12 ) ≥ (a + b + c)2
a4 + b4 + c4 (a2 + b2 + c2 )2 (a + b + c)4
So ≥ ≥ . Continue as in Proof 2.
3 9 81
√
4. Let Γ be a circle with radius r. Let A and B be distinct points on Γ such that AB < 3r.
Let the circle with centre B and radius AB meet Γ again at C. Let P be the point inside
Γ such that triangle ABP is equilateral. Finally, let CP meet Γ again at Q. Prove that
P Q = r.
Γ
O
Q P C
A B
Solution 1.
Let the center of Γ be O, the radius r. Since BP = BC, let θ = ]BP C = ]BCP .
Quadrilateral QABC is cyclic, so ]BAQ = 180◦ − θ and hence ]P AQ = 120◦ − θ.
Also ]AP Q = 180◦ − ]AP B − ]BP C = 120◦ − θ, so P Q = AQ and ]AQP = 2θ − 60◦ .
Again because quadrilateral QABC is cyclic, ]ABC = 180◦ − ]AQC = 240◦ − 2θ .
Triangles OAB and OCB are congruent, since OA = OB = OC = r and AB = BC.
1
Thus ]ABO = ]CBO = ]ABC = 120◦ − θ.
2
We have now shown that in triangles AQP and AOB, ]P AQ = ]BAO = ]AP Q = ]ABO.
Also AP = AB, so 4AQP ∼ = 4AOB. Hence QP = OB = r.
Solution 2.
Let the center of Γ be O, the radius r. Since A, P and C lie on a circle centered at B,
60◦ = ]ABP = 2]ACP , so ]ACP = ]ACQ = 30◦ .
Since Q, A, and C lie on Γ, ]QOA = 2]QCA = 60◦ .
So QA = r since if a chord of a circle subtends an angle of 60◦ at the center, its length is the
radius of the circle.
Now BP = BC, so ]BP C = ]BCP = ]ACB + 30◦ .
Thus ]AP Q = 180◦ − ]AP B − ]BP C = 90◦ − ]ACB.
Since Q, A, B and C lie on Γ and AB = BC, ]AQP = ]AQC = ]AQB + ]BQC = 2]ACB.
Finally, ]QAP = 180 − ]AQP − ]AP Q = 90 − ]ACB.
So ]P AQ = ]AP Q hence P Q = AQ = r.
5. Let N = {0, 1, 2, . . .}. Determine all functions f : N → N such that
Solution 2.
We claim f is a constant function. Define g(x) = f (x) − f (0). Then g(0) = 0, g(x) ≥ −f (0)
and
xg(y) + yg(x) = (x + y)g(x2 + y 2 )
for all x, y in N.
Letting y = 0 shows g(x2 ) = 0 (in particular, g(1) = g(4) = 0), and letting x = y = 1 shows
g(2) = 0. Also, if x, y and z in N satisfy x2 + y 2 = z 2 , then
y
g(y) = − g(x). (∗)
x
Letting x = 4 and y = 3, (∗) shows that g(3) = 0.
For any even number x = 2n > 4, let y = n2 − 1. Then y > x and x2 + y 2 = (n2 + 1)2 . For
any odd number x = 2n + 1 > 3, let y = 2(n + 1)n. Then y > x and x2 + y 2 = ((n + 1)2 + n2 )2 .
Thus for every x > 4 there is y > x such that (∗) is satisfied.
Suppose for a contradiction, that there is x > 4 with g(x) > 0. Then we can construct a
xi+1
sequence x = x0 < x1 < x2 < . . . where g(xi+1 ) = − g(xi ). It follows that |g(xi+1 )| >
xi
|g(xi )| and the signs of g(xi ) alternate. Since g(x) is always an integer, |g(xi+1 )| ≥ |g(xi )| + 1.
Thus for some sufficiently large value of i, g(xi ) < −f (0), a contradiction.
As for Proof 1, we now conclude that the functions that satisfy the given functional equation
are f (x) = c, c ∈ N.
Solution 3. Suppose that W is the set of nonnegative integers and that f : W → W satisfies:
xf (y) + yf (x) = (x + y)f (x2 + y 2 ). (∗)
x2 ∈ S ∀ x > 0 (1)
In particular, 1 ∈ S.
Suppose x2 + y 2 = z 2 . Then yf (x) + xf (y) = (x + y)f (z 2 ) = (x + y)k. Thus,
x ∈ S iff y ∈ S. (2)
For each integer n ≥ 2 define p(n) to be the largest prime such that p(n) | n.
Claim: For any integer n > 1 that is not a power of 2, there exists a sequence of integers
x1 , x2 , . . . , xr such that the following conditions hold:
a) x1 = n.
b) x2i + x2i+1 is a perfect square for each i = 1, 2, 3, . . . , r − 1.
c) p(x1 ) ≥ p(x2 ) ≥ . . . ≥ p(xr ) = 2.
Case 1: a = 1. Since (2m+1, 2m2 +2m, 2m2 +2m+1) is a Pythagorean Triple, if x2 = b(2m2 +
2m), then x21 + x22 = b2 (2m2 + 2m + 1)2 is a perfect square. Furthermore, x2 = 2bm(m + 1),
and so p(x2 ) < 2m + 1 = p(x1 ).
If xa+1 is not a power of 2, we extend the sequence xi using the same procedure described
above. We keep doing this until p(xr ) = 2, for some integer r.
We have proven that every integer n ≥ 1 is an element of S, and so we have proven that
f (n) = k = f (0), for each n ≥ 1. Therefore, f is constant, Q.E.D.
Solutions to the 2003 CMO
written March 26, 2003
1. Consider a standard twelve-hour clock whose hour and minute hands move continu-
ously. Let m be an integer, with 1 ≤ m ≤ 720. At precisely m minutes after 12:00, the
angle made by the hour hand and minute hand is exactly 1◦ . Determine all possible
values of m.
Solution
The minute hand makes a full revolution of 360◦ every 60 minutes, so after m minutes
it has swept through 360
60
m = 6m degrees. The hour hand makes a full revolution every
12 hours (720 minutes), so after m minutes it has swept through 360
720
m = m/2 degrees.
Since both hands started in the same position at 12:00, the angle between the two
hands will be 1◦ if 6m − m/2 = ±1 + 360k for some integer k. Solving this equation
we get
720k ± 2 5k ± 2
m= = 65k + .
11 11
Since 1 ≤ m ≤ 720, we have 1 ≤ k ≤ 11. Since m is an integer, 5k ± 2 must be divisible
by 11, say 5k ± 2 = 11q. Then
q±2
5k = 11q ± 2 ⇒ k = 2q + .
5
If is now clear that only q = 2 and q = 3 satisfy all the conditions. Thus k = 4 or
k = 7 and substituting these values into the expression for m we find that the only
possible values of m are 262 and 458.
2001
2. Find the last three digits of the number 20032002 .
Solution
2001
We must find the remainder when 20032002 is divided by 1000, which will be the
20022001
same as the remainder when 3 is divided by 1000, since 2003 ≡ 3 (mod 1000).
To do this we will first find a positive integer n such that 3n ≡ 1 (mod 1000) and then
try to express 20022001 in the form nk + r, so that
2001
20032002 ≡ 3nk+r ≡ (3n )k · 3r ≡ 1k · 3r ≡ 3r (mod 1000).
m(m − 1)
32m = (10 − 1)m = (−1)m + 10m(−1)m−1 + 100 (−1)m−2 + · · · + 10m .
2
After the first 3 terms of this expansion, all remaining terms are divisible by 1000, so
letting m = 2q, we have that
Using this, we can check that 3100 ≡ 1 (mod 1000) and now we wish to find the
remainder when 20022001 is divided by 100.
Now 20022001 ≡ 22001 (mod 100) ≡ 4 · 21999 (mod 4 · 25), so we’ll investigate powers of
2 modulo 25. Noting that 210 = 1024 ≡ −1 (mod 25), we have
Thus 22001 ≡ 4 · 13 = 52 (mod 100). Therefore 20022001 can be written in the form
100k + 52 for some integer k, so
2001
20032002 ≡ 352 (mod 1000) ≡ 1 − 20 · 13 + 1300 · 25 ≡ 241 (mod 1000)
2001
using equation (1). So the last 3 digits of 20032002 are 241.
3. Find all real positive solutions (if any) to
x3 + y 3 + z 3 = x + y + z, and
x2 + y 2 + z 2 = xyz.
Solution 1
Let f (x, y, z) = (x3 − x) + (y 3 − y) + (z 3 − z). The first equation above is equivalent
to f (x, y, z) = 0. If x, y, z ≥ 1, then f (x, y, z) ≥ 0 with equality only if x = y = z = 1.
But if x = y = z = 1, then the second equation is not satisfied. So in any solution to
the system of equations, at least one of the variables is less than 1. Without loss of
generality, suppose that x < 1. Then
Solution 2
We will show that the system has no real positive solution. Assume otherwise.
The second equation can be written x2 − (yz)x + (y 2 + z 2 ). Since this quadratic in x
has a real solution by hypothesis, its discrimant is nonnegative. Hence
y 2 z 2 − 4y 2 − 4z 2 ≥ 0.
√ q √ q
3 S
3
so S ≤ 3. But then P ≥ 3 and 3
≤ 1 which is inconsistent with P ≤ 3 S3 .
3
l
A
X
α Y
β
γ Z
Solution 1
Let l be a line through A different from AB and join B to A, X, Y and Z as in the
above diagram. No matter how l is chosen, the angles AXB, AY B and AZB always
subtend the chord AB. For this reason the angles in the triangles BXY and BXZ are
the same for all such l. Thus the ratio XY : Y Z remains constant by similar triangles.
Note that this is true no matter how X, Y and Z lie in relation to A. Suppose X, Y and
Z all lie on the same side of A (as in the diagram) and that ]AXB = α, ]AY B = β
and ]AZB = γ. Then ]BXY = 180◦ − α, ]BY X = β, ]BY Z = 180◦ − β and
]BZY = γ. Now suppose l is chosen so that X is now on the opposite side of A from
Y and Z. Now since X is on the other side of the chord AB, ]AXB = 180◦ − α, but
it is still the case that ]BXY = 180◦ − α and all other angles in the two pertinent
triangles remain unchanged. If l is chosen so that X is identical with A, then l is
tangent to the first circle and it is still the case that ]BXY = 180◦ − α. All other
cases can be checked in a similar manner.
l
A
X
P Q R Y
Z
O1 O2 O3
Solution 2
Let m be the perpendicular bisector of AB and let O1 , O2 , O3 be the centres of the
three circles. Since AB is a chord common to all three circles, O1 , O2 , O3 all lie on m.
Let l be a line through A different from AB and suppose that X, Y , Z all lie on the
same side of AB, as in the above diagram. Let perpendiculars from O1 , O2 , O3 meet l
at P , Q, R, respectively. Since a line through the centre of a circle bisects any chord,
Solution
We will construct the set T in the following way: Assume the points of S are in the
xy-plane and let P be a point in S with maximum y-coordinate. This point P will be a
member of√the set T and now, from S, we will remove P and all points in S which are
less than 3 units from P . From the remaining points we choose one with maximum
y-coordinate
√ to be a member of T and remove from S all points at distance less than
3 units from this new point. We continue in this way,
√ until all the points of S are
exhausted. Clearly any two points in T are at least 3 units apart. To show that T
has at least n/7 points, we must prove that at each stage no more than 6 other points
are removed along with P .
At a typical stage in this process, we’ve√ selected a point P with maximum y-coordinate,
so any points
√ at distance less than 3 from P must lie inside the semicircular region
of radius 3 centred at P shown in the first diagram below. Since points of S are at
least 1 unit apart, these points must lie outside (or on) the semicircle of radius 1. (So
they lie in the shaded region of the first diagram.) Now divide this shaded region into
6 congruent regions R1 , R2 , . . . , R6 as shown in this diagram.
We will show that each of these regions contains at most one point of S. Since all 6
regions are congruent, consider one of them as depicted in the second diagram below.
The distance between any two points in this shaded region √ must be less than the length
of the line segment AB. The lengths of P A and P B are 3 and 1, respectively, and
angle AP B = 30◦ . If√we construct a perpendicular from B to P A at C, then the length
of P C is cos 30◦ = 3/2. Thus BC is a perpendicular bisector of P A and therefore
AB = P B = 1. So the distance between any two points in this region is less than 1.
Therefore each of R1 , . . . , R6 can contain at most one point of S, which completes the
proof.
√
1 P 3
P C A
R1 R6 30◦
R2 R5
B
R3 R4
Solutions to the 2004 CMO
written March 31, 2004
1. Find all ordered triples (x, y, z) of real numbers which satisfy the following system of
equations:
xy = z − x − y
xz = y − x − z
yz = x − y − z
Solution 1
Subtracting the second equation from the first gives xy − xz = 2z − 2y. Factoring y − z
from each side and rearranging gives
(x + 2)(y − z) = 0,
so either x = −2 or z = y.
If x = −2, the first equation becomes −2y = z + 2 − y, or y + z = −2. Substituting
x = −2, y + z = −2 into the third equation gives yz = −2 − (−2) = 0. Hence either y
or z is 0, so if x = −2, the only solutions are (−2, 0, −2) and (−2, −2, 0).
If z = y the first equation becomes xy = −x, or x(y + 1) = 0. If x = 0 and z = y,
the third equation becomes y 2 = −2y which gives y = 0 or y = −2. If y = −1 and
z = y = −1, the third equation gives x = −1. So if y = z, the only solutions are
(0, 0, 0), (0, −2, −2) and (−1, −1, −1).
In summary, there are 5 solutions: (−2, 0, −2), (−2, −2, 0), (0, 0, 0), (0, −2, −2) and
(−1, −1, −1).
Solution 2
Adding x to both sides of the first equation gives
x(y + 1) = z − y = (z + 1) − (y + 1) ⇒ (x + 1)(y + 1) = z + 1.
If any one of a, b, c is 0, then it’s clear that all three are 0. So (a, b, c) = (0, 0, 0) is
one solution and now suppose that a, b, c are all nonzero. Substituting c = ab into the
second and third equations gives a2 b = b and b2a = a, respectively. Hence a2 = 1,
b2 = 1 (since a, b nonzero). This gives 4 more solutions: (a, b, c) = (1, 1, 1), (1, −1, −1),
(−1, 1, −1) or (−1, −1, 1). Reexpressing in terms of x, y, z, we obtain the 5 ordered
triples listed in Solution 1.
2. How many ways can 8 mutually non-attacking rooks be placed
on the 9 × 9 chessboard (shown here) so that all 8 rooks are on
squares of the same colour?
[Two rooks are said to be attacking each other if they are placed
in the same row or column of the board.]
Solution 1
We will first count the number of ways of placing 8 mutually non-attacking rooks on
black squares and then count the number of ways of placing them on white squares.
Suppose that the rows of the board have been numbered 1 to 9 from top to bottom.
First notice that a rook placed on a black square in an odd O O O O O
numbered row cannot attack a rook on a black square in an even E E E E
O O O O O
numbered row. This effectively partitions the black squares into E E E E
a 5 × 5 board and a 4 × 4 board (squares labelled O and E O O O O O
respectively, in the diagram at right) and rooks can be placed O E O E O E O E O
independently on these two boards. There are 5! ways to place E E E E
5 non-attacking rooks on the squares labelled O and 4! ways to O O O O O
place 4 non-attacking rooks on the squares labelled E.
This gives 5!4! ways to place 9 mutually non-attacking rooks on black squares and
removing any one of these 9 rooks gives one of the desired configurations. Thus there
are 9 · 5!4! ways to place 8 mutually non-attacking rooks on black squares.
Using very similar reasoning we can partition the white squares O O O O
as shown in the diagram at right. The white squares are par- E E E E E
O O O O
titioned into two 5 × 4 boards such that no rook on a square E E E E E
marked O can attack a rook on a square mark E. At most 4 O O O O
E E E E E
non-attacking rooks can be placed on a 5 × 4 board and they O O O O
can be placed in 5 · 4 · 3 · 2 = 5! ways. Thus there are (5!)2 ways E E E E E
O O O O
to place 8 mutually non-attacking rooks on white squares.
In total there are 9 · 5!4! + (5!)2 = (9 + 5)5!4! = 14 · 5!4! = 40320 ways to place 8
mutually non-attacking rooks on squares of the same colour.
Solution 2
Consider rooks on black squares first. We have 8 rooks and 9 rows, so exactly one row
will be without rooks. There are two cases: either the empty row has 5 black squares
or it has 4 black squares. By permutation these rows can be made either last or second
last. In each case we’ll count the possible number of ways of placing the rooks on the
board as we proceed row by row.
In the first case we have 5 choices for the empty row, then we can place a rook on any
of the black squares in row 1 (5 possibilities) and any of the black squares in row 2 (4
possibilities). When we attempt to place a rook in row 3, we must avoid the column
containing the rook that was placed in row 1, so we have 4 possibilities. Using similar
reasoning, we can place the rook on any of 3 possible black squares in row 4, etc. The
total number of possibilities for the first case is 5 · 5 · 4 · 4 · 3 · 3 · 2 · 2 · 1 = (5!)2 . In the
second case, we have 4 choices for the empty row (but assume it’s the second last row).
We now place rooks as before and using similar logic, we get that the total number of
possibilities for the second case is 4 · 5 · 4 · 4 · 3 · 3 · 2 · 1 · 1 = 4(5!4!).
Now, do the same for the white squares. If a row with 4 white squares is empty (5
ways to choose it), then the total number of possibilities is (5!)2. It’s impossible to
have a row with 5 white squares empty, so the total number of ways to place rooks is
B X
α
A α γ C
γ
Y D
Solution 1
We’re given that AB < AD. Since CY bisects ]BCD, BY = Y D, so Y lies between
D and A on the circle, as in the diagram above, and DY > Y A, DY > AB. Similar
reasoning confirms that X lies between B and C and BX > XC, BX > CD. So if
ABXCDY has 4 equal sides, then it must be that Y A = AB = XC = CD.
Let ]BAX = ]DAX = α and let ]BCY = ]DCY = γ. Since ABCD is cyclic,
]A+]C = 180◦ , which implies that α+γ = 90◦ . The fact that Y A = AB = XC = CD
means that the arc from Y to B (which is subtended by ]Y CB) is equal to the arc from
X to D (which is subtended by ]XAD). Hence ]Y CB = ]XAD, so α = γ = 45◦ .
Finally, BD is subtended by ]BAD = 2α = 90◦ . Therefore BD is a diameter of the
circle.
Solution 2
We’re given that AB < AD. Since CY bisects ]BCD, BY = Y D, so Y lies between
D and A on the circle, as in the diagram above, and DY > Y A, DY > AB. Similar
reasoning confirms that X lies between B and C and BX > XC, BX > CD. So
if ABXCDY has 4 equal sides, then it must be that Y A = AB = XC = CD.
This implies that the arc from Y to B is equal to the arc from X to D and hence
that Y B = XD. Since ]BAX = ]XAD, BX = XD and since ]DCY = ]Y CB,
DY = Y B. Therefore BXDY is a square and its diagonal, BD, must be a diameter
of the circle.
4. Let p be an odd prime. Prove that
p−1
X p(p + 1)
k 2p−1 ≡ (mod p2 ).
2
k=1
Solution
Since p − 1 is even, we can pair up the terms in the summation in the following way
(first term with last, 2nd term with 2nd last, etc.):
p−1
p−1
X 2
X
k 2p−1 = k 2p−1 + (p − k)2p−1 .
k=1 k=1
where every term on the right-hand side is divisible by p2 except the last two. Therefore
2p−1 2p−1 2p−1 2p − 1
k + (p − k) ≡k + pk 2p−2 − k 2p−1 ≡ (2p − 1)pk 2p−2 (mod p2 ).
1
For 1 ≤ k < p, k is not divisible by p, so k p−1 ≡ 1 (mod p), by Fermat’s Little Theorem.
So (2p − 1)k 2p−2 ≡ (2p − 1)(12 ) ≡ −1 (mod p), say (2p − 1)k 2p−2 = mp − 1 for some
integer m. Then
(2p − 1)pk 2p−2 = mp2 − p ≡ −p (mod p2 ).
Finally,
p−1
X
p−1
X
2
2p−1 p−1
k ≡ (−p) ≡ (−p) (mod p2 )
2
k=1 k=1
p − p2 p(p + 1)
≡ + p2 ≡ (mod p2 ).
2 2
5. Let T be the set of all positive integer divisors of 2004100 . What is the largest possible
number of elements that a subset S of T can have if no element of S is an integer
multiple of any other element of S?
Solution
Assume throughout that a, b, c are nonnegative integers. Since the prime factorization
of 2004 is 2004 = 22 · 3 · 167,
n o
T = 2a 3b 167c 0 ≤ a ≤ 200, 0 ≤ b, c ≤ 100 .
Let n o
S = 2200−b−c 3b 167c 0 ≤ b, c ≤ 100 .
200 − b − c ≥ 200 − j − k, b ≥ j, c ≥ k.
1. Consider an equilateral triangle of side length n, which is divided into unit triangles, as
shown. Let f (n) be the number of paths from the triangle in the top row to the middle
triangle in the bottom row, such that adjacent triangles in our path share a common
edge and the path never travels up (from a lower row to a higher row) or revisits a
triangle. An example of one such path is illustrated below for n = 5. Determine the
value of f (2005).
Solution
We shall show that f (n) = (n − 1)!.
Label the horizontal line segments in the triangle l1 , l2 , . . . as in the diagram below.
Since the path goes from the top triangle to a triangle in the bottom row and never
travels up, the path must cross each of l1 , l2 , . . . , ln−1 exactly once. The diagonal lines
in the triangle divide lk into k unit line segments and the path must cross exactly one
of these k segments for each k. (In the diagram below, these line segments have been
highlighted.) The path is completely determined by the set of n − 1 line segments
which are crossed. So as the path moves from the kth row to the (k + 1)st row,
there are k possible line segments where the path could cross lk . Since there are
1 · 2 · 3 · · · (n − 1) = (n − 1)! ways that the path could cross the n − 1 horizontal lines,
and each one corresponds to a unique path, we get f (n) = (n − 1)!.
Therefore f (2005) = (2004)!.
l1
l2
l3
l4
2. Let (a, b, c) be a Pythagorean triple, i.e., a triplet of positive integers with a2 + b2 = c2 .
a) Prove that (c/a + c/b)2 > 8.
b) Prove that there does not exist any integer n for which we can find a Pythagorean
triple (a, b, c) satisfying (c/a + c/b)2 = n.
a) Solution 1
Let (a, b, c) be a Pythagorean triple. View a, b as lengths of the legs of a right
angled triangle with hypotenuse of length c; let θ be the angle determined by the
sides with lengths a and c. Then
c c 2 2
1 1 sin2 θ + cos2 θ + 2 sin θ cos θ
+ = + =
a b cos θ sin θ (sin θ cos θ)2
1 + sin 2θ 4 4
= 4 2 = 2 +
sin 2θ sin 2θ sin 2θ
Note that because 0 < θ < 90◦ , we have √ 0 < sin 2θ ≤ 1, with equality only if
θ = 45◦ . But then a = b and we obtain 2 = c/a, contradicting a, c both being
integers. Thus, 0 < sin 2θ < 1 which gives (c/a + c/b)2 > 8.
Solution 2
Defining θ as in Solution 1, we have c/a √ + c/b = sec θ + csc θ. By the AM-GM
inequality, we have (sec θ + csc θ)/2 ≥ sec θ csc θ. So
√
2 2 2 √
c/a + c/b ≥ √ =√ ≥ 2 2.
sin θ cos θ sin 2θ
√
Since a, b, c are integers, we have c/a + c/b > 2 2 which gives (c/a + c/b)2 > 8.
Solution 3
By simplifying and using the AM-GM inequality,
c c 2 2 √ √
2 a+b (a2 + b2 )(a + b)2 2 a2 b2 (2 ab)2
+ =c = ≥ = 8,
a b ab a2 b 2 a2 b 2
with equality only if a = b. By using the same argument as in Solution 1, a cannot
equal b and the inequality is strict.
Solution 4
c c 2 c2 c2 2c2 b 2 a2 2(a2 + b2 )
+ = 2+ 2+ =1+ 2 + 2 +1+
a b a b ab a b ab
2
a b 2
= 2+ − +2+ (a − b)2 + 2ab
b a ab
2
a b 2(a − b)2
= 4+ − + + 4 ≥ 8,
b a ab
with equality only if a = b, which (as argued previously) cannot occur.
b) Solution 1
Since c/a + c/b is rational, (c/a + c/b)2 can only be an integer if c/a + c/b is an
integer. Suppose c/a + c/b = m. We may assume that gcd(a, b) = 1. (If not,
divide the common factor from (a, b, c), leaving m unchanged.)
Since c(a+b) = mab and gcd(a, a+b) = 1, a must divide c, say c = ak. This gives
a2 + b2 = a2 k 2 which implies b2 = (k 2 − 1)a2 . But then a divides b contradicting
the fact that gcd(a, b) = 1. Therefore (c/a + c/b)2 is not equal to any integer n.
Solution 2
We begin as in Solution 1, supposing that c/a + c/b = m with gcd(a, b) = 1.
Hence a and b are not both even. It is also the case that a and b are not both
odd, for then c2 = a2 + b2 ≡ 2 (mod 4), and perfect squares are congruent to
either 0 or 1 modulo 4. So one of a, b is odd and the other is even. Therefore
c must be odd.
Now c/a + c/b = m implies c(a + b) = mab, which cannot be true because c(a + b)
is odd and mab is even.
3. Let S be a set of n ≥ 3 points in the interior of a circle.
a) Show that there are three distinct points a, b, c ∈ S and three distinct points
A, B, C on the circle such that a is (strictly) closer to A than any other point in
S, b is closer to B than any other point in S and c is closer to C than any other
point in S.
b) Show that for no value of n can four such points in S (and corresponding points
on the circle) be guaranteed.
Solution 1
a) Let H be the smallest convex set of points in the plane which contains S.† Take
3 points a, b, c ∈ S which lie on the boundary of H. (There must always be at
least 3 (but not necessarily 4) such points.)
Since a lies on the boundary of the convex region H, we can construct a chord L
such that no two points of H lie on opposite sides of L. Of the two points where
the perpendicular to L at a meets the circle, choose one which is on a side of L
not containing any points of H and call this point A. Certainly A is closer to a
than to any other point on L or on the other side of L. Hence A is closer to a
than to any other point of S. We can find the required points B and C in an
analogous way and the proof is complete.
[Note that this argument still holds if all the points of S lie on a line.]
P
A √
3
a 2 r
r
a b
c
L
H r
b
Q c R
(a) (b)
†
By the way, H is called the convex hull of S. If the points of S lie on a line, then H will be the shortest
line segment containing the points of S. Otherwise, H is a polygon whose vertices are all elements of S and
such that all other points in S lie inside or on this polygon.
Solution 2
a) If all the points of S lie on a line L, then choose any 3 of them to be a, b, c. Let
A be a point on the circle which meets the perpendicular to L at a. Clearly A is
closer to a than to any other point on L, and hence closer than other other point
in S. We find B and C in an analogous way.
Otherwise, choose a, b, c from S so that the triangle formed by these points has
maximal area. Construct the altitude from the side bc to the point a and extend
this line until it meets the circle at A. We claim that A is closer to a than to any
other point in S.
Suppose not. Let x be a point in S for which the distance from A to x is less than
the distance from A to a. Then the perpendicular distance from x to the line bc
must be greater than the perpendicular distance from a to the line bc. But then
the triangle formed by the points x, b, c has greater area than the triangle formed
by a, b, c, contradicting the original choice of these 3 points. Therefore A is closer
to a than to any other point in S.
The points B and C are found by constructing similar altitudes through b and c,
respectively.
b) See Solution 1.
4. Let ABC be a triangle with circumradius R, perimeter P and area K. Determine the
maximum value of KP/R3 .
Solution 1
Since similar triangles give the same value of KP/R3 , we can fix R = 1 and maximize
KP over all triangles inscribed in the unit circle. Fix points A and B on the unit circle.
The locus of points C with a given perimeter P is an ellipse that meets the circle in at
most four points. The area K is maximized (for a fixed P ) when C is chosen on the
perpendicular bisector of AB, so we get a maximum value for KP if C is where the
perpendicular bisector of AB meets the circle. Thus the maximum value of KP for
a given AB occurs when ABC is an isosceles triangle. Repeating this argument with
BC fixed, we have that the maximum occurs when ABC is an equilateral triangle.
Consider
√ an equilateral √triangle with side length a. It has P = 3a. It has height equal
2
to a 3/2
√ giving K = a 3/4. ¿From the extended law of sines, 2R = a/ sin(60) giving
R = a/ 3. Therefore the maximum value we seek is
√ √ 3
a2 3 3 27
KP/R3 = (3a) = .
4 a 4
Solution 2
From the extended law of sines, the lengths of the sides of the triangle are 2R sin A,
2R sin B and 2R sin C. So
1
P = 2R(sin A + sin B + sin C) and K = (2R sin A)(2R sin B)(sin C),
2
giving
KP
= 4 sin A sin B sin C(sin A + sin B + sin C).
R3
We wish to find the maximum value of this expression over all A + B + C = 180◦ .
Using well-known identities for sums and products of sine functions, we can write
KP cos(B − C) cos(B + C) B+C B−C
= 4 sin A − sin A + 2 sin cos .
R3 2 2 2 2
giving
KP 4
≤ (sin A + sin B + sin C)4 ,
R 3 27
with equality when sin A = sin B = sin C. Since the sine function is concave on the
interval from 0 to π, Jensen’s inequality gives
√
sin A + sin B + sin C A+B+C π 3
≤ sin = sin = .
3 3 3 2
Since equality occurs here when sin A = sin B = sin C also, we can conclude that the
√ 4
4 3 3
maximum value of KP/R3 is 27 2
= 27/4.
5. Let’s say that an ordered triple of positive integers (a, b, c) is n-powerful if a ≤ b ≤ c,
gcd(a, b, c) = 1, and an + bn + cn is divisible by a + b + c. For example, (1, 2, 2) is
5-powerful.
a) Determine all ordered triples (if any) which are n-powerful for all n ≥ 1.
b) Determine all ordered triples (if any) which are 2004-powerful and 2005-powerful,
but not 2007-powerful.
[Note that gcd(a, b, c) is the greatest common divisor of a, b and c.]
Solution 1
Let Tn = an + bn + cn and consider the polynomial
P (x) = (x − a)(x − b)(x − c) = x3 − (a + b + c)x2 + (ab + ac + bc)x − abc.
Since P (a) = 0, we get a3 = (a + b + c)a2 − (ab + ac + bc)a + abc and multiplying both
sides by an−3 we obtain an = (a + b + c)an−1 − (ab + ac + bc)an−2 + (abc)an−3 . Applying
the same reasoning, we can obtain similar expressions for bn and cn and adding the
three identities we get that Tn satisfies the following 3-term recurrence:
Tn = (a + b + c)Tn−1 − (ab + ac + bc)Tn−2 + (abc)Tn−3 , for all n ≥ 3.
¿From this we see that if Tn−2 and Tn−3 are divisible by a + b + c, then so is Tn . This
immediately resolves part (b)—there are no ordered triples which are 2004-powerful
and 2005-powerful, but not 2007-powerful—and reduces the number of cases to be
considered in part (a): since all triples are 1-powerful, the recurrence implies that any
ordered triple which is both 2-powerful and 3-powerful is n-powerful for all n ≥ 1.
Putting n = 3 in the recurrence, we have
a3 + b3 + c3 = (a + b + c)(a2 + b2 + c2 ) − (ab + ac + bc)(a + b + c) + 3abc
which implies that (a, b, c) is 3-powerful if and only if 3abc is divisible by a + b + c.
Since
a2 + b2 + c2 = (a + b + c)2 − 2(ab + ac + bc),
(a, b, c) is 2-powerful if and only if 2(ab + ac + bc) is divisible by a + b + c.
Suppose a prime p ≥ 5 divides a + b + c. Then p divides abc. Since gcd(a, b, c) = 1, p
divides exactly one of a, b or c; but then p doesn’t divide 2(ab + ac + bc).
Suppose 32 divides a + b + c. Then 3 divides abc, implying 3 divides exactly one of a,
b or c. But then 3 doesn’t divide 2(ab + ac + bc).
Suppose 22 divides a + b + c. Then 4 divides abc. Since gcd(a, b, c) = 1, at most one
of a, b or c is even, implying one of a, b, c is divisible by 4 and the others are odd. But
then ab + ac + bc is odd and 4 doesn’t divide 2(ab + ac + bc).
So if (a, b, c) is 2- and 3-powerful, then a + b + c is not divisible by 4 or 9 or any prime
greater than 3. Since a + b + c is at least 3, a + b + c is either 3 or 6. It is now a
simple matter to check the possibilities and conclude that the only triples which are
n-powerful for all n ≥ 1 are (1, 1, 1) and (1, 1, 4).
Solution 2
Let p be a prime. By Fermat’s Little Theorem,
p−1 1 (mod p), if p doesn’t divide a;
a ≡
0 (mod p), if p divides a.
Since gcd(a, b, c) = 1, we have that ap−1 + bp−1 + cp−1 ≡ 1, 2 or 3 (mod p). Therefore if
p is a prime divisor of ap−1 +bp−1 +cp−1 , then p equals 2 or 3. So if (a, b, c) is n-powerful
for all n ≥ 1, then the only primes which can divide a + b + c are 2 or 3.
We can proceed in a similar fashion to show that a + b + c is not divisible by 4 or 9.
Since
2 0 (mod 4), if p is even;
a ≡
1 (mod 4), if p is odd
and a, b, c aren’t all even, we have that a2 + b2 + c2 ≡ 1, 2 or 3 (mod 4).
By expanding (3k)3 , (3k + 1)3 and (3k + 2)3 , we find that a3 is congruent to 0, 1 or
−1 modulo 9. Hence
6 0 (mod 9), if 3 divides a;
a ≡
1 (mod 9), if 3 doesn’t divide a.
1. Let f (n, k) be the number of ways of distributing k candies to n children so that each child receives at most 2 candies.
For example, if n = 3, then f (3, 7) = 0, f (3, 6) = 1 and f (3, 4) = 6.
Determine the value of
f (2006, 1) + f (2006, 4) + f (2006, 7) + · · · + f (2006, 1000) + f (2006, 1003) .
Comment. Unfortunately, there was an error in the statement of this problem. It was intended that the sum should
continue to f (2006, 4012).
Solution 1. The number of ways of distributing k candies to 2006 children is equal to the number of ways of distributing
0 to a particular child and k to the rest, plus the number of ways of distributing 1 to the particular child and k − 1
to the rest, plus the number of ways of distributing 2 to the particular child and k − 2 to the rest. Thus f (2006, k) =
f (2005, k) + f (2005, k − 1) + f (2005, k − 2), so that the required sum is
1003
X
1+ f (2005, k) .
k=1
¡n¢
In evaluating f (n, k), suppose that there are r children who receive 2 candies; these r children can be chosen in r ways.
Then there are k − 2r candies from which at most one is given to each of n − r children. Hence
bk/2c µ ¶µ ¶ ∞ µ ¶µ ¶
X n n−r X n n−r
f (n, k) = = ,
r=0
r k − 2r r=0
r k − 2r
¡x¢
with y = 0 when x < y and when y < 0. The answer is
1003
XX ∞ µ ¶µ ¶ ∞ µ
X ¶ 1003 µ ¶
2005 2005 − r 2005 X 2005 − r
= .
r k − 2r r k − 2r
k=0 r=0 r=0 k=0
Solution 2. The desired number is the sum of the coefficients of the terms of degree not exceeding 1003 in the expansion
of (1 + x + x2 )2005 , which is equal to the coefficient of x1003 in the expansion of
Since the degree of every term in the expansion of the second member on the right exceeds 1003, we are looking for the
coefficient of x1003 in the expansion of the first member:
2005
X µ ¶ ∞ µ ¶
2005 3i X −2006 j
(1 − x3 )2005 (1 − x)−2006 = (−1)i x (−1)j x
i=0
i j=0
j
1
2005
XX ∞ µ ¶µ ¶
2005 2005 + j 3i+j
= (−1)i x
i=0 j=0
i j
∞ µ 2005
X X µ ¶µ ¶¶
2005 2005 + k − 3i
= (−1)i xk .
i=1
i 2005
k=0
2. Let ABC be an acute-angled triangle. Inscribe a rectangle DEF G in this triangle so that D is on AB, E is on AC
and both F and G are on BC. Describe the locus of (i.e., the curve occupied by) the intersections of the diagonals of all
possible rectangles DEF G.
Solution. The locus is the line segment joining the midpoint M of BC to the midpoint K of the altitude AH. Note that
a segment DE with D on AB and E on AC determines an inscribed rectangle; the midpoint F of DE lies on the median
AM , while the midpoint of the perpendicular from F to BC is the centre of the rectangle. This lies on the median M K of
the triangle AM H.
Conversely, any point P on M K is the centre of a rectangle with base along BC whose height is double the distance from
K to BC.
3. In a rectangular array of nonnegative real numbers with m rows and n columns, each row and each column contains at
least one positive element. Moreover, if a row and a column intersect in a positive element, then the sums of their elements
are the same. Prove that m = n.
Solution 1. Consider first the case where all the rows have the same positive sum s; this covers the particular situation
in which m = 1. Then each column, sharing a positive element with some row, must also have the sum s. Then the sum of
all the entries in the matrix is ms = ns, whence m = n.
We prove the general case by induction on m. The case m = 1 is already covered. Suppose that we have an m × n array
not all of whose rows have the same sum. Let r < m of the rows have the sum s, and each of the of the other rows have a
different sum. Then every column sharing a positive entry with one of these rows must also have sum s, and these are the
only columns with the sum s. Suppose there are c columns with sum s. The situation is essentially unchanged if we permute
the rows and then the column so that the first r rows have the sum s and the first c columns have the sum s. Since all
the entries of the first r rows not in the first c columns and in the first c columns not in the first r rows must be 0, we can
partition the array into a r × c array in which all rows and columns have sum s and which satisfies the hypothesis of the
problem, two rectangular arrays of zeros in the upper right and lower left and a rectangular (m − r) × (n − c) array in the
lower right that satisfies the conditions of the problem. By the induction hypothesis, we see that r = c and so m = n.
Solution 2. [Y. Zhao] Let the term in the ith row and the jth column of the array be denoted by aij , and let S = {(i, j) :
aij > 0}. Suppose that ri is the sum of the ith row and cj the sum of the jth column. Then ri = cj whenever (i, j) ∈ S.
Then we have that X aij X aij
{ : (i, j) ∈ S} = { : (i, j) ∈ S} .
ri cj
X aij X aij Xn m n µ ¶ n
1 X X 1 X
{ : (i, j) ∈ S} = { : 1 ≤ i ≤ m, 1 ≤ j ≤ n} = aij = cj = 1=n.
cj cj c
j=1 j i=1 j=1
cj j=1
Hence m = n.
2
Comment. The second solution can be made cleaner and more elegant by defining uij = aij /ri for all (i, j). When aij = 0,
then uij = 0. When aij > 0, then, by hypothesis, uij = aij /cj , a relation that in fact holds for all (i, j). We find that
n
X n
X
uij = 1 and uij = 1
j=1 i=1
for 1 ≤ i ≤ m and 1 ≤ j ≤ n, so that (uij ) is an m × n array whose row sums and column sums are all equal to 1. Hence
m µX
X n ¶ X n µX
X m ¶
m= uij = {uij : 1 ≤ i ≤ m, 1 ≤ j ≤ n} = uij =n
i=1 j=1 j=1 i=1
4. Consider a round-robin tournament with 2n + 1 teams, where each team plays each other team exactly once. We say
that three teams X, Y and Z, form a cycle triplet if X beats Y , Y beats Z, and Z beats X. There are no ties.
(a) Determine the minimum number of cycle triplets possible.
(b) Determine the maximum number of cycle triplets possible.
Solution 1. (a) The minimum is 0, which is achieved by a tournament in which team Ti beats Tj if and only if i > j.
(b) Any set of three teams constitutes either a cycle triplet or a¡ “dominated
¢ triplet” in which one team beats the other
two; let there be c of the former and d of the latter. Then c + d = 2n+1 . Suppose that team Ti beats xi other teams; then
¡ ¢ 3P
2n+1 ¡ ¢
it is the winning team in exactly x2i dominated triples. Observe that i=1 xi = 2n+1 2 , the total number of games. Hence
Xµ
2n+1
xi
¶ 2n+1
1 X 2 1 2n + 1
µ ¶
d= = xi − .
i=1
2 2 i=1 2 2
P2n+1 P2n+1
By the Cauchy-Schwarz Inequality, (2n + 1) i=1 x2i ≥ ( i=1 xi )2 = n2 (2n + 1)2 , whence
µ ¶ 2n+1
X µxi ¶ µ2n + 1¶ n2 (2n + 1) 1 µ2n + 1¶ n(n + 1)(2n + 1)
2n + 1
c= − ≤ − + = .
3 i=1
2 3 2 2 2 6
To realize the upper bound, let the teams be T1 = T2n+2 , T2 = T2n+3 . · · ·, Ti = T2n+1+i , · · ·, T2n+1 = T4n+2 . For
each i, let team Ti beat Ti+1 , Ti+2 , · · · , Ti+n and lose to Ti+n+1 , · · · , Ti+2n . We need to check that this is a consistent
assignment of wins and losses, since the result for each pair of teams is defined twice. This can be seen by noting that
(2n + 1 + i) − (i + j) = 2n + 1 − j ≥ n + 1 for 1 ≤ j ≤ n . The cycle triplets are (Ti , Ti+j , Ti+j+k ) where 1 ≤ j ≤ n and
(2n + 1 + i) − (i + j + k) ≤ n, i.e., when 1 ≤ j ≤ n and n + 1 − j ≤ k ≤ n. For each i, this counts 1 + 2 + · · · + n = 12 n(n + 1)
cycle triplets. When we range over all i, each cycle triplet gets counted three times, so the number of cycle triplets is
µ ¶
2n + 1 n(n + 1) n(n + 1)(2n + 1)
= .
3 2 6
Solution 2. [S. Eastwood] (b) Let t be the number of cycle triplets and u be the number of ordered triplets of teams
(X, Y, Z) where X beats Y and Y beats Z. Each cycle triplet generates three ordered triplets while other triplets generate
exactly one. The total number of triplets is µ ¶
2n + 1 n(4n2 − 1)
= .
3 3
The number of triples that are not cycle is
n(4n2 − 1)
−t .
3
Hence µ ¶
n(4n2 − 1)
u = 3t + −t =⇒
3
3
3u − n(4n2 − 1) u − (2n + 1)n2 n(n + 1)(2n + 1)
t= = + .
6 2 6
If team Y beats a teams and loses to b teams, then the number of ordered triples with Y as the central element is ab.
Since a + b = 2n, by the Arithmetic-Geometric Means Inequality, we have that ab ≤ n2. Hence u ≤ (2n + 1)n2, so that
n(n + 1)(2n + 1)
t≤ .
6
The maximum is attainable when u = (2n + 1)n2, which can occur when we arrange all the teams in a circle with each team
beating exactly the n teams in the clockwise direction.
Pn
Comment. Interestingly enough, the maximum is i=1 i2 ; is there a nice argument that gives the answer in this form?
5. The vertices of a right triangle ABC inscribed in a circle divide the circumference into three arcs. The right angle is
at A, so that the opposite arc BC is a semicircle while arc AB and arc AC are supplementary. To each of the three arcs, we
draw a tangent such that its point of tangency is the midpoint of that portion of the tangent intercepted by the extended
lines AB and AC. More precisely, the point D on arc BC is the midpoint of the segment joining the points D0 and D00 where
the tangent at D intersects the extended lines AB and AC. Similarly for E on arc AC and F on arc AB.
Prove that triangle DEF is equilateral.
Solution 1. A prime indicates where a tangent meets AB and a double prime where it meets AC. It is given that
DD0 = DD00 , EE 0 = EE 00 and F F 0 = F F 00 . It is required to show that arc EF is a third of the circumference as is arc
DBF .
AF is the median to the hypotenuse of right triangle AF 0 F 00 , so that F F 0 = F A and therefore
4
39th Canadian Mathematical Olympiad
Wednesday, March 28, 2007
Solution to 1. Identify ve subsets A; B; C; D; E of the board, where C consists of the squares occupied by the six dominos
already placed, B is the upper right corner, D is the lower left corner, A consists of the squares above and to the left of
those in B [ C [ D and E consists of the squares below and to the right of those in B [ C [ D. The board can be coloured
checkerboard fashion so that A has 13 black and 16 white squares, B a single white square, E 16 black and 13 white squares
and D a single black square. Each domino beyond the original six must lie either entirely in A [ B [ D or C [ B [ D, either of
which contains at most 14 dominos. Thus, altogether, we cannot have more that 2 14 + 6 = 34 dominos. This is achievable,
by placing 14 dominos in A [ D and 14 in E [ B .
Solution to 2. If the triangles are isosceles, then they must be congruent and the desired ratio is 1. For, if they share
equal side lengths, at least one of these side lengths on one triangle corresponds to the same length on the other. And if they
share unequal side lengths, then either equal sides correspond or unequal sides correspond in both directions and the ratio is
1. This falls within the bounds.
Let the triangles be scalene. It is not possible for the same length to be an extreme length (largest or smallest) of both
triangles. Therefore, we must have a situation in which the corresponding side lengths of the two triangles are (x; y; z ) and
(y; z; u) with x < y < z and y < z < u. We are given that y=x = z=y = u=z = r > 1. Thus, y = rx andpz = ry = r2 x. From
the triangle inequality z < x + y, we have that r2 < 1 + r. Since r2 r 1 < p 0 and r > 1, 1 < r < 12 ( 5 + 1). The ratio of
the dimensions from the smaller to the larger triangle is 1=r which satises 2 ( 5 1) < 1=r < 1. The result follows.
1
1
u,the equation t t 1 = u leads to the quadratic t2 ut 1 = 0 which has a positive discriminant and so a real solution.
Hence f (u) 0 for each real u.
Comment. The substitution v = y x, u = y + x whose inverse is x = 12 (u v), y = 12 (u + v) renders p the condition as
f ( (u
1
4
2
v )) + f (v ) f (u). The same strategy as in the foregoing solution leads to the choice u = 2 + v 2 + 4 and f (v ) 0
2
for all v.
Solution to 4 (b). It is straightforward to verify that a 1 = 1 for a 6= 1, so that once 1 is included in the list, it can never
by removed and so the list terminates with the single value 1.
Solution to 4 (a). There are several ways of approaching (a). It is important to verify that the set fx : 0 < x < 1g is
closed under the operation so that it is always dened.
If 0 < a; b < 1, then
a + b 2ab
0< <1:
1 ab
The left inequality follows from
a + b 2ab = a(1 b) + b(1 a) > 0
and the right from
a + b 2ab (1 a)(1 b)
1 = >0:
1 ab 1 ab
Hence, it will never happen that a set of numbers will contain a pair of reciprocals, and the operation can always be performed.
Solution 1. It can be shown by induction that any two numbers in any of the sets arise from disjoint subsets of S .
Use an induction argument on the number of entries that one starts with. At each stage the number of entries is reduced
by one. If we start with n numbers, the nal result is
1 22 + 33 + ( 1)n 1 nn
;
1 2 + 23 34 + + ( 1)n 1 (n 1)n
n
where i is the symmetric sum of all i i fold products of the n elements xi in the list.
Solution 2. Dene
a+b 2ab
ab= :
1 ab
This operation is commutative and also associative:
a+b+c 2(ab + bc + ca) + 3abc
a (b c) = (a b) c = :
1 (ab + bc + ca) + 2abc
Since the nal result amounts to a product of elements of S with some arrangement of brackets, the result follows.
Solution 3. Let (x) = x=(1 x) for 0 < x < 1. This is a one-one function from the open interval (0; 1) to the half line
(0; 1). For any numbers a; b 2 S , we have that
a+b 2ab a+b 2ab a+b 2ab
= ab) (a+b 2ab) = 1 a b+ab
1 ab (1
that
1 xy 1 1
f (x y ) = = + 1:
1 x y + xy 1 x 1 y
If f (x) > 1 and f (y) > 1, then also f (x y) > 1. It follows that if x and y lie in the open interval (0; 1), so does x y. We
also note that f (x) is a one-one function.
2
To each list L, we associate the function g(L) dened by
X
g ( L) = ff (x) : x 2 Lg :
Let Ln be the given list, and let the subsequent lists be Ln 1 ; Ln 2 ; ; L1 , where Li has i elements. Since f (x y) =
f (x) + f (y ) 1, g(Li ) = g(Ln ) (n i) regardless of the choice that creates each list from its predecessors. Hence
g (L1 ) = g (Ln ) (n 1) is xed. However, g(L1 ) = f (a) for some number a with 0 < a < 1. Hence a = f 1 (g(Ln ) (n 1))
is xed.
Solution to 5 (a). Let I be the incentre of triangle ABC . Since the quadrilateral AEIF has right angles at E and F , it
is concyclic, so that passes through I . Similarly, 2 and 3 pass through I , and (a) follows.
1
Solution to 5 (b). Let ! and I denote the incircle and incentre of triangle ABC , respectively. Observe that, since AI
bisects the angle F AE and AF = AE , then AI right bisects the segment F E . Similarly, BI right bisects DF and CI right
bisects DE .
We invert the diagram through !. Under this inversion, let the image of A be A0 , etc. Note that the centre I of inversion
is collinear with any point and its image under the inversion. Under this inversion, the image of 1 is EF , which makes A0
the midpoint of EF . Similarly, B 0 is the midpoint of DF and C 0 is the midpoint of DE . Hence, 0 , the image of under
this inversion, is the circumcircle of triangle A0 B 0 C 0 , which implies that 0 is the nine-point circle of triangle DEF .
Since P is the intersection of and 1 other than A, P 0 is the intersection of 0 and EF other than A0 , which means
that P 0 is the foot of the altitude from D to EF . Similarly, Q0 is the foot of the altitude from E to DF and R0 is the foot
of the altitude from F to DE .
Now, let X , Y and Z be the midpoints of arcs BC , AC and AB on respectively. We claim that X lies on P D.
Let X 0 be the image of X under the inversion, so I , X and X 0 are collinear. But X is the midpoint of arc BC , so A,
A0 , I , X 0 and X are collinear. The image of line P D is the circumcircle of triangle P 0 ID, so to prove that X lies on P D, it
suces to prove that points P 0 , I , X 0 and D are concyclic.
We know that B 0 is the midpoint of DF , C 0 is the midpoint of DE and P 0 is the foot of the altitude from D to EF .
Hence, D is the re
ection of P 0 in B 0 C 0 .
Since IA0 ? EF , IB 0 ? DF and IC 0 ? DE , I is the orthocentre of triangle A0 B 0 C 0 . So, X 0 is the intersection of the
altitude from A0 to B 0 C 0 with the circumcircle of triangle A0 B 0 C 0 . From a wellknown fact, X 0 is the re
ection of I in B 0 C 0 .
This means that B 0 C 0 is the perpendicular bisector of both P 0 D and IX 0 , so that the points P 0 , I , X 0 and D are concyclic.
Hence, X lies on P D. Similarly, Y lies on QE and Z lies on RF . Thus, to prove that P D, QE and RF are concurrent,
it suces to prove that DX , EY and F Z are concurrent.
To show this, consider tangents to at X , Y and Z . These are parallel to BC , AC and AB , respectively. Hence, the
triangle that these tangents dene is homothetic to the triangle ABC . Let S be the centre of homothety. Then the
homothety taking triangle ABC to takes ! to , and so takes D to X , E to Y and F to Z . Hence DX , EY and F Z
concur at S .
Comment. The solution uses the following result: Suppose ABC is a triangle with orthocentre H and that AH intersects
BC at P and the circumcircle of ABC at D. Then HP = P D. The proof is straightforward: Let BH meet AC at Q. Note
that AD ? BC and BQ ? AC . Since \ACB = \ADB ,
\HBC = \QBC = 90 \QCB = 90 \ACB = 90 \ADB = \DBP ;
from which follows the congruence of triangle HBP and DBP and equality of HP and P D.
Solution 2. (a) Let 2 and 3 intersect at J . Then BDJF and CDJE are concyclic. We have that
3
Let O be the centre of circle , and U , V , W be the respective midpoints of the minor arc BC , CA, AB on this circle,
so that P U contains D, QV contains E and RW contains F . It is required to prove that DU , EV and F W are concurrent.
Since ID and OU are perpendicular to BC , IDkOU . Similarly, IE kOV and IF kOW . Since jIDj = jIE j = jIF j = r (the
inradius) and jOU j = jOV j = jOW j = R (the circumradius), a translation IO ! followed by a dilatation of factor R=r takes
triangle DEF to triangle U V W , so that these triangles are similar with corresponding sides parallel.
Suppose that EV and F W intersect at K and that DU and F W intersect at L. Taking account of the similarity of the
triangles KEF and KV W , LDF and LU W , DEF and U V W , we have that
KF : F W = EF : V W = DF : U W = LF : LW ;
so that K = L and the lines DU , EV and F W intersect in a common point K , as desired.
4
Report - Fortieth Canadian Mathematical Olympiad 2008
3. Let a, b, c be [M
positive
P C] =real
[M numbers for which
AC] + [CAP ] = [MaAC]
+ b+
+ [CAD]
c = 1. Prove that = [BM C]
= [M ADC]
a − bc b − ca c − ab 3
whence BM = M P . Similarly BN = N Q, so that
+ MN + ≤ of. triangle BP Q and must bisect BD.
is a midline
a + bc b + ca c + ab 2
2.4.Determine
Determineall
allfunctions
functions ff defined on the
defined on the natural
set of rationals
numbersthat
that take
take rational valuesthe
values among fornatural
which numbers
for which
f (2f
(f (x)
(n)) p + f (y)) = 2x + y
≡n mod f (p)
for all n ∈ N and all prime numbers p.
for each x and y.
5. A self-avoiding rook walk on a chessboard (a rectangular grid of unit squares) is a path traced by
Solution 1. The
a sequence only solutions
of moves parallel toarean
f (x) = xoffor
edge theallboard
rational x and
from (x) =
one funit −x for
square toall rationalsuch
another, x. Both
that of
these each
readily check out.
begins where the previous move ended and such that no move ever crosses a square that has
Setting y = been
previously x yields f (3f (x))
crossed, i.e., = 3xrook’s
the for allpath
rational x. Now replacing x by 3f (x), we find that
is non-self-intersecting.
f (u + v) = f (u) + f (v)
f (u + v) = f (u) + f (v)
Report - Fortieth Canadian Mathematical Olympiad 2008
for each rational pair (u, v).
Since 0 = f (0) = f (−1) + f (1), f (−1) = −f (1). By induction, it can be established that for each intger
n and rational x, f (nx) = nf (x). If k = f (1), we can establish from this that f (n) = nk, f (1/n) = k/n and
f (m/n) = mk/n for each integer pair (m, n). Thus f (x) = kx for all rational x. Since f (f (x)) = x, we must
have k2 = 1. Hence f (x) = x or f (x) = −x. These check out.
x = y = 2f (z) + f (w)
a + bc = a(a + b + c) + bc = (a + b)(a + c)
and that a + b = 1 − c, with analogous relations for other permutations of the variables. Then
Putting the left side of the desired inequality over a common denominator, we find that it is equal to
(a − bc)(1 − a) + (b − ac)(1 − b) + (c − ab)(1 − c) (a + b + c) − (a2 + b2 + c2) − (bc + ca + ab) + 3abc
=
(b + c)(c + a)(a + b) (b + c)(c + a)(a + b)
1 − (a + b + c)2 + (bc + ca + ab) + 3abc
=
(ab + bc + ca) − abc
(bc + ca + ab) + 3abc
=
(bc + bc + ab) − abc
4abc
=1+ .
a + bc = a(a + b + c) + bc = (a + b)(a + c)
and that a + b = 1 − c, with analogous relations for other permutations of the variables. Then
whence 4abc/[(a + b)(b + c)(c + a)] ≤ 21 . The desired2result follows. Equality occurs exactly when a = b =
c = 31 .
4. Find all functions f defined on the natural numbers that take values among the natural numbers for
which
(f (n))p ≡ n mod f (p)
Solution. The substitution n = p, a prime, yields p ≡ (f (p))p ≡ 0 (mod f (p)), so that p is divisible by
f (p). Hence, for each prime p, f (p) = 1 or f (p) = p.
Let S = {p : p is prime and f (p) = p}. If S is infinite, then f (n)p ≡ n (mod p) for infinitely many
primes p. By the little Fermat theorem, n ≡ f (n)p ≡ f (n), so that f (n) − n is a multiple of p for infinitely
many primes p. This can happen only if f (n) = n for all values of n, and it can be verified that this is a
solution.
If S is empty, then f (p) = 1 for all primes p, and any function satisfying this condition is a solution.
Now suppose that S is finite and non-empty. Let q be the largest prime in S. Suppose, if possible, that
q ≥ 3. Therefore, for any prime p exceeding q, p ≡ 1 (mod q). However, this is not true. Let Q be the
product of all the odd primes up to q. Then Q + 2 must have a prime factor exceeding q and at least one
of them must be incongruent to 1 (mod q). (An alternative argument notes that Bertrand’s postulate can
turn up a prime p between q and 2q which fails to satisfy p ≡ 1 mod q.)
The only remaining case is that S = {2}. Then f (2) = 2 and f (p) = 1 for every odd prime p. Since
f (n)2 ≡ n (mod 2), f (n) and n must have the same parity. Conversely, any function f for which f (n) ≡ n
(mod 2) for all n, f (2) = 2 and f (p) = 1 for all odd primes p satisfies the condition.
Therefore the only solutions are
• f (n) = n for all n ∈ N;
• any function f with f (p) = 1 for all primes p;
• any function for which f (2) = 2, f (p) = 1 for primes p exceeding 2 and f (n) and n have the same
parity.
5. A self-avoiding rook walk on a chessboard (a rectangular grid of squares) is a path traced by a sequence
of rook moves parallel to an edge of the board from one unit square to another, such that each begins
where the previous move ended and such that no move ever crosses a square that has previously been
crossed, i.e., the rook’s path is non-self-intersecting.
Let R(m, n) be the number of self-avoiding rook walks on an m × n (m rows, n columns) chessboard
which begin at the lower-left corner and end at the upper-left corner. For example, R(m, 1) = 1 for all
natural numbers m; R(2, 2) = 2; R(3, 2) = 4; R(3, 3) = 11. Find a formula for R(3, n) for each natural
number n.
Solution 1. Let rn = R(3, n). It can be checked directly that r1 = 1 and r2 = 4. Let 1 ≤ i ≤ 3 and
1 ≤ j; let (i, j) denote the cell in the ith row from the bottom and the jth column from the left, so that the
paths in question go from (1, 1) to (3, 1).
5. A self-avoiding rook walk on a chessboard (a rectangular grid of squares) is a path traced by a sequence
of rook moves parallel to an edge of the board from one unit square to another, such that each begins
where the previous move ended and such that no move ever crosses a square that has previously been
crossed, i.e., the rook’s path is non-self-intersecting.
Report -ofFortieth
Let R(m, n) be the number Canadian
self-avoiding rook Mathematical
walks on an mOlympiad 2008n columns) chessboard
× n (m rows,
which begin at the lower-left corner and end at the upper-left corner. For example, R(m, 1) = 1 for all
natural numbers m; R(2, 2) = 2; R(3, 2) = 4; R(3, 3) = 11. Find a formula for R(3, n) for each natural
number n.
Solution 1. Let rn = R(3, n). It can be checked directly that r1 = 1 and r2 = 4. Let 1 ≤ i ≤ 3 and
1 ≤ j; let (i, j) denote the cell in the ith row from the bottom and the jth column from the left, so that the
paths in question go from (1, 1) to (3, 1).
Suppose that n ≥ 3. The rook walks fall into exactly one of the following six categories:
(1) One walk given by (1, 1) → (2, 1) → (3, 1).
(2) Walks that avoid the cell (2, 1): Any such walk must start with (1, 1) → (1, 2) and finish with (3, 2) →
(3, 1); there are rn−1 such walks.
(3) Walks that begin with (1, 1) → (2, 1) → (2, 2) and never return to the first row: Such walks enter the
third row from (2, k) for some k with 2 ≤ k ≤ n and then go along the third row leftwards to (3, 1); there
are n − 1 such walks.
(4) Walks that begin with (1, 1) → (2, 1) → · · · → (2, k) → (1, k) → (1, k + 1) and end with (3, k + 1) →
(3, k) → (3, k − 1) → · · · → (3, 2) → (3, 1) for some k3with 2 ≤ k ≤ n − 1; there are rn−2 + rn−3 + · · · + r1
such walks.
(5) Walks that are the horizontal reflected images of walks in (3) that begin with (1, 1) → (2, 1) and never
enter the third row until the final cell; there are n − 1 such walks.
(6) Walks that are horizontal reflected images of walks in (5); there are rn−2 + rn−3 + · · · + r1 such walks.
Thus, r3 = 1 + r2 + 2(2 + r1 ) = 11 and, for n ≥ 3,
and
rn+1 = 2n + 1 + rn + 2(rn−1 + rn−2 + · · · + r1 ) .
Therefore
rn+1 − rn = 2 + rn + rn−1 =⇒ rn+1 = 2 + 2rn + rn−1 .
Thus
rn+1 + 1 = 2(rn + 1) + (rn−1 + 1) ,
whence
1 √ 1 √
rn + 1 = √ (1 + 2)n+1 − √ (1 − 2)n+1 ,
2 2 2 2
and
1 √ 1 √
rn = √ (1 + 2)n+1 − √ (1 − 2)n+1 − 1 .
2 2 2 2
Solution 2. Employ the same notation as in Solution 1. We have that r1 = 1, r2 = 4 and r3 = 11. Let
n ≥ 3. Consider the situation that there are rn+1 columns. There are basically three types of rook walks.
Type 1. There are four rook walks that enter only the first two columns.
Type 2. There are 3rn−1 rooks walks that do not pass between the second and third columns in the
middle row (in either direction), viz. rn−1 of each of the types:
Type 3. Consider the rook walks that pass between the second and third column along the middle row.
They are of Type 3a:
or Type 3b:
(1, 1) −→ (1, 2) −→ (1, 3) −→ · · · −→ (2, 3) −→ (2, 2) −→ ∗ −→ (3, 1) ,
where in each case the asterisk stands for one of two possible options.
(1, 1) −→ (1, 2) −→ (1, 3) −→ · · · −→ (3, 3) −→ (3, 2) −→ (3, 1) ;
or Type 3b:
(1, 1) −→ (1, 2) −→ (1, 3) −→ · · · −→ (2, 3) −→ (2, 2) −→ ∗ −→ (3, 1) ,
where in each case the asterisk stands for one of two possible options.
We can associate in a two-one way the walks of Type 3a to a rook walk on the last n columns, namely
and the walks of Type 3b to a rook walk on the last n columns, namely
4
The number of rook walks of the latter two types together is rn − 1 − rn−1 . From the number of rook walks
on the last n columns, we subtract one for (1, 2) → (2, 2) → (3, 2) and rn−1 for those of the type
Therefore, the number of rook walks of Type 3 is 2(rn − 1 − rn−1 ) and we find that
Solution 3. Let S(3, n) be the set of self-avoiding rook walks in which the rook occupies column n but
does not occupy column n + 1. Then R(3, n) = |S(3, 1)| + |S(3, 2)| + · · · + |S(3, n)|. Furthermore, topological
considerations allow us to break S(3, n) into three disjoint subsets S1 (3, n), the set of paths in which corner
(1, n) is not occupied, but there is a path segment (2, n) −→ (3, n); S2 (3, n), the set of paths in which corners
(1, n) and (3, n) are both occupied by a path (1, n) −→ (2, n) −→ (3, n); and S3 (3, n), the set of paths in
which corner (3, n) is not occupied but there is a path segment (1, n) −→ (2, n). Let si (n) = |Si (3, n)| for
i = 1, 2, 3. Note that s1 (1) = 0, s2 (1) = 1 and s3 (1) = 0. By symmetry, s1 (n) = s3 (n) for every positive n.
Furthermore, we can construct paths in S(3, n + 1) by “bulging” paths in S(3, n), from which we obtain
s1 (n + 1) = s1 (n) + s2 (n) ;
s2 (n + 1) = s1 (n) + s2 (n) + s3 (n) ;
s3 (n + 1) = s2 (n) + s3 (n) ;
We find that
1 √ 1 √
s1 (n) = √ (1 + 2)n−1 − √ (1 − 2)n−1 ;
2 2 2 2
1 √ n−1 1 √
s2 (n) = (1 + 2) + (1 − 2)n−1 .
2 2
Summing a geometric series yields that 10
We find that
1 √ 1 √
s1 (n) = √ (1 + 2)n−1 − √ (1 − 2)n−1 ;
2 2 2 2
1 √ n−1 1 √
s2 (n) = (1 + 2) + (1 − 2)n−1 .
2 2
Summing a geometric series yields that
Acknowledgment. The first two solutions are due to Man-Duen Choi, and the third to Ed Doolittle.
11
Report - Forty First Canadian Mathematical Olympiad 2009
Problem 1. Given an m × n grid with squares coloured either black or white, we say
that a black square in the grid is stranded if there is some square to its left in the same
row that is white and there is some square above it in the same column that is white (see
Figure).
Find a closed formula for the number of 2 × n grids with no stranded black squares.
Solution. There is no condition for squares in the first row. A square in the second row
can be black only if the square above it is black or all squares to the left of it are black.
Suppose the first k squares in the second row are black and the (k + 1)-st square is white
or k = n. When k < n then for each of the first k + 1 squares in the first row we have 2
choices, and for each of the remaining n − k − 1 columns we have 3 choices. When k = n,
there are 2n choices for the first row. The total number of choices is thus:
n−1
2k+1 3n−k−1 + 2n .
k=0
This expression simplifies to
2 · 3n − 2n .
Report - Forty First Canadian Mathematical Olympiad 2009
Problem 2. Two circles of different radii are cut out of cardboard. Each circle is subdi-
vided into 200 equal sectors. On each circle 100 sectors are painted white and the other
100 are painted black. The smaller circle is then placed on top of the larger circle, so that
their centers coincide. Show that one can rotate the small circle so that the sectors on
the two circles line up and at least 100 sectors on the small circle lie over sectors of the
same color on the big circle.
Report - Forty First Canadian Mathematical Olympiad 2009
2 CANADIAN
CANADIAN MATHEMATICAL
MATHEMATICAL OLYMPIAD
OLYMPIAD 2009 2009 SOLUTIONS
SOLUTIONS 3
Problem
Problem 2. 3. Two
Define circles of different radii are cut out of cardboard. Each circle is subdi-
vided into 200 equal sectors. On each(xy + yz
circle 100+ zx)(x
sectors+arey +painted
z) white and the other
f (x, y, z) = .
100 are painted black. The smaller circle(xis + then
y)(xplaced
+ z)(yon+topz) of the larger circle, so that
their
Determine the set of real numbers r for which there exists circle
centers coincide. Show that one can rotate the small so that
a triplet (x, y,the
z) sectors on
of positive
the
realtwo circlessatisfying
numbers line up and f (x,aty,least
z) = 100
r. sectors on the small circle lie over sectors of the
same color on the big circle.
Solution. We prove that 1 < f (x, y, z) ≤ 98 , and that f (x, y, z) can take on any value
Solution.
within the Let x0 ,(1,
range . . .9,].x199 be variables. Assign the value of +1 or −1 to xi depending on
8
whether the (i +for
The expression 1)st segment
f (x, y, z) can of the larger circle
be simplified to (counting counterclockwise) is black or
white, respectively. Similarly, assign the value of +1 xyzor −1 to the variable yi depending
f (x,
on whether the (i + 1)th segment of the (x y, z) = 1 + smaller .
+ y)(xcircle+ z)(y is +
black
z) or white. We can now
restate the problem in the following equivalent way: show that
Since x, y, z are positive, we get 1 < f (x, 200
y, z).
The inequality f (x, y, z) ≤ 98 can be simplified to
Sj = xi yi+j ≥ 0 ,
x2 y + x2 z + y 2 x + i=1 y 2 z + z 2 x + z 2 y − 6xyz ≥ 0.
for some j =
Rearrange 0, left
the . . . , hand
199. Here side as thefollows:
subscript i + j is understood modulo 200.
Now observe that2 y0 + ·2· · + y2199 = 02 and 2thus 2
x y + x z + y x + y z + z x + z y − 6xyz =
199
x(y 2 +Sz02+ ) −· ·2xyz
· + S199 = + x
+ y(x 2
z 2i (y
)− 2xyz + z(x2 + y 2 ) − 2xyz =
0 + · · · + y199 ) = 0 .
x(y − z)2 + y(x − z)2 + z(x I=0 − y) .
2
Thus
This S j ≥ 0 for some
expression is clearly j = non-negative
0, . . . , 199, as when
claimed. x, y, z are non-negative.
9
To prove that f (x, y, z) takes any values in the interval (1, 8 ], define
t
g(t) = f (t, 1, 1) = 1 + .
2(1 + t)2
Then g(1) = 98 and g(t) approaches 1 as t approaches 0. It follows from the continuity
of g(t) for 0 < t ≤ 1 that it takes all values in the interval (1, 98 ]. (Alternatively, one
can check that the quadratic equation g(t) = r has a solution t for any number r in the
interval (1, 98 ].)
Report - Forty First Canadian Mathematical Olympiad 2009
Problem 4. Find all ordered pairs (a, b) such that a and b are integers and 3a + 7b is a
perfect square.
10
Report - Forty First Canadian Mathematical Olympiad 2009
Problem 2. Two circles of different radii are cut out of cardboard. Each circle is subdi-
Problem 5. A set of points is marked on the plane, with the property that any three
vided into 200 equal sectors. On each circle 100 sectors are painted white and the other
marked points can be covered with a disk of radius 1. Prove that the set of all marked
100 are painted black. The smaller circle is then placed on top of the larger circle, so that
points can be covered with a disk of radius 1.
their centers coincide. Show that one can rotate the small circle so that the sectors on
the two circles line up and at least 100 sectors on the small circle lie over sectors of the
Solution. (For a finite set of points only.) Let D be a disk of smallest radius that covers
same color on the big circle.
all marked points. Consider the marked points on the boundary C of this disk. Note that
if all marked points on C lie on an arc smaller than the half circle (ASTTHC for short),
Solution. Let x0 , . . . , x199 be variables. Assign the value of +1 or −1 to xi depending on
then the disk can be moved a little towards these points on the boundary and its radius
whether the (i + 1)st segment of the larger circle (counting counterclockwise) is black or
can be decreased. Since we assumed that our disk has minimal radius, the marked points
white, respectively. Similarly, assign the value of +1 or −1 to the variable yi depending
on its boundary do not lie on an ASTTHC.
on whether the (i + 1)th segment of the smaller circle is black or white. We can now
If the two endpoints of a diagonal of D are marked, then D is the smallest disk containing
restate the problem in the following equivalent way: show that
these two points, hence must have radius at most 1.
200
If there are 3 marked points on C that do not lie on an ASTTHC, then D is the smallest
disk covering these 3 points and hence must S j = xi yi+j ≥ 0radius
have , at most 1. (In this case the
i=1
triangle formed by the three points is acute and C is its circumcircle.)
for some are
If there j =more
0, . . .than
, 199.3 Here
marked the points
subscript i + boundary
on the j is understood
that domodulo
not lie200.
on an ASTTHC,
Now observe that
then we can remove y + · · · +
0 one of themy 199 = 0 and thus
so that the remaining points again do not lie on an
ASTTHC. By induction this leads us to 199the case of 3 points. Indeed, given 4 or more
11
CANADIAN MATHEMATICAL OLYMPIAD 2010
PROBLEMS AND SOLUTIONS
(1) For a positive integer n, an n-staircase is a figure consisting of unit squares, with
one square in the first row, two squares in the second row, and so on, up to n
squares in the nth row, such that all the left-most squares in each row are aligned
vertically. For example, the 5-staircase is shown below.
Let f (n) denote the minimum number of square tiles required to tile the n-
staircase, where the side lengths of the square tiles can be any positive integer.
For example, f (2) = 3 and f (4) = 7.
1
Next, consider the left-most unit square in the fourth row. The only square tile
that can cover this unit square and a diagonal square is a 4 × 4 square tile.
Continuing this construction, we see that the side lengths of the square tiles
we encounter will be 1, 2, 4, and so on, up to 2k for some nonnegative integer k.
Therefore, n, the height of the n-staircase, is equal to 1+2+4+· · ·+2k = 2k+1 −1.
Alternatively, n = 2k − 1 for some positive integer k. Let p(k) = 2k − 1.
Conversely, we can tile a p(k)-staircase with p(k) square tiles recursively as
follows: We have that p(1) = 1, and we can tile a 1-staircase with 1 square tile.
Assume that we can tile a p(k)-staircase with p(k) square tiles for some positive
integer k.
Consider a p(k + 1)-staircase. Place a 2k × 2k square tile in the bottom left
corner. Note that this square tile covers a digaonal square. Then p(k + 1) − 2k =
2k+1 − 1 − 2k = 2k − 1 = p(k), so we are left with two p(k)-staircases.
p(k)
2k
2k p(k)
Furthermore, these two p(k)-staircases can be tiled with 2p(k) square tiles, which
means we use 2p(k) + 1 = p(k + 1) square tiles.
Therefore, f (n) = n if and only if n = 2k − 1 = p(k) for some positive integer
k. In other words, the binary representation of n consists of all 1s, with no 0s.
(b) Let n be a positive integer such that f (n) = n + 1, and consider a minimal
tiling of an n-staircase. Since there are n diagonal squares, every square tile
except one covers a diagonal square. We claim that the square tile that covers
the bottom-left unit square must be the square tile that does not cover a diagonal
square.
If n is even, then this fact is obvious, because the square tile that covers the
bottom-left unit square cannot cover any diagonal square, so assume that n is odd.
Let n = 2m + 1. We may assume that n > 1, so m ≥ 1. Suppose that the square
tile covering the bottom-left unit square also covers a diagonal square. Then the
side length of this square tile must be m + 1. After this (m + 1) × (m + 1) square
tile has been placed, we are left with two m-staircases.
2
m
m+1
m+1 m
Hence, f (n) = 2f (m) + 1. But 2f (m) + 1 is odd, and n + 1 = 2m + 2 is even,
so f (n) cannot be equal to n + 1, contradiction. Therefore, the square tile that
covers the bottom-left unit square is the square tile that does not cover a diagonal
square.
Let t be the side length of the square tile covering the bottom-left unit square.
Then every other square tile must cover a diagonal square, so by the same con-
struction as in part (a), n = 1 + 2 + 4 + · · · + 2k−1 + t = 2k + t − 1 for some positive
integer k. Furthermore, the top p(k) = 2k − 1 rows of the n-staircase must be tiled
the same way as the minimal tiling of a p(k)-staircase. Therefore, the horizontal
line between rows p(k) and p(k) + 1 does not pass through any square tiles. Let
us call such a line a fault line. Similarly, the vertical line between columns t and
t + 1 is also a fault line. These two fault lines partition two p(k)-staircases.
p(k)
t p(k)
Hence, assume that the two p(k)-staircases do overlap. The intersection of the
two p(k)-staircases is a [p(k) − t]-staircase. Since this [p(k) − t]-staircase is tiled
the same way as the top p(k) − t rows of a minimal tiling of a p(k)-staircase,
p(k) − t = p(l) for some positive integer l < k, so t = p(k) − p(l). Then
(2) Let A, B, P be three points on a circle. Prove that if a and b are the distances
from P to the tangents at A and B and c is the distance from P to the chord AB,
then c2 = ab.
Solution. Let r be the radius of the circle, and let a’ and b’ be the respective
lengths of P A and P B. Since b0 = 2r sin ∠P AB = 2rc/a0 , c = a0 b0 /(2r). Let AC
be the diameter of the circle and H the foot of the perpendicular from P to AC.
The similarity of the triangles ACP and AP H imply that AH : AP = AP : AC
or (a0 )2 = 2ra. Similarly, (b0 )2 = 2rb. Hence
(a0 )2 (b0 )2
c2 = = ab
2r 2r
as desired.
(3) Three speed skaters have a friendly race on a skating oval. They all start from
the same point and skate in the same direction, but with different speeds that
they maintain throughout the race. The slowest skater does 1 lap a minute, the
fastest one does 3.14 laps a minute, and the middle one does L laps a minute for
some 1 < L < 3.14. The race ends at the moment when all three skaters again
come together to the same point on the oval (which may differ from the starting
4
point.) Find how many different choices for L are there such that 117 passings
occur before the end of the race. (A passing is defined when one skater passes
another one. The beginning and the end of the race when all three skaters are at
together are not counted as a passing.)
Solution. Assume that the length of the oval is one unit. Let x(t) be the
difference of distances that the slowest and the fastest skaters have skated by time
t. Similarly, let y(t) be the difference between the middle skater and the slowest
skater. The path (x(t), y(t)) is a straight ray R in R2 , starting from the origin,
with slope depending on L. By assumption, 0 < y(t) < x(t).
One skater passes another one when either x(t) ∈ Z, y(t) ∈ Z or x(t) − y(t) ∈ Z.
The race ends when both x(t), y(t) ∈ Z.
Let (a, b) ∈ Z2 be the endpoint of the ray R. We need to find the number of
such points satisfying:
(a) 0 < b < a
(b) The ray R intersects Z2 at endpoints only.
(c) The ray R crosses 357 times the lines x ∈ Z, y ∈ Z, y − x ∈ Z.
The second condition says that a and b are relatively prime. The ray R crosses
a − 1 of the lines x ∈ Z, b − 1 of the lines y ∈ Z and a − b − 1 of the lines x − y ∈ Z.
Thus, we need (a − 1) + (b − 1) + (a − b − 1) = 117, or equivalently, 2a − 3 = 117.
That is a = 60.
Now b must be a positive integer less than and relatively prime to 60. The
number of such b can be found using the Euler’s φ function:
φ(60) = φ(22 · 3 · 5) = (2 − 1) · 2 · (3 − 1) · (5 − 1) = 16.
Thus the answer is 16.
Alternate Solution. First, let us name our skaters. From fastest to slowest,
call them: A, B and C. (Abel, Bernoulli and Cayley?)
Now, it is helpful to consider the race from the viewpoint of C. Relative to C,
both A and B complete a whole number of laps, since they both start and finish
at C.
Let n be the number of laps completed by A relative to C, and let m be the
number of laps completed by B relative to C. Note that: n > m ∈ Z+
Consider the number of minutes required to complete the race. Relative to C,
A is moving with a speed of 3.14 − 1 = 2.14 laps per minute and completes the
n
race in 2.14 minutes. Also relative to C, B is moving with a speed of (L − 1) laps
m
per minute and completes the race in L−1 minutes. Since A and B finish the race
together (when they both meet C):
n m m
= ⇒ L = 2.14 + 1.
2.14 L−1 n
Hence, there is a one-to-one relation between values of L and values of the postive
proper fraction mn
. The fraction should be reduced, that is the pair (m, n) should
5
be relatively prime, or else, with k = gcd(m, n), the race ends after n/k laps for
A and m/k laps for B when they first meet C together.
It is also helpful to consider the race from the viewpoint of B. In this frame
of reference, A completes only n − m laps. Hence A passes B only (n − m) − 1
times, since the racers do not ”pass” at the end of the race (nor at the beginning).
Similarily A passes C only n − 1 times and B passes C only m − 1 times. The
total number of passings is:
117 = (n − 1) + (m − 1) + (n − m − 1) = 2n − 3 ⇒ n = 60
m
Hence the number of values of L equals the number of m for which the fraction 60 is
positive, proper and reduced. That is the number of positive integer values smaller
than and relatively prime to 60. One could simply count: {1,7,11,13,17,...}, but
Euler’s φ function gives this number:
φ(60) = φ(22 · 3 · 5) = (2 − 1) · 2 · (3 − 1) · (5 − 1) = 16.
Therefore, there are 16 values for L which give the desired number of passings.
Note that the actual values for the speeds of A and C do not affect the result.
They could be any values, rational or irrational, just so long as they are different,
and there will be 16 possible values for the speed of B between them.
(4) Each vertex of a finite graph can be colored either black or white. Initially all
vertices are black. We are allowed to pick a vertex P and change the color of P
and all of its neighbours. Is it possible to change the colour of every vertex from
black to white by a sequence of operations of this type?
(5) Let P (x) and Q(x) be polynomials with integer coefficients. Let an = n! + n.
Show that if P (an )/Q(an ) is an integer for every n, then P (n)/Q(n) is an integer
for every integer n such that Q(n) 6= 0.
7
43rd Canadian Mathematical Olympiad
Wednesday, March 23, 2011
Solution. Assume the contrary: there exist a and b of the prescribed form, such that
b ≥ a and a divides b. Then a divides b − a.
Claim: a is not divisible by 3 but b − a is divisible by 9. Indeed, the sum of the digits
is 10(1 + · · · + 7) = 280, for both a and b. [Here one needs to know or prove that an
integer n is equivalent of the sum of its digits modulo 3 and modulo 9.]
We conclude that b − a is divisible by 9a. But this is impossible, since 9a has 71 digits
and b has only 70 digits, so 9a > b > b − a. ¤
(2) Let ABCD be a cyclic quadrilateral whose opposite sides are not parallel, X the inter-
section of AB and CD, and Y the intersection of AD and BC. Let the angle bisector
of ∠AXD intersect AD, BC at E, F respectively and let the angle bisector of ∠AY B
intersect AB, CD at G, H respectively. Prove that EGF H is a parallelogram.
1
(3) Amy has divided a square up into finitely many white and red rectangles, each with sides
parallel to the sides of the square. Within each white rectangle, she writes down its width
divided by its height. Within each red rectangle, she writes down its height divided by
its width. Finally, she calculates x, the sum of these numbers. If the total area of the
white rectangles equals the total area of the red rectangles, what is the smallest possible
value of x?
Solution. Let ai and bi denote the width and height of each white rectangle, and let
ci and di denote the width and height of each red rectangle. Also, let L denote the side
length of the original square.
P P
Lemma: Either ai ≥ L or di ≥ L.
Proof of lemma: Suppose there exists a horizontal line across the square that is
covered entirely with white rectangles. Then, the total width of these rectangles is at
least L, and the claim is proven. Otherwise, there is a red rectangle intersecting every
horizontal line, and hence the total height of these rectangles is at least L. ¤
P
Now, let us assume without loss of generality that ai ≥ L. By the Cauchy-Schwarz
inequality,
µX ¶ ³X ´ ³X ´2
ai
· ai bi ≥ ai
bi
≥ L2 .
P L2 P ai
But we know ai bi = 2 , so it follows that bi ≥ 2. Furthermore, each ci ≤ L, so
X di 1 X 1
≥ 2
· ci di = .
ci L 2
Therefore, x is at least 2.5. Conversely, x = 2.5 can be achieved by making the top half
of the square one colour, and the bottom half the other colour. ¤
(4) Show that there exists a positive integer N such that for all integers a > N , there exists
a contiguous substring of the decimal expansion of a that is divisible by 2011. (For
instance, if a = 153204, then 15, 532, and 0 are all contiguous substrings of a. Note that
0 is divisible by 2011.)
Solution. We claim that if the decimal expansion of a has at least 2012 digits, then
a contains the required substring. Let the decimal expansion of a be ak ak−1 . . . a0 . For
i = 0, . . . , 2011, Let bi be the number with decimal expansion ai ai−1 . . . a0 . Then by
pidgenhole principle, bi ≡ bj mod 2011 for some i < j ≤ 2011. It follows that 2011
divides bj − bi = c · 10i . Here c is the substring aj . . . ai+1 . Since 2011 and 10 are
relatively prime, it follows that 2011 divides c. ¤
2
(5) Let d be a positive integer. Show that for every integer S, there exists an integer n > 0
and a sequence ²1 , ²2 , . . . , ²n , where for any k, ²k = 1 or ²k = −1, such that
S = ²1 (1 + d)2 + ²2 (1 + 2d)2 + ²3 (1 + 3d)2 + · · · + ²n (1 + nd)2 .
3
Sun Life Financial Canadian Mathematical Olympiad
x2 ≥ 4x − 4, y 2 ≥ 4y − 4, and z 2 ≥ 4z − 4,
and therefore
2. For any positive integers n and k, let L(n, k) be the least common multiple of the
k consecutive integers n, n + 1, . . . , n + k − 1. Show that for any integer b, there
exist integers n and k such that L(n, k) > b L(n + 1, k).
L(m! − 1, m + 1) m! − 1
≥ .
L(m!, m + 1) (m − 1)! + 1
II. Note that the angle bisectors ∠ACB and ∠AP B intersect at the excentres of
4P BC opposite C and the angle bisectors of ∠ADB and ∠AP B intersect at the
excentres of 4P AD opposite D. Hence, it suffices to prove that these two excentres
coincide.
Let the excircle of 4P BC opposite C touch side P B at a point X, line CP at a
point Y and line CB at a point Z. Hence, CY = CZ, P X = P Y and BX = BZ.
Therefore, CP + P X = CB + BX. Since CP + P X + CB + BX is the perimeter
of 4CBP , CP + P X = CB + BX = s, where s is the semi-perimeter of 4CBP .
Therefore,
s CB + BP + P C CB + BP − P C
P X = CB + BX − CP = − CP = − CP = .
2 2 2
Similarly, if we let the excircle of 4P AD opposite D touch side P A at a point
0
X , then
DA + AP − P D
P X0 = .
2
Since both excircles are tangent to AC and BD, if we show that P X = P X 0 ,
then we would show that the two excircles are tangent to AC and BD at the same
points, i.e. the two excircles are identical. Hence, the two excentres coincide.
We will use the fact that AC + AD = BC + BD to prove that P X = P X 0 . Since
AC +AD = BC +BD, AP +P C +AD = BC +BP +P D. Hence, AP +AD −P D =
BC + BP − P C. Therefore, P X = P X 0 , as desired.
Solution. We will prove any two robots can be moved to the same square. From
that point on, they will always be on the same square. We can then similarly move
Sun Life Financial Canadian Mathematical Olympiad
a third robot onto the same square as these two, and then a fourth, and so on, until
all robots are on the same square.
Towards that end, consider two robots A and B. Let d(A, B) denote the mini-
mum number of commands that need to be given in order to move A to the square
on which B is currently standing. We will give a procedure that is guaranteed to de-
crease d(A, B). Since d(A, B) is a non-negative integer, this procedure will eventually
decrease n to 0, which finishes the proof.
Let n = d(A, B), and let S = {s1 , s2 , . . . , sn } be a minimum sequence of moves
that takes A to the square where B is currently standing. Certainly A will not run
into an impassable edge during this sequence, or we could get a shorter sequence by
removing that command. Now suppose B runs into an impassable edge after some
command si . From that point, we can get A to the square on which B started with
the commands si+1 , si+2 , . . . , sn and then to the square where B is currently with
the commands s1 , s2 , . . . , si−1 . But this was only n − 1 commands in total, and so
we have decreased d(A, B) as required.
Otherwise, we have given a sequence of n commands to A and B, and neither
ran into an impassable edge during the execution of these commands. In particular,
the vector v connecting A to B on the grid must have never changed. We moved
A to the position B = A + v, and therefore we must have also moved B to B + v.
Repeating this process k times, we will move A to A + kv and B to B + kv. But if
v 6= (0, 0), this will eventually force B off the edge of the grid, giving a contradiction.
5. A bookshelf contains n volumes, labelled 1 to n, in some order. The librarian
wishes to put them in the correct order as follows. The librarian selects a volume
that is too far to the right, say the volume with label k, takes it out, and inserts it
in the k-th position. For example, if the bookshelf contains the volumes 1, 3, 2, 4 in
that order, the librarian could take out volume 2 and place it in the second position.
The books will then be in the correct order 1, 2, 3, 4.
(a) Show that if this process is repeated, then, however the librarian makes the
selections, all the volumes will eventually be in the correct order.
(b) What is the largest number of steps that this process can take?
Solution. (a) If tk is the number of times that volume k is selected, then we have
tk ≤ 1 + (t1 + t2 + · · · + tk−1 ). This is because volume k must move to the right
between selections, which means some volume was placed to its left. The only way
that can happen is if a lower-numbered volume was selected. This leads to the bound
tk ≤ 2k−1 . Furthermore, tn = 0 since the nth volume will never be too far to the
right. Therefore if N is the total number of moves then
N = t1 + t2 + · · · + tn−1 ≤ 1 + 2 + · · · + 2n−2 = 2n−1 − 1,
Sun Life Financial Canadian Mathematical Olympiad
Solution 1: The answer is P (x) being any constant polynomial and P (x) ≡
kx2 + kx + c for any (nonzero) constant k and constant c.
Let Λ be the expression (x + 1)P (x − 1) − (x − 1)P (x), i.e. the expression in the
problem statement.
Let c = P (−1) = P (0) and Q(x) = P (x) − c. Then Q(−1) = Q(0) = 0. Hence,
0, −1 are roots of Q(x). Consequently, Q(x) = x(x + 1)R(x) for some polynomial R.
Then P (x) − c = x(x + 1)R(x), or equivalently, P (x) = x(x + 1)R(x) + c.
Finally, we verify that all such P (x) = kx(x + 1) + c work. Substituting this into
Λ yield
(x + 1)(kx(x − 1) + c) − (x − 1)(kx(x + 1) + c)
= kx(x + 1)(x − 1) + c(x + 1) − kx(x + 1)(x − 1) − c(x − 1) = 2c.
with an 6= 0. Then
n
X n
X
i
(x + 1) ai (x − 1) − (x − 1) ai xi = C,
i=0 i=0
for some constant C. We will compare the coefficient of xn of the left-hand side of
this equation with the right-hand side. Since C is a constant and n ≥ 1, the coeffi-
cient of xn of the right-hand side is equal to zero. We now determine the coefficient
of xn of the left-hand side of this expression.
By the Binomial Theorem, the coefficient¡ of x¢n of the first term is equal to that
n
of x (an−1 (x − 1)n−1 + an (x − 1)n ) = an−1 − n−1 an = an−1 − nan .
The coefficient of xn of the third term is equal to an−1 and that of the fourth
term is equal to an .
(b − a)x + 2c = 2C.
n
If n is even, then a1 + a2 + . . . + an = 1 + 2 + . . . + n = 2
· (n + 1), which is
congruent to 0 mod n + 1. Therefore, the task is impossible.
Now suppose n is odd. We will show that we can construct a1 , a2 , . . . , an that sat-
isfy the conditions given in the problem. Then let n = 2k + 1 for some non-negative
integer k. Consider the sequence: 1, 2k, 3, 2k − 2, 5, 2k − 3, . . . , 2, 2k + 1, i.e. for each
1 ≤ i ≤ 2k + 1, ai = i if i is odd and ai = 2k + 2 − i if i is even.
We first show that each term 1, 2, . . . , 2k + 1 appears exactly once. Clearly, there
are 2k + 1 terms. For each odd number m in {1, 2, . . . , 2k + 1}, am = m. For each
even number m in this set, a2k+2−m = 2k + 2 − (2k + 2 − m) = m. Hence, every
number appears in a1 , . . . , a2k+1 . Hence, a1 , . . . , a2k+1 does consist of the numbers
1, 2, . . . , 2k + 1 in some order.
Solution 1. Since ∠C = 90◦ , the point C lies on the semicircle with diameter AB
which implies that, if M is te midpoint of side AB, then M A = M C = M B. This
implies that triangle AM C is isosceles and hence that ∠ACM = ∠A. By definition,
G lies on segment M and it follows that ∠ACG = ∠ACM = ∠A = ∠CP A. This
implies that triangles AP C and ACG are similar and hence that AC 2 = AG · AP .
Now if D denotes the foot of the perpendicular from C to AB, it follows that triangles
ACD and ABC are similar which implies that AC 2 = AD·AB. Therefore AG·AP =
AC 2 = AD·AB and, by power of a point, quadrilateral DGP B is cyclic. This implies
that D lies on the circumcircle of triangle BP G and, by a symmetric argument, it
follows that D also lies on the circumcircle of triangle AGQ. Therefore these two
circumcircles meet at the point D on side AB.
Solution 2. Define D and M as in Solution 1. Let R be the point on side AB
such that AC = CR and triangle ACR is isosceles. Since ∠CRA = ∠A = ∠CP A,
it follows that CP RA is cyclic and hence that ∠GP R = ∠AP R = ∠ACR = 180◦ −
2∠A. As in Solution 1, M C = M B and hence ∠GM R = ∠CM B = 2∠A = 180◦ −
∠GP R. Therefore GP RM is cyclic and, by power of a point, AM · AR = AG · AP .
Since ACR is isosceles, D is the midpoint of AR and thus, since M is the midpoint
of AB, it follows that AM · AR = AD · AB = AG · AP . Therefore DGP B is cyclic,
implying the result as in Solution 1.
4. Let n be a positive integer. For any positive integer j and positive real number
r, define
µ ¶ µ» ¼ ¶
j j
fj (r) = min (jr, n) + min , n , and gj (r) = min (djre, n) + min ,n ,
r r
where dxe denotes the smallest integer greater than or equal to x. Prove that
n
X n
X
2
fj (r) ≤ n + n ≤ gj (r).
j=1 j=1
Solution 1: We first prove the left hand side inequality. We begin by drawing
an n × n board, with corners at (0, 0), (n, 0), (0, n) and (n, n) on the Cartesian plane.
Consider the line ` with slope r passing through (0, 0). For each j ∈ {1, . . . , n},
consider the point (j, min(jr, n)). Note that each such point either lies on ` or the
top edge of the board. In the j th column from the left, draw the rectangle of height
min(jr, n). Note that the sum of the n rectangles is equal to the area of the board
under the line ` plus n triangles (possibly with area 0) each with width at most 1
and whose sum of the heights is at most P n. Therefore, the sum of the areas of these
n triangles is at most n/2. Therefore, nj=1 min(jr, n) is at most the area of the
square under ` plus n/2.
Consider the line with slope 1/r. By symmetry about the line y = x, the area of
the square under the line with slope 1/r is equal to the area
Pn of the square above the
line `. Therefore, using the same reasoning as before, j=1 min(j/r, n) is at most
the area of the square above ` plus n/2.
P P
Therefore, nj=1 fj (r) = nj=1 (min(jr, n) + min( rj , n)) is at most the area of the
board plus n, which is n2 + n. This proves the left hand side inequality.
To prove the right hand side inequality, we will use the following lemma:
Lemma: Consider the line ` with slope s passing through (0, 0). P Then the num-
ber of squares on the board that contain an interior point below ` is nj=1 min (djse, n).
Proof of Lemma: For each j ∈ {1, . . . , n}, we count the number of squares in the
j th column (from the left) that contain an interior point lying below the line `. The
line x = j intersect the line ` at (j, js). Hence, since each column contains n squares
total, the number of such squares is min(djse, n). Summing over all j ∈ {1, 2, . . . , n}
proves the lemma. End Proof of Lemma
By the lemma, the rightmost expression of the inequality is equal to the number
of squares containing an interior point below the line with slope r plus the number
of squares containing an interior point below the line with slope 1/r. By symmetry
about the line y = x, the latter number is equal to the number of squares containing
an interior point above the line with slope r. Therefore, the rightmost expression
of the inequality is equal to the number of squares of the board plus the number of
squares of which ` passes through the interior. The former is equal to n2 . Hence, to
prove the inequality, it suffices to show that every line passes through the interior of
at least n squares. Since ` has positive slope, each ` passes through either n rows
and/or n columns. In either case, ` passes through the interior of at least n squares.
Hence, the right inequality holds. ¤
PnSolution 2: We first prove the left inequality. Define the function f (r) =
j=1 fj (r). Note that f (r) = f (1/r) for all r > 0. Therefore, we may assume
that r ≥ 1.
Let m = bn/rc, where bxc denotes the largest integer less than or equal to x. Then
min(jr, n) = jr for all j ∈ {1, . . . , m} and min(jr, n) = n for all j ∈ {m + 1, . . . , n}.
Note that since r ≥ 1, min(j/r, n) ≤ n for all j ∈ {1, . . . , n}. Therefore,
n
X 1
f (r) = fj (r) = (1 + 2 + . . . m)r + (n − m)n + (1 + 2 + . . . + n) ·
j=1
r
m(m + 1) n(n + 1) 1
= ·r+ · + n(n − m) (1)
2 2 r
2
Then by (??), note that f (r) ≤ n + n if and only if
m(m + 1)r n(n + 1)
+ ≤ n(m + 1)
2 2r
if and only if
m(m + 1)r2 + n(n + 1) ≤ 2rn(m + 1) (2)
Since m = bn/rc, there exist a real number b satisfying 0 ≤ b < r such that
n = mr + b. Substituting this into (??) yields
which holds since r ≥ 1 and b < r. Therefore, the left inequality holds.
P
We now prove the right inequality. Define the function g(r) = nj=1 = gj (r).
Note that g(r) = g(1/r) for all r > 0. Therefore, we may assume that r ≥ 1. We
will consider two cases; r ≥ n and 1 ≤ r < n.
Now we consider the case 1 ≤ r < n. Let m = bn/rc. Hence, jr ≤ n for all
j ∈ {1, . . . , m}, i.e. min(djr, e, n) = djre and jr ≥ n for all j ∈ {m + 1, . . . , n}, i.e.
min(djre, n) = n. Therefore,
n
X m
X
min(djre, n) = djre + (n − m)n. (3)
j=1 j=1
Pn
We will now consider the second sum j=1 min{dj/re, n}.
For each positive integer k ∈ {1, . . . , m + 1}, we now determine the number of
positive integers j ∈ {1, . . . , n} such that dj/re = k. We denote this number by sk .
Note that dj/re = k if and only if k − 1 < j/r ≤ k if and only if (k − 1)r < j ≤
min(kr, n), since j ≤ n. We will handle the cases k ∈ {1, . . . , m} and k = m + 1
separately. If k ∈ {1, . . . , m}, then min(kr, n) = kr, since r ≤ m and m = bn/rc.
The set of positive integers j satisfying (k − 1)r < j ≤ kr is {b(k − 1)rc + 1, b(k −
1)rc + 2, . . . , bkrc}. Hence,
for all k ∈ {1, . . . , m}. If k = m + 1, then (k − 1)r < j ≤ min(kr, n) = n. The set
of positive integers j satisfying (k − 1)r < j ≤ kr is {b(k − 1)rc + 1, . . . , n}. Then
sm+1 = n − br(k − 1)c = n − bmrc. Note that this number is non-negative by the
definition of m. Therefore, by the definition of sk , we have
n
X µ» ¼ ¶ m+1
X
j
min ,n = ksk
j=1
r k=1
m
X m
X
= (k (bkrc − b(k − 1)rc)) + (m + 1)(n − brmc) = (m + 1)n − bkrc.
k=1 k=1
(4)
Solution. Let the circumcircle of triangle OBP intersect side BC at the points R
and B and let ∠A, ∠B and ∠C denote the angles at vertices A, B and C, respectively.
Now note that since ∠BOP = ∠B and ∠COQ = ∠C, it follows that
∠QP R = ∠QP O + ∠OP R = ∠OAQ + ∠OBR = (90◦ − ∠B) + (90◦ − ∠A) = ∠C.
Since CQOR is cyclic, ∠QRC = ∠COQ = ∠C = ∠QP R which implies that the
circumcircle of triangle P QR is tangent to BC. Further, since ∠P RB = ∠BOP =
∠B,
Note that it is not possible that all rows are red-dominated and all columns are
blue-dominated. This is true, since the number of rows and columns are both odd,
the number of squares is odd. Hence, there are more squares of one color than the
other. Without loss of generality, suppose there are more red squares than blue
squares. Then it is not possible that for every column, there are more blue squares
than red squares. Hence, every column cannot be blue-dominated.
If one of m, n is equal to 1, say m without loss of generality, then by the claim, the
answer is less than n + 1. The example where there are n blue-dominated columns
is by painting every square blue. There are 0 red-dominated rows. The sum of the
two is n = max{m, n}.
There are m rows and n columns on the board. Hence, the answer is at most
m + n. We have already shown that the answer cannot be m + n.
Since m, n are odd, let m = 2a − 1 and n = 2b − 1 for some positive integers
a, b. Since m, n ≥ 3, a, b ≥ 2. We first show that the answer is not m + n − 1. By
symmetry, it suffices to show that we cannot have all rows red-dominated and all-but-
one column blue-dominated. If all rows are red dominated, then each row has at least
b red squares. Hence, there are at least bm = (2a − 1)b red squares. Since all-but-one
column is blue-dominated, there are at least 2b − 2 blue-dominated columns. Each
such column then has at least a blue squares. Therefore, there are at least a(2b − 2)
blue squares. Therefore, the board has at least (2a − 1)b + a(2b − 2) = 4ab − b − 2a
squares. But the total number of squares on the board is
(2a − 1)(2b − 1) = 4ab − 2a − 2b + 1 = 4ab − 2a − b − b + 1 < 4ab − 2a − b,
which is true since b ≥ 2. This is a contradiction. Therefore, the answer is less than
m + n − 1.
We now claim that there is a colouring of the board such that the number of blue-
dominated columns plus the number of red-dominated rows is m + n − 2; Colour the
first column entirely red, and the first row, minus the top-left corner, entirely blue.
The remaining uncoloured square is an even-by-even board. Colour the remaining
board in an alternating pattern (i.e. checkerboard pattern). Hence, on this even-
by-even board, each row has the same number of red squares as blue squares and
each column has the same number of red squares as blue squares. Then on the
whole board, since the top row, minus the top-left square is blue, all columns, but
the leftmost column, are blue-dominated. Hence, there are n − 1 blue-dominated
columns. Since the left column is red, all rows but the top row are red dominated.
Hence, there are m − 1 red-dominated rows. The sum of these two quantities is
m + n − 2, as desired.
(iii) a1 a2 + a2 a3 + a3 a4 + · · · + ap a1 is divisible by p.
Solution. Let S be the set of all sequences (b1 , b2 , . . . , bp ) of numbers from the
set {0, 1, 2, . . . , p − 1} such that b1 + b2 + · · · + bp is not divisible by p. We show
that |S| = pp − pp−1 . For let b1 , b2 , . . . , bp−1 be an arbitrary sequence of numbers
chosen from {0, 1, 2, . . . , p − 1}. There are exactly p − 1 choices for bp such that
b1 + b2 + · · · + bp−1 + bp 6≡ 0 (mod p), and therefore |S| = pp−1 (p − 1) = pp − pp−1 .
Now it will be shown that the number of good sequences in S is p1 |S|. For a
sequence B = (b1 , b2 , . . . , bp ) in S, define the sequence Bk = (a1 , a2 , . . . , ap ) by
ai = bi − b1 + k mod p
and therefore Bk is in S for all non-negative k. Now note that Bk has first element
k for all 0 ≤ k ≤ p − 1 and therefore the sequences B0 , B1 , . . . , Bp−1 are distinct.
Now define the cycle of B as the set {B0 , B1 , . . . , Bp−1 }. Note that B is in its
own cycle since B = Bk where k = b1 . Now note that since every sequence in S is in
exactly one cycle, S is the disjoint union of cycles.
Now it will be shown that exactly one sequence per cycle is good. Consider
an arbitrary cycle B0 , B1 , . . . , Bp−1 , and let B0 = (b1 , b2 , . . . , bp ) where b0 = 0, and
note that Bk = (b1 + k, b2 + k, . . . , bp + k) mod p. Let u = b1 + b2 + · · · + bp , and
v = b1 b2 + b2 b3 + · · · + bp b1 and note that (b1 + k)(b2 + k) + (b2 + k)(b3 + k)) + · · · +
(bp + k)(b1 + k) = u + 2kv mod p for all 0 ≤ k ≤ p − 1. Since 2v is not divisible by
p, there is exactly one value of k with 0 ≤ k ≤ p − 1 such that p divides u + 2kv
and it is exactly for this value of k that Bk is good. This shows that exactly one
sequence per cycle is good and therefore that the number of good sequences in S is
1
p
|S|, which is pp−1 − pp−2 .
4. The quadrilateral ABCD is inscribed in a circle. The point P lies in the interior
of ABCD, and ∠P AB = ∠P BC = ∠P CD = ∠P DA. The lines AD and BC meet
at Q, and the lines AB and CD meet at R. Prove that the lines P Q and P R form
the same angle as the diagonals of ABCD.
• If the first number is j with 0 < j < k, then choose the interval stretching from
the first number to the jth-last non-zero number.
First note that this strategy is indeed well defined. The first number must have
value between 0 and k − 1, and if we do not stop immediately, then there are at least
k − 1 non-zero numbers, and hence the third step can be performed.
For each j with 1 ≤ j ≤ k − 2, we claim the first number can take on the value of
j at most a finite number of times without taking on the value of j − 1 in between. If
this were to fail, then every time the first number became j, I would have to add 1 to
the selected numbers to avoid making it j − 1. This will always increase the j-th last
non-zero number, and that number will never be changed by other steps. Therefore,
that number would eventually become 0, and the next last non-zero number would
eventually become zero, and so on, until the first number itself becomes the j-th last
non-zero number, at which point we are done since j ≤ k − 2.
Rephrasing slightly, if 1 ≤ j ≤ k − 2, the first number can take on the value of j
at most a finite number of times between each time it takes on the value of j − 1. It
then immediately follows that if the first number can take on the value of j − 1 at
most a finite number of times, then it can also only take on the value of j a finite
number of times. However, if it ever takes on the value of 0, we have already reduced
the problem to n − 1, so we can assume that never happens. It then follows that the
first number can take on all the values 0, 1, 2, . . . , k − 2 at most a finite number of
times.
Finally, every time the first number takes on the value of k − 1, it must subse-
quently take on the value of k − 2 or 0, and so that can also happen only finitely
many times.
Solutions to 2015 CMO
Problem 1. Let N = {1, 2, 3, . . .} be the set of positive integers. Find all functions f , defined
on N and taking values in N, such that (n − 1)2 < f (n)f (f (n)) < n2 + n for every positive
integer n.
therefore that f (f (n)) = f (n) since f (n)2 is the unique square satisfying this constraint.
This implies that f (n)f (f (n)) = f (n)2 ≥ (n + 1)2 which is a contradiction, completing the
induction.
Problem 2. Let ABC be an acute-angled triangle with altitudes AD, BE, and CF . Let H
be the orthocentre, that is, the point where the altitudes meet. Prove that
AB · AC + BC · BA + CA · CB
≤ 2.
AH · AD + BH · BE + CH · CF
Solution. Method 1: Let AB = c, AC = b, and BC = a denote the three side lengths of
the triangle.
As ∠BF H = ∠BDH = 90◦ , F HDB is a cyclic quadrilateral. By the Power-of-a-Point
Theorem, AH · AD = AF · AB. (We can derive this result in other ways: for example, see
Method 2, below.)
Since AF = AC · cos ∠A, we have AH · AD = AC · AB · cos ∠A = bc cos ∠A.
1
Solutions to 2015 CMO
b2 + c2 − a2 b2 + c2 − a2
By the Cosine Law, cos ∠A = , which implies that AH · AD = .
2bc 2
2 2 2 2 2 2
a +c −b a +b −c
By symmetry, we can show that BH · BE = and CH · CF = .
2 2
Hence,
b2 + c2 − a2 a2 + c2 − b 2 a2 + b2 − c2
AH · AD + BH · BE + CH · CF = + +
2 2 2
2 2 2
a +b +c
= . (1)
2
AB · AC + BC · BA + CA · CB
Our desired inequality, ≤ 2, is equivalent to the inequality
AH · AD + BH · BE + CH · CF
cb + ac + ba
a2 +b2 +c2
≤ 2, which simplifies to 2a2 + 2b2 + 2c2 ≥ 2ab + 2bc + 2ca.
2
But this last inequality is easy to prove, as it is equivalent to (a−b)2 +(a−c)2 +(b−c)2 ≥ 0.
Therefore, we have established the desired inequality. The proof also shows that equality
occurs if and only if a = b = c, i.e., 4ABC is equilateral.
Method 2: Observe that
AE AD AF AD
= cos(∠HAE) = and = cos(∠HAF ) = .
AH AC AH AB
It follows that
AC · AE = AH · AD = AB · AF .
By symmetry, we similarly have
BC · BD = BH · BE = BF · BA and CD · CB = CH · CF = CE · CA .
Therefore
2(AH · AD + BH · BE + CH · CF )
= AB(AF + BF ) + AC(AE + CE) + BC(BD + CD)
= AB 2 + AC 2 + BC 2 .
This proves Equation (1) in Method 1. The rest of the proof is the same as the part of the
proof of Method 1 that follows Equation (1).
Problem 3. On a (4n + 2) × (4n + 2) square grid, a turtle can move between squares sharing
a side. The turtle begins in a corner square of the grid and enters each square exactly once,
ending in the square where she started. In terms of n, what is the largest positive integer k
such that there must be a row or column that the turtle has entered at least k distinct times?
2
Solutions to 2015 CMO
Solution. We shall prove that the answer is 2n + 2. Number the rows in increasing order,
from top to bottom, and number the columns from left to right. By symmetry, we may (and
shall) assume that the turtle starts in the top right corner square.
First we shall prove that some row or column must be entered at least 2n + 2 times. Let
m = 4n + 2. First note that each time the turtle moves, she enters either a row or a column.
Let ri denote the number of times the turtle enters row i, and let ci be similarly defined for
column i. Since the turtle moves m2 times,
r1 + r2 + · · · + rm + c1 + c2 + · · · + cm = m2 .
Now note that each time the turtle enters column 1, the next column she enters must be
column 2. Therefore c1 is equal to the number of times the turtle enters column 2 from
column 1. Furthermore, the turtle must enter column 2 from column 3 at least once, which
implies that c2 > c1 . Therefore since the 2m terms ri and ci are not all equal, one must be
strictly greater than m2 /(2m) = 2n + 1 and therefore at least 2n + 2.
Now we construct an example to show that it is possible that no row or column is entered
more than 2n + 2 times. Partition the square grid into four (2n + 1) × (2n + 1) quadrants
A, B, C, and D, containing the upper left, upper right, lower left, and lower right corners,
respectively. The turtle begins at the top right corner square of B, moves one square down,
and then moves left through the whole second row of B. She then moves one square down
and moves right through the whole third row of B. She continues in this pattern, moving
through each remaining row of B in succession and moving one square down when each row
is completed. Since 2n + 1 is odd, the turtle ends at the bottom right corner of B. She then
moves one square down into D and through each column of D in turn, moving one square to
the left when each column is completed. She ends at the lower left corner of D and moves
left into C and through the rows of C, moving one square up when each row is completed,
ending in the upper left corner of C. She then enters A and moves through the columns of
A, moving one square right when each column is completed. This takes her to the upper
right corner of A, whereupon she enters B and moves right through the top row of B, which
returns her to her starting point. Each row passing through A and B is entered at most
2n + 1 times in A and once in B, and thus at most 2n + 2 times in total. Similarly, each row
and column in the grid is entered at most 2n + 2 times by this path. (See figure below.)
3
Solutions to 2015 CMO
start
Solution. Let ω be the circumcircle of BOC. Let M be the point diametrically opposite
to O on ω and let the line AM intersect ω at M and K. Since O is the circumcenter of
ABC, it follows that OB = OC and therefore that O is the midpoint of the arc BOC\ of ω.
Since M is diametrically opposite to O, it follows that M is the midpoint of the arc BM
\ C
of ω. This implies since K is on ω that KM is the bisector of ∠BKC.Since K is on ω, this
implies that ∠BKM = ∠CKM , i.e. KM is the bisector of ∠BKC.
Since O is the circumcenter of ABC, it follows that ∠BOC = 2∠BAC. Since B, K, O
and C all lie on ω, it also follows that ∠BKC = ∠BOC = 2∠BAC. Since KM bisects
∠BKC, it follows that ∠BKM = ∠CKM = ∠BAC. The fact that A, K and M lie on a
line therefore implies that ∠AKB = ∠AKC = 180◦ − ∠BAC. Now it follows that
This implies that triangles KBA and KAC are similar. Rearranging the condition in the
problem statement yields that BP/AP = AQ/CQ which, when combined with the fact that
KBA and KAC are similar, implies that triangles KP A and KQC are similar. Therefore
∠KP A = ∠KQC = 180◦ − ∠KQA which implies that K lies on Γ.
Now let S denote the centre of Γ and let T denote the centre of ω. Note that T is the
midpoint of segment OM and that T M and AS, which are both perpendicular to BC, are
parallel. This implies that ∠KM T = ∠KAS since A, K and M are collinear. Further, since
KT M and KSA are isosceles triangles, it follows that ∠T KM = ∠KM T and ∠SKA =
4
Solutions to 2015 CMO
∠KSA. Therefore ∠T KM = ∠SKA which implies that S, T and K are collinear. Therefore
Γ and ω intersect at a point K which lies on the line ST connecting the centres of the two
circles. This implies that the circles Γ and ω are tangent at K.
5
"!$#&% ')(*+,.-./01
2436587:9<;>=?@9BAC9BDFEG24HFI1HFJ1HBKBKBKHFI4LM2ONP4DF9<Q8DR;S?@?@9O=UTV=WPYX.TVP4DRZ38[0TV\^]BPC=^]F7MT1TVE@9
PC=_U?`QaTU=1\:b<Xc9BDFEdTV=e?f7M9GXcTVP4DFZePC=:Z^Df9BghiPC]j9"?f7:9ObkQl;S?f7^?f7M9O;SDmPonC9BDFP4AC9C3
p TCDq9jrsPCbtg
hS9Cu_CTV\v]BPC=eDf9Bg
h>PC]j92tPC=:ZvI)Ql;S?f7w24Kyx1uTCDq_CTV\e]BPC=eDf9Bgh>PC]j9z2
PC=:Z^JtQ6;S?f7{P)E@9O]jTV=:ZW]jTCg1_zTC|aI13~}l|?@9BD~I4LM2Ox)DF9Bgh>PC]j9Obt9O=?fEdTC|?f7:;>E61;>=Zu
?f7M9mXcTVP4DFZzQl;>h>h.7:POnC9<TV=:hS_YTV=M9q=1\:bqXc9BD8hS9B|?,TV=z;S?B3
P
DfTonC96?f7:P4?0?f7M9BDf9d;>E0PEf9O\M9O=]j98TC|Df9Bgh>PC]j9Ob9O=?fE
?f7:P4?0Ql;>hihMbP4C9l?f7M9
=PCh=\:b<Xc9BD,9O\PCh?@TYI13
X.
DfTonC96?f7:P4?0?f7M9BDf9d;>E0PEf9O\M9O=]j98TC|Df9Bgh>PC]j9Ob9O=?fE
?f7:P4?0Ql;>hihMbP4C9l?f7M9
=PCh=\:b<Xc9BD,9O\PCh?@TU2BLCLCLs3
CM4
p CT D<PYg
P4Df?f;>]B\:h>P4DmE@TVhi\M?f;STV= ¯ ° H ¯ µ HBKBKBKH ¯ °± RuhS9B?¸ ´®¯µ° ¡ ¯µµ ¡¹¶B¶B¶¡ ¯µ°± 3
587:9O=
N
¯ ³ ´ 2 ¡ ¯¸ ³µ º N ¯ ³µ ¦v¸ ¯ ³ ¡ ¸ ´ LsK
» 9B? PC=Z¢8Xc9l?f7M9~DfT1TC?fETC|?f7M9m\PCZMDFP4?f;>]dN+¼ µ ¦U¸o¼ ¡ ¸ ´ Lsu:EfT<|TCD¥9OPC]F7
· u ¯4³,´ TCD ¯4³,´ ¢3)e9)PChiE@TU7:PonC9 ¢ ´ ¸+½4N X_^¾~;S9B?fPs¿ÀEq|TCDFb"\:h>Psu|¬TCD
9jrMPCbtghS9R3
§ |*PChihc?f7M9 ¯ ³ P4DF99O\PChuM?f7M9O=
N ©
¯+³´ 2 ¡ 2BL ´ x
|TCD8PCh>h · 3aÁd?f7:9BDfQl;>E@9CuMhS9B?lx ¡w TC|*?f7M9 ¯4³ Xc9 u:PC=ZzhS9B?8x~¦  TC|?f7M9 ¯4³ Xc9
¢uMQl7M9BDF9LÃ ÂÄ M3
5l7M9O=X1_Y?f7M9}~ÅzÇÆmÅÈ;>=M9O1\:PCh>;S?`_Cu
N ¢ ´ ¸ ´ x ¡É µ ¡ xm¦  ʢ µË I ¢4Ì ICxm¦  µ K
p DFTVbÍ?f7M9AV;SnC9O=w9O1\:P4?f;STV=:EOu ¯ ³ Ë 2|¬TCDYPCh>h · uEfT PC=:Z ¢)P4Df9gcTVEf;S?f;>nC9C3
587:9O=ÉÎ ICxm¦ Â µ Ä J º ICxY¦ Â µ Ä ¨ º Â µ Ë 2ON º Â ´ M3ÐÏ69O=:]j9Cu
N ¢ ´ ¨ µ ¡ ¢ µ º ¢¥¦«J µl´ L º ¢ ´ J 3
}dZ:Z:;>=:A"PCh>hAV;SnC9O=?@9O=z9O1\:P4?f;STV=EBuMQa9qAC9B?
¯ ° ¡ ¯ µ ¡¶B¶B¶4¡ ¯ °± ´ 2ON1K
Ñ \M? ¯ ° ¡ ¯ µ ¡®¶B¶B¶M¡ ¯ °± ´ ¨ )¡ ¢ ´ 2OI u8EfT ´ 2ONV½12OI ´ ½4JvPC=:Z
¢ ´ M3$5l7M9BDf9B|TCDf9Cul?f7M9eE@TVhi\M?f;STV=:EP4Df9 ©V½4x1HF©V½4x1HBKBKBKCHF©V½4xVPC=:ZPCh>hd?@9O=
gc9BDFb"\M?fP4?f;STV=:E¥TC| ½4J1H@½4J1HBKBKBKVH@½4J1H@R3
J13 p >; =:Z"PCh>hgcTVhS_1=:TVb;>PCh>EÒ ¼cQl;>?f7<;>=?@9BAC9BD0]jT19BÓ]B;S9O=?fEEf\:]F7G?f7P4?ÔÒ Ò Õ ¡
Õ >; E,Pg:DF;>bt9m=1\:b<X.9BD,|TCDl;>= =:;S?@9OhS_bPC=_;>=?@9BAC9BDFE Õ 3
Ö :×RØaÙjÚB Ò Õ ´ÜÛ Ql7M9BDf9 Û ;iEPg:DF;ibt9t=\:b<Xc9BDPC=:ZeÒ Õ ´ ¦lI Õz¡ ¢
Ql7:9BDf9¢~;>E¥T1ZZ3
CM4 ²Ý TC?@9«?f7:P4?U;S|GÒ Õ ´ LÉ?f7:9O=ÞÒ Ò Õ ¡ßÕ ´ Ò Õ ´ L
Ql7;>]F7v;iE=MTCà?qgDF;>bt9C3 »àá 9B?<Ò ¼c~Xc9P{ZM9BACDf9B9  gcTVhS_s=MTVb;>PCh*TC|,?f7M9Y|¬TCDFb
Ò ¼ ´ 1à ¼ ¡w 1àá ° ¼ ° ¡¶B¶B¶+¡w ± PC=:Z=MTC?@9?f7P4?l;S|ÔÒ Õ d´ â Lt?f7M9O=
Ò Ò Õ ¡ÐÕ *¦vÒ Õ ´
àsãS Ò Õ ¡ÐÕ à ¦ Õ àoä ¡w àá ° ãS Ò Õ ¡wÕ àoá ° ¦ Õ àá ° ä ¡å¶B¶B¶4¡É ° Ò Õ
I
hS9O=:AC?f7êq3
+
² § |ª¥hiPC;>bûIG;>E,|PCh>E@9CuM?f7M9O=
³
° ´ ¼ ³
° ´ ¼ ³
° Ë ¼ ³
° ¡ÜÕ ¦ 2oÇê ¡ ë
õ ý ³ ¡ÐÕ ê ¡ ô
´ ü ³
° ¡ 2
õ ³
°
Ql7;>]F7;>E,P]jTV=?@DFPCZ;>]j?f;STV=3
5l7:;>Eg:DfTnC9OEdª¥h>PC;ibûI13
e9q]BPC={=MToQð]jTV=:]Bh>\:ZM9m?f7P4?
¼ ³
°
° ´ ¼ ³
µ ´ ¼ ³
° ¡ÐÕ ê ¡ ëó
;3 9C3Su ò ³
° ´ ò ³ ¡ÐÕ ê ¡ ë |TCD89OPC]F7 · Ë 243
587:9BDf9B|¬TCDF9
ò ³
° ¦vý ³
° ´ ò ³ ¡ÐÕ ê ¡ ëȦ ý ³ ¡wÕ ê ¡ ô ¦É2 ¡ êm
´ ò ³ ¦vý ³ ¡ 2ÔK
Ï69O=:]j9
ô Ë ò
° ¦vý
° ´ ò ° ¦vý ° ¡ ô õöô
Ql7;>]F7;>ElP]jTV=?@DRPCZ:;>]j?f;STV=3a587M9BDf9B|TCDf9q=MTtg
P4?f7z|TCD8?f7M9ñ:9OPPOnCTV;>Z:E6PCh>h?f7M9
h>Pon+Ps3«e9TCXE@9BDfnC9?f7:P4? » POn4PCbPC=ÉTV=:hS_=M9B9OZ:EG?@T^g\M?th>Pon+PWTV=w?f7M9 DFEf?
ô ¡ 2;>=?@9BDfn+PChiEB3
Ý ToQèPCEfEf\:bt9ì Ë Õ ¦É2oÇê ¡ ë)3e9Ql;>h>hcEf7:ToQÞ?f7:P4?l?f7M9mñ:9OP]BPC={POnCTV;>Z
PCh>hc?f7:9h>POn4Ps3
e9qEF7:PCh>h=M9B9OZ?f7:9|¬TVhihSToQl;i=MA<DF9OEf\:hS? ²
ª¥hiPC;>bîJ ² » 9B?~÷ Ë Õ ê<3587M9O={?f7M9BDf9G9jrM;>E@?m=MTV=:=:9BAVP4?f;SnC9t;>=?@9BAC9BDRE¸tPC=:Z
Ef\]F7?f7:P4?d¸oê ¡ Êë ÿ ÷"¦ ô Hf÷ ä 3
e9qEF7:PCh>hcg:DfTnC9?f7:;>E¥DF9OEf\:hS?8P4?8?f7:9m9O=:Z3
p ;SDFEf?BuTCXEf9BDfnC9?f7:P4? ü ° Ë Õ êq3 Ñ _ª¥h>PC;ib J1u0;S?q;>EqgcTVEfEf;SXh>9"|TCD"?f7M9ñ:9OP
?@TbP4C9<PtE@ä9O\:9O=:]j9mTC|M£f\:btgE¥E@?fP4DF?f;>=MAt|DfTVbîLtPC=:Z9O=:Z:;i=MA"P4?8PGgcTV;>=?¥TC|
ü ° ¦ ô H ü ° 3 p DfTVbPC=_gcTV;>=?,TC|?f7:;>E6;>=?@9BDFn+PChu
PEf;>ä =:AVhS9£@\btgzTC|0Ef;SçB9"ë
?fP4C9OEÔ?f7M9¥ñ:9OP6TonC9BD ü ° Hfý!?@TmPdgcTV;>=?*;>= ý ° Hfý ° ¡Yô u4Ql7:;i]F7"]jTCDfDf9OE@gcTV=:Z:E
?@T?f7:9mg.TV;i=?,¼ °
° ´ ò ° aTV=z?f7M9mñ:9OPs¿ÀElgP4?f73
Ý ToQ®Q9t\:E@9t;>=:Z\:]j?f;STV={?@Tg:DfTonC9?f7:P4?Bu|TCDm9BnC9BDf_ · Ë 24u?f7M9BDf9t;>EmP)gP4?f7
Ef\]F7?f7P4?a¼ þ PonCTV;>Z:Eh>POn4P|TCDPChih" Ä · ¡ 243
587:96]BPCE@9 · ´ 26;>E
ZMTV=:9Cu1E@T
N
>
KML
?A@
CB DFE
GH IJ
;: RQ NPO <=
JS T
» B9 ?aý¹Z:9O=MTC?@96?f7:9d;>=?@9BDFE@9O]j?f;>TV=TC|h>;i=M9OEU1/îPC=:ZYÒV2«3
¤s;>=]j9l\PCZMDF;>h>P4?@9BDf
PCh>EU1 ô /W2PC=:ZêdÒ32WëèP4DF9l]j_1]Bhi;>]4uQ9l7:PonC9YX¥ýY/)ê ´ 2O©4L[Z¦WX\1V/)ê ´
2O©4L[Zl¦]X^1/62 ´ 2O©4L[Zl¦]X^1 ô 2 ´ ¨4L[Z ¡ êqucPC=:Z_X¥ýmÒê ´ X^2WÒê ´
2O©4L Z ¦`X^2{ëGê ´ ¨4L Z ¡ ê<3*5l7M9BDf9B|TCDf9CuêdÒ3/Yý;>EÔ]j_s]Bh>;>]43587:;>E*;>="?f\MDF=G;>bt
ghi;S9OE¥?f7:P4?aX,Òë1 ´ X¥Òë2 ´ X¥Òqê!2 ´ X¥Òê0/ ´ X¥ÒýY/ ´ X¥ÒýY1u
PC=:ZEfTÒëGýY1$;>E,PChiE@T]j_s]Bh>;>]43
» 9B?~ìîZ:9O=MTC?@9t?f7M9tXPCE@9GTC|a?f7M9PChS?f;S?f\:Z:9<|DfTVb ô ?@TzêdëY3"587M9O=_/{Hb1Hfì,H
PC=:Z PCh>hh>;S9
TV=<?f7M9,¨gcTV;>=?*]B;SDF]BhS9
TC|-êdë ô u+PC=Z<E@T~P4Df9¥]j_1]Bhi;>]43e9,PCh>E@T
s=MToQ êdÒ3/)ýGuÒëGýY1uë ô 1<ìtuPC=:Z^ê ô /YìíP4Df9]j_s]Bh>;>]4ucQl7:;i]F7^;>btghi;S9OE
X¥êdýmë ´ X,ÒýmëߦcX¥Òýmê ´ X¥Ò31që ¦]X¥Ò3/)ê ´ X¥Ò31<ì ¡ X¥ì31qëߦ
X¥ÒV/Yì ¡ X¥ê!/)ì ´ X,ì31që ¡ X,ê!/)ì ´ X¥ì ô ë ¡ X¥ê ô ì ´ ô 3587M9BDf9j
|TCDf9Cu:ý h>;S9OE¥TV=U?f7M9]B;SDF]B\b]B;SDF]BhS9~TC|d-êdë ô 3
Ý ToQ$h>9B? 8Ye PC=Zeý e ZM9O=MTC?@9t?f7:9;>=?@9BDRE@9O]j?f;STV=:E~TC|h>;>=M9 8 Ql;S?f7W?f7M9]B;SDf
]B\:b]B;SDF]BhS9,TC|f-êdë ô u]R7MTVE@9O=)E@Tq?f7:P4? 8 e H H 8 Hfý e h>;S9,TV=?f7M96h>;i=M9,;>=t?f7:P4?
TCDFZ:9BDO3e9lQl;>h>h1Ef7MTQÉ?f7:P4?
ý e ´ ýGuVQl7:;i]F7"Ql;>h>h1]jE TVbtgh>9B?@9,?f7M9,g:DfT1TC= |`3ÔÏ6ToQ,
9BnC9BDOu DFE@?6=MTC?@9?f7:P4?6?f7M9<]B;SDR]B\:b]B;SDF]Bh>9dTC|U-êd=ë ô 7:PCElDFPCZ:;>\= E ; u
PC=:Z
?f7M9~]B;SDF]B\b]B;SDF]BhS96TC|k-êdë2 7:PCEDFPCZ:;i\:E ; ; =å´
µ
g A
h m
j l µ
g A
h j °; n@±bo µ[á gi hAj 305l7\:E
?f7M9)?QTe]B;SDF]BhS9OE"7:PonC99O\:PChaDFPCZ:;i\:EBuPC=:ZÐE@T{?f7:9B_b"\:E@?"X.9)E@_sbbt9B?@DF;>]BPCh
P4XcTV\M?,?f7M9mgcTV;>=? 3 § =g
P4Df?f;>]B\:h>P4Dou 8 ´ 8 e 3
¤s;i=:]j9\X,ê!1<ë ´ X¥ê!/)ë ´ ¨4L[Z+uVQ98|\MDf?f7M9BDFbTCDf9as=MTQ ?f7:P4? ;>E*?f7M9l]B;SDf
]B\:b]j9O=?@9BD~TC|XcTC?f7-ê01që PC=:Z_-ê!/)ë)38587\EBu ê ´ 1 ´ / ´
ë)3 Ñ _*ToQ9BDdTC|PYTV;i=?Bu
Qa9<?f7M9O=U7:PonC9 8 ¶ ý e ´ 8Ye ¶ ý e ´
ê ¶ ë ´ / µ 3 § =gP4Df?f;i]B\:h>P4DOuM?f7:;iE8bt9OPC=:El?f7:P4?l?f7M9<]B;SDF]B\:b]B;>DF]BhS9~TC|
©
2017 Canadian
Mathematical Olympiad
Official Solutions
1. Let a, b, and c be non-negative real numbers, no two of which are equal. Prove that
a2 b2 c2
2
+ 2
+ > 2.
(b − c) (c − a) (a − b)2
Solution: The left-hand side is symmetric with respect to a, b, c. Hence, we may assume that
a > b > c ≥ 0. Note that replacing (a, b, c) with (a − c, b − c, 0) lowers the value of the left-
hand side, since the numerators of each of the fractions would decrease and the denominators
remain the same. Therefore, to obtain the minimum possible value of the left-hand side, we
may assume that c = 0.
Then the left-hand side becomes
a2 b2
2
+ 2,
b a
which yields, by the Arithmetic Mean - Geometric Mean Inequality,
r
a2 b2 a2 b2
2
+ 2 ≥ 2 · = 2,
b a b2 a2
with equality if and only if a2 /b2 = b2 /a2 , or equivalently, a4 = b4 . Since a, b ≥ 0, a = b. But
since no two of a, b, c are equal, a 6= b. Hence, equality cannot hold. This yields
a2 b2
+ > 2.
b2 a2
Ultimately, this implies the desired inequality.
a2 b2 c2
+ + −2 =
(b − c)2 (c − a)2 (a − b)2
[a(a − b)(a − c) + b(b − a)(b − c) + c(c − a)(c − b)]2
.
[(a − b)(b − c)(c − a)]2
Then Schur’s Inequality tells us that the numerator of the right-hand side cannot be zero.
c 2017 Canadian Mathematical Society Page 1/ 5
Official Solutions https://cms.math.ca/Competitions/CMO/ CMO 2017
2. Let f be a function from the set of positive integers to itself such that, for every n, the
number of positive integer divisors of n is equal to f (f (n)). For example, f (f (6)) = 4 and
f (f (25)) = 3. Prove that if p is prime then f (p) is also prime.
Solution: Let d(n) = f (f (n)) denote the number of divisors of n and observe that f (d(n)) =
f (f (f (n))) = d(f (n)) for all n. Also note that because all divisors of n are distinct positive
integers between 1 and n, including 1 and n, and excluding n − 1 if n > 2, it follows that
2 ≤ d(n) < n for all n > 2. Furthermore d(1) = 1 and d(2) = 2.
We first will show that f (2) = 2. Let m = f (2) and note that 2 = d(2) = f (f (2)) = f (m). If
m ≥ 2, then let m0 be the smallest positive integer satisfying that m0 ≥ 2 and f (m0 ) = 2.
It follows that f (d(m0 )) = d(f (m0 )) = d(2) = 2. By the minimality of m0 , it follows that
d(m0 ) ≥ m0 , which implies that m0 = 2. Therefore if m ≥ 2, it follows that f (2) = 2. It
suffices to examine the case in which f (2) = m = 1. If m = 1, then f (1) = f (f (2)) = 2
and furthermore, each prime p satisfies that d(f (p)) = f (d(p)) = f (2) = 1 which implies
that f (p) = 1. Therefore d(f (p2 )) = f (d(p2 )) = f (3) = 1 which implies that f (p2 ) = 1 for
any prime p. This implies that 3 = d(p2 ) = f (f (p2 )) = f (1) = 2, which is a contradiction.
Therefore m 6= 1 and f (2) = 2.
It now follows that if p is prime then 2 = f (2) = f (d(p)) = d(f (p)) which implies that f (p)
is prime.
Remark. Such a function exists and can be constructed inductively.
Page 2/ 5
c 2017 Canadian Mathematical Society
CMO 2017 https://cms.math.ca/Competitions/CMO/ Official Solutions
3. Let n be a positive integer, and define Sn = {1, 2, . . . , n}. Consider a non-empty subset T of
Sn . We say that T is balanced if the median of T is equal to the average of T . For example,
for n = 9, each of the subsets {7}, {2, 5}, {2, 3, 4}, {5, 6, 8, 9}, and {1, 4, 5, 7, 8} is balanced;
however, the subsets {2, 4, 5} and {1, 2, 3, 5} are not balanced. For each n ≥ 1, prove that
the number of balanced subsets of Sn is odd.
(To define the median of a set of k numbers, first put the numbers in increasing order; then
the median is the middle number if k is odd, and the average of the two middle numbers if
k is even. For example, the median of {1, 3, 4, 8, 9} is 4, and the median of {1, 3, 4, 7, 8, 9} is
(4 + 7)/2 = 5.5.)
Solution: The problem is to prove that there is an odd number of nonempty subsets T of
Sn such that the average A(T ) and median M (T ) satisfy A(T ) = M (T ). Given a subset T ,
consider the subset T ∗ = {n + 1 − t : t ∈ T }. It holds that A(T ∗ ) = n + 1 − A(T ) and
M (T ∗ ) = n + 1 − M (T ), which implies that if A(T ) = M (T ) then A(T ∗ ) = M (T ∗ ). Pairing
each set T with T ∗ yields that there are an even number of sets T such that A(T ) = M (T )
and T 6= T ∗ .
Thus it suffices to show that the number of nonempty subsets T such that A(T ) = M (T ) and
T = T ∗ is odd. Now note that if T = T ∗ , then A(T ) = M (T ) = n+1 2 . Hence it suffices to
show the number of nonempty subsets T with T = T is odd. Given such a set T , let T 0 be
∗
the largest nonempty subset of {1, 2, . . . , dn/2e} contained in T . Pairing T with T 0 forms a
bijection between these sets T and the nonempty subsets of {1, 2, . . . , dn/2e}. Thus there are
2dn/2e − 1 such subsets, which is odd as desired.
Alternate solution: Using the notation from the above solution: Let B be the number of
subsets T with M (T ) > A(T ), C be the number with M (T ) = A(T ), and D be the number
with M (T ) < A(T ). Pairing each set T counted by B with T ∗ = {n + 1 − t : t ∈ T } shows
that B = D. Now since B + C + D = 2n − 1, we have that C = 2n − 1 − 2B, which is odd.
c 2017 Canadian Mathematical Society Page 3/ 5
Official Solutions https://cms.math.ca/Competitions/CMO/ CMO 2017
4. Points P and Q lie inside parallelogram ABCD and are such that triangles ABP and BCQ
are equilateral. Prove that the line through P perpendicular to DP and the line through Q
perpendicular to DQ meet on the altitude from B in triangle ABC.
Solution: Let ∠ABC = m and let O be the circumcenter of triangle DP Q. Since P and Q
are in the interior of ABCD, it follows that m = ∠ABC > 60◦ and ∠DAB = 180◦ − m > 60◦
which together imply that 60◦ < m < 120◦ . Now note that ∠DAP = ∠DAB−60◦ = 120◦ −m,
∠DCQ = ∠DCB −60◦ = 120◦ −m and that ∠P BQ = 60◦ −∠ABQ = 60◦ −(∠ABC −60◦ ) =
120◦ − m. This combined with the facts that AD = BQ = CQ and AP = BP = CD implies
that triangles DAP , QBP and QCD are congruent. Therefore DP = P Q = DQ and triangle
DP Q is equilateral. This implies that ∠ODA = ∠P DA + 30◦ = ∠DQC + 30◦ = ∠OQC.
Combining this fact with OQ = OD and CQ = AD implies that triangles ODA and OQC
are congruent. Therefore OA = OC and, if M is the midpoint of segment AC, it follows
that OM is perpendicular to AC. Since ABCD is a parallelogram, M is also the midpoint
of DB. If K denotes the intersection of the line through P perpendicular to DP and the line
through Q perpendicular to DQ, then K is diametrically opposite D on the circumcircle of
DP Q and O is the midpoint of segment DK. This implies that OM is a midline of triangle
DBK and hence that BK is parallel to OM which is perpendicular to AC. Therefore K lies
on the altitude from B in triangle ABC, as desired.
Page 4/ 5
c 2017 Canadian Mathematical Society
CMO 2017 https://cms.math.ca/Competitions/CMO/ Official Solutions
5. One hundred circles of radius one are positioned in the plane so that the area of any triangle
formed by the centres of three of these circles is at most 2017. Prove that there is a line
intersecting at least three of these circles.
n
Solution: We will prove that given n circles, there is some line intersecting more than 46 of
them. Let S be the set of centers of the n circles. We will first show that there
√ is a line ` such
that the projections of the points in S lie in an interval of length at most 8068 < 90 on `.
Let A and B be the pair of points in S that are farthest apart and let the distance between A
and B be d. Now consider any point C ∈ S distinct from A and B. The distance from C to
the line AB must be at most 4034d since triangle ABC has area at most 2017. Therefore if ` is
a line perpendicular to AB, then the projections of S onto ` lie in an interval of length 8068 d
centered at the intersection of ` and AB. Furthermore, all of these projections must lie on an
interval of length at most d on ` since√the largest distance between two of these projections
is at most d. Since min(d, 8068/d) ≤ 8068 < 90, this proves the claim.
Now note that the projections of the n circles
√ onto the line ` are intervals of length 2, all
contained in an interval of length at most 8068 + 2 < 92. Each point of this interval belongs
2n n
to on average √8068+2 > 46 of the subintervals of length 2 corresponding to the projections of
the n circles onto `. Thus there is some point x ∈ ` belonging to the projections of more than
n
46 circles. The line perpendicular to ` through x has the desired property. Setting n = 100
yields that there is a line intersecting at least three of the circles.
c 2017 Canadian Mathematical Society Page 5/ 5