INTERNATIONAL MATHEMATICS
TOURNAMENT OF TOWNS
1997-2002
BOOK 5
AM STOROZHEV
AMT Publishing

IN TERN ATI ОМ AL MATHEMATICS
TOURNAMENT OF TOWNS
1997-2002
Published by
AMT Publishing
Australian Mathematics Trust
University of Canberra ACT 2601
AUSTRALIA
Copyright ®2006 AMT Publishing
Telephone: +61 2 6201 5137
www.amt.edu.au
AMTT Limited ACN 083 950 341
National Library of Australia Card Number and ISSN
Australian Mathematics Trust Enrichment Series ISSN 1326-0170
International Mathematics Tournament of Towns 1997-2002 Book 5
ISBN 978-1-876420-19-2
The Australian Mathematics Trust
Enrichment Series
Editorial Committee
•	Editor Peter J Taylor, Canberra Australia
•	Assoc Editor Andrei Storozhev, Canberra Australia
Warren J Atkins, Newcastle Australia
Ed J Barbeau, Toronto Canada
George Berzsenyi, Terra Haute USA
Bon Dunkley, Waterloo Canada
Walter E Mientka, Lincoln EISA
Nikolay Konstantinov, Moscow Russia
Andy Liu, Edmonton Canada
Jordan В Tabov, Sofia Bulgaria
John Webb, Cape Town South Aerica
The books in this series are selected for their motivating, interesting
and stimulating sets of quality problems, with a lucid expository
style in their solutions. Typically, the problems have occurred in either
national or international contests at the secondary school level.
They are intended to be sufficiently detailed at an elementary level
for the mathematically inclined or interested to understand but, at
the same time, be interesting and sometimes challenging to the
undergraduate and the more advanced mathematician. It is believed
that these mathematics competition problems are a positive influence
on the learning and enrichment of mathematics.
The Australian Mathematics Trust
Enrichment Series
Books in the Series
1 Australian Mathematics Competition Book 1 1978-1984
JD Edwards, DJ King Et PJ O’Halloran
2 Mathematical Toolchest
AW Plank Et NH Williams
3 International Mathematics Tournament of Towns 1984-1989 Book 2
PT Taylor
4 Australian Mathematics Competition Book 2 1985-1991
PJ O’Halloran, G Pollard Et PJ Taylor
5 Problem Solving Via the AMC
W Atkins
6 International Mathematics Tournament of Towns 1980-1984 Book 1
PT Taylor
7 International Mathematics Tournament of Towns 1989-1993 Book 3
PJ Taylor
8 Asian Pacific Mathematics Olympiads 1989-2000
H Lausch Et C Bosch Giral
9 Methods Of Problem Solving Book 1
JB Tabov Et PJ Taylor
10 Challenge! 1991-1995
JB Henry, J Dowsey, AR Edwards, U Mottershead,
A Nakos Et G Vardaro
11 USSR Mathematical Olympiads 1989-1992
AM Slinko
12 Australian Mathematical Olympiads 1979-1995
H Lausch Et PJ Taylor
13 Chinese Mathematics Competitions and Olympiads 1981-1993
A Liu
,14 Polish ft Austrian Mathematical Olympiads 1981- 1995
ME Kuczma Et E Windischbacher
,15 International Mathematics Tournament of Towns 1993-1997 Book 4
PJ Taylor Et AM Storozhev
,16 Australian Mathematics Competition Book 3 1992-1998
WJ Atkins, JE Munro Et PJ Taylor
,17 Seeking Solutions
JC Burns
,18 101 Problems in Algebra
T Andreescu Et Z Eeng
,19 Methods of Problem Solving Book 2
JB Tabov Et PJ Taylor
,20 Hungary-Israel Mathematics Competition: The First Twelve Years
S Gueron
,21 Bulgarian Mathematics Competition 1992-2001
BJ Lazarov, JB Tabov, PJ Taylor Et A Storozhev
,22 Chinese Mathematics Competitions and Olympiads 1993-2001 Book 2
A Liu
,23 International Mathematics Tournament of Towns 1997-2002 Book 5
AM Storozhev

CONTENTS
•	FOREWORD	1
•	PREFACE	3
•	ACKNOWLEDGEMENTS	5
•	TOURNAMENT	19	9
Junior Questions	9
Senior Questions	1 4
Junior Solutions	20
Senior Solutions	33
• TOURNAMENT	20	53
Junior Questions	53
Senior Questions	57
Junior Solutions	63
Senior Solutions	76
• TOURNAMENT	21	93
Junior Questions	93
Senior Questions	98
Junior Solutions	103
Senior Solutions	11 4
• TOURNAMENT 22	131
Junior Questions	1 31
Senior Questions	136
Junior Solutions	142
Senior Solutions	1 56
• TOURNAMENT 23	173
Junior Questions	173
Senior Questions	178
Junior Solutions	182
Senior Solutions	1 95
• GENERAL REFERENCES	211

FOREWORD
This is the fifth book covering the problems and solutions of the In-
ternational Mathematics Tournament of Towns. I worked through the
original manuscripts and produced the first three books, while my val-
ued colleague Andrei Storozhev took over this work half way through the
fourth book. This fifth book is attributable completely to Andrei.
There is something special about the problems in the Tournament and
this collection, bringing us up to 2002, is no exception. Many of the
problems are accessible to students without too much experience, but
some are extremely challenging by any international standard. However
the difficult problems are not difficult for the sake of being so. There
is normally something beautiful in the structure and the achievement of
solving one of these problems always provides the thirst to want to solve
more.
The problems are also highly innovative and some of the methods needed
in solving these problems are often quite new also. One feels often at the
cutting edge when attempting these problems.
One of the underlying features of this book which is easily noticed is that
most of the solutions offered are by Andy Liu, of Edmonton. Whereas
the problems are innovative, Andy is one of the world’s most renowned
problem solvers, and I hope that the reader gains as much joy from
Andy’s solutions as they do from attempting the problems.
I hope you enjoy this book as much as the others.
Peter Taylor
Executive Director
Australian Mathematics Trust
08 December 2005

PREFACE
We refer the reader to the Prefaces to previous books, particularly Book
2, which contains a detailed history of the Tournament.
Further Comments
Anyone seeking further information about the Tournament is referred to
the official tournament web site at
http: //www.amt.edu.au/imtotgen.html
h
ACKNOWLEDGEMENTS
The names of the Problem authors and solvers are acknowledged during
the text as appropriate.
Peter Taylor gave considerable assistance in the type-setting and proof-
reading while thanks are also due to Clarice McLean for proof-reading.
TOURNAMENT 19

TOURNAMENT 19
JUNIOR QUESTIONS
Autumn 1997 (0 Level)
1.	On an escalator which is not moving, a person descends faster than
he ascends. Is it faster for this person to descend and ascend once
on an upward-moving escalator, or to descend and ascend once on
a downward-moving escalator? (It is assumed that all the speeds
mentioned here are constant, that the speed of the escalator is the
same no matter if it is moving up or down and that the speed of
the person relative to the escalator is always greater than the speed
of the escalator.)	(Folklore, 3 points)
2.	Prove that the equation x2 + y2 — z2 = 1997 has infinitely many
solutions in integers a;, у and z.	(N Vassiliev, 3 points)
3.	In a square ABCD. К is a point on the side BC and the bisector
of LKAD cuts the side CD at the point M. Prove that the length
of segment AK is equal to the sum of the lengths of segments DM
and BK.	(Folklore, 4 points)
4.	We want to draw a number of straight lines such that for each
square of a chessboard, at least one of the lines passes through an
interior point of the square. What is the smallest number of lines
needed for a
(a)	3x3;
(b)	4x4
(2 points)
(4 points)
chessboard? Use a picture to show that this many lines are enough,
and prove that no smaller number would do.	(M Vyalyi)
10
TOURNAMENT 19
Autumn 1997 (A Level)
1.	The sequence Xi, x%,... is defined by the following equations:
Ж1 19, Ж 2	97, Ж?г_|-2
^n+1
for n > 1. Prove that there exists a positive integer к such that
Xk — 0 and find k.	(A Berzinsh, 3 points)
2.	M is the midpoint of the side BC of a triangle ABC. Construct
a line I intersecting the triangle and parallel to BC such that the
segment of I between the sides AB and AC is the hypotenuse of a
right-angled triangle with M being its third vertex.
(Folklore, 3 points)
3.	Initially there is a checker on every square of a 1 x n board. The
first move consists of moving a checker to an adjacent square thus
creating a stack of two checkers. Then each time when making a
move, one can choose a stack and move it in either direction as
many squares on the board as there are checkers in the stack. If
after the move the stack lands on a non-empty square, it is placed
on top of the stack which is already there. Prove that it is possible
to stack all the checkers on one square in n — 1 moves.
(A Shapovalov, 5 points)
4.	Two circles intersect at points A and B. A common tangent touches
the first circle at point C and the second at point D. Let ACBD >
ACAD. Let the line CB intersect the second circle again at point
E. Prove that AD bisects the angle CAE.
(P Kozhevnikov, 5 points)
5.	Each face of a cube is of the same size as each square of a chess-
board. The cube is coloured black and white, placed on one of
the squares of the chessboard and rolled so that each square of the
chessboard is visited exactly once. Can this be done in such a way
that the colour of the visited square and the colour of the bottom
face of the cube are always the same? (A Shapovalov, 8 points)
Junior Questions
11
6.	Lines parallel to the sides of an equilateral triangle are drawn so
that they cut each of the sides into 10 equal segments and the tri-
angle into 100 congruent triangles. Each of these 100 triangles is
called a “cell”. Also lines parallel to each of the sides of the origi-
nal triangle are drawn through each of the vertices of the original
triangle. The cells between any two adjacent parallel lines form a
“stripe”. What is the maximum number of cells that can be chosen
so that no two chosen cells belong to one stripe?
(R Zhenodarov, 9 points)
12
TOURNAMENT 19
Spring 1998 (О Level)
1.	Anya, Borya, and Vasya listed words that could be formed from a
given set of letters. They each listed a different number of words:
Anya listed the most, Vasya the least. They were awarded points
as follows. Each word listed by only one of them scored 2 points
for this child. Each word listed by two of them scored 1 point for
each of these two children. Words listed by all three of them scored
0 points. Is it possible that Vasya got the highest score, and Anya
the lowest?	(A Shapovalov, 3 points)
2.	A chess king tours an entire 8x8 chess board, visiting each square
exactly once and returning at last to his starting position. Prove
that he made an even number of diagonal moves.
(V Proizvolov, 3 points)
3.	AB and CD are segments lying on the two sides of an angle whose
vertex is O. A is between О and B, and C is between О and D.
The line connecting the midpoints of the segments AD and BC
intersects AB at M and CD at N. Prove that
CM _ AB
~ON ” CD'
(V Senderov, 3 points)
4.	For every three-digit number, we take the product of its three digits.
Then we add all of these products together. What is the result?
(G Galperin, 4 points)
5.	Pinocchio claims that he can divide an isoceles triangle into three
triangles, any two of which can be put together to form a new
isosceles triangle. Is Pinocchio lying? (A Shapovalov, 5 points)
Junior Questions
13
Spring 1998 (A Level)
1.	Do there exist 10 positive integers such that each of them is divis-
ible by none of the other numbers but the square of each of these
numbers is divisible by each of the other numbers?
(Folklore, 3 points)
2.	ABCD is a parallelogram. A point M is found on the side AB
or its extension such that LMAD = LAMO where О is the point
of intersection of the diagonals of the parallelogram. Prove that
MD = MC.	(M Smurov, 3 points)
3.	Six dice are strung on a rigid wire so that the wire passes through
two opposite faces of each die. Each die can be rotated indepen-
dently of the others. Prove that it is always possible to rotate the
dice and then place the wire horizontally on a table so that the
six-digit number formed by their top faces is divisible by 7. (The
faces of a die are numbered from 1 to 6; the sum of the numbers
on opposite faces is always equal to 7.) (G Galperin, 4 points)
4.	A traveller visited a village whose inhabitants either always tell the
truth or always lie. The villagers stood in a circle facing the cen-
tre of the circle, and each villager announced whether the person
standing to his right is a truth-teller. On the basis of this infor-
mation, the traveller was able to determine what fraction of the
villagers were liars. What was this fraction? (B Frenkin, 4 points)
5.	A square is divided into 25 small squares. We draw diagonals of
some of the small squares so that no two diagonals share a common
point (not even a common endpoint). What is the largest possible
number of diagonals that we can draw? (I Rubanov, 7 points)
6.	10 people are sitting at a round table. There are some nuts in front
of each of them, 100 nuts altogether. After a certain signal each
person passes some of his nuts to the person sitting to his right. If
he has an even number of nuts, he passes half of them; otherwise
he passes one nut plus half of the remaining nuts. This procedure
is repeated over and over again. Prove that eventually everyone
will have exactly 10 nuts.	(A Shapovalov, 8 points)
14
TOURNAMENT 19
SENIOR QUESTIONS
Autumn 1997 (0 Level)
1.	We want to draw a number of straight lines such that for each
square of a chessboard, at least one of the lines passes through an
interior point of the square. What is the smallest number of lines
needed for a
(a)	3 x 3;
(b)	4x4
(2 points)
(3 points)
chessboard? Use a picture to show that this many lines are enough,
and prove that no smaller number would do.	(M Vyalyi)
2.	Let a and b be two sides of a triangle. How should the third side c be
chosen so that the points of contact of the incircle and the excircle
with side c divide that side into three equal segments? (The excircle
corresponding to the side c is the circle which is tangent to the side
c and to the extensions of the sides a and b.) (Folklore, 3 points)
3.	Prove that the equation
xy(x — y) + yz(y — z) + zx(z — x) = 6
has infinitely many solutions in integers ж, у and z.
(N Vassiliev, 4 points)
4.	The maximum possible number of knights are placed on a 5 x 5
chessboard so that no two attack each other. Prove that there is
only one possible placement.	(A Kanel, 4 points)
Senior Questions
15
Autumn 1997 (A Level)
1.	M and N are the midpoints of the sides AB and AC of a triangle
ABC respectively. P and Q are points on the sides AB and AC
respectively such that the bisector of the angle AC В also bisects
the angle MCP, and the bisector of the angle ABC also bisects the
angle NBQ. If AP = AQ, does it follow that ABC is isosceles?
(V Senderov, 4 points)
2.	Which of the following statements are true?
(a)	If a polygon can be divided into two congruent polygons by
a broken line segment, it can be divided into two congruent
polygons by a straight line segment.	(1 point)
(b)	If a convex polygon can be divided into two congruent poly-
gons by a broken line segment, it can be so divided by a
straight line segment.	(2 points)
(c)	If a convex polygon can be divided into two polygons by a
broken line segment, one of which can be mapped onto the
other by a combination of rotations and translations, it can
be so divided by a straight line segment.
(S Markelov, 4 points)
3.	All expressions of the form
±У1 ± V2 ± • • • ± \/100
(with every possible combination of signs) are multiplied together.
Prove that the result is:
(a)	an integer;
(b)	the square of an integer.
(3 points)
(A Kanel, 3 points)
4.	(a) Several identical napkins, each in the shape of a regular hex-
agon, are put on a table (the napkins may overlap). Each
napkin has one side which is parallel to a fixed line. Is it
always possible to hammer a few nails into the table so that
each napkin is nailed with exactly one nail? (4 points)
(b) The same question for regular pentagons.
(A Kanel, 4 points)
16
TOURNAMENT 19
5.	Dima invented a secret code in which every letter is replaced by a
word no longer than 10 letters. A code is called “good” if every
encoded word can be decoded in only one way. Serjozha (with the
help of a computer) checked that for Dima’s code, every possible
word of at most 10000 letters can be decoded in only one way. Does
it follow that Dima’s code is good? (Note that Dima and Serjozha
are Russian, so they use the Cyrillic alphabet, which has 33 letters!
A word is any sequence of letters.)
(D Piontkovskiy, S Shalunov, 8 points)
6.	Lines parallel to the sides of an equilateral triangle are drawn so
that they cut each of the sides into n equal segments and the trian-
gle into n2 congruent triangles. Each of these n2 triangles is called
a “cell”. Also lines parallel to each of the sides of the original trian-
gle are drawn through each of the vertices of the original triangle.
The cells between any two adjacent parallel lines form a “stripe”.
(a)	If n — 10, what is the maximum number of cells that can be
chosen so that no two chosen cells belong to one stripe?
(7 points)
(b)	The same question for n = 9. (R Zhenodarov, 7 points)
Senior Questions
17
Spring 1998 (0 Level)
1.	Pinocchio claims that he can take some non-right-angled triangles,
all of which are similar to one another and some of which may
be congruent to one another, and put them together to form a
rectangle. Is Pinocchio lying?	(A Fedotov, 3 points)
2.	For every four-digit number, we take the product of its four digits.
Then we add all of these products together. What is the result?
(G Galperin, 3 points)
3.	What is the maximum number of colours that can be used to paint
an 8 x 8 chessboard so that every square is painted in a single
colour, and is adjacent, horizontally, vertically but not diagonally,
to at least two other squares of its own colour?
(A Shapovalov, 3 points)
4.	For some positive numbers А, В, C and D, the system of equations
x2 + y2 — A and |ж| + \y\ — В
has m solutions, while the system of equations
x2 + y2 + z2 = C and |ж| + \y\ + \z\ = D
has n solutions. If m > n > 1, find m and n.
(G Galperin, 4 points)
5.	A circle with center О is inscribed in an angle. Let A be the
reflection of О across one side of the angle. Tangents to the circle
from A intersect the other side of the angle at points В and C.
Prove that the circumcenter of triangle ABC lies on the bisector
of the original angle.	(I Sharygin, 5 points)
18
TOURNAMENT 19
Spring 1998 (A Level)
1.	Prove the inequality
a3	b3	c3	> a + b + c
a2 + ab + b2 b2 + be + c2	c2 + ca + a2 ~	3
where a, b and c are positive real numbers. (S Tokarev, 4 points)
2.	A square of side 1 is divided into rectangles. We choose one of
the two smaller sides of each rectangle (if the rectangle is a square,
then we choose any of the four sides). Prove that the sum of the
lengths of all the chosen sides is at least 1. (Folklore, 4 points)
3.	(a) The numbers 1, 2, 4, 8, 16, 32, 64, 128 are written on a black-
board. We are allowed to erase any two numbers and write
their difference instead (this is always a non-negative num-
ber). After this procedure has been repeated seven times,
only a single number will remain. Could this number be 97?
(2 points)
(b) The numbers 1, 2, 22, 23, ..., 210 are written on a blackboard.
We are allowed to erase any two numbers and write their dif-
ference instead (this is always a non-negative number). After
this procedure has been repeated ten times, only a single num-
ber will remain. What values could this number have? (A
Shapovalov, 3 points)
4.	A point M is found inside a convex quadrilateral ABCD such that
triangles AMB and CMD are isoceles (AM = MB, CM = MD)
and /.AMB = /CMD = 120°. Prove that there exists a point N
such that triangles BNC and DNA are equilateral.
(I Sharygin, 5 points)
5.	A “labyrinth” is an 8 x 8 chessboard with walls between some neigh-
boring squares. If a rook can traverse the entire board without
jumping over the walls, the labyrinth is “good”; otherwise it is
“bad”. Are there more good labyrinths or bad labyrinths?
(A Shapovalov, 6 points)
Senior Questions
19
6.	(a) Two people perform a card trick. The first performer takes 5
cards from a 52-card deck (previously shuffled by a member of
the audience), looks at them, and arranges them in a row from
left to right: one face down (not necessarily the first one), the
others face up. The second performer guesses correctly the
card which is face down. Prove that the performers can agree
on a system which always makes this possible. (6 points)
(b) For their second trick, the first performer arranges four cards
in a row, face up; the fifth card is kept hidden. Can they
still agree on a system which enables the second performer to
correctly guess the hidden card? (G Galperin, 6 points)
20
TOURNAMENT 19
JUNIOR SOLUTIONS
Autumn 1997 (0 Level)
1. Let d, и and e be the speeds of the person descending, the per-
son ascending and the escalator, respectively. Then the person
descends a downward-moving escalator at the speed d + e and an
upward-moving escalator at d — e, and ascends a downward-moving
escalator at the speed u—e and an upward-moving escalator at u+e.
We may assume that the length of the escalator is 1. Then the time
for a round-trip on a downward-moving escalator is
1	1	d + и
d + e и — e (d + e)(u — e)
while that on an upward-moving escalator is
1	1	d + и
d — e u + e (d — e) (u + e)'
Now
(d + e) (u — e) = du — e2 + ue — de
while
(d — e)(u + e) = du — e2 — ue + de.
Since d > u, we have
(d + e)(u - e) < (d — e)(u + e).
Therefore it is faster to descend and ascend once on an upward-
moving escalator.
(A Liu)
2. We have
(y — z)(y + z) — 1997 — x2.
Let x = 2t for any integer t. We may set у — z = 1 and у + z =
1997 — 4t2. Addition and substraction yield 2y = 1998 — 4t2 and
2z = 1996 — 4t2 respectively. Hence
(ж, у, z) = (2t, 999 - 2t2,998 - 2t2)
is a solution of x2 + y2 — z2 = 1997. Since t is an arbitrary integer,
there are infinitely many solutions.
(A Liu)
Junior Solutions
21
3. Extend KB to L such that BL = DM.
Since AB = AD and AABL = 90° = AADM, triangles ABL
and ADM are congruent. Hence ABAL = ADAM and AALK =
AAMD. Now
AKAL = AB AL + AKAB
= AM AD + AKAB
= AMAK + AK AB
= AMAB
= AAMD
since AB and DC are parallel. It follows that AKAL = AALK,
and therefore AK = KL = KB + BL = KB + DM.
(A Liu)
4. We claim that a line can intersect at most m + n — 1 squares of
an m x n chessboard in an interior point. Now there are m — 1
horizontal and n — 1 vertical grid lines inside this chessboard. In
passing from the interior of one square to the next, a straight line
must cross one of these m+n—2 grid lines. Since two lines intersect
in at most one point, this line is divided into at most m + n — 1
segments by the grid lines. This justifies the claim.
22
TOURNAMENT 19
(a)	On a 3 x 3 chessboard, a line can intersect at most 5 squares
in an interior point. Hence we need at least 2 lines, and the
diagram below shows that 2 lines are enough.
(b)	On a 4 x 4 chessboard, a line can intersect at most 7 squares
in an interior point. Hence we need at least 3 lines, and the
diagram above shows that 3 lines are enough.
(A Liu)
Junior Solutions
23
Autumn 1997 (A Level)
1.	Note that
1
*^n+2 — Xn
•Sn+l
implies
*^n+2^n+l Zn-f-lLn 1-
Now let yk = жд;+1Жд; for к > 1. Then the sequence 2/1, Z/2,... is
defined by тд = 19 x 97 = 1843 and yn+i = Уп — 1- Clearly, if
yk 0 neither xk nor xk+\ equals 0. The smallest к such that
yk = 0 is к = 1844.
Therefore xn 0 for 1 < n < 1844. But #1845^1844 = ?/i844 = 0
and Ж1844 7^ 0. Hence ад845 = 0. Thus the answer is 1845.
(A Liu)
2.	Alternative 1
Construct a semicircle with diameter BC outside triangle ABC.
Let it cut the extension of AM at N. Through M, draw the line
parallel to BN, cutting AB at K. Through K, draw the line
parallel to BC, cutting CA at L. We claim that KL is the desired
line. Note that BAN and KAM are similar triangles, as are ВАС
and К AL. It follows that so are NBC and M КL. Hence /.KML =
ABNC = 90°.
(A Liu)
24
TOURNAMENT 19
Alternative 2
Let X and Y be points on the sides AB and AC respectively such
that MX besects LB MA and MY bisects LCM A. Then
AX _ AM _ AM _ AY
XB ~ BM ~ CM ~ YC'
Hence XY is parallel to BC.
Also
LXMY-
LX MA + LYMA
-LBMA+-LCMA
2	2
| (LBMA+ LCMA)
90°
so triangle YXM is right-angled.
Clearly I is unique. Therefore I passes through X and Y.
(A Storozhev)
3.	Start with a square which is closest to the centre of the board. Then
move to the next square which is on the other side of the centre of
the board (to either of the neighbouring squares if n is odd). Then
each time when making a move, go to the next occupied square on
the other side of the centre of the board.
(A Liu)
4.	Draw AB. Then LCAB = LBCD and LDAB = LBDC by the
alternate segment theorem.
Hence
LCAD = LBCD + LBDC.
Junior Solutions
25
On the other hand,
LEBD = LBCD + LBDC
and LEBD = LEAD. Hence
LEAD = LBCD + LBDC.
Thus LCAD = LEAD.
(A Liu)
5.	The answer is no.
We first consider the 2x2 board. We may assume that the cube
starts on the top left corner square which is black. Hence the
current bottom face of the cube is black. We may also assume that
the next move is to the white square on the right. The current
left face is black. In the third move, we come to the bottom right
black square, and the current left face is still black. However, this
face must land on the bottom left white square in the last move,
violating the colour-matching condition.
Consider now the ordinary 8x8 board. Label the rows 1 to 8
and the columns a to h. Suppose a tour is possible. Divide the
chessboard into four quadrants. We may assume that the tour
does not start or finish in the quadrant containing square al. On
the tour, al must be between 61 and a2. Now 61 cannot be between
al and 62, as otherwise the cube would have completed a tour on
a 2 x 2 board. Similarly, a 2 is not between al and 62. Thus a
sequence of moves is
cl — 61 — al — a2 — a3.
26
TOURNAMENT 19
Consider now the square 62. The same reasoning shows that we
have
d2 — c2 — 62 — 63 — 64,
so that the previous sequence must be expanded to
dl — cl — 61 — al — a2 — a3 — a4.
By considering c3, d4 and so on, we will have
el — dl — cl — 61 — al — a2 — a3 — a4 — a5,
e2 — d2 — c2 — 62 — 63 — 64 — 65,
e3 — d3 — c3 — c4 — c5
and
e4 — d4 — db.
Now there is another quadrant which does not contain either the
starting or finishing points of the tour, so that the analogous sit-
uation occurs there. However, the cube must complete a tour on
the 2x2 board consisting of the squares d4, d5, e4 and eb. This is
a contradiction.
(A Liu)
6.	See solution to Problem 6 in Senior paper.
Junior Solutions
27
Spring 1998 (0 Level)
1.	The answer is yes. Let 2 words be listed by Borya alone, 4 words
by Vasya alone, 6 words by Anya and Borya only, and 3 words by
Anya and Vasya only. Then Anya, Borya and Vasya have listed 9,
8 and 7 words, and scored 9, 10 and 11 points, respectively.
(A Liu)
2.	When the king moves vertically or horizontally, it changes the
colour of the square it is on. In a diagonal move, it maintains
that colour. Since the king returns to his starting square, it must
have changed colours an even number of times. Hence it has made
an even number of diagonal moves as the total number of moves
that the king has made is even.
(A Liu)
3.	Alternative 1
Denote by [T] the area of triangle T. Let X and Y be the midpoints
of AD and BC respectively.
Since AX = DX, we have [AAA] = [ATT]. Similarly, [MAX] =
[MDX]. Therefore
[MAA] = [AAA] + [MAA]
= [ADA] + [MDX]
= [MDN].
Thus [MAA] = [MDA] and sumilarly [MBA] = [MCA] as Y is
the midpoint of BC. Hence
[ABN] = [MAA] + [MBA]
= [MDA] + [MCA]
= [CDM]
28
TOURNAMENT 19
So [AB7V] = [CDM] and therefore
OM _ [OMN]
~AB ~ [ABN]
[OMN]
[CDM]
ON
~CD'
Thus
OM _ AB
~0N ~ CD'
(A Liu)
Alternative 2
Let X, Y and Z be the midpoints of AD, BC and AC respectively.
Then XZ\]ON and YZ]\OM. Hence XYZ and NMO are similar
triangles. Therefore
OM _ ZY
~ON ~ ZX'
Since ZX — CD and ZY — ^AB, we obtain
OM _ AB
~0N ~ ~CD'
(A Storozhev)
4.	More generally, let Sn denote the answer when we are dealing with
n-digit numbers. We shall prove by induction that Sn — 45n. For
n = 1, we have
= 1 + 2 + • • • + 9 = 45.
Suppose the result holds for some n > 1. Consider now (n+l)-digit
numbers whose first digit is k, where к is any of 1, 2, ..., 9. The
Junior Solutions
29
sum of the products of the digits of these numbers is equal to the
common factor к times Sn, so that
Sn+1 = (1 + 2 +  • • + 9)S„ = 45"+1.
This completes the inductive argument. In particular, Ss — 45 .
(A Liu)
5.	The answer is no, Pinocchio is not lying.
В
А	К H C
Consider a triangle ABH such that AH = BH = 1 and L АН В =
90°. Produce AH to point C such that HC = V2 — 1 and H is
between A and C. Now by Pythagoras’ theorem AB = -\/2 and
AC = AH + HC = y/2. So ABC is an isosceles triangle.
Let A? be a point on AH between A and H such that KH = HC.
Then triangles BHK and BHC are congruent and hence В К =
BC. Now it is easily seen that any two of triangles ABK, BHK
and BHC can be put together to form an isosceles triangle.
(A Storozhev)
30
TOURNAMENT 19
Spring 1998 (A Level)
1.	The answer is yes.
Let pi, 1 < i < 10 be distinct primes and P be their product. For
1 < i < 10, define Xi = piP. For i j, clearly, Xi does not divide
Xj since pi does not divide pj. On the other hand, since pi divides
P, Xi divides x?.
(A Liu)
2.	Extend MO to cut CD at N. Since AM AD = AAMN, AMND is
an isosceles trapezoid. By symmetry, AM = NC so that AMCN is
a parallelogram. Hence AM DC = A AND — AM CD and therefore
MC = MD.
(A Liu)
3.	There are three pairs of numbers on opposite faces, 1 and 6, 2 and
5, and 3 and 4. For each of the dice, numbers from exactly two
pairs can appear on top. Hence for any two dice, we can arrange
for the same number to appear on top of both of them.
Now 7 is a divisor of 1001. If we arrange for the top face of the
first and the fourth dice to have the same number, and the same
for the second and the fifth dice, as well as for the third and the
sixth dice, then the six-digit number obtained will be a multiple of
7.
(A Liu)
4.	If one villager claimed that the next one was a truth-teller, then
both were of the same type. If the villager claimed that the next
one was a liar, then they were of opposite types.
Hence the traveller could tell what fraction of the villagers were of
one type, and the remainder of the opposite type, but not which
was which. Since he knew, the fraction must be |.
(A Liu)
Junior Solutions
31
5.	The board may be regarded as a 6 x 6 array of dots and each
diagonal uses 2 of them. Thus we can have at most 18 diagonals.
At least 1 of the 6 dots along an edge of the array must be unused.
Otherwise, each will be joined to a dot in the adjacent line, and
2 diagonals will cross. Hence the total number of diagonals is at
most 17.
To have this many, only 2 dots are unused. Since they have to
cover all four edges of the array, they must be at opposite corners.
This implies that each side of the square contains endpoints of five
diagonals and all these diagonals are parallel. It is easily seen that
this is not possible. Hence the total number of diagonals is at
most 16. The figure below shows that we can have as many as 16
diagonals.
(A Liu)
6.	For 1 < i < 10 and j > 1, let the г-th child keep nuts and
give away gi(f) nuts on the j'-th move. Then gi(j') — k^f) < 1 for
all i and j. Now
cZi-i(J) + ki(j) = kt(j + 1) + gi(j + 1),
where go(f) is to be interpreted as <7io(«7) for all j. Since ki(j + 1)
and gi(j + 1) are at least as close to each other as ^-i(j) and ki(f),
we have
tei-iO'))2 + (Mj))2 > (kiU + l))2 +	+ i))2-	(*)
Define
io
s(j) = E((fc.o))2 + ЫЛ)2)-
i—1
Then (*) shows that S(f) is a non-increasing function of j with
positive integral values. Hence it must reach its minimum value
S(t) for some t. This means that for j > t and 1 < i < 10,
\gi-i(j) ~ ki(j)\ < 1.
32
TOURNAMENT 19
Therefore two adjacent numbers in the sequence ki(j), gi(j),
^2(7), • • , ^io(j), <710(7) in this cyclic order differ by at most 1.
Suppose not all of them are 5s. Then there exist i and I such that
= 6,
ki+i(t) = ^+i(t) = • • • = k^t) = g^t) = 5
and (t) =4.
Now Pi+i(t +1) = 6,
ki+^t +1) = gi+2(,t + !) = ••• = ke(t + 1) = gi(t + 1) = 5
and + 1) = 4. Eventually, we have ge(t + € — i) = 6 and
k^+i(t + € — i) = 4, but they are supposed to differ by at most 1.
This contradiction shows that all twenty numbers are 5s, so that
each child has 10 nuts after the t-th move.
(A Liu)
Senior Solutions
33
SENIOR SOLUTIONS
Autumn 1997 (O Level)
1.	We claim that a line can intersect at most m + n — 1 squares of
an m x n chessboard in an interior point. Now there are m — 1
horizontal and n — 1 vertical grid lines inside this chessboard. In
passing from the interior of one square to the next, a straight line
must cross one of these m+n —2 grid lines. Since two lines intersect
in at most one point, this line is divided into at most m + n — 1
segments by the grid lines. This justifies the claim.
(a)	On a 3 x 3 chessboard, a line can intersect at most 5 squares
in an interior point. Hence we need at least 2 lines, and the
diagram below shows that 2 lines are enough.
(b)	On a 4 x 4 chessboard, a line can intersect at most 7 squares
in an interior point. Hence we need at least 3 lines, and the
diagram above shows that 3 lines are enough.
(A Liu)
2.	Let the triangle be ABC with BC — a, CA = b and AB = c.
34
TOURNAMENT 19
We cannot have a = b as otherwise both circles will be tangent to
AB at its midpoint. We may assume that a > b. Let the incircle
be tangent to BC at P, CA at E and AB at F. Then AF = f
and BF — y- It follows that
a-b= (BD + CD) - (AE + CE) = BD - AE = BF - AF = -.
3
Hence we should choose c = 3(6 — a). We still have to check that
for this choice, AB is also trisected by its point of tangency with
the excircle opposite C. Let this circle be tangent to the extension
of CB at G, the extension of CA at H and AB at K. Then
AK + BK = c while
AK-BK = AH-BG
= (CH - CA) - (CG - CB)
= CB-CA
= a — b
c
3’
Thus we indeed have AK = and В К = |.
(A Liu)
3.	We have
6 = xy(x - y) + yz(y - z) + zx(z - x)
= xy(x — y) + y2z — x2z + z2x — z2y
= xy(x-y) + z(y2-x2) + z2(x-y)
= (x - y)(xy - ZX - zy + z2)
= (x-y)(x -z)(y-z).
Thus (ж — y)(x — z)(y — z) = 6. Clearly, (x,y, z) = (3,1,0) is a
solution. Then for any integer t, (ж, у, z) = (t + 3, t + 1, t) is also a
solution. Hence there are infintely many solutions.
(A Liu)
4.	A knight can visit all 25 squares of a 5 x 5 chessboard once and
only once. In the diagram below, it starts on square 1 and visits
the other squares in numerical order. If two knights occupy squares
with consecutive numbers, they will attack each other. Hence we
must leave vacant at least every other square on this knight tour.
This means that we can put at most 13 knights on the chessboard
if they are not to attack one another. Moreover, if we have exactly
Senior Solutions
35
13 knights, the only way is to put all of them on the odd-numbered
squares. It is easily seen that no two knights on odd-numbered
squares attack each other.
7	20	25	14	5
18	13	6	9	24
21	8	19	4	15
12	17	2	23	10
1	22	11	16	3
(A Liu)
36
TOURNAMENT 19
Autumn 1997 (A Level)
1. Alternative 1
The answer is no.
Let ABC be a triangle such that LABC = 90°, AB = 1 and
cos(ZBAC) =	.
The bisector of LABC also bisects LN BQ. This gives LNBC =
LQBA. Similarly LMCA = LPCB.
Since N is the midpoint of AC and LABC = 90°, NC = NB.
Hence LNBC = LNCB. Therefore LQBA = LACB, which means
that LAQB = 90°.
AB 1
Let LB AC = a. From A ABC, AC = ------ — ---- and BC =
cos a cos a
ABtaiia = tana. From L\ABQ, AQ = AB cos a = cos a and
BQ — AB sin a = sin a.
Let R be the foot of the perpendicular from M to AC. Then
AR — -Q- and MR = as M is the midpoint of AB. Hence
, cos a , , r sin a
AR =------- and MR =---------.
2
2
CR MR
Since triangles CRM and СВР are similar, —— =	. Hence
CB BP
sin a tan a
MRxCB	о	sin2 a
BP —----------=-----------=----------
CR	1 _ cos a 2 - cos2 a'
cos a 2
Therefore
AP = AB-BP
sin2 a 2 — cos2 a — sin2 a 1
2 — cos2 a 2 — cos2 a 2 — cos2 a
Senior Solutions
37
/	\ 2
a. 2 M-il 3-^5
Since cos a = I —-— I = —-—, we
AP = Ъ-----Ц- ~	= AQ-
2 — cos2 a y/5 + 1	2
Thus AP = AQ and clearly AB < BC < AC.
(A Storozhev)
Alternative 2
AP = AQ does not imply that ABC is an isosceles triangle. In the
coordinate plane, let В be the origin (0,0), A be (2,2ж) and C be
(2,0), with x < 1 so that AB > ВС > CA. Then M is the point
(1,ж) and N the point (2, ж).
Let Q be the point (2, y). Then we have 0 < у < x.
Let AABN — 0 = /.QBC. Applying the Cosine Law to triangle
NBA, we have
л 4(ж2 + 1) + ж2 + 4 — ж2
cos 0 =-------, г п - 
2 • 2д/ж2 + 1\/ж2 + 4
From triangle QBC, we have
2
cos# = —.
V?y+4
Eliminating cos 0 yields
Rejecting the negative root, we have
ж2 + 2
Now let P be the point (t, tx). Then 1 < t < 2.
Let LACP = ф = ШСВ. Applying the Cosine Law to triangles
CAP and MBC, we have
4ж2 + (2 - t)2 + t2x2 - (2 - t)2 - (2 - г)2ж2
cos ф =-------------------,	-----------
2 • 2жУ(2 - t)2 + t2x2
38
TOURNAMENT 19
and
,	4 + ж2 + 1 — ж2 — 1
cos ф =--------1=	---,
2 • 2x/^TT
which simplifies to t2(rc4 — l)+4t — 4 = 0, so that
The latter must be rejected as otherwise t > 2. Hence
\/ж2 +1
From AP = AQ, we have ж4 + ж2 — 1 = 0, and a root satisfying
0 < ж < 1 is 
This yields a counterexample where AP = AQ and yet ABC is not
isosceles.
(A Liu)
2.	(a) The statement is not true - see (b).
(b)	The statement is not true.
Let А, В, C, D, E, X, Y, Z be eight points in the coor-
dinate plane: A(0,0), В(0,л/3), C(2,fy3), L»(|, ^), £/(1,0),
X(l,^3),
It is easily seen that ABC DE is a convex pentagon which can
be cut along the dotted broken line XYZE into two congruent
polygons.
If this pentagon can be cut into two congruent polygons by
a straight line segment, this line must pass through one of
Senior Solutions
39
the vertices of the pentagon. Also this line should divide the
perimeter of the pentagon in half. So there are only five pos-
sible lines that could be used for cutting the pentagon into
two congruent polygons. Simple checking shows that none of
them cuts the pentagon into two congruent polygons.
(c)	The statement is true.
Let a convex polygon P be cut into two polygons P± and P2 by
a broken line segment A± ... An so that P± can be mapped
onto P2 by a combination of rotations and translations. Let
n be the smallest possible number. If n > 2, then one of the
interior angles of P± is bigger than 180°. Since P is convex,
both this angle and the corresponding angle in P% are formed
by the broken line segment. Hence this angle is /.AiAi+iAi+2
and the corresponding angle is /.AjAj+±Aj+2 for some i and
j-
Now if \i — j| > 1, we can replace the sections AiAi+±Ai+2
and	of the broken line segment with А^А^+2 and
respectively, and get a shorter broken line segment.
If | г — j | = 1, say j = i + 1, then we can replace the section
AiAi+iAi+2A+3 with AiAi+3 and again get a shorter broken
line segment. Thus n = 2.
(A Storozhev)
3.	(a) See (b)
(b) It suffices to show that the product of all expressions of the
form 1 ± y/2 ± • • • ± yTOO is an integer. Let us consider a
polynomial P in 99 variables x±, X2, • • •, xgg which is equal to
the product of all polynomials of the form 1 ± x± ± • • • ± xgg.
If we substitute —Xi for each Xi in this product, the product
will be the same. Hence P does not have terms with odd
power of Xi. Since i is arbitrary, all terms in P have only
even powers of the variables. Therefore Р(л/2,..., л/ЮО) is
an integer.
(A Storozhev)
4.	(a) The answer is yes.
Consider a hexagonal grid in the same orientation as that of
the napkins. A nail at the centre of a hexagon of the grid
catches a napkin if and only if the centre of the napkin lies
inside or on the boundary of the hexagon.
If the centre of every napkin is not on any grid lines, we can
hammer nails at the centres of the hexagons of the grid to
40
TOURNAMENT 19
catch all napkins. No napkin can be nailed twice as otherwise
its centre is in two hexagons and hence on some grid line.
Suppose the centre of at least one napkin is on a grid line.
Let M be the set of centres of napkins not on any grid lines,
and N be the set of the centres of the other napkins. Since M
is finite, there exists a positive real number 8 such that each
point in M is at a distance at least 6 from all grid lines.
We can perform a parallel shift of the whole grid a distance
less than 5, so that all points in M are still not on any grid
lines. Since N is also finite, we can choose a direction for the
parallel shift so that all points in N come off the grid lines.
We can now hammer nails at the centres of the hexagons of
the new grid.
(b) The answer is no.
Let the napkins have side 1. Take a circle cj with radius 10.
Place napkins so that every circle of radius whose centre
is inside w contains the centre of at least one napkin. This
can be accomplished with a finite number of napkins.
Consider a point P inside cv. If a nail is hammered at P, it
will catch all napkins whose centres lie in a pentagon of side
1 with centre P, but in an orientation opposite to that of the
napkins. We call this the danger zone of P.
Consider any set of nails. Their danger zones are a set of pen-
tagons obtained from one another by translation. We claim
that there is always a circle of radius whose centre is in-
side such that the small circle is either inside at least two
danger zones or outside all danger zones. Since it contains the
centre of at least one napkin, this napkin will be hammered
either at least twice or not at all.
All that remains to be done is to justify the claim. We shrink
each danger zone towards its centre so that its side length
becomes . We consider two cases.
Case 1.
There is a point X inside w which is contained in at least
two shrunken danger zones. Then X is the centre of a circle
of radius which is inside both danger zones before they
shrink.
This is because the distance from the centre of a danger zone
to the nearest point on its boundary is greater than so
Senior Solutions
41
that the expansion of a shrunken danger zone will advance its
boundary by more than ^55 •
Case 2.
No two shrunken danger zones intersect. We shall show that
there is enough space between danger zones to fit in circles
of radii ^q. We may assume that a vertex F of a shrunken
danger zone is right up against a side AB of another danger
zone.
Although the two have no points in common, F may be so
close to AB that we can consider it to be on AB. By symme-
try, we may also assume that AF > BF.
Extend the other side of the second danger zone at the vertex
A to cut the boundary of the first at К.
Then triangle AFK is outside all shrunken danger zones. Now
99
FK = AF > —
- 200’
and the distance from К to AF is at least
99	99	1
—— sin 36	>	—— sin 30	>	-
200	200	5
We can fit a circle of radius ± between AF and the line joining
the midpoints of AK and FK. so that it lies inside triangle
AFK.
Let Y be the centre of this circle. Then the circle with centre
Y and radius is outside all danger zones. This is because
the distance from the centre of a danger zone to the farthest
point on its boundary is less than one, so that the expansion
of a shrunken danger zone will advance its boundary by less
than TjTj.
(A Liu)
42
TOURNAMENT 19
5.	The answer is yes.
Suppose Dima’s code is not good. Then there must be some blocks
which can be interpreted in two different ways, say Dima’s way
and Serjozha’s way. Consider such a block with minimum length
which, by Serjozha’s checking, must be at least 10001. Call each
block which Dima uses to replace a letter a word.
Since each word is of length at most 10, there must be at least
1001 words in Dima’s interpretation. Hence there are at least 1001
letters in the block which is an initial letter of a word in Dima’s
interpretation. By the Pigeonhole Principle, at least 31 of them
belong to identical words in Serjozha’s interpretation.
Now in Serjozha’s interpretation, these letters may be the г-th letter
of a word, 1 < г < 10. By the Pigeonhole Principle again, at least 4
of them have the same positional value i. Choose 2 of these letters.
Remove all letters between them along with one of them.
In Dima’s interpretation, complete words are removed, so that the
resulting block is still meaningful. In Serjozha’s interpretation, two
part-words are removed along with some complete words, but the
choice of the 2 letters ensure that the two part-words will combine
into a complete word.
Hence the resulting block is also meaningful here. Now we have
a shorter block which can be interpreted in two different ways, a
contradiction. Hence Dima’s code is good.
(A Liu)
6.	Alternative 1
(a)	We can interprete the location of a cell as a triple (a, b, c) of
integers a, b, c such that 1 < a, b, c < 10 and either c = a + b
or c = a + 6— 1. It is easily seen that the cells (1,4,4), (2, 7, 8),
(3, 3, 5), (4,6, 9), (5, 2, 6), (6,5,10) and (7,1, 7) satisfy all the
restrictions.
Now assume that we have eight cells. Consider all cells (ж, у, z)
from this set of eight cells such that x > 5. There are at least
three such cells. For each of these cells, the second number of
the corresponding triple is one of the numbers 1, 2, 3, 4 and 5.
On the other hand, there are at least three cells (ж, у, z) such
that z < 6. Again for each of these cells, the second number
of the corresponding triple is one of the numbers 1, 2, 3, 4 and
5.
Senior Solutions
43
Since 3 + 3 > 5, there should be a cell (ж, у, z) that satisfies
x > 5 and z < 6, which is not possible. Thus the answer is
seven.
(b)	Using the same approach as in (a), we see that the cells
(1,4,4), (2,7,8), (3,3,5), (4,6,9), (5,2,6) and (7,1,7) sat-
isfy all the restrictions. Now assume that we have seven cells.
Consider all cells (ж, ?/, z') from this set of seven cells such that
ж > 4. There are at least three such cells.
For each of these cells, the second number of the corresponding
triple is one of the numbers 1, 2, 3, 4 and 5. On the other hand,
there are at least three cells (ж, ?/, z) such that z < 6. Again
for each of these cells, the second number of the corresponding
triple is one of the numbers 1, 2, 3, 4 and 5.
Since 3 + 3 > 5, there should be a cell (ж, ?/, z} that satisfies
ж > 4 and z < 6. There is only one such cell, namely (5,1, 5).
Thus the cell (5,1,5) has to be chosen. But we can show in
the same manner, that the cell (1, 5,5) also has to be chosen.
Since the cells (5,1,5) and (1,5,5) belong to one stripe, the
maximum number of cells we can chose is six.
Alternative 2
The shape of the triangle is immaterial, and we use instead an
isosceles right triangle in our illustrations. Let /(n) denote the
maximum number of chosen cells on a triangle each side of which
is divided into n parts, with no two such cells in the same stripe.
We claim that /(8) < 5. Suppose to the contrary that 6 cells can
be chosen. We divide the triangle into four zones as shown in the
diagram below.
44
TOURNAMENT 19
There are at most four chosen cells on the bottom four rows, so
that Zone A has at least 2. Similarly, so has each of Zones В and
D. Hence each of them has exactly 2, while Zone C has 0. Since
there are 4 chosen cells in Zones В and D, one of them must be P
or Q.
By symmetry, we may assume that P is chosen. This eliminates Q
and all cells marked o. Similarly, we must choose R and S, thereby
eliminating all cells marked •. Of the 3 cells remaining in Zones
A, В and D, at most 1 may be chosen.
This contradiction shows that /(8) < 5. Now f(n + 1) < f(n) + 1
for all n. Hence /(9) < 6 and /(10) < 7.
(a)	The diagram below shows that /(10) = 7. The chosen cells
are marked with •.
(b)	If we omit the bottom row in the diagram above, we have
/(9) = 6.
(A Liu)
Alternative 3
The aim is to prove /(n) = [(2n + l)/3]. It is easy to give an
example of exactly [(2n + l)/3] marked little triangles. The non-
trivial part is to show that this estimate is the best one.
Let us enumerate each line of the triangle. Choose one of the
three directions. The triangle is subdivided into n lines parallel
to this direction. These lines contain 1, 3, 5,..., 2n — 1 triangles,
respectively.
Let us enumerate these n lines in the following way: n, n — 1,..., 1.
Do the same for each direction. Now, for each little triangle, we
Senior Solutions
45
define its weight as a sum of numbers of the lines it belongs to. It is
easy to check that each little triangle that has the same orientation
as the big one, has weight n + 2.
Also it is easy to see that all the other little triangles have weight
n + 1. Suppose we have marked к little triangles such that no line
contains two of them. By S we denote the sum of weights of the
marked triangles. By the above, S < k(n + 2).
For each of the three directions, к triangles occupy к different lines.
Obviously, the sum of numbers of к different lines is at least 1 +
2 + • • • + к = k(k + l)/2. This implies S > 3k(k + l)/2.
As a result, 3k(k + l)/2 < k(n + 2) i.e. 3{k + 1) < 2(n + 2) or
к < (2n + l)/3.
(V Guba)
46
TOURNAMENT 19
Spring 1998 (О Level)
1.	The answer is no, Pinocchio is not lying.
He can put together eight (30°, 30°, 120°) triangles to form a rec-
tangle, as shown in the diagram below.
(A Liu)
2.	More generally, let Sn denote the answer when we are dealing with
n-digit numbers. We shall prove by induction that Sn = 45n. For
n — 1, we have = 1 -b 2 H- • - - 9 = 45. Suppose the result holds
for some n > 1. Consider now (n + l)-digit numbers whose first
digit is k, where к is any of 1, 2, ..., 9. The sum of the products of
the digits of these numbers is equal to the common factor к times
Sn, so that Sn+i = (1 + 2 + • • • + 9)Sn = 45n+1. This completes
the inductive argument. In particular, S4 = 454.
(A Liu)
3.	We continue to refer to the squares as Black or White even though
they are now painted with other colours. Only Black squares are
adjacent to White squares, and vice versa. A red Black square
must be adjacent to at least two red White squares, and a red
White square must be adjacent to at least two red Black squares.
Hence there must be at least 4 red squares.
This applies to each of the other colours. Since we have 64 squares
altogether, the number of colours is at most = 16. We may have
16 colours if we divide the chessboard into 16 sub-boards of size
2x2, and paint each in a different colour.
(A Liu)
4. If AB = 0, then the only possible solution to the first system
of equations is (x,y) = (0,0), but we are not interested in this
case since m < 1. If AB 0, the solutions are the points of
intersection of a circle and a square with the same centre. The
Senior Solutions
47
maximum value of m is 8. For the second system of equations, we
may assume as before that CD 0. Then the solutions are the
points of intersection of a sphere and a regular octahedron with
the same centre. The only positive value of n less than 8 is 6. It
follows that m = 8 and n = 6.
(A Liu)
5. Let T be the midpoint of AO and P be the vertex of the given
angle. Let P be closer to В than to C. Let Q be the point of
contact of the circle with AC. In triangle OQA, AOQA — 90° and
О A = 2OQ. Hence AOAQ = 30°. Therefore AO AB = 30°.
perpendicular to AO, we have
ABPT + 90° + 150° - 6 + 180° - 0 = 360°.
Hence A В PT = 20 — 60°, which means that ABPO = 0 — 30°.
Therefore ABOP = 30°. Since О is the incentre of triangle ABC,
ABOC = 90° + ^ABAC = 120°.
Now let R be the circumcentre of triangle ABC, then
ABRC = 2ABAC = 120°.
Hence BORC is a cyclic quadrilateral. In triangle BRC, ABRC =
120° and BR = RC. Hence ABCR = 30°. Therefore ABOR =
150°. Thus
APOB + ABOR = 180°,
and therefore P, O, R lie on a straight line.
(A Liu)
48
TOURNAMENT 19
Spring 1998 (A Level)
1. Note that
a3	ab(a + 6) a + b
a2 + ab + b2 a a2 + ab + b2 ~ a 3
since a2 + ab + b2 > 3ab.
o- -i !	, b + c	c3	c + a
Similarly,	>b-------— and -----------— >c----------
bz + be + c2	3 c2 + ca + a2	3
Addition yields the desired inequality.
(A Liu)
2. If the projections of the horizontal chosen sides on a horizontal side
of the square covers this side, the sum of the lengths of all chosen
sides is at least 1. Assume that there is a point A on a horizontal
side of the square such that the projections of the horizontal chosen
sides do not cover A and also assume that there is a point В on a
vertical side of the square such that the projections of the vertical
chosen sides do not cover B. Then there is a point X such that its
projections on the horizontal and vertical sides of the square are A
and В respectively. Since X belongs to a rectangle, the chosen side
of this rectangle contains the projection of X on this side. Hence
the projection of this side on the corresponding side of the square
contains one of the letters A and В which is a contradiction.
(A Liu)
3. (a) We replace 32 and 64 with 32, and replace 16 and the new 32
with 16. Then we replace 128 and the new 16 with 112, 112
and 8 with 104, 104 and 4 with 100, 100 and 2 with 98, and
finally 98 and 1 with 97.
(b) We prove more generally that if we start with the first n + 1
powers of 2, then all positive odd integers under 2n are ob-
tainable. We use induction on n. For n = 1, we can certainly
replace 2 and 1 to get 1. Suppose the result holds for some
n > 1. Consider the next case where the largest number is
2n+1. We can start off by replacing 2n+1 and 2n with 2n. By
the induction hypothesis, all positive odd integers under 2n
are obtained. Alternatively, save 2n+1 till the end. By the
induction hypothesis again, all odd positive integers under 2n
are obtainable. Combined with 2n+1, we can get all odd in-
tegers between 2n and 2n+1. This completes the inductive
argument.
(A Liu)
Senior Solutions
49
4.	Let cj = | + ^i. Then ca2 — ca + 1 = 0 and ca3 + 1 = 0. Let
M be the origin in the complex plane, and let A and C be repre-
sented by the complex numbers a and c respectively. Since В is
obtained from A by a 120°-rotation about M, it is represented by
the complex number aw2. Similarly, D is represented by cw2. The
point obtained from C by a 60°-rotation about В is represented
by ca(c — аса2) + аса2 = cw + a(l + ca2) = (c + d)ua. Similarly, the
point obtained from A by a 60°-rotation about D is represented by
(a + c)ca2. Hence these two points coincide, and we can choose it
to be N, whereby both BNC and DNA are equilateral triangles.
(A Liu)
5.	The chessboard has 7 internal vertical grid lines, each divided into
8 segments. Hence there are 56 possible vertical barriers. Similarly,
there are 56 possible horizontal barriers. Consider a tour that
traverses the entire board.
By representing squares with vertices and moves between neigh-
bouring squares with edges, we obtain a graph. The maximal
subtree of this graph will contain 64 vertices and therefore 63
edges. Hence a good labyrinth can have at most 49 barriers. Two
labyrinths are said to be complementary if every possible barrier
appears in exactly one of them. In any such pair, at least one of
them has at least 56 barriers and is bad.
Hence there are at least as many bad labyrinths as good ones.
Consider the labyrinth with only two barriers isolating a corner
square of the chessboard. Then both it and its complement are
bad. It follows that there are more bad labyrinths than good ones.
(A Liu)
6.	(a) Number the cards from the Ace of Spades to the King of Clubs
1 to 52. When four cards are exposed as in the trick, they are
relegated to numbers 49 to 52, but maintaining their relative
order. The other cards move up to fill the voids, so that the
48 hidden cards are numbered 1 to 48. The four exposed
cards can be arranged in 4! ways, from the 1st permutation
(49,50,51,52) to the 24th permutation (52,51,50,49).
If the fifth card is numbered between 1 and 24 inclusive, the
magician puts it to the left of the four exposed cards. The
assistant will know that the identity number of the fifth card is
equal to the permutation number. If the fifth card is numbered
between 25 and 48 inclusive, the magician puts it to the right
of the four exposed cards. The assistant will know that the
50
TOURNAMENT 19
identity number of the fifth card is 24 plus the permutation
number.
(b) This is still possible, but the performers must make use of the
absolute rather than the relative values of the four exposed
cards. We construct a graph whose vertices are in two sets X
and Y. Each vertex in X represents a set of 5 cards, while
each vertex in Y represents a display of 4 cards. A vertex x
in X is joined to a vertex у in Y if the 4 cards in the display
represented by у come from the set of 5 cards represented by
x. There are no other edges.
If for each ж, we can find a distinct у joined to it, then the
performers’ task is solved mathematically. Such a graph is
called a bipartite graph because the vertices are in two sets.
The set of edges we seek is called an X-sat mating matching
because each vertex in X is matched with some vertex in Y,
though not necessarily conversely. A famous result known
as Hall’s Theorem states that a bipartite graph has an X-
saturating matching if and only if |A| < |X(A)| for any subset
A of X, where N(A) is the subset of Y consisting of all ys
joined to some x in A.
In our graph, let A be a subset of X. Now each x is joined
to 5-4! ys since there are 5 ways of choosing 4 of 5 cards,
and 4! ways to arrange the display. Hence 120|A| edges go
from A to N(A). Each у is joined to 48 xs since there are
48 ways of choosing a fifth card to go along with the 4 on
display. Hence 48|7V(A)| edges are received by X(A), not all
of which come from A. It follows that 120|A| < 48|X(A)| so
that |A| < |X(A)|. It follows from Hall’s Theorem that an
X-saturating matching exists. When 5 cards are drawn, the
magician locates the vertex x representing this set, finds the
vertex у matched with ж, and uses the display which у rep-
resents. The assistant can then reverse the steps and identify
the set of 5 cards, and in particular the hidden fifth card.
(A Liu)
TOURNAMENT 20

TOURNAMENT 20
JUNIOR QUESTIONS
Autumn 1998 (0 Level)
1.	A 20 x 20 x 20 block is cut up into 8000 non-overlapping unit cubes
and a number is assigned to each. It is known that in each column
of 20 cubes parallel to any edge of the block, the sum of their
numbers is equal to 1. The number assigned to one of the unit
cubes is 10. Three 1 x 20 x 20 slices parallel to the faces of the
block contain this unit cube. Find the sum of all numbers of the
cubes outside these slices.	(A Belov, 3 points)
2.	The units-digit of the square of an integer is 9 and the tens-digit
of this square is 0. Prove that the hundreds-digit is even.
(Folklore, 3 points)
3.	In a triangle ABC the points A', B' and C lie on the sides BC,
CA and AB, respectively. It is known that LACB' — LB'A'C,
LCB'A' = LA'C'B and LB A'C = LC'B'A. Prove that AL, B'
and C are the midpoints of the corresponding sides.
(V Proizvolov, 4 points)
4.	Twelve candidates for mayor participate in a TV talk show. At
some point a candidate said: “One lie has been told.” Another
said: “Now two lies have been told”. “Now three lies,” said a
third. This continued until the twelfth said: “Now twelve lies have
been told”. At this point the moderator ended the discussion. It
turned out that at least one of the candidates correctly stated the
number of lies told before he made the claim. How many lies were
actually told by the candidates?	(A Shapovalov, 4 points)
5.	Let n and m be given positive integers. In one move, a chess piece
called an (n, m)-crocodile goes n squares horizontally or vertically
and then goes m squares in a perpendicular direction. Prove that
the squares of an infinite chessboard can be painted in black and
white so that this chess piece always moves from a black square to
a white one or vice-versa.	(A Ger ко, 5 points)
54
TOURNAMENT 20
Autumn 1998 (A Level)
1.	Prove that for any two positive integers a and b the equation
LCM(n, a + 5) = LCM(6,6 + 5) implies a = b.
(A Shapovalov, 3 points)
2.	John and Mary each have a white 8x8 square divided into 1x1 cells.
They have painted an equal number of cells on their respective
squares in blue. Prove that one can cut up each of the two squares
into 2x1 dominoes so that it is possible to reassemble John’s
dominoes into a new square and Mary’s dominoes into another
square with the same pattern of blue cells. (A Shapovalov, 4
points)
3.	Segment AB intersects two equal circles, is parallel to the line join-
ing their centres, and all the points of intersection of the segment
and the circles lie between A and B. From the point A tangents to
the circle nearest to A are drawn, and from the point В tangents
to the circle nearest to В are also drawn. It turns out that the
quadrilateral formed by the four tangents extended contains both
circles. Prove that a circle can be drawn so that it touches all four
sides of the quadrilateral.	(P Kozhevnikov, 5 points)
4.	All the diagonals of a regular 25-gon are drawn. Prove that no 9
of the diagonals pass through one interior point of the 25-gon.
(A Shapovalov, 6 points)
5.	There are 20 beads of 10 colours, two of each colour. They are
put in 10 boxes. It is known that one bead can be selected from
each of the boxes so that each colour is represented. Prove that
the number of such selections is a non-zero power of 2.
(A Grishin, 7 points)
6.	A gang of robbers took away a bag of coins from a merchant. Each
coin is worth an integer number of pennies. It is known that if
any single coin is removed from the bag, then the remaining coins
can be divided fairly among the robbers (that is, they all get coins
with the same total value in pennies). Prove that after one coin
is removed, the number of the remaining coins is divisible by the
number of robbers. (Folklore, modified by A Shapovalov, 7 points)
Junior Questions
55
Spring 1999 (0 Level)
1.	A father and his son are skating around a circular skating rink.
From time to time, the father overtakes the son. After the son
starts skating in the opposite direction, they begin to meet five
times more often. What is the ratio of the skating speeds of the
father and the son?	(Tairova, 3 points)
2.	ABC is a right-angled triangle. A square ABDE is constructed on
the opposite side of the hypothenuse AB from C. The bisector of
DF
AC cuts DE at F. If AC = 1 and BC = 3, compute —=
EF
(A Blinkov, 4 points)
3.	Several positive integers ao, a±, a,2,   , an are written on a board.
On a second board, we write the amount bo of numbers written on
the first board, the amount bi of numbers on the first board exceed-
ing 1, the amount 62 of numbers greater than 2, and so on as long as
the bs are still positive. Then we stop, so that we do not write any
zeros. On a third board we write the numbers cq, ci, C2,. • . using
the same rules as before, but applied to the numbers bo, &i, 62, • • •
of the second board. Prove that the same numbers are written on
the first and the third boards.
(H. Lebesgue - A Kanel, 4 points)
4.	A black unit equilateral triangle is drawn on the plane. How can
we place nine tiles, each a unit equilateral triangle, on the plane so
that they do not overlap, and each tile covers at least one interior
point of the black triangle?	(Folklore, 5 points)
5.	A square is cut into 100 rectangles by 9 straight lines parallel to
one of the sides and 9 lines parallel to another. If exactly 9 of the
rectangles are actually squares, prove that at least two of these 9
squares are of the same size.	(V Proizvolov, 5 points)
56
TOURNAMENT 20
Spring 1999 (A Level)
1.	There is $500 in a bank. Two bank operations are allowed: to
withdraw $300 from the bank or to deposit $198 into the bank.
These operations can be repeated as many times as necessary but
only the money that was initially in the bank can be used. What is
the largest amount of money that can be borrowed from the bank?
How can this be done?	(AK Tolpygo, 3 points)
2.	Let О be the intersection point of the diagonals of a parallelogram
ABCD. Prove that if the line BC is tangent to the circle passing
through the points A, B, and O, then the line CD is tangent to
the circle passing through the points В, C and O.
(A Zaslavskiy, 4 points)
3.	Two players play the following game. The first player starts by
writing either 0 or 1 and then, on his every move, chooses either 0
or 1 and writes it to the right of the existing digits until there are
1999 digits. Each time the first player puts down a digit (except
the first one), the second player chooses two digits among those
already written and swaps them. Can the second player guarantee
that after his last move the line of digits will be symmetrical about
the middle digit?	(I Izmestiev, 4 points)
4.	n diameters divide a disk into 2n equal sectors, n of the sectors
are coloured blue, and the other n are coloured red (in arbitrary
order). Blue sectors are numbered from 1 to n in the anticlockwise
direction, starting from an arbitrary blue sector, and red sectors
are numbered from 1 to n in the clockwise direction, starting from
an arbitrary red sector. Prove that there is a semi-disk containing
sectors with all numbers from 1 to n. (V Proizvolov, 6 points)
5.	The sides AB and AC are tangent at points P and Q, respectively,
to the incircle of a triangle ABC. R and S are the midpoints of
the sides AC and BC, respectively, and T is the intersection point
of the lines PQ and RS. Prove that T lies on the bisector of the
angle В of the triangle.	(M Evdokimov, 6 points)
6.	A rook is allowed to move one cell either horizontally or vertically.
After 64 moves the rook visited all cells of the 8x8 chessboard and
returned back to the initial cell. Prove that the number of moves
in the vertical direction and the number of moves in the horizontal
direction cannot be equal. (A Shapovalov, R Sadykov, 9 points)
Senior Questions
57
SENIOR QUESTIONS
Autumn 1998 (0 Level)
1.	Nineteen weights of mass 1 gm, 2 gm, 3 gm, ..., 19 gm are given.
Nine are made of iron, nine are of bronze and one is pure gold. It
is known that the total mass of all the iron weights is 90 gm more
than the total mass of all the bronze ones. Find the mass of the
gold weight.	(V Proizvolov, 3 points)
2.	On the plane are n paper disks of radius 1 whose boundaries all
pass through a certain point, which lies inside the region covered
by the disks. Find the perimeter of this region.
(P Kozhevnikov, 3 points)
3.	On an 8 x 8 chessboard, 17 cells are marked. Prove that one can
always choose two cells among the marked ones so that a Knight
will need at least three moves to go from one of the chosen cells to
the other.	(R Zhenodarov, 4 points)
4.	Among all sets of real numbers {®i, ®2, • • •, ®2o} from the open
interval (0,1) such that ®i®2 • • • ®20 = (1 — ®i)(l — ®г) •••(! — ®2o),
find the one for which Ж1Ж2 • • • ж20 is maximal.
(A Cherniatiev, 4 points)
5.	The intelligence quotient (IQ) of a country is defined as the average
IQ of its entire population. It is assumed that the total population
and individual IQs remain constant throughout.
(a)	(i) A group of people from country A has emigrated to coun-
try B. Show that it can happen that as a result, the IQs
of both countries have increased.	(1 point)
(ii)	After this, a group of people from B, which may include
immigrants from A, emigrates to A. Can it happen that
the IQs of both countries will increase again? (3 points)
(b)	A group of people from country A has emigrated to country
B, and a group of people from В has emigrated to country C.
It is known that as a result, the IQs of all three countries have
increased. After this, a group of people from C emigrates to В
and a group of people from В emigrates to A. Can it happen
that the IQs of all three countries will increase again?
(A Kanel, В Begun, 2 points)
58
TOURNAMENT 20
Autumn 1998 (A Level)
1.	(a) Prove that for any two positive integers a and b the equation
LCM(n, a + 5) = LCM(6, 6+5) implies a = b. (2 points)
(b) Is it possible that LCM(n, 6) = LCM(n + c, b + c) for positive
integers a, b and c?	(A Shapovalov, 3 points)
2.	Segment AB intersects two equal circles, is parallel to the line join-
ing their centres, and all the points of intersection of the segment
and the circles lie between A and B. From the point A tangents to
the circle nearest to A are drawn, and from the point В tangents
to the circle nearest to В are also drawn. It turns out that the
quadrilateral formed by the four tangents extended contains both
circles. Prove that a circle can be drawn so that it touches all four
sides of the quadrilateral.	(P Kozhevnikov, 4 points)
3.	Nine numbers are arranged in a square table:
(Z1	«2	a3
bi b? bs
Ci C2 C3.
It is known that the six numbers obtained by summing the rows
and columns of the table are equal: a± +	+ «3 = 61 + ^2 + 63 —
ci + C2 + c3 = ai + bi + Ci = a2 + 62 + c2 = «з + 63 + c3. Prove that
the sum of products of numbers in the rows is equal to the sum of
products of numbers in the columns: aibiCi + (Z262C2 + «36303 =
«1«2«з + 616263 + C1C2C3.	(V Proizvolov, 5 points)
4.	Twelve places have been arranged at a round table for members
of the Jury, with a name tag at each place. Professor K. being
absent-minded instead of occupying his place, sits down at the
next place (clockwise). Each of the other Jury members in turn
either occupies the place assigned to this member or, if it has been
already occupied, sits down at the first free place in the clockwise
order. The resulting seating arrangement depends on the order in
which the Jury members come to the table. How many different
seating arrangements of this kind are possible?
(A Shapovalov, 6 points)
5.	The sum of the length, width, and height of a rectangular paral-
lelepiped will be called its size. Can it happen that one rectangular
parallelepiped contains another one of greater size?
(A Shen, 7 points)
Senior Questions
59
6.	In a function /(ж) = (ж2 + ax + b)/(x2 + ex + d), the quadratics
ж2 + ax + b and ж2 + ex + d have no common roots. Prove that the
next two statements are equivalent:
(i)	there is a numerical interval without any values of /(ж);
(ii)	/(ж) can be represented in the form
/(ж) = /1(/2(.../п-1(/п(ж))...))
where each of the functions fj is of one of the three forms
kjX + bj, 1/ж, ж2.
(A Kanel, 8 points)
60
TOURNAMENT 20
Spring 1999 (О Level)
1.	In a row are written 1999 numbers such that except the first and
the last, each is equal to the sum of its neighbours. If the first
number is 1, find the last number.	(V Senderov, 3 points)
2.	ABC is a right-angled triangle. A square ABDE is constructed on
the opposite side of the hypotenuse AB from C. The bisector of
DF
LC cuts DE at F. If AC = 1 and BC — 3, compute ——.
EF
(A Blinkov, 3 points)
3.	Several positive integers ao, a±, az,   ., an are written on a board.
On a second board, we write the amount bo of numbers written on
the first board, the amount b± of numbers on the first board exceed-
ing 1, the amount 62 of numbers greater than 2, and so on as long as
the bs are still positive. Then we stop, so that we do not write any
zeros. On a third board we write the numbers co, ci, 02,... using
the same rules as before, but applied to the numbers bo, &i, &2, • • •
of the second board. Prove that the same numbers are written on
the first and the third boards. (H Lebesgue - A Kanel, 3 points)
4.	A black unit square is drawn on the plane. How can we place seven
tiles, each a unit square, on the plane so that they do not overlap,
and each tile covers at least one interior point of the black square?
(Folklore, 5 points)
5.	Two people play a game on a 9 x 9 board. They move alternately.
On each move, the first player draws a cross in an empty cell, and
the second player draws a nought in an empty cell. When all 81
cells are filled, the number К of rows and columns in which there
are more crosses and the number H of rows and columns in which
there are more noughts are counted. The score for the first player
is the difference В = К — H. Find a value of В such that the first
player can guarantee a score of at least B, while the second player
can hold the first player’s score to at most B, regardless how the
opponent plays.	(A Kanel, 5 points)
Senior Questions
61
Spring 1999 (A Level)
1.	A convex polyhedron is floating in a sea. Can it happen that 90%
of its volume is below the water level, while more than half of its
surface area is above the water level? (A Shapovalov, 4 points)
2.	Let all vertices of a convex quadrilateral ABCD lie on the circum-
ference of a circle with centre O. Let F be the second point of
intersection of the circumcircles of the triangles ABO and CDO.
Prove that the circle passing through the points A, F and D also
passes through the point of intersection of the segments AC and
BD.	(A Zaslavskiy, 4 points)
3.	Find all pairs (x,y) of integers satisfying the following condition:
each of the numbers x3 + у and x + y3 is divisible by x2 + y2.
(S Zlobin, 5 points)
4.	n diameters divide a disk into 2n equal sectors, n of the sectors
are colored blue, and the other n are colored red (in arbitrary
order). Blue sectors are numbered from 1 to n in the anticlockwise
direction, starting from an arbitrary blue sector, and red sectors
are numbered from 1 to n in the clockwise direction, starting from
an arbitrary red sector. Prove that there is a semi-disk containing
sectors with all numbers from 1 to n. (V Proizvolov, 5 points)
5.	For every non-negative integer г, define the number M(i) as follows:
write i down as a binary number, so that we have a string of zeroes
and ones; if the number of ones in this string is even, then set
М(г) — 0, otherwise set М(г) — 1. (The first terms of the sequence
М(г), i = 0,1, 2,... are 0,1,1,0,1,0,0,1,....)
(a)	Consider the finite sequence
M(0),M(l),...,M(1000).
Prove that there are at least 320 terms in this sequence which
are equal to their neighbour on the right: М(г) = M(i + 1).
(2 points)
(b)	Consider the finite sequence
M(0), M(l),..., M(IOOOOOO).
Prove that the number of terms M(i) such that М(г) = M(i +
7) is at least 450000.	(A Kanel, 5 points)
62
TOURNAMENT 20
6.	A rook is allowed to move one cell either horizontally or vertically.
After 64 moves the rook visited all cells of the 8x8 chessboard and
returned back to the initial cell. Prove that the number of moves
in the vertical direction and the number of moves in the horizontal
direction cannot be equal. (A Shapovalov, R Sadykov, 8 points)
Junior Solutions
63
JUNIOR SOLUTIONS
Autumn 1998 (0 Level)
1.	The whole block consists of 400 columns, so that the sum of all
8000 numbers is 400. Similarly, the sum of the numbers in each
slice is 20. When the three slices are removed, the sum of the
remaining numbers is greater than 400 — 3-20. This is because
the three columns where the slices intersect pairwise have been
removed twice, and must be added back. However, the cube where
the slices intersect would have been removed three times and then
added back three times. So it has to be removed again. It follows
that the desired sum is 400 — 3-20+ 3-1 — 10 = 333.
(A Liu)
2.	Alternative 1
Let the original integer be n = 100® + 10?/ + z where each of у and
z is a single-digit number. Then
n2 = 10000®2 + 2000®?/ + 200®;? + 100?/2 + 20?/^ + z2.
Thus the value of x has no effect on the last two digits of n2, nor
on the parity of its hundreds-digit. Hence we may assume that
it is 0 and take n = 10?/ + z. Since n2 ends in 9, we must have
z = 3 or 7. Suppose z = 3. Then n2 = 100?/2 + 60?/ + 9. Since
the tens-digit of n2 is 0, we must have у = 0 or 5. Suppose z = 7.
Then n2 = 100?/2 + 140?/ + 49. Since the tens-digit of n2 is 0, we
must have у = 4 or 9. Now 32 = 9, 532 = 2809, 472 = 2209 and
972 = 9409. All four have even hundreds-digits.
(A Liu)
Alternative 2
Let the original number be n. Then n is odd. Hence n2 leaves
remainder 1 when divided by 8. Therefore n2 — 1 is divisible by 8.
An integer is divisible by 8 only when the number formed by its
last three digits is divisible by 8. Since the last two digits of n2, — 1
are 0 and 8, the hundreds-digit must be even.
(A Storozhev)
3.	Let
LCB'A' =	LA'C'B	=	a,
LAC'B' =	LB'A'C	=	(3
and	ZBA'C" =	LC'B'A	=	7.
1
64
TOURNAMENT 20
Then
2a + 2/3 + 27 + AC'A'B' + AA'B'C + AB'C'A' = 540°.
Since the sum of the last three angles is 180°, we have
a + /3 + 7 = 180°.
It follows that
AC'A'B' = AC AB = a,
AA’B’C = AABC = (3
and AB'C'A = ABC A = y.
Therefore both A'BC'B' and A'CB'C are parallelograms, and A'
is the midpoint of BC since BA' = C'B' = A'C. Similarly, B' is
the midpoint of CA and C is the midpoint of AB.
(A Liu)
4.	Suppose the г-th candidate is the first one to correctly state the
number of lies told so far. Then all the claims after that are false,
so that the total number of lies is i + (12 — г) = 12. (In fact, we
must have i = 1, though this fact is not needed to determine the
answer.)
(A Liu)
5.	If n is even and m is odd, then the usual checkerboard colouring
will work. We may assume that the chess piece starts from a white
square. Since n is even, the square at which the chess piece makes
the right angle turn is also white. However, since m is odd, the
final square is black.
The same colouring scheme and an analogous argument also work
when n is odd and m is even. If both are odd, colour the vertical
columns of the infinite chessboard alternately black and white. We
Junior Solutions
65
may assume that the chess piece starts from a white square. Since
it goes an odd number of squares horizontally, it will land on a
black square. Finally, suppose both n and m are even. Let t be the
largest integer such that 2f divides both n and m. Then we have
n = ‘2tk and m = 2*£, where at least one of к and £ is odd. Divide
the infinite chessboard into 2* x 2* subboards.
All squares within the same sub-board will have the same colour, so
that we have a new infinite chessboard with bigger “squares”. The
movement of the (n, m)-crocodile on the old chessboard is equiva-
lent to the movement of a (fc, £)-crocodile on the new chessboard,
whose “squares” will now be coloured depending on whether one
of к and I is odd, or both are.
(A Liu)
66
TOURNAMENT 20
Autumn 1998 (A Level)
1.	Since (ft + 5) — a = 5, GCD(ft, ft + 5) equals either 1 or 5. Similarly,
GCD(6, b + 5) is either 1 or 5.
Now
ft(ft + 5)
LCM(ft, ft + 5) =	-------r-
v 7 GCD(ft,ft + 5)
and
LCM(M + 5)^Gcg+^5).
If GCD(ft, ft + 5) = 1 and GCD(6, b + 5) = 5, we have 5ft(ft + 5) =
b(b + 5). Since b is divisible by 5, b(b + 5) is divisible by 25 and
therefore a is divisible by 5. Thus GCD(ft, a + 5) > 1 which is a
contradiction.
Similarly, the case when GOD (ft, a + 5) = 5 and GOD (6, b + 5) = 1
is impossible.
If GCD(ft, ft + 5) = GCD(&, b + 5), then a[a + 5) = b[b + 5). Hence
(ft — b) (ft + b + 5) =0 which implies ft = 6 as ft and b are positive.
(A Liu)
2.	Let’s call a domino white if it consists of two white cells, blue if it
consists of two blue cells and grey otherwise. Cut each of the two
squares into 32 vertical dominoes. If each of the squares contains
a white domino, take these two dominoes out of the squares. Then
repeat this process until one of the squares is left without white
dominoes. Do a similar thing with blue dominoes and then with
grey ones. Now we are left with one square containing only grey
dominoes, and the other with white and blue dominoes only.
There are the same number of white and blue dominoes in the
second square. We can cut the original squares into 2x2 squares
and fill some of these squares with the remaining dominoes so that
the pattern of blue cells will be the same in the original squares.
Since the numbers of white, blue and grey dominoes pulled out
of the original squares are respectively equal, we can put these
dominos back so that the pattern of blue cells will stay the same
on the two squares.
(A Liu)
Junior Solutions
67
3.	Let C and D be the other two vertices of the quadrilateral. Let
X and У be the points of contact of the two circles with AC and
BC respectively. We see that O±X is perpendicular to AC and
O2Y is perpendicular to BC where Oi and 0% are the centres of
the corresponding circles. Let AO± and BO2 extended meet in Z.
Also let P and Q be the feet of the perpendiculars from Z to AC
and BC respectively.
PZ AZ
Since APZ and AXOi are similar triangles, we have	.
XOr AOi
AB
Since ABZ and О1О2У are similar triangles, -	- = holds.
O±Z O1O2
Hence
PZ
xc
Similary,
QZ
YO2
AZ _ /	ЯОЛ"1 _ Л 0i02\ 1
AOi \	AZ)	\ AB J
BZ = /	Z02\ 1 = Л 0i02\ 1
B02 \	BZ J \ AB J
Since XOi = YO2, we have PZ = QZ which means that CZ
bisects LACB. Thus the angle bisectors of ZA, LB and LC in the
quadrilateral ABCD meet at one point. Hence there exists a circle
which touches all four sides of the quadrilateral.
(A Liu)
68
TOURNAMENT 20
4.	Let the size of a diagonal of the 25-gon be the smallest number
of sides joining the endpoints of the diagonal. In order to have 9
diagonals meeting in one point, the size of each of these 9 diagonals
must be at least 9. Hence these diagonals can only be of size 9,
10, 11 and 12. Therefore we can find three diagonals of the same
size. But diagonals of the same size have the same length. Thus we
have three diagonals of the same length passing through one point
inside a regular polygon. This means that there are three chords
in the circumcircle of the polygon that have the same length and
pass through one point. Therefore the three chords are diameters,
which is not possible as the regular polygon has an odd number of
vertices.
(A Storozhev)
5.	Consider a box. Pick a bead from this box. Find a box which
contains a bead of the same colour. Look at the other bead in
the second box. Find a box with the matching bead. Look at the
second bead in the third box and repeat the procedure. Eventually
we come to the first box. Let us call such sequence of boxes a
cycle. We can partition the set of all boxes into m, say, cycles.
Then clearly the number of required selections is 2m.
(A Liu)
6.	Let the number of coins be к and the number of robbers n. Also
let the values of the coins in pennies be cz-i, a2,.. •, dk respectively.
Then we have
«2 + а-зН-----hafc = nbi;
ai+азН--------= n62;
Q-i + 0,2 + • • • T Ufc—i = idbk-)
where bi is the total value of coins in pennies that each of the
robbers gets after the zth coin has been removed. When we add all
these equations together, we get
(& —	+ 0,2 + • ' ’ + Ok) = n(bi + 62 + ’ ’ ’ + bk)- (*)
Now assume that d is the largest common factor of cq + • • • + Ok
and n. Then
0,2 + 0,3 -I------1- ak = nb-L
Junior Solutions
69
implies that ai is divisible by d. Similarly is divisible by d for
each 1 < i < k. Since bi is the sum of the values of some coins, bi
is divisible by d for each 1 < i < k. Therefore we can divide each
ai and bi by d and assume that d — 1. Then it follows from (*)
that к — 1 is divisible by n.
(A Liu)
70
TOURNAMENT 20
Spring 1999 (0 Level)
1.	Let the skating speeds of the father and the son be и and v respec-
tively. Then и > v. When they are skating in the same direction,
the father’s relative speed to the son is и — n, so that the interval
between consecutive meetings is When they are skating in
opposite directions, the relative speed is и + v and the interval is
—. From
u-\-v
5 _ 1
и + v u — n ’
we have 5u — 5n = и + v so that
и 3
v = 2’
(A Liu)
2.	Let GF cut AB at G.
Since CG bisects ZC,
AG AC 1
BG BC 3’
Let О be the centre of ABDE. Then AAOB + LACB = 180°, so
that AOBC is a cyclic quadrilateral. Moreover, since О A = OB,
О also lies on the bisector of AACB. By symmetry,
DF _ AG _1
~EF ~ BG ~ 3’
(A Liu)
Junior Solutions
71
3.	We may assume that ai,... ,an are in non-ascending order. For
each of ftj, г = 1,..., n, draw a column of dots on the first board
so that the bottom dots of these columns lie on a horizontal line.
Then if we reflect this diagram in the line that passes through the
leftmost bottom dot and bisects the angle formed by the leftmost
column and the bottom row, we get a diagram corresponding to
bo, bi, • • •• If we apply the same procedure to this new diagram,
we obtain the first diagram. Hence the numbers on the first and
third boards are the same.
(A Liu)
4.	The nine tiles of side length 1 may be placed as shown in the
following diagram. The triangle in the middle is of side-length
< 1. It can be expanded into the black triangle so that each
tile covers at least one interior point of it.
We may actually place ten tiles of side length 1 as shown in the
following diagram. The three black dots define a triangle of side-
length < 1. This triangle can be expanded into the black
triangle which will share at least one interior point with each tile.
We may even place eleven tiles of side length 1 as shown in the
following diagram. The three black dots define a triangle of side-
length < 1. This triangle can be expanded into the black
72
TOURNAMENT 20
triangle which will share at least one interior point with each tile.
(A Liu)
5.	Let one side of the square be divided into segments of lengths ai,
a2,..., cqo, and the other side into segments of lengths &i, 62, • • ,
bw. Suppose no 2 of the 9 squares are of the same size, then their
side lengths are equal respectively to 9 distinct as, as well as 9
distinct bs. This means that the 10th a and the 10th b must be
equal to each other, and there is a 10th square with side length
equal to their common value.
(A Liu)
Junior Solutions
73
Spring 1999 (A Level)
1.	Since both 300 and 198 are even, only an even number of dollars
can be borrowed from the bank.
Since both 300 and 198 are divisible by 3, it is not possible to
borrow $500 from the bank.
Therefore the largest amount of money that can be borrowed from
the bank is at most $498. After we withdraw $300, then deposit
$198 and after that withdraw $300, there will be $98 left in the
bank. After we apply the sequence +$198+$198—$300+$198—$300
of bank operations to the amount $98, there will be $92 in the
bank. Every time we repeat this sequence, there will be $6 less in
the bank. So we can come to the situation where there is $2 in the
bank. Thus the answer is $498.
(A Liu)
2.	Alternative 1
Since BC is tangent to the circle passing through the points A, В,
and O, we have ВС2 = AC x ОС = 2CC2.
Since ABCD is a parallelogram, CD2 + BC2 = 2(OC2 + OB2).
Therefore CD2 = 2OB2 = BD x BO, which means that CD is
tangent to the circle passing through the points С, B, and О.
(A Liu)
Alternative 2
Since BC is tangent to the circle passing through the points A, B,
and O, we have LB AO = LOBC.
Since AB is parallel to CD, LB AO = LOCD.
74
1
TOURNAMENT 20
Therefore AOBC = AOCD, which means that CD is tangent to
the circle passing through the points С, B, and O.
(A Storozhev)
3.	Let the first player make his (1000 + i)th move, where i > 0. Then
the second player looks at (1000 + г)th and (1000 — г)th digits. If
they are the same, he swaps them. If they are different, he looks
at the 1000th digit and swaps it with the (1000 ± г)th digit which
is different from it. Clearly after his last move, the second player
will get a symmetrical line of digits.
(A Liu)
4.	Without loss of generality, we can assume that when going from
red sector 1 to blue sector 1 clockwise we find no more sectors
numbered the same. Then also without loss of generality we can
assume that when going from red sector 1 to blue sector 1 clockwise
we find only blue sectors. Now draw a diameter AB where A is
the last point on the circumference of the circle belonging to blue
sector 1 when going anticlockwise. Consider blue sector i. If it is
on the same side of AB as blue sector 1, there are at least n — i + 2
blue sectors on this side of AB. Hence red sector i will be on the
other side of AB. Similarly if red sector i is on the same side of
AB as red sector 1, blue sector i will be on the other side of AB.
Hence AB cuts the circle into two required semi-disks.
(A Liu)
5.
Assume that BC > AB. Then
„„	AC AC + AB — BC BC - AB
QR = AR-AQ= —-----------------=---------.
Since AP = AQ, LAPQ = AQP. Hence LRQT — LRTQ as AB is
parallel to RS. Therefore RT = QR. Hence TS = TR+RS =
Since BS = TS, LTSC = 2LTBS. Hence ВТ bisects LABC.
Junior Solutions
75
The other case can be considered similarly.
(A Liu)
6.	Each time the rook moves from one square to the next one, we
connect the centres of these squares. Thus we have a closed broken
line Lq of length 64. We will call a broken line of length 3, which
is formed by three sides of a unit square, a staple. It is easily seen
that any closed broken line that contains no cells inside it contains
at least one staple. Thus L contains a staple, say ABCD. When
this staple is replaced with a straight line segment AB of length 1
joining the endpoints of the staple, we obtain a closed broken line
Li of length 62. We also cut out the 2x1 rectangle consisting of the
cells with centres В and C. Note that if this rectangle is horizontal,
Li has 2 vertical sides fewer than Lq, and if this rectangle is vertical,
Li has 2 horizontal sides fewer than Lq.
We repeat this procedure until we cut the whole chessboard into 2 x
1 rectangles. If the number of vertical sides in Lq is the same as the
number of horizontal sides, the difference between the vertical and
horizontal 2x1 rectangles will be 2. Assume that the numbers of
vertical and horizontal 2x1 rectangles are a and a + 2 respectively.
Then 2a + 2 = 32 which means that a = 15. Now consider vertical
2x1 rectangles with their top squares in the top row of cells of the
chessboard. Clearly, there is an even number of them. Hence the
number of vertical 2x1 rectangles with their top squares in the
second top row of cells of the chessboard is even too. By repeating
this reasoning, we come to the conclusion that a is even which is
contradiction.
(A Liu)
76
TOURNAMENT 20
SENIOR SOLUTIONS
Autumn 1998 (0 Level)
1.	The total mass of the heaviest nine weights is 11 + 12 + • • • + 19
gm while that of the lightest nine weights is 1 + 2 + • • • + 9 gm.
The difference is 90 gm. Hence the total mass of the iron weights
cannot exceed that of the bronze ones by more than 90 gm. Since
this difference is also 90 gm, the iron weights are the heaviest nine
while the bronze ones are the lightest nine. It follows that the mass
of the gold weight is 10 gm.
(A Liu)
2.	Let the boundary of the region consist of n arcs, where the г-th
arc, 1 < г < n, subtends an angle of 6i at the common point of
intersection. Since this point is inside the region, we have 6h + 0^ +
• • • + 0n = 2гг. Now the г-th arc subtends an angle of 26*г at the
centre of the corresponding circle, which is of radius 1. Hence the
length of this arc is 26*г. It follows that the perimeter of the region
is equal to 2#i + 26*2 4-----1- ^0n = 4%.
(A Liu)
3.	Use each of A, B, ..., P to label four cells of the chessboard as
shown in the diagram on the left. It is easy to verify that the
Knight takes at least three moves to go from any cell to another
one with the same label. By the Pigeonhole Principle, two of the
17 marked cells must have the same label, and these will be the
two cells we choose.
D	H	L	P	в	F	J	N
D	H	L	P	в	F	J	N
C	G	К	0	A	E	I	M
C	G	К	0	A	E	I	M
В	F	J	N	D	H	L	p
В	F	J	N	D	H	L	p
A	E	I	M	C	G	К	0
A	E	I	M	C	G	К	0
в	C	A	I	I	В	D	A
G	F	J	E	E	J	F	H
H	I	В	C	D	A	I	G
J	E	G	C	D	H	E	J
J	F	G	A	В	H	F	J
H	I	D	A	В	c	I	G
G	E	J	F	F	J	E	H
D	A	C	I	I	D	В	C
The diagram on the right shows that 17 can be replaced by 11.
This cannot be reduced to 9 since the 9 marked cells may consist
of one near the centre of the board and all 8 cells to which a Knight
Senior Solutions
77
can move from that one.
(A Liu)
4.	Since Ж1Ж2 • • • £20 = (1 — ^i)(l — aq) • • • (1 — Ж20), maximizing
Ж1Ж2 • • • ^20 is equivalent to maximizing aqaq • • • aqo(l — aq)(l —
x2) • • • (1 - x20) = %i(l ~ xi)x2(l - a?2) • • • a?2o(l - ^20)- Since
each Xi is chosen independently from (0,1), we only need max-
imize Xi(l — x^. By the Arithmetic-Mean Geometric-Mean In-
/	—1_ (— Xi) \	1
equality, Xi(l — Xi) < I —-----------— ] = -, with equality if and
only if Xi = 1 — Xi = It follows that the maximum of aqa?2 • • • aqo
occurs when aq = x2 = • • • = aqo =
(A Liu)
5.	(a) (i) Country A has two citizens of IQs 50 and 30 respectively.
Country В has one citizen of IQ 10. Thus the IQs of A
and В are 40 and 10 respectively. Now the person of IQ
30 moves from A to B. Afterwards, the IQs of A and В
are 50 and 20, and both have increased.
(ii)	The situation is impossible. Suppose the initial IQs of A
and В are ao and bo respectively. After a group of people
of average IQ ci moves from A to B, let the new IQs of
A and В be a± and b± respectively. In order for a± > ao,
we must have ao > c±. In order for b± > bo, we must have
ci > &i- Hence a± > b±. Suppose after a group of people
of average IQ c2 moves from В to A, let the new IQs of A
and В be a2 and b2 respectively. In order for a2 > a± and
b2 > b±, we must have b2 > b± > c2 > a2 > a±. However,
this contradicts a± >61.
(b) Country A has two citizens of IQs 30 and 10 respectively.
Country В has five citizens of IQs 630, 60, 60, 50 and 50
respectively. Country C has one citizen of IQ 20. Thus the
IQs of A, В and C are 20, 170 and 20 respectively. Now the
person of IQ 10 moves from A to В while the two people of
IQs 50 move from В to C. Afterwards, the IQs of A, В and C
are 30, 190 and 40 respectively, and all three have increased.
Now the person of IQ 20 moves from C to В while the two
people of IQs 60 move from В to A. Afterwards, the IQs of A,
В and C are 50, 220 and 50 respectively, and again all three
have increased.
(A Liu)
78
TOURNAMENT 20
Autumn 1998 (A Level)
1.	(a) See solution to Problem 1 in Junior paper.
(b) The answer is no.
Assume that a + c and b + c have a common prime divisor p.
Then LCM(a + c, b + c) is divisible by p. Hence LCM(a, 6) is
divisible by p. Therefore at least one of a and b is divisible by
p which means that c is divisible by p. Since LCM f -, - ) =
PJ
LCM(a, b)	.(a + c 6 + c\ LCM(a + c, b + c)
------------- and LCM ------,----- = --------------------	-,
p---------------------------------------------------------\ P P J-P
we can assume that a + c and b + c are relatively prime. But
then LCM(a + c, b + c) = (a + c)(b + c) > LCM(a, b).
(A Liu)
2.	See solution to Problem 3 in Junior paper.
3.	Let t = ai + a-2 + аз. Then
аз	=	t	—	ai — a2;
63	=	t	-	br - 62;
ci	=	t-ai-61;
C2	=	t	—	tt2 — &2S
C3 = ai + a2 + 61 + 62 — t-
After replacing аз, 63, ci, C2 and 03 by the right-hand side expres-
sions of the above equations in the expression aib^ci + 026202 +
036303 — (010203 + 616263 + C1C2C3), and then expanding and col-
lecting like terms, we get zero.
(A Liu)
4.	Assume that there are n places around the table and an is the
number of possible sitting arrangements. Let us number the mem-
bers of the Jury starting with professor K. If in an arrangement
the second member of the Jury sits at the zth place then all the
members of the Jury with numbers from 3 to i — 1 are sitting at
their places. Hence the number of sitting arrangements of this kind
will be an-i+2- It follows that an = an_i + an-2 + • • • + (12 + L
Since a2 = 1, we obtain an = 2n-2. Hence 012 = 1024.
(A Liu)
5.	Alternative 1
Consider a parallelepiped inside another one. Consider three edges
of the inner parallelepiped that have a common vertex. The sum
Senior Solutions
79
of the projections of these edges on any edge of the outer paral-
lelepiped is at most the length of this edge. Hence the sum of
the projections of the selected three edges on three perpendicular
edges of the outer parallelepiped is at most the size of the outer
parallelepiped.
Since the length of any edge of the inner parallelepiped is at most
the sum of its projections on three perpendicular edges of the outer
parallelepiped, the result follows.
(A Storozhev)
Alternative 2
Let ж, y, z be the lengths of three perpendicular edges of the inner
parallelepiped and let a, b, c be the lengths of three perpendicular
edges of the outer parallelepiped. Since the area of the surface of
the inner parallelepiped cannot exceed the area of the surface of
the outer one, we have 2xy + 2xz + 2yz < 2ab + 2ac + 2bc. Since
the diagonals of the inner parallelepiped cannot be longer than the
diagonals of the outer one, we obtain ж2 + y2 + z2 < a2 + b2 + c2.
Hence (ж + у + z)2 < (a + b + c)2 which means x + y + z < a + b + c.
(A Storozhev)
6.	Let f(x') =	+ аж + 6 a functjon such that the numerator
and the denominator have no common roots. The problem asks to
prove that the following two statements are equivalent:
(A)	There exist two real numbers h < к such that for any real
number ж, either /(ж) < h or /(ж) > к.
(В)	The function /(ж) can be expressed in the form
where each of the functions fj is of one of the three forms
kjX + bj, 1/x, x2.
We first carry out some preliminary analysis. To test whether they
have any common real roots, we perform the Euclidean Algorithm
as follows:
ж2 + ax + b = (ж2 + ex + d) + ((a — с)ж + (b — d)),	(1)
2	7	( x ac - c2 — b + d\ ..	.	...
ж + ex + d =----------1--------------- (la — c)x — (o — d))
\a — c \a — cy J
80
TOURNAMENT 20
(b — d)2 + (a — c)(ad — be)
(a — c)z
From (1) and (2), we see that in order for the numerator and the
denominator of /(ж) not to have any common real roots, we must
have (b — d)2 + (a — c)(ad — be) У 0. We shall prove that each of
(A) and (B) is equivalent to
(C)	The coefficients a, 6, c and d in /(ж) satisfy
(b — d)2 + (a — c)(ad — be) > 0.	(3)
It will then follow that (A) and (B) are equivalent to each other.
There are four cases which we need to consider.
Case 1.
Neither x2 + ax + b nor x2 + ex + d has distinct real roots. Then
a2 < 4b and c2 < 4d. Using these and the Arithmetic-Geometric
Means Inequality, we have
(b — d)2 + (a — e)(ad — be)
—	(b — d) T a d T c b — ac(b T d)
>	(b — d)2 + 2acVbd — ac(b + d)
= (b — d)2 — ac(Vb — Vd)2
>	(b - d)2 - 4Vbd(Vb - Vd)2
= (Vl) ~ Vd)4
> 0.
Since equality cannot hold, (3) is established.
Case 2.
Exactly one of x2 + ax + b and x2 + ex + d has distinct real roots.
Suppose only x2 + ax + b has distinct real roots a and {3. Then
a-\-(3 = —a and a(3 = b. Moreover, a2+ca+d > 0 and (32+c(3+d >
0. It follows that
0 < (a2 + cot + d)(/32 + c/3 + d)
— (ot[3) T c2ot/3 T d T cqi/3(q! T (3) T cd{oL T /3) T d(cn T (32)
= b2 + be2 + d2 — abc — acd + d(a2 — 2b)
= (b — d)2 + (a — c)(ad — be).
Since (3) is symmetric with respect to x2 + ax + b and x2 + ex + d,
this case also covers the scenario where only x2 + ex + d has distinct
real roots.
Senior Solutions
81
Case 3.
Both x2 + ax + b and x2 + ex + d have distinct real roots and the
two pairs do not separate each other. In other words, if the roots
of x2 + ax + b are a < (3, and the roots of x2 + ex + d are у < 5,
then we have a < (3 < у < 8, у < 6 < a < (3, a < ^ < 8 < [3
or 7 < a < (3 < 6. In any of these four situations, a2 + ca + d
and (32 + c(3 + d have the same sign, so that we can establish (3) in
exactly the same way as in Case 2.
Case 4.
Both x2 + ax + b and x2 + ex + d have distinct real roots and the
two pairs separate each other. In the notation of Case 3, we have
a. < 7 < (3 < 8 or 7 < a. < 8 < /3. In this case, the inequality sign
of (3) is reversed.
We now give the main argument, in four parts.
Part I:	(A)=»(C).
We shall prove that if f{x) has property (A), then Case 4 cannot
occur. It will then follow that f(x) has property (C).
Suppose Case 4 occurs with a < < (3 < 5. Then y2 + ay + b < 0
while 82+a8+b > 0. Asa; approaches 7 from the right, x2+ax+b <
0 while x2+cx+d approaches 0 from below, so that f(x) approaches
00. As x approaches 6 from the left, ж2+аа;+6 > 0 while x2 + ex+d
approaches 0 from below, so that f(x) approaches —00. Since f(x)
is continuous on (7,5), it cannot have property (A).
If instead we have 7 < a < 8 < (3, then f(x) approaches 00 as
x approaches 7 from the right, and f(x) approaches —00 as x ap-
proaches 8 from the left. The same contradiction arises.
Part II:	(C)=>(A).
We first dispose of Case 1. Here, we have x2 + ax + b > 0 and
x2 + ex + d > 0 for all x. Hence f(x) >0 for all x, so that we can
take any h and к which satisfy h < к < 0.
It is easy to show that /(ж) has property (A) if and only if so has
, -. Hence Cases 2 and 3 can be combined into the scenario
Я*)
where only x2 + ex + d has distinct real roots 7 and 8. Moreover,
we may assume that y2 + ay + b > 0 and 82 + aS + b > 0. This
only rules out a < у < 8 < (3 in Case 3, but in that situation, we
may work with - instead.
№)
82
TOURNAMENT 20
Note that f(x) approaches oo as x approaches 7 from the left but
approaches —00 if x approaches 7 from the right. Also, f(x) ap-
proaches —00 as x approaches 6 from the left and approaches 00
as x approaches 5 from the right. Let the maximum of f(x) on
(7,5) occur at xq. On (—00,7), let the greatest lower bound for
f(x) be F±. Then either Fi = 1 or Fi = f(xi) for some xi on this
interval. On (5, 00), let the greatest lower bound for f(x) be F^.
Then either Fz = 1 or F% = /(ж2) for some xz in this interval. We
shall prove that /(жо) < min{Fi, F2} so that we can take h and к
with /(жо) < h < к < min{Fi,F2}.
From (1), we are led to consider the expressions (a — 0)7 + (b — d)
and (a — c)S + (b — d). Now
((a - 0)7 + (b- d)) + ((a - c)d) + (b - d))
= (a + 7 + d)(7 + 5) + 2b —
= (q2 + aq + b) + (d2 + ab + b)
> 0
while
((a - c)y + (b - d))((a - c)d + (b - d))
= (a — c)2d — (a — c) (b — d)c + (b — d)2
= (b — d)2 + (a — c)(ad — be)
> 0.
It follows that (a — 0)7+ (b — d) > band (a — c)6 + (b — d) > 0. Since
7 < xq < 6, we have (a — c)xq + (b — d) > 0 or Xq + axQ + b > Xq +
7	9	,	„	, p/ x xq + axQ + b
cxq + d. Since Xc, + cxq + d < 0, we have j(xq) = —5----------- < 1.
Xq + cxq + d
We now prove that /(жо) < F2. In view of the preceding paragraph,
we may as well assume that F2 = /(ж2) < 1 for some ж2 6 (d, 00).
AT Жо + аж2 + b Xq + ах0 + b .	. , , ,
Now —?------------- > —?---------- is equivalent to
Ж2 + сж2 + d Xq + cxq + d
(Ж2 + аж2 + b) (жд + cxq + d) < (ж§ + axQ + b) (x% + сж2 + d)
since Xq + cxq + d < 0 < Ж2 + сж2 + d. The last displayed inequality
may be rewritten in the form (ж2 — жо)((а — с)жож2 + (b — d)^o +
ж2) — (ad — be)) > 0. Since жо < 5 < ж2, this is equivalent to
0
(a — с)жож2 + (b — d)(xQ + ж2) — (ad — be)
((a — c)xq + (b — d)^2 + (b — d)xo — (ad — be).
Senior Solutions
83
Denote the last displayed expression by X. Since (a—c)xo+(b—d)
0 and X2 > 5, we have
X > ((a — c)xq + (b — d))S + (b — d)xo — (ad — be)
= ((a — c)6 + (b — d))xQ + (b — d)6 — (ad — be).
Since (a — c)6 + (b — d) >0 and xq > y, we have
X > ((a — c)6 + (b — d) + (b — d))y + (b — d)6 — (ad — be)
= (a — c)^d + (b — d)(y + 5) — (ad — be)
= (a — c)d — (b — d)c + (ad — be)
= 0.
It follows that f(xo) < f(x%). In the same way, we can prove that
f(x0)<F1.
Part III:	(B)=>(C).
If f(x) =	• • fn-i(fn(x)) • • •)), exactly one fa(x) = x2. If
i < n, let
Л+1(Л+2(- •  W) )) = ^77?
С? X “t* U
We may assume that AD BC as otherwise we can reduce n to
i. If i > 1, let
CrX + 11
We may assume that EH EG as otherwise we can reduce г to 1.
E(Ax + B)2 + F(Cx + D)2
°W G(Ax + B)2 + H(Cx + D)2'
q 2(EAB + FCD) ъ ЕВ2 + FD2
T еП a ~ EA2 + FC2 ' ~ EA2 + FC2 1
2(GAB + HCD) л 1 GB2+HD2
C~ GA2 + НС2 аП “ GA2 + HC2 ’
тт zr. Z \l \ (EH-FG)2(AD-Bcy
Hence (b d) + (a c)(ad ~ ^Ea2 p FC2)2(GA2 + HC2)2'
Since either AD BC or EH FG, (3) is established.
Part IV:	(C)=>(B).
We claim that there exist real numbers к and A such that
„z .	(1 + к)х2 + (a + ck)x + (b + dn) . (x + A)2
j(x)Fk—-----------5---------------— (l + Av)—5
x2 + ex + d	x2 + ex + d
84
TOURNAMENT 20
We need
(c2 - 4d)«2 + 2(ac — 2b — 2d)n + (a2 - 46) = 0.
If c2 — 4d 7^ 0, then the discriminant of this quadratic equation is
4(ac — 2b — 2d)2 — (c2 — 4d)(a2 — 4b) = 4((6 — d)2 + (a — c) (ad — be)).
By (3), this is positive so that there are two choices for к. If
c2 — 4d — 0, then ac — 2b — 2d 0 as otherwise a2 — 4b = 0. This
will force a = c = a/2, b = d = | and f(x) = 1 for all x. Hence we
can take
_ 4b - a2
K 2(ac — 2b — 2d)
Note that we cannot have 1 + к = 0 as otherwise f(x) = — к for all
x.
Since f(x) has property (C), it has property (A). It follows that
1 + к x2 + ex + d
9 X f(x) + к (x + A)2
also has property (A), so that it has property (C) as well. Using
the same technique as before, we can choose real numbers p, and v
such that
( qr _L
9(а:)+^ = (1+м)(а, + л)2.
Note that we must have 1 + p 7^ 0 and v — A 7^ 0 as otherwise /(ж)
is a constant function.
Let
A(z)
/2 (ж)
/з(^)
/4 (x)
h (x)
fe(x)
and f7(x)
x — K,
1
X
1 + p p
------x-----------,
1 + к 1 + к
X2,
X + 1,
1
X
1 A
------\x 4--------V
v — A //, — A
Senior Solutions
85
we have
№) = Л(Ш(Ш(№И)))))
1 + ft
(1 + м)(^)2-л
x2, + ax + b
x2 + ex + d
(X Li and A Liu)
86
TOURNAMENT 20
Spring 1999 (0 Level)
1.	Let the numbers be ai with 1 < i < 1999. From = ai + аз and
аз = az + а4, we have a± +	— 0. Similarly, + ay = 0, so that
ai — a^. It follows that a±ggg = 01993 = • • • = ai = 1.
(A Liu)
2.	See solution to Problem 2 in Junior paper.
3.	See solution to Problem 3 in Junior paper.
4.	The seven tiles may be placed as shown in the following diagram.
The black square is drawn in thin lines.
(A Liu)
5.	Alternative 1
The value is В = 2. The first player can guarantee a score of
2 by taking the central square and then play symmetrically with
respect to the second player. The first player will win the central
row and exactly one of each pair of symmetric rows, as well as the
central column and exactly one of each pair of symmetric columns.
The second player can hold the first player’s score to 2 by playing
symmetrically with respect to the first player. If not forced to do
so, the second player can play anywhere. The first player will win
exactly the same rows and columns as before.
(A Liu)
Alternative 2
The value is В = 2. Divide the board into 40 dominoes and 1 single
cell as shown in the diagram below. The first player can guarantee
a score of 2 by taking the single cell and completing any domino
the second player starts. The first player will win the first row
and exactly one of each pair of rows thereafter, as well as the first
Senior Solutions
87
column and exactly one of each pair of columns thereafter. The
second player can hold the first player’s score to 2 by completing
any domino the first player starts. If not forced to do so, the
second player can start a domino. The first player will win exactly
the same rows and columns as before.
(A Liu)
88
TOURNAMENT 20
Spring 1999 (A Level)
1. The answer is yes, it can happen.
Consider a regular pyramid with an angle a between its base and
the other faces. Cut this pyramid with a plane parallel to its base
so that there is another pyramid similar to the original. Let the
enlargment factor be t-1.
In order for the smaller pyramid to have at least 90% of the volume
of the original one, we need t3 > 0.9. Also for the surface area
1	2t2
condition to be met, the inequality 1 H------> ------- must hold.
COSO!	COSO!
We can	find t that	satisfies both inequalities	if----> 0.92/3.
Clearly	such a exists.
(A Liu)
Let /.ADB = a and LDAC = (3. Then /.AOB = 2a. Hence
LABO = 90° - a. Hence LAFO = 90° - a. Similarly LDFO =
90° — (3. Hence AAFD = 180° — a — (3. Let the point where AC and
BD meet be X. Then LAXD = /180° - a - /3. Thus 3AFD =
LAXD, which means that AFXD is a cyclic quadrilateral.
(A Liu)
3. Since both x3 + у and y3 + x are divisible by x2 + y2, x and у are
relatively prime. Hence x2 + y2 and xy are relatively prime. Now
x(x3 + y) + y(y3 + x) = x4 + y4 + 2xy
is divisible by x2 + y2. Hence
(x2 + у2)2 — x4 — у4 — 2xy = 2xy(xy — 1)
Senior Solutions
89
is divisible by x2 + y2. Therefore 2(xy — 1) is divisible by x2 + y2.
If xy > 0, then the fact that 2(xy — 1) is divisible by x2 + y2 implies
either 2(xy — 1) > x2 + y2 or xy — 1 = 0. When 2(xy — 1) > x2 + ?/2,
we have (x — y)2 + 2 < 0 which is not possible. Hence xy = 1 which
means that either x = 1, у = 1 or x = —1, у = —1.
If xy < 0, then — 2(xy — 1) > x2 ± y2 which implies (x + y)2 < 2.
Hence x + y equals 0, 1 or —1. If x = —y, then either x = 1, у = —1
or x = —1, у = 1. If x+y = 1 or x+y = —1, then x2 +y2 = 1 — 2xy.
Hence 2(xy — 1) is divisible by 1 — 2xy^ and therefore 1 is divisible
by 1 — 2xy, which is not possible when xy < 0.
If xy = 0, then r = 0, ?/= 1 or a; = 0, ?/= -1 or r = 1, ?/= 0 or
x = -1, у = 0.
Thus the solutions are (±1,±1), (0,±l), (±1,0).
(A Liu)
4. See solution to Problem 4 in Junior paper.
5.
(a) If the last two digits of the binary representation of i are 01,
then M(i) = M(i + 1). So there are at least —= 250
numbers i such that M(i) = M(i ± 1). Similarly if the last
four digits of the binary representation of i are 0111, then
M(i) = M(i +1). Hence there are at least
1000
16
= 62 more
numbers i such that M(i) = M(z±l). In the same manner we
can show that there are at least
i such that M(i) = M(i ± 1).
1000
~64~
= 15 more numbers
Thus there are at least 327
numbers i such that M(i) = M(i + 1).
(b) If the last four digits of the binary representation of i are
0001, 0011, 0100, 0101 or 0111, then M(i) = M(i + 7). If
the last five digits of the binary representation of i are 01010
or OHIO, then M(i) = M(i ± 7). If the last six digits of the
binary representation of i are 011001, 011011, 011100, 011101
or 011111, then M(i) = M(i ± 7). If the last seven digits of
the binary representation of i are 0111010 or 0111110, then
M(i) ~ M(i + 7). Now we see that there are at least
106'
U
IO6’
"32“
IO6’
IO6’
128
x 5 +
x 2 +
x 5 +
x 2
Г106!
218
’IO6
219
x 5 +
x 2
90
TOURNAMENT 20
numbers i such that M(i) = M(i + 7). Hence there are at
least 450000 numbers i such that M(i) = M(i + 7).
(A Liu)
6. See solution to Problem 6 in Junior paper.
TOURNAMENT 21

TOURNAMENT 21
JUNIOR QUESTIONS
Autumn 1999 (0 Level)
1.	A right-angled triangle made of paper is folded along a straight line
so that the vertex at the right angle coincides with one of the other
vertices of the triangle and a quadrilateral is obtained.
(a)	What is the ratio into which the diagonals of this quadrilateral
divide each other?	(2 points)
(b)	This quadrilateral is cut along its longest diagonal. Find the
area of the smallest piece of paper thus obtained if the area
of the original triangle is 1.	(A Shapovalov, 2 points)
2.	Let d = u1999 + 61999 + c1999, where a, b and c are integers such
that a + b + c = 0.
(a)	May it happen that d = 2?	(2 points)
(b)	May it happen that d is prime? (V Senderov, 2 points)
3.	There are n straight lines in the plane such that each intersects
exactly 1999 of the others. Find all posssible values of n.
(R Zhenodarov, 4 points)
4.	Every 24 hours, the minute hand of an ordinary clock completes
24 revolutions while the hour hand completes 2. Every 24 hours,
the minute hand of an Italian clock completes 24 revolutions while
the hour hand completes only 1. The minute hand of each clock is
longer than the hour hand, and “zero hour” is located at the top of
the clock’s face. How many positions of the two hands can occur
on an Italian clock within a 24-hour period that are possible on an
ordinary one?	(Folklore, 4 points)
5.	Is it possible to divide a 6 x 6 chessboard into 18 rectangles, each
either 1 x 2 or 2 x 1, and to draw exactly one diagonal on each
rectangle such that no two of these diagonals have a common end-
point?	(A Shapovalov, 4
points)
94
TOURNAMENT 21
Autumn 1999 (A Level)
1.	n consecutive positive integers are put down in a row (not neces-
sarily in order) so that the sum of any three successive integers in
the row is divisible by the leftmost number in the triple. What is
the largest possible value of n if the last number in the row is odd?
(A Shapovalov, 3 points)
2.	Let ABC be an acute-angled triangle, C and A' be arbitrary points
on the sides AB and BC respectively, and B' be the midpoint of
the side AC.
(a)	Prove that the area of triangle A' B'C is at most half the area
of triangle ABC.	(2 points)
(b)	Prove that the area of triangle A'B'C is equal to one fourth
of the area of triangle ABC if and only if at least one of the
points A', C is the midpoint of the corresponding side.
(E Cherepanov, 2 points)
3.	The numbers 1,2,..., 100 are divided into two groups so that the
sum of all numbers in one group is equal to that in the other. Prove
that one can remove two numbers from each group so that the sums
of all numbers in each group are still the same.
(A Shapovalov, 5 points)
4.	(a) On each of the lxl squares of the top row of an 8 x 8 chess-
board there is a black pawn, and on each of the lxl squares
of the bottom row of this chessboard there is a white pawn.
On each move one can shift any pawn vertically or horizon-
tally to any adjacent empty lxl square. What is the smallest
number of moves that are needed to move all white pawns to
the top row and all black pawns to the bottom one?
(3 points)
(b) The same question for a 7 x 7 board.
(A Shapovalov, 4 points)
Junior Questions
95
5.	Tireless Thomas and Jeremy construct a sequence. At the be-
ginning there is one positive integer in the sequence. Then they
successively write new numbers in the sequence in the following
way: Thomas obtains the next number by adding to the previous
number one of its (decimal) digits, while Jeremy obtains the next
number by subtracting from the previous number one of its dig-
its. Prove that there is a number in this sequence which will be
repeated at least 100 times.	(A Shapovalov, 8 points)
6.	Inside a rectangular piece of paper n rectangular holes with sides
parallel to the sides of the paper have been cut out. Into what
minimal number of rectangular pieces (without holes) is it always
possible to cut this piece of paper? (A Shapovalov, 9 points)
96
TOURNAMENT 21
Spring 2000 (О Level)
1.	Can the product of two consecutive positive integers be equal to
the product of two consecutive even positive integers?
(V Proizvolov, 3 points)
2.	In a quadrilateral ABCD of area 1, the parallel sides BC and AD
are in the ratio 1:2. К is the midpoint of the diagonal AC and
L is the point of intersection of the line DK and the side AB.
Determine the area of the quadrilateral BCKL.
(MG Sonkin, 4 points)
3.	The base of a prism is an n-gon. We wish to colour its 2n vertices
in three colours in such a way that every vertex is connected by
edges to vertices of all three colours.
(a)	Prove that if n is divisible by 3, then the task is possible.
(2 points)
(b)	Prove that if the task is possible, then n is divisible by 3.
(A Shapovalov, 3 points)
4.	Can one place positive integers at all vertices of a cube in such a
way that for every pair of numbers connected by an edge, one will
be divisible by the other, and there are no other pairs of numbers
with this property?	(A Shapovalov, 5 points)
Junior Questions
97
Spring 2000 (A Level)
1.	Determine all real numbers that satisfy the equation
(ж +1)21 + (жТ 1)20(ж — 1) + (ж + 1)19(ж — I)2 ---1- (ж — I)21 = 0.
(RM Kuznec, 3 points)
2.	Two parallel sides of a quadrilateral have integer lengths. Prove
that this quadrilateral can be cut into congruent triangles.
(A Shapovalov, 3 points)
3.	A is a fixed point inside a given circle. Determine the locus of
points C such that ABCD is a rectangle with В and D on the
circumference of the given circle.	(M Panov, 6 points)
4.	Give and Take divide 100 coins between themselves as follows. In
each step, Give chooses a handful of coins from the heap, and Take
decides who gets this handful. This is repeated until all coins have
been taken, or one of them has 9 handfuls. In the latter case, the
other gets all the remaining coins. What is the largest number of
coins that Give can be sure of getting no matter what Take does?
(A Shapovalov, 7 points)
5.	What is the largest number of knights that can be put on a 5 x 5
chess board so that each knight attacks exactly two other knights?
(M Gorelov, 7 points)
6.	In a chess tournament, every two participants play each other ex-
actly once. A win is worth one point, a draw is worth half a point
and a loss is worth zero points. Looking back at the end of the
tournament, a game is called an upset if the total number of points
obtained by the winner of that game is less than the total number
of points obtained by the loser of that game. Prove that the num-
ber of upsets is always strictly less than three-quarters of the total
number of games in the tournament. (S Tokarev, 10 points)
98
TOURNAMENT 21
SENIOR QUESTIONS
Autumn 1999 (0 Level)
1.	The incentre of a triangle is joined by three segments to the three
vertices of the triangle, thereby dividing it into three smaller trian-
gles. If one of these three triangles is similar to the original triangle,
find its angles.	(A Shapovalov, 4 points)
2.	Prove that there exist infinitely many odd positive integers n for
which the number 2n + n is composite. (V Senderov, 4 points)
3.	There are n planes in space such that each intersects exactly 1999
of the others. Find all possible values of n.
(R Zhenodarov, 4 points)
4.	Is it possible to divide the integers from 1 to 100 inclusive into 50
pairs such that for 1 < к < 50, the difference between the two
numbers in the fc-th pair is fc?	(V Proizvolov, 4 points)
5.	Is it possible to divide an 8 x 8 chessboard into 32 rectangles, each
either 1 x 2 or 2 x 1, and to draw exactly one diagonal on each
rectangle such that no two of these diagonals have a common end-
point?	(A Shapovalov, 4
points)
Senior Questions
99
Autumn 1999 (A Level)
1.	For what values of n is it possible to place the integers from 1 to
n inclusive on a circle (not necessarily in order) so that the sum of
any two successive integers in the circle is divisible by the next one
in the clockwise order?	(A Shapovalov, 3 points)
2.	On a rectangular piece of paper there are
(a) several marked points all on one straight line; (2 points)
(b) three marked points (not necessarily on a straight line).
(3 points)
We are allowed to fold the paper several times along a straight line
not containing marked points and then puncture the folded paper
with a needle. Show that this can be done so that after the paper
has been unfolded all the marked points are punctured and there
are no extra holes.	(A Shapovalov)
3.	Tireless Thomas and Jeremy construct a sequence. At the be-
ginning there is one positive integer in the sequence. Then they
successively write new numbers in the sequence in the following
way: Thomas obtains the next number by adding to the previous
number one of its (decimal) digits, while Jeremy obtains the next
number by subtracting from the previous number one of its dig-
its. Prove that there is a number in this sequence which will be
repeated at least 100 times.	(A Shapovalov, 6 points)
4.	Points K, L on sides AC, CB respectively of a triangle ABC are
the points of contact of the excircles with the corresponding sides.
Prove that the straight line through the midpoints of КL and AB
(a) divides the perimeter of triangle ABC in half; (3 points)
(b) is parallel to the bisector of angle ACB.
(L Emelianov, 3 points)
5.	(a) The numbers 1,2,..., 100 are divided into two groups so that
the sum of all numbers in one group is equal to that in the
other. Prove that one can remove two numbers from each
group so that the sums of all numbers in each group are still
the same.	(4 points)
(b) The numbers 1, 2,..., n are divided into two groups so that
the sum of all numbers in one group is equal to that in the
other. Is it true that for every such n > 4 one can remove two
numbers from each group so that the sums of all numbers in
each group are still the same? (A Shapovalov, 4 points)
100
TOURNAMENT 21
6.	On a large chessboard, 2n of its 1 x 1 squares have been marked
such that the rook (which moves only horizontally or vertically) can
visit all the marked squares without jumping over any unmarked
ones. Prove that the figure consisting of all the marked squares can
be cut into n rectangles.	(A Shapovalov, 8 points)
7.	Prove that any convex polyhedron with lOn faces has at least n
faces with the same number of sides.	(A Kanel, 8 points)
Senior Questions
101
Spring 2000 (0 Level)
1.	The diagonals of a convex quadrilateral ABCD meet at P. The
sum of the areas of triangles PAB and PCD is equal to the sum
of areas of triangles PAD and PCB. Prove that P is the midpoint
of either AC or BD.	(Folklore, 3 points)
2.	Each of a pair of opposite faces of a unit cube is marked by a
dot. Each of another pair of opposite faces is marked by two dots.
Each of the remaining two faces is marked by three dots. Eight
such cubes are used to construct a 2 x 2 x 2 cube. Count the
total number of dots on each of its six faces. Can we obtain six
consecutive numbers?	(A Shapovalov, 4 points)
3.	Prove the inequality
lfc + 2k 4------------к nk <
n2k — (n — l)fc
nk — (n — l)fc
for all positive integers n and k.
(L Emelianov, 4 points)
4.	(a) Does there exist an infinite sequence of real numbers such that
the sum of every ten successive numbers is positive, while for
every n the sum of the first lOn + 1 successive numbers is
negative?	(3 points)
(b) Does there exist an infinite sequence of integers with the same
properties?	(AK Tolpygo, 3 points)
102
TOURNAMENT 21
Spring 2000 (A Level)
1.	Positive integers m and n have no common divisor greater than
one. What is the largest possible value of the greatest common
divisor of m + 2000n and n + 2000m? (S Zlobin, 3 points)
2.	The chords AC and BD of a circle with centre О intersect at the
point K. The circumcentres of triangles AKB and CKD are M
and N respectively. Prove that OM = KN.
(A Zaslavskij, 5 points)
3.	Peter plays a solitaire game with a deck of cards, some of which
are face-up while the others are face-down. Peter loses if all the
cards are face-down. As long as at least one card is face up, Peter
must choose a stack of consecutive cards from the deck, so that the
top and the bottom cards of the stack are face-up. They may be
the same card. Then Peter turns the whole stack over and puts it
back into the deck in exactly the same place as before. Prove that
Peter always loses.	(A Shapovalov, 5 points)
4.	Each vertex of a convex polygon has integer coordinates, and no
side of this polygon is horizontal or vertical. Prove that the sum
of the lengths of the segments of lines of the form x = m, m
an integer, that lie within the polygon is equal to the sum of the
lengths of the segments of lines of the form у = n, n an integer,
that lie within the polygon.	(G Galperin, 5 points)
5.	What is the largest number N for which there exist N consecutive
positive integers such that the sum of the digits in the fc-th integer
is divisible by к for 1 < к < N?	(S Tokarev, 7 points)
6.	In a chess tournament, every two participants play each other ex-
actly once. A win is worth one point, a draw is worth half a point
and a loss is worth zero points. Looking back at the end of the
tournament, a game is called an upset if the total number of points
obtained by the winner of that game is less than the total number
of points obtained by the loser of that game.
(a)	Prove that the number of upsets is always strictly less than
three-quarters of the total number of games in the tourna-
ment.	(6 points)
(b)	Prove that three-quarters cannot be replaced by a smaller
number.	(S Tokarev, 6 points)
Junior Solutions
103
JUNIOR SOLUTIONS
Autumn 1999 (0 Level)
1.	Let ABC be the paper triangle with the vertex C at the right angle
folded into B. Let the line of fold be DF with D on BC and F on
AB. Now D is the midpoint of BC, and DF is perpendicular to
BC. It follows that DF is parallel to AC, so that F is the midpoint
of AB. Let G be the point of intersection of AD and CF.
(a)	G is the centroid of triangle ABC, and we have AG : GD =
2:1 = CG:GF.
(b)	When cut along AD, the smallest piece of paper is congruent
to triangle GCD. Since the area of ABC is 1 and BD : DC =
1 : 1, the area of ACD is Since AG : GD = 2:1, the area
of area of GCD is |.
(A Liu)
2.	Since a + b + c = 0, we have c = — (a + b). Hence
d = a1999 + 61999 -(a + 6)1999
= (a + 6)(a1998 - a19976 + • • • + 61998) - (a + 6)1999.
So d is divisible by a + b and therefore by c. Similarly d is divisible
by a and b.
Now let d be a prime. Then each of a, b, c is equal to 1, —1, d or
—d. Therefore without loss of generality either a = —b or a = b.
If a = — b, then d = 0, which is not possible.
If a = b, then d = 2a1999 — (2a)1999 = a1999 (2 — 21999). Clearly
21999 _ 2 is not a prime, so d cannot be a prime.
Thus the answer to both (a) and (b) is no.
(A Liu)
104
TOURNAMENT 21
3.	Let there be к families of mutually parallel lines such that lines in
different families are not parallel. The total number of lines in any
к — 1 families is 1999. Hence all families are of size n — 1999. It
follows that к — 1 is a divisor of 1999. Since 1999 is a prime, either
к = 2 and n = 3998, or к = 2000 and n = 2000.
(A Liu)
4.	In any position which can occur on both clocks, let the angle from
“zero hour” to the minute hand be 240. Then 0° < в < 15°. Now
the angle between “zero hour” and the hour hand of an ordinary
clock is 20 + m • 30° for some integer m, while the angle between
“zero hour” and the hour hand of an Italian clock is 0 + n • 15° for
some integer n.
Equating these two angles, we have (n — 2m) 15° = 0. From the
bounds on d, we must have 0 = 0°. It follows that there are exactly
12 positions which can occur on both clocks, with the angle between
“zero hour” and the hour hand being к  30° for к = 0,1,2,..., 11.
(A Liu)
5.	The task is possible, as shown in the diagram below.
(A Liu)
Junior Solutions
105
Autumn 1999 (A Level)
1.	If there are two successive numbers in the sequence that are both
even, then the next number on their right must be even too. Since
the rightmost number in the sequence is odd, there are no two even
numbers in the sequence that are next to each other.
Also clearly any two even numbers in the sequence cannot be sep-
arated by one odd number. Hence there are at most two even
numbers in the sequence since otherwise the total number of odd
numbers in the sequence would be at least two more than that of
even numbers. Thus n < 5. The sequence 2,1,3,4, 5 shows that
the answer is n = 5.
(A Liu)
2.	(a) Construct a parallelogram ABCD. Extend A'B' and СB'
beyond B' to meet the sides AD and CD of the parallelogram
in points A" and C" respectively.
Now we have a parallelogram A'C A"C" inside a parallelo-
gram ABCD. Hence the area of A'C'A"C" is at most the
area of ABCD. Since the area of A'CB' is a quarter of the
the area of A'C A"C", the result follows.
(A Liu)
(b) Assume that C is not the midpoint of AB. Now let us move a
point X along BC in one direction. Then the area of XB'C
will be changing monotonously, which implies that there is at
most one point X on BC such that the area of XB'C is one
fourth of the area of ABC. If X is the midpoint of BC, then
the area of XB'C is a quarter of the area of ABC. Hence A'
is the midpoint of BC.
(A Liu)
3.	See solution to Problem 5 (a) in Senior Paper.
106
TOURNAMENT 21
4.	(a) Consider a column of the chessboard. If the top pawn of this
column has moved to the bottom position without making
any horizontal moves, then the bottom pawn of this column
must have made at least one horizontal move on its way to
the top row. Hence the total number of moves is at least
7x2x818 = 120.
Now we shall show that one can do the required rearrangement
of the pawns in 120 moves. Consider two columns that are
next to each other and the following sequence of moves: left
bottom pawn moves three squares up; right top pawn moves
six squares down, one left and one down; right bottom pawn
moves seven squares up; left top pawn moves two squares
down, one right and five down; left white pawn moves four
squares up.
We can see now that the positions of white and black pawns
in these two columns have been exchanged in 30 moves. Since
there are 8 columns in the chessboard, the answer is 120.
(b) Similarly to part (a), we can assert that the number of moves
needed to finish that task is at least 6x2x7 + 7 = 91. We
shall prove that the smallest number of moves is 92. Assume
that we can move the pawns as required in 91 moves. This
means that exactly one pawn in each column made precisely
one horizontal move.
Consider the leftmost column of the chessboard. Assume that
the bottom pawn of this column is to make a horizontal move.
The only possibility for this pawn is to move right. Then the
bottom pawn of the second left column must make a horizontal
move as the top position in this column will be occupied. If
this pawn moves right, then one of the remaining five pawns
will need to make at least two horizontal moves which is not
possible. Hence the second left white pawn has to make a
move to the left.
Now we can repeat the same reasoning starting from the third
left column. Thus we group the columns of the chessboard into
pairs which means that the total number of columns is even, a
contradiction. Next we shall show that we can do the required
rearrangement of the pawns in 92 moves.
Consider three columns that are next to each other and the
following sequence of moves: left bottom pawn moves three
squares up; middle top pawn moves five squares down, one
left and one down; middle bottom pawn moves six squares
Junior Solutions
107
up; right top pawn moves five squares down, one left and
one down; right bottom pawn moves six squares up; left top
pawn moves two squares down, two right and four down; left
white pawn moves three squares up. We can see now that
the positions of white and black pawns in these three columns
have been exchanged in 40 moves.
The remaining four columns can be done similarly to part (a).
Thus the answer is 92.
(A Liu)
5.	Assume that the sequence does not have an upper bound. Consider
a number A in the sequence obtained by Thomas. Let В be the next
number in the sequence obtained by Thomas. Then \B — A| < 10.
Therefore we can find a number X obtained by Thomas such that
all its digits except the rightmost digit are nines. Now it is eas-
ily seen that no term of the sequence obtained after X can exceed
X + 10. Hence the sequence has an upper bound which is a con-
tradiction.
Similarly, we can prove that the sequence has a lower bound which
implies that there is a number in the sequence that will be repeated
at least 100 times.
(A Liu)
6.	The answer is 3n + 1.
Consider n square holes AiBiCiDi (i = 1,... ,n) such that their
centres lie on a straight line parallel to one of the sides of the piece
of paper, all AiDi are parallel to the line through their centres and
are on the same side of this line, and AiBi = х/Зг where x is the
length of the shortest side of the piece of paper.
Assume that the piece of paper (with the holes) has been cut into
rectangular pieces. Then no two interior points of the sides AiBi,
BiCi, AiDi (i = 1,..., n) and CnDn taken on different sides belong
to one of the new pieces as the segment joining them always has
common points with the interior of the holes. Hence the number
of the pieces is at least 3n + 1.
Now consider a rectangular piece of paper with n holes in it. Extend
each vertical side of the holes in both directions until it meets
horizontal sides of the holes or the edges of this piece of paper, and
make cuts along these extensions thus dissecting the original piece
of paper into rectangular pieces.
108
TOURNAMENT 21
For each of the vertical sides of the holes, there were two straight
line segments that extended it. Therefore each vertical side of the
holes contributed two the boundaries of three rectangular pieces.
Clearly every rectangular piece, except the leftmost and rightmost
ones, was counted at least twice in this way.
Hence there are at most (3 x 2n 2)/2 = 3n +1 rectangular pieces.
(A Liu)
Junior Solutions
109
Spring 2000 (0 Level)
1.	The answer is no.
Let n and n +1 be two consecutive positive integers and let 2k and
2k+2 be two consecutive even positive integers. Suppose n(n+l) =
2k(2k + 2'). Then 4n2+4n — 16fc2 + 16fc or (2n+l)2 + 3 = (4fc+2)2.
The only two squares which differ by 3 are 1 and 4. From 2n+l = 1
we have n = 0, which contradicts the requirement that n is positive.
(A Liu)
2.	Complete the parallelogram ADCE. Since its diagonals bisect each
other, К is also the midpoint of DE. Now EC = AD = 2BC.
Hence В is the midpoint of EC and L is the centroid of triangle
ACE. It follows that DK = KE = 3KL and AL = 2BL.
Denote the area of a polygon P by [P] and let [BLK] = x. Then
[ALK] = 2x since AL = 2BL and [ADK] = 6x since DK = 3KL.
Moreover, [BCK] = 3x and [DCK] = 6x since AK = КС.
Hence [ABCD] = l&r so that x — -A. It follows that [BCKL] =
4ж= |.
(A Liu)
3.	(a) Suppose n is divisible by 3. Paint the vertices of the base red,
yellow and blue cyclically. Paint the vertices of the top in the
same colour as the corresponding vertices on the base.
For any red vertex, its neighbours on the same level are paint-
ed yellow and blue while its neighbour on the other level is
coloured red. Similarly, we can verify that yellow and blue
vertices also have neighbours in all three colours.
(b) Suppose the task is possible. Let the number of red vertices
be r. Each red vertex is the neighbour of three other vertices.
Hence 3r vertices can have a red neighbour.
Since each vertex has exactly one red neighbour, there are
exactly 3r vertices.
110
TOURNAMENT 21
It follows that 3r = 2n. Since 3 and 2 are relatively prime to
each other, n must be divisible by 3.
(A Liu)
4.	The answer is no.
A possible placement is shown in the diagram below.
(A Liu)
Junior Solutions
111
Spring 2000 (A Level)
1.	Multiply both sides by (x + 1) — (x — 1) = 2 and we have
(x + I)22 - (x - l)22 = 0.
It follows that x + l = ±(x — 1) which leads uniquely to x = 0.
(A Liu)
2.	Let the quadrilateral be AB CD with BC parallel to AD. Let
BC = m and AD = n, where m and n are positive integers and
m > n. Draw a line PQ parallel to BC, where P is a point on CD
such that DP : DC = 1 : (m — n).
Also draw DS parallel to AB, where S is on BC. Let DS cut
PQ in R. Since DABS is a parallelogram, BS = AD. Hence
CS = m — n. The triangles DPR and DCS are similar. Therefore
PR : CS = DP : DC = 1 : (m - n). Hence PR = 1.
Now consider parallelogram DAQR. Let X and Y be points on
DA and RQ respectively such that DX = RY = 1. Then DXRP
is a parallelogram and therefore DRP and RDX are congruent
triangles. Similarly RDX and XYR are congruent triangles.
Applying the same procedure to parallelogram XAQY and so on,
we see that DAQP can be cut into triangles congruent to DPR.
Now we can consider PQBC and deal with it in the same manner
as we did with DABC. Eventually DABC will be cut into triangles
congruent to DPR.
(A Liu)
3.	Let the centre of the given circle be О and its radius r. Let d < r be
the distance of A from О. Draw the line through О parallel to AB,
cutting BC (possibly extended) at E and AD (possibly extended)
at F.
112
TOURNAMENT 21
By Pythagoras’ Theorem, we have
О A2 + ОС2
(OF2 + AF2) + (OE2 + CE2)
(OE2 + BE2) + (OF2 + DF2)
OB2 + О D2.
Since OA, OB and OD all have constant length, ОС also has
constant length. It follows that the locus of C is a subset of the
circle with centre О and radius д/2г2 — d2 > r. Conversely, for
any point C on this circle, we can draw a circle with diameter AC.
It will intersect the given circle at some point B. Complete the
rectangle ABCD.
Since О A2 + ОС2 = OB2 + OD2, OB = г, О A = d and ОС =
л/2г2 — d2, we have OD = r. So D must also lie on the given circle.
It follows that the locus of C is the entire circle with centre О and
radius д/2г2 — d2.
(A Liu)
4.	Give can be sure of securing 46 coins. Choose handfuls of 5 coins.
Suppose Take does not take any. After the eighth handful, Give
chooses handfuls of 6 coins. If Take refuses any, Give will have 46
coins. If Take takes nine handfuls of 6 coins, Give still has 46 coins.
If Take takes any of the handfuls of 5 coins earlier, Give continues
to offer handfuls of 5 coins until one of them has eight handfuls.
Give is guaranteed to have at least 46 coins. To prevent Give from
getting more than 46 coins, Take will take any handful of 6 coins
or more and gives Give any handful of 5 coins or less. If Take takes
nine handfuls of 6 coins or more, Give can get at most 46 coins.
Give cannot get more than 46 coins by getting handfuls of 5 coins
or less.
(A Liu)
Junior Solutions
113
5.	The diagram below shows that as many as sixteen knights can be
placed.
black and white alternately in the usual manner, with all four cor-
ner squares black. Since knights on black squares can only attack
knights on white squares and vice versa, the number of knights on
white squares is equal to the number of knights on black squares.
If we can place more than sixteen knights, at most four black and
three white squares may be vacant. A knight on the central black
square can attack eight white squares, six of which would have to
be vacant. Hence the central square itself must be vacant.
A knight on a white square next to the central square attacks six
other black squares, four of which must be vacant. Together with
the central square, we have too many vacant black squares.
However, this means that all four white squares next to the central
square must be vacant, and we have too many vacant white squares.
It follows that we can put at most sixteen knights on the 5x5 board.
(A Liu)
6.	See solution to Problem 6 (a) in Senior paper.
114
TOURNAMENT 21
SENIOR SOLUTIONS
Autumn 1999 (0 Level)
1.	Let ABC be the given triangle with incentre I. Let LB Al =
LCAI = a, LABI = LCBI = (3 and LBCI = LACI = y, with
Qi > /3 > 7-
Each of triangles IBC and ICA has an angle smaller than any
angle of triangle ABC. Hence I AB is similar to ABC, which leads
to a = 2/3 = 4y. Now 14y = 180°. It follows that LCAB =
|180°, LABC = |180° and LBCA = |180°.
(A Liu)
2.	Since 21 = 2 (mod 3) and 22 = 1 (mod 3), 2m = 2 (mod 3) if m is
odd. Let n = 6k + 1 for any positive integer k. Then 2n = 2 (mod
3) while n = 1 (mod 3). Hence 2n + n is a multiple of 3. Since it
is greater than 3, it is composite.
(A Liu)
3.	Let there be к families of mutually parallel planes such that planes
in different families are not parallel. The total number of planes in
any к — 1 families is 1999. Hence all families are of size n — 1999.
It follows that к — 1 is a divisor of 1999. Since 1999 is a prime,
either к = 2 and n = 3998, or к = 2000 and n = 2000.
(A Liu)
4.	Let A be the sum of the 50 larger numbers within the pairs, and
let В be the sum of the other 50 numbers. Then
A + В = 1 + 2 + •  • + 100 = 5050
while
А-В = 1 + 2H--------+ 50 = 1275.
Hence 2 A = 6325, which is a contradiction. It follows that the
division is impossible.
(A Liu)
Senior Solutions
115
5. The task is possible, as shown in the diagram below.
(A Liu)
116
TOURNAMENT 21
Autumn 1999 (A Level)
1-	If there are two successive numbers that are both even, then the
next number in the anti-clockwise order must be even too. Since
1 is an odd number, no two even numbers in the circle are next to
each other.
Also clearly no two even numbers in the circle can be separated by
exactly one odd number. Hence there is at most one even number
in the circle since otherwise the total number of odd numbers in
the circle would be at least two more than that of even numbers.
Thus n < 3.
Simple checking shows that n = 1, n — 3 is the answer to the
problem.
(A Liu)
2.	(a) Let Ai (i = 1,... ,n) be points in order lying on a straight
line I on a piece of paper. Let d be the smallest of AiA^i
(i = 1,... ,n — 1). Let PQ be a straight line perpendicular to
I such that it does not meet A±An and the distance between
Ai and PQ is d.
By folding the paper along lines perpendicular to I we can
make the edge of the paper be on the same side of PQ as Ai
without affecting the number of paper layers above and under
each of Ai. Then we fold the paper along the perpendicular
bisector of A1A2 and repeat the whole procedure n — 2 more
times.
(b) Let Ai, A2, A3 be three points on a piece of paper. Let
A1A2 < Ai A3 and the perpendicular bisector of A2A3 cut
Ai A3 in X. If the distance between Ai and A%X is d, let PQ
be a straight line parallel to A1A3 such that it is on the other
side of Ai A3 then A2 and the distance between Ai A3 and PQ
is d.
Then by folding the paper along lines parallel to A1A3 we can
make the edge of the paper be on the same side of PQ as
Ai A3 without affecting the number of paper layers above and
under each of Ai. Then we fold the paper along the perpendic-
ular bisector of A2A3, and after that along the perpendicular
bisector of A1A2.
If A1A2A3 is an equilateral triangle with height d, consider
an equilateral triangle PQR with height bd/3 such that the
Senior Solutions
117
centres of Ai Л2А3 and PQR coincide and their corresponding
sides are parallel.
Now fold the paper to make the edges of the paper to lie
strictly within PQR without affecting the number of paper
layers above and under each of Ai. Next fold the paper along
a line through the centre of A± A2A3 parallel to one of its sides
and then repeat the above procedure for a non-equilateral
triangle.
(A Liu)
3.	See solution to Problem 5 in Junior paper.
4.	(a) Follows immediately from (b) and from the fact that AT :
ТВ = AC : CB, where T is a point on AB such that CT
bisects angle ACB.
(b) Since К and L are the points of contact of the excircles with
the corresponding sides, AK = BL. Draw a parallelogram
ABXK. Let Y be the midpoint of XL, Z the midpoint of
KL and W the midpoint of AB.
Then YZ is parallel to XK and YZ = ^XK. But also BW
is parallel to XK and BW = ±XK. Hence BYZW is a
parallelogram.
Therefore WZ is parallel to BY. Since BX = BL, BY bisects
/.XBL. Hence WZ is parallel to the bisector of LACB.
(A Liu)
5.	(a) Let us colour all numbers from one group red and all numbers
from the other blue. A set of consecutive integers of the same
colour will be called a batch, if this set is not a subset of a
larger set of consecutive integers of the same colour.
Assume that there are at least three red batches. Let the
largest number in the batch with smallest red numbers be x
118
TOURNAMENT 21
and the smallest number in the batch with largest red numbers
be y. Then if we remove x, y, x + 1 and у — 1, the sums of
all numbers in each group will still be the same. Thus we can
assume that there are at most two batches of the same colour.
Also if there is a batch which contains at least two numbers
but neither 1 nor 100, then removing its smallest and largest
numbers a and 6, and removing numbers a — 1 and 6 + 1, we
obtain groups with equal sums. If we have one red batch and
two blue ones, then the red batch contains neither 1 nor n and
therefore contains only one number.
Since 1 + 2 + • • • + 100 = 5050, the red batch consists of
number 2525, which is not possible. Now we assume that we
have two red batches and two blue ones. Then without loss
of generality we assume that the sum of the red numbers is
(1+ ••• + &-1) +A;+ 1.
Hence
k(k — 1)
+ к + 1 = 2525,
which does not have integer solutions. Thus we have to con-
sider only the case when there is one red batch and one blue
batch. Then we have k(k + 1) = 5050 which has no integer
solutions.
(b) The answer is no.
Let n = 20, the first group consist of the numbers from 1
through 14 and the second group of the numbers from 15
through 20. It is easily seen that the sums of all numbers
in each group are equal, but when two numbers are removed
from each group the sums of the remaining numbers cannot
be equal.
(A Liu)
6. Let us place a point in the centre of each marked square and then
for every pair of these points join them if they belong to squares
sharing a side. Then we obtain a graph G. If there is a vertex V
in G of even index, we can construct (by removing edges only) a
subgraph F of G such that V is of the same index in F and F is a
tree.
Thus we have a vertex V connected to an even number of trees.
Since the total number of vertices in F is even, at least one of these
trees has an even number of vertices. Then we can cut F into two
subtrees with even number of vertices and use induction.
Senior Solutions
119
So we can. assume that each vertex of G has an odd index. Now
we assume that G has a cycle of length 4. Then we can obtain a
subgraph H of G such that there is one cycle of length 4 in H and
each vertex in this cycle is connected to one or two trees. If for one
of the vertices of this cycle, the graph formed by the vertex and
the connected trees contains even number of vertices, we can use
induction.
Otherwise we can consider two adjacent vertices of the cycle and
the trees connected to them and then use induction. Thus we can
assume that G does not have cycles of length 4 either. Clearly there
is only one graph that satisfies these two restrictions: n +1 vertices
on a straight line and n — 1 vertices alternately on different sides
of this straight line connected to the inner vertices on the line.
One can easily cut the corresponding figure into n rectangles: one
1 x (n + 1) rectangle and n — 1 small squares.
(A Liu)
7. Let V and E be the number of vertices and edges respectively of
a polyhedron with lOn faces. Then we have V — E + IQn = 2.
Clearly, ЗУ < 2E. Hence
E
10n > — + 2.
О
Let this polyhedron have ai faces with ki sides, < ... < krn,
i — 1,..., m. Then
uiAq T • • • T amkm 2E
and
a± + • • • + am = lOn.
Hence
a±ki T • • • + O'mkm o
ai + • • • + am > -------	H 2.
6
If m < 10, then it follows from cq H-|- am = lOn that ai > n for
at least one i, where i = 1,..., m.
Now assume that m > 10. Then
a^k\ + a^k^ + • • • + amkm > cq x 3 + П2 x 4 + • • • + am(rn + 2).
Hence
a± x 3 T • • • T am(m T 2)
a± + • • • + am >	-	|- 2,
6
120
TOURNAMENT 21
which implies
3ai + 2a2 + аз > a-5 + 2ae 4---h am(m — 4) + 12.
Since «1 + • • • + am = lOn, we have
fll + fl2 + 0-3 + 0-4 — 10n — CZ.5 — CLq — • • • — am.
Therefore
4oi + 3o2 + 2a3 + a4 > Юп + o6 4-----1- am(m - 5) + 12.
Hence
4dx T За2 T 2o3 -|- 04 > lOn,
which means that ai > n for at least one г, where i = 1,2, 3,4.
(A Liu)
Senior Solutions
121
Spring 2000 (0 Level)
Denote the area of a triangle T by [Т]. Let PC = uPA and PD =
vPB, where и and v are positive real numbers. Let [PAB] = 1.
Then
PC _
[PAB] ~ PA~U'
Similarly, [PAD] = v and [PCD] = uv. From the given condition
[PAB] + [PCD] = [PCB] + [PAD],
we have
0 = 1 +ud — u — u = (1 — u)(l — v).
Hence either и = 1 or v = 1. It follows that P is the midpoint of
either AC or BD.
(A Liu)
2. Exactly one of each pair of opposite faces of a unit cube is on the
surface of the 2x2x2 cube, so that each unit cube contributes
exactly 6 dots. Hence the total number of dots on the six faces of
the large cube is 48. Since six consecutive integers contain exactly
three odd numbers, their sum is odd and cannot be 48. Hence we
cannot obtain six consecutive numbers.
(A Liu)
3. We use induction on n. For n = 1, both sides reduce to 1, and the
inequality holds. Suppose it holds for some n > 1. Then
lfc + 2k + • • • + nk + (n + l)fc <	---— 1 + (n + l)fc.
nfc — (n — l)fe
To complete the induction argument, we must show that the right
side of the above inequality is less than
(n + l)2fc — nk
(n + l)fc — nk
122
TOURNAMENT 21
This is equivalent to
((n + l)2fc — nfc)(nfc — (n — l)fc)
-(n2fc-(n-l)fc)((n+l)fc-nfc)
—	(n + l)fc((n + l)fc — nk)(nk — (n — l)fc)
= nk(n + l)2fc — n2fc — (n + l)2fc(n — l)fc + nfc(n — l)fc
—	n2fc(n + l)fc + (n — l)fc(n + l)fc + n3fc — nfc(n — l)fc
-	nfc(n + l)2fc + n2fc(n + l)fc + (n - l)fc(n + l)2fc
-	nfc(n + l)fc(n - l)fc
= n3fc - n2fc - nfc(n + l)fc(n - l)fc + (n + l)k(n - l)k
= (nk - l)(n2fc - (n2 - l)fc)
> o.
(A Liu)
4. (a) Define ftion+i = (0.1)n+1 — 9 and = 1 otherwise. In every
ten consecutive terms, exactly one is negative and is greater
than —9 while the other nine are 1’s. Hence the sum of every
ten consecutive terms is positive. The sum of the first lOn
terms is
0.1 + (0.1)2 + --- + (0.1)n < 1
while aion+i < —8- Hence the sum of the first lOn + 1 terms
is negative for every n.
(b) Such a sequence does not exist. The sum of the lOn + 2-nd
to lOn + 11-th is positive and hence at least 1 for every n. In
order for the sum of the first lOn + 1 terms to be negative for
every n, we must have cq less than —n for every n. This is
clearly impossible.
(A Liu)
Senior Solutions
123
Spring 2000 (A Level)
1. Let d denote the greatest common divisor of 2000m+n and 2000n+
m. Then d divides
2000(2000m + n) - (2000n + m) = 3 999 999m.
Suppose some prime p divides both d and m. Then p must also
divide 2000m + n and hence n itself. Since m and n are relatively
prime, so are m and d. It follows that d divides 3999999, and
cannot be any larger.
It can be equal to 3 999999 by taking n = 1 and m = 3997999.
Indeed, 2000n + m = 3 999 999 while
2000m + n = 2000(3 999 999 - 2000) + 1 = 1999(3 999 999).
(A Liu)
Let O', M' and N' be the respective midpoints of AC, AK and
CK. They are also the respective projections on to AC of О, M
and N. Now
O'M' = O'A - M'A = O'C - M'K = O'C - О'К - O'M'
so that 20'M' = CK = 2KN'. Similarly, O"M" = KN", where
О", M" and N" are the respective projections of О, M and N on
to BD. It follows that OM = KN.
(A Liu)
3.	We use induction on the number n of cards in the deck. If n = 1,
Peter loses immediately if it is face-down, or loses after one step if
124
TOURNAMENT 21
it is face-up. Suppose Peter loses whenever the deck has n cards
for some n > 1. Consider a deck with n + 1 cards.
If the top card is face-down, it remains face-down through the game,
which is then played as though it is not there. By the induction
hypothesis, Peter must lose.
Suppose the top card is face-up. If after any step, it becomes face-
down, the desired conclusion can be drawn as before.
We claim that it must become face-down eventually. If this does
not happen, again the game can be played as though it is not there.
By the induction hypothesis, all other cards will become face-down.
At this point, Peter will be forced to turn over the top card, and
loses the game.
(A Liu)
4.	The polygon can be divided into horizontal strips by lines of the
form у = n, where n is an integer. The top strip and the bottom
strips are triangles while the remaining ones are quadrilaterals.
Each quadrilateral can be divided into two triangles. Now each
horizontal segment inside the polygon is the base of two triangles
of height 1.
It follows that the total length of these segments is equal to the
area of the polygon. Similarly, the total length of the segments of
the lines x = m, m an integer, inside the polygon is equal to the
area of the polygon also. Thus the two total lengths are the same.
(A Liu)
5.	In running through a sequence of consecutive positive integers, the
digit-sum changes by 1, so that its parity alternates. The only ex-
ception is when the units-digit changes from 9 to 0. If the carrying
stops at the tens-digit, then the parity of the digit-sum will not
change.
If the carrying spills over to the hundreds-digit but not to the
thousands-digit, then the parity of the digit-sum will change, and
so on. In any case, in two consecutive changes of the units-digit
from 9 to 0, the parity of the digit-sum cannot change both times.
In order for the digit-sums of N consecutive positive integers to be
divisible by the first N positive integers respectively, those digit-
sums must alternate in parity except possibly the first one since 1
divides any number.
Senior Solutions
125
It follows that we can have at most two changes of the units-digit
from 9 to 0, the first one occurring at the beginning of the sequence
without any change in the parity of the digit-sum. Thus TV < 21.
The following table shows 21 consecutive positive integers whose
digit-sums are divisible by the first 21 positive integers respectively.
Positive Integer		Digit-sum	Divisor
479 ••	•989	27730	1
479	•990	27722	2
479-	•991	27723	3
479-	••998	27730	10
479 ••	•999	27731	11
480 ••	•000	12	12
480-	••001	13	13
480-	••008	20	20
480-	•009	21	21
(A Liu)
6.
(a) First suppose that the tournament has 2n players, with a total
of n(2n —
. 2n — 1
1S 2 ’
n(2n — 1)
2
1) games played. The average score of each player
so that the top n players have among them at least
n(n — 1)
points. Since they score exactly ----------- against
one another, they score against the bottom n players at least
n(2n — 1) n(n — 1) _ n2
2	2	“ T
points.
These points are scored in games which cannot be upsets. It
follows that the fraction of non-upsets is at least
n2 1
2n(2n - 1) > 4’
so that the fraction of upsets is less than |.
Suppose now that the tournament has 2n+l players, with a to-
tal of n(2n+l) games played. The average score of each player
is n points, so that the top n + 1 players have among them
126
TOURNAMENT 21
at least n(n + 1) points. Since they score exactly	—-
points against one another, they score against the bottom n
players at least
.	.. n(n +1) n(n +1)
k 7	2	2
points. These points are scored in games which cannot be
upsets. It follows that the fraction of non-upsets is greater
than
n(n + l) 1
2n(2n +1) > 4’
so that the fraction of upsets is less than
(b) Let there be 4n2 + 6n + 1 players, with a total of
n(2n + 3)(4n2 + 6n + 1)
games played.
Divide the players into groups labeled A±, A%,..., А2П+1 and
B, with 2n +1 players in each Ai and 2n players in B. Within
each Ai, every player scores exactly n points.
The internal scores of В are irrelevant and can be arbitrarily
assigned. For 1 < i < 2n + 1, each player in Ai beats exactly
2n +1 — i players in В, every player in Ai+j for n +1 < j <2n
but loses to every player in Ai+j for 1 < j < n, where the
subscript is reduced by 2n + 1 if it exceeds 2n + 1.
This means that a player in Ai has a higher score than a player
in Aj if and only if i < j. For 2 < i < n + 1, the players in Ai
beat the players in Aj for 1 < j < i — 1, resulting in
..	_.9 n(n + l)(2n +1)2
(I + 2 + • • • + n)(2n + I)2 = k
upsets.
For n + 2<z<2n+l, the players in Ai beat the players in
Aj for i — n < j < i — I, resulting in n2(2n + I)2 upsets.
Thus the total number of upsets is at least
n(n + l)(2n + I)2	2 n2 _ n(3n + l)(2n + I)2
and the fraction of upsets is at least
(3n + l)(2n + l)2
2(2n + 3)(4n2 + 6n+l) ‘
Senior Solutions
127
Since the limiting value of this fraction is | as n approaches
infinity, we cannot replace | by any smaller number.
(A Liu)
TOURNAMENT 22

TOURNAMENT 22
JUNIOR QUESTIONS
Autumn 2000 (0 Level)
1.	Each of the 16 squares in a 4 x 4 table contains a number. For any
square, the sum of the numbers in the squares sharing a common
side with the chosen square is equal to 1. Determine the sum of all
16 numbers in the table.	(R Zhenodarov, 3 points)
2.	ABCD is parallelogram, M is the midpoint of side CD and H is
the foot of the perpendicular from В to line AM. Prove that BCH
is an isosceles triangle.	(M Volchkevich, 3 points)
3.	(a) On a blackboard are written 100 different numbers. Prove
that you can choose 8 of them so that their average value is
not equal to that of any 9 of the numbers on the blackboard.
(2 points)
(b) On a blackboard are written 100 integers. For any 8 of them,
you can find 9 numbers on the blackboard so that the average
value of the 8 numbers is equal to that of the 9. Prove that
all the numbers on the blackboard are equal.
(A Shapovalov, 4 points)
4.	Among a set of 32 coins, all identical in appearance, 30 are real
and 2 are fake. Any two real coins have the same weight. The fake
coins have the same weight, which is different from the weight of
a real coin. How can one divide the coins into two groups of equal
total weight by using a balance at most 4 times?
(A Shapovalov, 5 points)
132
TOURNAMENT 22
Autumn 2000 (A Level)
1.	Each lxl square of an n x n table contains a different number. The
smallest number in each row is marked, and these marked numbers
are in different columns. Then the smallest number in each column
is marked, and these marked numbers are in different rows. Prove
that the two sets of marked numbers are identical.
(V Klepcyn, 3 points)
2.	In triangle ABC, AB = AC. A line is drawn through A parallel to
BC. Outside triangle ABC, a circle is drawn tangent to this line,
to the line BC, to AB and to the incircle of ABC. If the radius of
this circle is 1, determine the inradius of ABC.
(RK Gordin, 3 points)
3.	The least common multiple of positive integers a, b, c and d is
equal to a + b + c + d. Prove that abed is divisible by at least one
of 3 and 5.	(V Senderov, 4 points)
4.	In how many ways can 31 squares be marked on an 8 x 8 chessboard
so that no two of the marked squares have a common side?
(R Zhenodarov, 4 points)
5.	A weight of 11111 grams is placed in the left pan of a balance.
Weights are added one at a time, the first weighing 1 gram, and
each subsequent one weighing twice as much as the preceding one.
Each weight may be added to either pan. After a while, equilibrium
is achieved. Is the 16 gram weight placed in the left pan or the right
pan?	(AV Kalinin, 6 points)
6.	In the spring round of the Tournament of Towns this year, 6 prob-
lems were posed in the Senior А-Level paper. In a certain coun-
try, each problem was solved by exactly 1000 participants, but no
two participants solved all 6 problems between them. What is the
smallest possible number of participants from this country in the
spring round Senior А-Level paper? (R Zhenodarov, 7 points)
7.	A student has 100 cards on which the integers 1 to 100 are printed,
as well as a sufficiently large number of cards on which the symbols
+ and = are printed. What is the maximal number of correct
equalities the student can construct, if each card is used at most
once?	(R Zhenodarov, 8 points)
Junior Questions
133
Spring 2001 (0 Level)
1.	We may replace the positive integer n by the product a x b where
a and b are positive integers such that a + b = n. Can 2001 be
obtained from 22 by a sequence of such replacements?
(V Klepcyn, 3 points)
2.	Let D, E and F be the midpoints of В C. CA and AB respectively.
If one of DE, EF and FD is longer than one of AD, BE and CF,
prove that ABC is an obtuse triangle.
(A Shapovalov, 4 points)
3.	Twenty kilograms of cheese were on sale in a food store, and cus-
tomers queued up to buy some of it. For each of the first ten
customers, after he/she had made his/her purchase, the sales girl
announced, “If everyone buys an amount equal to the average
amount bought by customers already served, then there is just
enough cheese left for ten more customers.” Could she be right,
and if so, how much cheese was left after the first ten customers
had made their purchases?	(IG Rybnikov, 4 points)
4.	There are five identical paper triangles on a table. Each may be
slid in any direction parallel to itself without rotation.
(a)	Is it true that any one of them can be covered by the other
four?	(2 points)
(b)	Prove that any one of them can be covered by the other four
if the triangle is equilateral. (A Shapovalov, 3 points)
5.	15 counters are placed on a 15 x 15 board so that no two counters
are in the same row or column. Then each of the counters is moved
either two cells horizontally and one cell vertically or two cells
vertically and one cell horizontally. Prove that after this is done,
one can always find a row or a column containing at least two
counters.	(S Berlov, 5 points)
134
TOURNAMENT 22
Spring 2001 (A Level)
1.	In a certain company, 10% of the employees get 90% of the total
salary. The company consists of several branches. Is it possible
that in each branch, the total salary of any 10% of the employees
is at most 11% of the total salary paid in this branch?
(M Vyalyi, 3 points)
2.	There are three piles of stones, with 51, 49 and 5 stones respec-
tively. In a move, any two piles may be combined into one pile.
Alternatively, any pile with an even number of stones may be di-
vided into two equal piles. Is it possible to obtain 105 piles with 1
stone in each after a sequence of such moves?
(V Klepcyn, 5 points)
3.	The point A lies inside /.KMN. The points В and C lie respec-
tively on KM and MN. If LCBM = LABK and LBCM =
/ACN, prove that the circumcentre of triangle BCM lies on the
line AM.	(A Zaslavskiy, 5 points)
4.	A convex polygon is divided into triangles by diagonals which do
not intersect except at the vertices of the polygon. Each vertex
is labelled with the number of triangles to which it belongs. Is it
possible to reconstruct all the diagonals using these numbers if the
diagonals are erased?	(S Zaicev, 5 points)
5.	A black pawn and a white pawn are placed on a chessboard. In
each move, one of the pawns goes to an adjacent vacant square
of the chessboard either vertically or horizontally. It is desired to
construct a sequence of moves so that every possible position of the
two pawns on the chessboard will appear exactly once.
(a)	Is this possible if the pawns must be moved alternately?
(3 points)
(b)	Is this possible if the pawns need not be moved alternately?
(A Shapovalov, 4 points)
6.	AD, BE and CF are the altitudes of triangle ABC. К, M and N
are the respective orthocentres of triangles AEF, BFD and CDE.
Prove that KMN and DEF are congruent triangles.
(A Akopian, 7 points)
JuniorQuestions
135
7.	Alex picks an integer greater than 9 and less than 100. Gregory is
trying to guess this integer by naming its two digits. If the integer
named by Gregory is correct, or if one digit is correct and the other
differs from its correct value by one, Alex will say “hot”; otherwise
he will say “cold”. For example, if the number 65 is the one picked
by Alex, then the answer is “hot” if and only if Gregory names 65,
64, 66, 55 or 75.
(a)	Prove that Gregory has no strategy guaranteeing that he will
deduce Alex’s integer in at most 18 attempts. (2 points)
(b)	Find a strategy for Gregory to deduce Alex’s integer, regard-
less of what it is, using at most 24 attempts. (3 points)
(c)	Is there a strategy for Gregory to do so in at most 22 attempts?
(Folklore, 3 points)
136
TOURNAMENT 22
SENIOR QUESTIONS
Autumn 2000 (0 Level)
1.	Triangle ABC is inscribed in a circle. Chords AM and AN inter-
sect side ВC at points К and L respectively. Prove that if a circle
passes through all of the points K, L, M and N, then ABC is an
isosceles triangle.	(V Zhgun, 3 points)
2.	Positive integers a, b, c, d satisfy the inequality ad — be > 1. Prove
that at least one of the numbers a, b, c, d is not divisible by ad—be.
(A Spivak, 3 points)
3.	In each lateral face of a pentagonal prism at least one of the four
angles is equal to f. Find all possible values of f.
(A Shapovalov, 4 points)
4.	Among a set of 2N coins, all identical in appearance, 2N — 2 are
real and 2 are fake. Any two real coins have the same weight. The
fake coins have the same weight, which is different from the weight
of a real coin. How can one divide the coins into two groups of
equal total weight by using a balance at most 4 times, if
(a)	N = 16;
(b)	N = 11?
(3 points)
(A Shapovalov, 2 points)
Senior Questions
137
Autumn 2000 (A Level)
1.	The least common multiple of positive integers a, b, c and d is
equal to a + b + c + d. Prove that abed is divisible by at least one
of 3 and 5.	(V Senderov, 3 points)
2.	What is the largest integer n such that one can find n points on the
surface of a cube, not all lying on one face and being the vertices
of a regular n-gon?	(A Shapovalov, 4 points)
3.	In a triangle ABC, AB — с, ВС = a, CA = b, and a < b < c.
Points Bf and A' are chosen on the rays BC and AC respectively
so that BB' = AA' = c. Points C" and B" are chosen on the
rays CA and BA so that CC" = BB" = a. Find the ratio of the
segment A'B' to the segment С"B". (R Zhenodarov, 4 points)
4.	Let ai,a2,    ,an be non-zero integers that satisfy the equation
a 2 H--------------------
аз +
1
Г
an H—
x
for all values of x for which the lefthand side of the equation makes
sense.
(a)	Prove that n is even.	(3 points)
(b)	What is the smallest n for which such numbers cq, a?,   , an
exist?	(M Skopenkov, 4 points)
5.	Each of the cells of an m x n table is coloured either black or white.
For each cell, the total number of the cells which are in the same
row or in the same column and of the same colour as this cell is
strictly less than the total number of the cells which are in the
same row or in the same column and of the other colour as this
cell. Prove that in each row and in each column the number of
white cells is the same as the number of black ones.
(A Shapovalov, 6 points)
138
TOURNAMENT 22
6.	(a) Several black squares of side 1 cm are nailed to a white plane
with a nail of thickness 0.1 cm so that they form a black
polygon. Can it happen that the perimeter of this polygon is
1 km long? (The nail is not allowed to touch the boundary of
any of the squares.)	(5 points)
(b) The same problem as in (a) but with a nail of thickness 0 (a
point).	(5 points)
(c) Several black squares of side 1 cm lie on a white plane so that
they form a black polygon (possibly having more than one
piece and/or having holes). Can it happen that the ratio of its
perimeter (in centimetres) to its area (in square centimetres)
is more than 100000?	(Hungarian Folklore, 5 points)
Senior Questions
139
Spring 2001 (0 Level)
1.	At 12:20 pm, a bus leaves on a 100-kilometre route. It is equipped
with a computer, which makes the following announcement at 1:00
pm, 2:00 pm, 3:00 pm, 4:00 pm, 5:00 pm and 6:00 pm: “Assuming
that the average speed for the remaining part of the route is the
same as that in the part already covered, the bus will arrive at its
destination in another hour.” Can it be right, and if so, how many
kilometers has the bus covered at 6 pm? (IG Rybnikov, 3 points)
2.	The cube of an n-digit number has m digits. Is n + m = 2001
possible?	(G Galperin, 4 points)
3.	In triangle ABC, X is a point on AB and У is a point on BC. The
segments AY and CX intersect at Z. If AY = YC and AB — ZC,
prove that the points В, X, Z and Y lie on a circle.
(R Zhenodarov, 4 points)
4.	On a 3 x 100 board, two players alternately place dominoes. The
first player places them as 1 x 2 rectangles while the second places
them as 2 x 1 rectangles. The loser is the one who cannot make
a move. Which player can force a win, and what is the winning
strategy?	(V Trushkov, 5 points)
5.	Nine points are drawn on the surface of a regular tetrahedron of
edge 1 centimetre.
Prove that among these points there are two such that the distance
in space between them is at most 5 millimetres.
(V Proizvolov, 5 points)
140
TOURNAMENT 22
Spring 2001 (A Level)
1.	Find a polynomial P(x) of degree 2001 such that P(x) +P(1 — x) =
1 for all real numbers x.	(Folklore, 3 points)
2.	In a class with at least 5 students, each subject taken by a student
results in pass or failure. For any arbitrarily chosen group of no
less than 5 students, at least 80% of the failures received by this
group are given to at most 20% of the students in the group. Prove
that at least 75% of all the failures in this class are given to one
student.	(M Vyalyi, 5 points)
3.	AD, BE and CF are the altitudes of triangle ABC. К, M and N
are the respective orthocentres of triangles AEF, BFD and CDE.
Prove that KMN and DEF are congruent triangles.
(A Akopian, 5 points)
4.	Each entry in two m x n tables A and В is either 0 or 1. The number
of Is in A is equal to the number of Is in B. In both A and B, the
numbers do not decrease from the left to the right in any row, nor
from top to bottom in any column. For every к, 1 < к < m, the
sum of the entries in the top к rows of A is not less than the sum
of entries in the top к rows of B. Prove that for any £, 1 < £ < n,
the sum of the numbers in the leftmost I columns of В is at least
the sum of the numbers in the leftmost £ columns of A.
(A Kanel, 5 points)
5.	In a chess tournament, every participant played with the others
exactly once, getting 1 point for a win, | for a draw and 0 for a
loss. For each player, the sum of the points earned by the players
who were beaten by this player was computed, as was the sum of
the points earned by the players who beat this player.
(a)	Is it possible for the first sum to be greater than the second
one for every player?	(4 points)
(b)	Is it possible for the first sum to be less than the second one
for every player?	(AK Tolpygo, 4 points)
6.	Prove that there exist 2001 convex polyhedra such that any three
of them do not have any common points, and any two of them have
at least one common boundary point but no common inner points.
(A Kanel, 8 points)
Senior Questions
141
7.	Several boxes are placed along a circle. Each box may contain any
number of chips, including zero. A move consists of taking all the
chips from some box and placing them in the subsequent boxes
clockwise, one chip in every box, beginning from the next box in
the clockwise direction.
(a)	Suppose that in each move after the first one, one must take
the chips from the box in which the last chip was placed on
the previous move. Prove that after several moves, the initial
distribution of the chips among the boxes will reappear.
(4 points)
(b)	Suppose that in each move, one may take the chips from any
box. Is it true that for every initial distribution of the chips,
one can get any possible distribution by performing an appro-
priate sequence of moves?
(V Gurovic, 4 points)
142
TOURNAMENT 22
JUNIOR SOLUTIONS
Autumn 2000 (0 Level)
1.	In the diagram on the left, each white square is the neighbour of
exactly one of the three black squares with arrows pointing out-
wards. Hence the sum of the numbers in the white squares is 3.
By symmetry, so is that in the black squares, yielding a total of 6.
This can be achieved as shown in the diagram on the right, where
w, ж, у and z are numbers such that w + у = 1 and x + z = 1.
	
T	
a :::::::::	TT7 ::r.<
	:::::::::: T
w	z	У	X
X	0	0	w
У	0	0	z
z	w	X	У
(A Liu)
2.	Alternative 1
Let the extension of AM and В C meet at N. Since AD is parallel
to CN, ШAD = LMNC.
Since LAMD = ШМС and MD = MC, triangles MAD and
MNC are congruent, so that CN = DA = CB.
Junior Solutions
143
Since /.BHN = 90°, H lies on the circle with diameter BN which
has centre C. Hence CH = CB.	(A Liu)
Alternative 2
Let N be the midpoint of AB and let CN cut BH at G. Now
MC is parallel to AN. Moreover, MC = ^CD = ^AB = AN.
Hence AMCN is a parallelogram, so that AM is parallel to CN.
It follows that G is the midpoint of BH, and CG is perpendicular
to BH. Hence triangles BCG and HCG are congruent, so that
BC = HC.
(A Zhou)
3.	(a) The average of the largest eight numbers must exceed the
average of any nine of the numbers.
(b) Raising or reducing each number by the same amount has no
effect on the comparison of averages. Hence we may assume
that the smallest of the 100 integers is 0. Now the average of
the smallest 8 numbers must be equal to the average of the
smallest 9 numbers.
It follows that the smallest 9 numbers are all Os. Let x be any
of the 100 numbers. Then the average of 7 copies of 0 and
x is equal to the average of 9 other numbers whose sum we
denote by y. Then 9x = 8y, which implies that x is divisible
by 8. Since x is arbitrarily chosen, every number is divisible
by 8. Hence у is also divisible by 8.
Now 9x = 8y implies that x must be divisible by 82. Continu-
ing this way, we see that x is divisible by 8n for every positive
integer n. This is only possible if x is 0.
Since x is arbitrarily chosen, all numbers are 0, and therefore
equal to one another.
(A Liu)
144
TOURNAMENT 22
4.	More generally, we prove that the task can be accomplished in n
weighings if the total number of coins is 2n+1. Label each coin with
a binary number from 0 to 2n+1 — 1 and fill in the leading Os so
that each is an n + 1-digit number. In the г-th weighing, put a coin
in the left pan if its г-th digit from the left is 0, and in the right
pan if it is 1.
There will always be 2n coins in each pan. If equilibrium is achieved
in any of these n weighings, the task is accomplished. If not, the
two fake coins are always in the same pan. This means that their
binary labels are identical except for the last digit. The task can
now be accomplished by putting in one group all coins whose last
digits are Os, and in another group those whose last digits are Is.
(A Liu)
Junior Solutions
145
Autumn 2000 (A Level)
1.	Note that permutations of the rows or the columns of the table
do not affect the conclusion of the problem. After the row scan,
permute the rows and columns so that the marked numbers appear
in ascending order along the main diagonal.
In particular, the smallest number in the table is now at the top
left corner. Now perform the column scan. Suppose not all the
marked numbers are on the main diagonal. Let the J-th column
be the first one for which the marked number у is on the г-th row
where i j. We must have i > j as otherwise the г-th row would
contain two marked numbers.
Let the j-th number along the main diagonal be x and the г-th one
be z. Since у is the marked square of the 7-th column, we have
x > y. We must also have у > z as we mark z rather than у when
scanning the ith row.
Hence x > z, but this contradicts the fact that the numbers on the
main diagonal are in ascending order.
(A Liu)
2.	Let О be the centre of the larger circle and let this circle be tangent
to BC at S. Let T be the point of common tangency of the two
circles, and let I be the incentre of triangle ABC. Since AB = AC,
I lies on the altitude AD and D is also the point of tangency of
the incircle with BC.
Extend OI to meet BC at E. Let the inradius of ABC be r. Since
OS = 1, AD = 2.
Triangles BAD and BET are congruent since LABD — LEBT,
LADB = 90° = LETB and BD = ВТ. Hence ET = 2 and
El = 2-r.
146
TOURNAMENT 22
Now triangles SOE and DIE are similar. Hence
_ ID _ IE _ 2 - r
Г ~ OS ~ OE~ 3 ‘
It follows that r =
(A Liu)
3.	Alternative 1
We may assume that no prime number divides each of a, b, c and
d. Let a + b + c + d = L. Since L is their least common multiple,
there exist positive integers w, x, у and z such that aw = bx =
cy = dz = L.
It follows that L is also the least common multiple of w, x, у and
z. Moreover,
We may assume that w < x < у < z. The largest value of w is 4,
and this forces ж, у and z to be 4 also, so that a = b = c = d=l.
However, L = 4 is not their least common multiple.
Suppose w = 3 and x = 3. The largest value of у is 6, and this
forces z to be 6 also, so that a = b = 2 and c = d — 1. However,
L = 6 is not their least common multiple. If у = 5, then z is not
an integer. Now у = 4 forces z = 12, so that a = 6 = 4, c = 3 and
d = 1. Indeed, L = 12 is their least common multiple, and it is
divisible by 3. If у = 3, then
already. It follows that there are no more solutions with w = 3.
For w = 2, similar analysis yields the following solutions.
(w, ж, y, z)	L	(a, b, c, d)	Remarks
(2,6,6,6)	6	(3,1,1,1)	L not l.c.m.
(2,5,5,10)	10	(5,2,2,1)	L divisible by 5
(2,4,8,8)	8	(4,2,1,1)	L not l.c.m.
(2,4,6,12)	12	(6,3,2,1)	L not l.c.m.
(2,4,5,20)	20	(10,5,4,1)	L divisible by 5
(2,3,12,12)	12	(6,4,1,1)	L divisible by 3
(2,3,9,18)	18	(9,6,2,1)	L divisible by 3
(2,3,8,24)	24	(12,8,3,1)	L divisible by 3
(2,3,7,42)	42	(21,14,6,1)	L divisible by 3
Junior Solutions
147
In each acceptable case, L is indeed divisible by 3 or 5.
(A Liu)
Alternative 2
We may assume that a > b > c > d and denote their least common
multiple by L. Suppose abed is not divisible by either 3 or 5. Then
the same is true for L, so that each of a, b. c and d comes from y,
y, j, .... Suppose ft < y. Then
L
L — a+b+c+d< 4— = L.
~ 4
This implies that a = b = c — d = ^, but their least common
multiple would not have been L. Hence a = y. We cannot have
b — у also as otherwise c = d — 0. Suppose b < y. Then
T ,	, L	L	13L
L — a+b+c+d< — + 3 — —	< L,
2	7	14
a contradiction. Hence b = у. We cannot have с = у as otherwise
d = 0.
Suppose c < y. Then
T	,	L	L	L	т
L — a + b + c + d < — H—— + 2— — L.
2	4	8
This implies that
a = 2b — 4c = 4d = —,
2
but their least common multiple would not have been L. Hence
c = y. Now
,	1	1	lx	3L
v 2	4	7'	28
and is not a divisor of L. This contradiction shows that abed must
be divisible by either 3 or 5.
(M Holmes)
4.	The answer is 68.
Each row can contain at most 4 marked squares. Hence seven of
the rows contain exactly 4 marked squares each while the eighth
contains 3. Whenever two adjacent rows contain 4 marked squares
each, these 8 marked squares must follow the checkered pattern in
the standard checkerboard.
148
TOURNAMENT 22
We may assume that the exceptional row is in the top half of the
checkerboard, and that the bottom left corner square is marked.
Suppose the first row contains 3 marked squares, then the locations
of the marked squares in the remaining rows are fixed. This forces
the 3 marked squares in the first row to be chosen from 4 positions,
yielding 4 patterns. This is also the case if there are 3 marked
squares in the third or fourth row. If the second row has 3 marked
squares, we have a fifth pattern if the rightmost position for a
marked square in the second row is not used, so that the rightmost
marked square in the first row can be shifted one place to the right.
It follows that the total number of patterns is (4+5+4+4)x2x2 =
68, since the bottom left corner square could have been unmarked,
and the deficient row could have been in the bottom half of the
checkerboard.
(A Liu)
5.	Since
1 + 2 + • • • + 212 = 213 - 1 = 8191 < 11111,
equilibrium cannot be achieved before the 8192 gram weight is
added. At that point, the total weight is
8191 + 8192 + 11111 = 27494
grams. If equilibrium is achieved, each pan carries a weight of
13747 grams. Apart from the 11111 gram weight, the combined
weight of the others in the left pan is 13747 — 11111 = 2636 grams.
Now
2636 = 211 + 29 + 26 + 23 + 22.
This leads to the only way in which equilibrium may be achieved
with these weights, and the 16 gram weight is in the right pan. The
next weight we can add weighs 16384 grams. Now the total weight
is 27494 + 16384 = 43878 grams. If equilibrium is achieved, each
pan carries a weight of 21939 grams.
Thus the 16384 gram weight must be in the right pan and the 8192
gram weight in the left pan. However, by removing the 16384 gram
weight and transferring the 8192 gram weight from the left pan to
the right pan, we have the same situation as before. It follows that
no matter how many more weights are added, equilibrium can only
be achieved with the 16 gram weight in the right pan.
(A Liu)
Junior Solutions
149
6.	The answer is 2000.
Since no two students solved all six problems between them, each
individual student solved at most four problems. Suppose some
student did solve four problems. Then no other student solved
both of the remaining problems. Since each of these two problems
was solved by 1000 students, the total number of students would
be at least 2001.
On the other hand, 6 x 1000 = 6000 correct solutions were submit-
ted altogether. If each student solved at most 3 problems, then the
total number of students was at least 6000 4- 3 = 2000. We now
show that the minimum could be 2000. Let there be ten groups of
200 students. Students in the same group solved the same three
problems, and among the groups, they were (1,2,3), (2,3,4), (3,4,5),
(4,5,1), (5,1,2), (1,3,6), (3,5,6), (5,2,6), (2,4,6) and (4,1,6). It is easy
to verify that each problem was solved by exactly 1000 students,
and no two students solved all six problems between them.
(A Liu)
7.	The answer is 33.
Since each equation uses up at least 3 numbers, we can have at most
33 equations. This is attainable as shown below. The number 24
is not used.
1+97=98
5+89=94
9+81=90
13+73=86
17+65=82
21+57=78
25+49=74
29+41=70
3+96=99
7+88=95
11+80=91
15+72=87
19+64=83
23+56=79
27+48=75
31+40=71
2+43=45
6+47=53
10+51=61
14+55=69
18+59=77
22+63=85
26+67=93
33+35=68
37+39=76
4+46=50
12+42=54
20+38=58
28+34=62
36+30=66
8+44=52
16+84=100
32+60=92
(A Liu)
Alternatively, we can form 33 equations as follows. For 0 < к < 16,
we have (2k + 1) + (83 — fc) = 84 + k. These use up all the odd
numbers from 1 to 33 inclusive, as well as the numbers from 67 to
100 inclusive. For 1 < к < 16, we have 2k + (50 — fc) = 50 + k.
These use up all the even numbers from 2 to 32 inclusive, as well
as the numbers from 34 to 66 inclusive except 50.
(RB Leigh)
150
TOURNAMENT 22
Spring 2001 (О Level)
1.	The answer is yes.
Working backwards, we see that 2001 = 3 x 667 can be obtained
from 3+667=670, that 670 = 10x67 can be obtained from 10+67 =
77 and that 77 = 7 x 11 can be obtained from 7+11=18. From any
n = 1 + (n — 1), we can obtain n — 1 = l(n — 1). Hence starting
from 22, we can obtain in succession 21, 20, 19, 18, 77, 670 and
2001.
(A Liu)
2.	Suppose first that EF is longer than AD. Let G be the point of
intersection of AD and EF. Then AG < EG = FG.
Hence LGAE > LGEA and LGAF > LG FA. Since the sum of
these four angles is 180°, LCAB = LGAE + LGAF > 90°.
Suppose now that EF is longer than BE. Then
LABC > LEBF > LEFB = LFAE + LFEA = LCAB + LBCA.
Hence LABC > 90°. All other cases are equivalent to either of
these two.
(A Liu)
3.	The sales girl can be right if the first к customers buy of the
cheese for 1 < к < 10. After the fc-th purchase, the average amount
sold to each customer so far is of the cheese, and 1(^fc of it
remains. Thus there is just enough for ten more customers. Note
that the fc-th customer buys
к к -1 _	10
10 + fc - 9 + fc “ (10 + fc)(9 + fc)
Junior Solutions
151
of the cheese, and these quantites are all positive. After the 10-th
purchase, 10^10 = | of the cheese has been sold, meaning that ten
kilograms are left.
(A Liu)
4.	(a) The answer is no.
Let ABC be a triangle where В is very close to the mid-
point of CA. Rotate this triangle about C through angles of
72°, 144°, 216° and 288°, obtaining four other triangles con-
gruent to it. Since each can cover a very small portion of the
long side of any of the other triangles, none can be covered by
the other four by translation only.
(b) Divide the chosen equilateral triangle into four small equilat-
eral triangles by segments joining the midpoints of its sides.
The circumcircle of the small triangle in the middle coincides
with the incircle of the large triangle. We now slide each of
the other four large triangles so that the incircle of each coin-
cides with the circumcircle of a different one of the four small
triangles. Then the chosen triangle is completely covered by
the other four.
(A Liu)
5.	Record the row numbers and column numbers of each counter.
Then the row numbers are all distinct, as are the column numbers.
Therefore, among these 30 numbers, 16 are odd and 14 are even.
When a counter is moved, either its row number changes by 1 and
its column number changes by 2, or vice versa. In all, 15 of the
30 numbers preserve their parity while the remaining 15 change
theirs. Thus it is not possible to have 16 odd and 14 even numbers
among them after the moves. This means that two of the counters
must attack each other.
(A Liu)
152
TOURNAMENT 22
Spring 2001 (A Level)
1.	The answer is yes.
Let the company have two branches with a total of 100 employees.
The first branch consists of 10% of all the employees but receiving
90% of the total salary. The second branch consists of the remain-
ing 90% of the employees receiving the remaining 10% of the total
salary.
Within each branch, all employees have equal pay. Then 90% of
the total salary does go to 10% of the employees, and yet in each
branch, any 10% of the employees get exactly 10% of the total
salary paid in that branch.
(A Liu)
2.	The answer is no.
Since all three piles initially contain odd numbers of stones, the first
move must be a merge. If we merge the piles with 5 and 49 stones,
then we have two piles in each of which the number of stones is a
multiple of 3.
We claim that from now on, the number of stones in any pile must
be a multiple of 3. Since 1 is not a multiple of 3, not even 1 pile
with 1 stone can be obtained.
Note that the merger of two piles of stones each with a number of
stones equal to a multiple of 3 will result in one pile with a number
of stones equal to a multiple of 3.
Splitting of a pile with an even number of stones does not change
this property. Thus the claim is justified. Similarly, if we begin by
merging the piles with 5 and 51 stones, then the number of stones
in every subsequent pile must be a multiple of 7.
If we begin by merging the piles with 49 and 51 stones, then the
number of stones in every subsequent pile must be a multiple of 5.
It follows that we cannot get 105 piles each with 1 stone.
(A Liu)
3.	The result is trivial if MB = MC. Hence we assume that MB <
MC. Let D be the point on the circumcircle of triangle MBC such
that MB — MD.
Then LACN = /.BCM = /DCM, so that A, C and D are
collinear.
Junior Solutions
153
Now
LMDC = LCBK
= LCBA + LABK
= ACBA + ШВС
= ШВА.
Moreover, this angle is obtuse. Since MD = MB and AM =
AM. triangles MAD and MAB are congruent. By symmetry, the
circumcentre of triangle MBC lies on AM.
(A Liu)
4.	The answer is yes.
We use induction on the number n of sides of the convex polygon.
For n = 3, we have a trivial reconstruction. Suppose reconstruction
is possible for some n > 3. Consider an (n + l)-gon with erased
diagonals. At least one vertex must belong to a single triangle and
is labelled 1. Draw the diagonal connecting its two neighbours.
The remaining part is then a convex n-gon, with labels suitably
adjusted, and reconstruction can be continued by the induction
hypothesis.
(A Liu)
5.	(a) This is impossible. For any position of the black pawn, there
are 63 possible positions for the white pawn. Since the pawns
move alternately, each visit of the black pawn to this square
accounts for 2 of the 63 possible positions for the white pawn.
Since 63 is odd, this means that the black pawn must either
end its moves there or begin there. It is clearly not possible
for the black pawn to do so in every square.
154
TOURNAMENT 22
(b) This is still impossible. Define a position as even if both pawns
are on squares of the same colour, and odd otherwise. Even
if alternate moves are not required, the positions must nec-
essarily be alternately odd and even. The number of even
positions is 2(322) = 992 while the number of odd positions
is 322 = 1024. If all even positions appear, then some odd
positions must appear more than once.
(A Liu)
6. Let H be the orthocentre of triangle ABC.
Note that FM and HD are both perpendicular to BC. Hence they
are parallel to each other. Similarly, so are FH and MD. It follows
that DHFM is a parallelogram. Similarly, so is DHEN. Hence
FM = EN and they are parallel to each other. It follows that
EFMN is also a parallelogram, so that EF = NM. Similarly,
we have FD = KN and DE = MK. Hence triangles DEF and
KMN are congruent.
(A Liu)
7. (a) Since each guess covers at most 5 numbers, it takes at least
18 guesses to cover all 90 numbers, even if this can be done
with no overlap. However, if all answers other than the last
one are “cold”, there are no more guess to nail down the exact
number.
(b) We represent the 90 numbers by a 9 x 10 grid, which is parti-
tioned into 18 crosses, some incomplete, along with 8 isolated
squares. These squares represent the numbers 10, 12, 17, 49,
60, 92, 97 and 99. The centres of the crosses represent the
first 18 guesses. If any of the answers is “hot”, we certainly
have enough guesses left to nail down the exact number. Sup-
pose all answers are “cold”. The next two guesses will be 11
Junior Solutions
155
and 98. If either answer is “hot”, we can nail down the exact
number. If not, the next three guesses will be 18, 39 and 70.
We will know Alex’s number for sure in 23 moves.
0123456789
(c) The answer is yes.
By making minor adjustments to the crosses near the top right
and bottom left corners, we can save 1 move. Again, assume
that the first 18 guesses are answered with “cold”. The next
three guesses will be 11, 39 and 70. If any of the answers is
“hot”, we have one more guess that will make it work. If all
the answers are “cold”, the guess 96 will tell us whether Alex’s
number is 97 or 99.
0123456789
(A Liu)
156
TOURNAMENT 22
SENIOR SOLUTIONS
Autumn 2000 (0 Level)
1.	Alternative 1
Since ABMNC is cyclic, we have AB AM = ABCM and AANM =
AACM. By the Exterior Angle Theorem applied to triangle BAK,
AABC + AB AM = AAKC.
By the Exterior Angle Theorem applied to the cyclic quadrilateral
MKLN,
AAKC = AANM = AACM.
It follows that
AABC = AAKC - AB AM = AACM - ABCM = AACB,
so that AB = AC.
(A Liu)
Alternative 2
Since ACNM and KLNM are cyclic quadrilaterals, AACN =
180° - AAMN = AKLN = AALC. Since AC AN = ALAC, trian-
gles ACN and ALC are similar so that AC2 = AN  AL. Similarly,
AB2 = AM  AK. However, AN  AL = AM  AK since KLNM is
cyclic. Hence AB = AC.
(D Brox)
2.	Suppose there exist positive integers w, x, у and z such that a =
w(ad — be), b = x(ad — be), c = у (ad — be) and d = z(ad — be). Then
ad — bc = (wz — xy)(ad — bc)2. It follows that (wz — xy)(ad—be) = 1
so that ad — be = ±1. However, this contradicts ad — be > 1.
(A Liu)
Senior Solutions
157
3.	Let the lateral edges of the polyhedron be vertical and let ABCDE
be its top face. If at least one edge of ABCDE is horizontal, then
the lateral face of the polyhedron which contains this edge must be
a rectangle. It follows that all lateral faces are rectangles.
Assume henceforth that the lateral faces are not rectangles. Then
no edge of ABCDE is horizontal. Let П be the lowest horizontal
plane which contains a vertex of ABCDE, and we may assume
that this vertex is A. From A, we can trace two rising paths along
the perimenter of ABCDE until they meet at the highest vertex.
There are three vertices other than this one and A.
By the Pigeonhole Principle, one of the paths contains at least two
of them. By symmetry, we may assume that D is higher than C
and C is higher than B. Let the projections of В, C and D onto
П be В', C and D' respectively.
Let t be the line of intersection of П with the plane of ABCDE.
Then I passes through A. Since DD' and CC are parallel, DC
and D'C are coplanar and must meet at some point X. Since DC
is in the plane of ABCDE while D'C is in П, X must lie on t.
Similarly, CB and СB' meet at some point У on/.
Now the lateral faces have a common acute angle, so that A ABB' =
ABCC — ACDD'. They are also equal to AYBB' and AXCC.
Hence triangles ABB' and YBB' are congruent, as are triangles
YCC and XCC.
This means that BA = BY and CY = CX, so that ABAY =
A BY A and ACYX = ACXY. Hence these four angles are all
acute, but this contradicts ABYA + ACYX = 180°. It follows
that the lateral faces of the polyhedron must be rectangles, and
the common possible common value of an angle of theirs is 90°.
(A Liu)
158
TOURNAMENT 22
4.	(a) More generally, we prove that if N — 2n, the task can be
accomplished in n weighings. Label each coin with a binary
number from 0 to 2n+1 — 1 and fill in the leading Os so that
each is an n + 1-digit number. In the г-th weighing, put a coin
in the left pan if its г-th digit from the left is 0, and in the
right pan if it is 1. There will always be 2n coins in each pan.
If equilibrium is achieved in any of these n weighings, the task
is accomplished. If not, the two fake coins are always in the
same pan. This means that their binary labels are identical
except for the last digit. The task can now be accomplished
by putting in one group all coins whose last digits are Os, and
in another group those whose last digits are Is.
(b) More generally, we prove that if 2n-1 < N < 2n, the task can
be accomplished in n weighings. Divide the coins into two
groups with N — 2n~1 in each and two groups with 2n-1 in
each. Weigh the two larger groups against each other and the
two smaller groups against each other.
If we have equilibrium in both cases, or fail to have equilibrium
in both cases, the task can be accomplished by combining
a larger group with an appropriate smaller group. Suppose
equilibrium is achieved only between the smaller groups. Then
both fake coins are in one of the two larger groups.
Together, they have 2n coins, and by (a), n — 1 weighings are
sufficient. Since we have already performed one such weighing,
n — 2 more will suffice, yielding a total of at most n weighings
as desired. Suppose equilibrium is achieved only between the
larger groups.
Then all the coins in them are real. Simply transfer enough
coins to the smaller groups so that each has 2n~1 coins. As
before, at most n — 2 more weighings are needed.
(A Liu)
Senior Solutions
159
Autumn 2000 (A Level)
1.	See solution to Problem 3 in Junior paper.
2.	By taking the midpoints of six of the cube’s edges as shown in the
diagram, we have a regular hexagon whose entire boundary lies on
the surface of the cube.
Let the sidelength of this hexagon be 2 + ^/3. From each corner,
cut off a triangle with sidelengths 1, 1 and ^/3. We will be left
with a regular 12-gon of sidelength л/3, whose vertices all lie on
the surface of the cube.
Suppose there is such a regular n-gon with n > 13. Since the cube
has six faces, the Pigeonhole Principle implies that at least three
of the vertices of the n-gon lie on the same face. Since these three
vertices are not collinear, they determine a unique plane which is
the face of the cube on which they lie. However, this forces the
entire n-gon to be on that face too, and this is contrary to the
hypothesis. Thus the maximum value we seek is 12.
(A Liu)
3.	Since ВС : BB' = BB" : BA = a : c, we have B"C : AB' = a : c
and B"C\\AB'.
Hence B"C : B'A = CC" : AA' and LB"CC" = AB'AA'. There-
fore the triangles B"CC" and B'AA' are similar. Hence A'B' :
C"B" = AA' : CC" = c : a.
(A Liu)
160
TOURNAMENT 22
4.	(a) Given an expression Px + У- we сац _ qS determi-
sx +1
nant of this expression.
Assume that aX = x for all values of x except a finite
ex + a
number of values. Then ex2 + (d — a)x — b = 0 for infinitely
many values of x, which implies that c = 0, d = a and 6 = 0.
tt	p ax + b	9 i .
Hence the determinant of ------- equals a and therefore is
ex + d
positive.
Now consider
(px + q\ 1 sx + t	(ap + s)x(aq + t)
\sx + t J	px + q	px + q
/ x + \ -1
Then the determinant of a + I ------- I equals qs — pt.
\sx + t J
Therefore since the determinant of a; is 1, the determinant
of
1
ai 4---------------j----------
U2 4---------------------
аз + .
1
Г
an +
x
equals (—l)n. But it has been shown above that the resulting
determinant is positive, so n must be even.
(b) if
1
ai 4-------p = x,
a2 4---
X
then (а1й2	0,1 = x and therefore a± = a 2 = 0, which
a2x +1
is not allowed. Hence n^2, and by part (a), n > 4.
The following equation shows that n = 4 is possible:
2 4-----------= x.
-i+ J
2+-------p
— 1 4—
x
Thus the answer is 4.
(A Liu)
Senior Solutions
161
5. Let’s call a column or row white (black) if the total number of
white (black) cells in this column or row is greater than that of the
other colour. Assume that there is a black row in the table. Then
for each black cell in this row, its column is white. Hence there are
more white columns in the table than the black ones. Hence there
are no white rows in the table as otherwise there would be more
black columns than the white ones. Similarly, since there are white
columns in the table, there are no black ones. Hence counting by
columns, we see that there are more white cells in the table than
the black ones which is not possible as there are no white rows in
the table.
(A Liu)
6. (a) The answer is no.
Let Ф = Ai A2 ... An be the black polygonal figure and О the
centre of the cross-section of the nail, a circle of radius
centimetre. Join OAi for 1 < i < n. Since О belongs to all
the black squares, Ф is partitioned into triangles OAiAi+i for
1 < г < n, where An+i is to be interpreted as A±.
The area of this triangle is given by ±AiAi+ihi, where hi is
the distance of О from AiAi+±. It is also given by ^OAi •
OAi+i sinAiOAi+i. Now hi > ± since the nail is contained
in all black squares. On the other hand, each of OAi and
OAi+i is at most \/2, the diagonal of each black square.
Finally, we note that sin A^OAi+i is less than the radian mea-
sure of Z Ai ОAi+1. The lengths of OAi and OAi+i being ir-
relevant to this inequality, we may take OAi = OAi+± = д/2.
Then sinAiOA^+i represents the area of triangle OAiAi+i
while the radian measure of /.AiOAi+i represent the area of
the circular sector OAiAi+±. Since the former is contained in
the latter, the inequality follows. Hence
AiAw = OA.OA+1sinAOA+1 < 40MiOA+i
Finally, the perimeter of Ф in centimetres is given by
' AiAi+i < 40 Z AOAi+i = 80tf,
i=l	i—1
which is significantly less than 1 kilometre.
Ьк.,
162
TOURNAMENT 22
(b) The answer is also no.
Consider a fixed square lattice of side With each lattice
point as centre, a circle of radius is drawn. We call this a
nail.
For any unit square, its centre is at most from some lattice
point. Since
a/2	1	1
T + 20 < 2’
the nail at this lattice point is contained in the unit square.
Let Ф = Ai Л.2 • • • An be the polygonal figure held together by
the pin О.
Superimpose Ф on this lattice. Obviously, Ф is inside the circle
with centre О and radius \/2, which is in turn inside a square
V of sidelength 2д/2, with centre О and sides parallel to the
axes of the lattice. Since 2\/2 < 3, there are at most 6 rows
and 6 columns of lattice points intersecting V. Hence there
are at most 62 = 36 lattice points inside V, and at most 36
nails inside Ф.
We now divide the black squares which make up Ф into groups
according to the nails they contain. Since every black square
contains at least one nail, none is left out. If a black square
contains at least two nails, we assign it arbitrarily to one of
these nails. Thus the black squares are partitioned into at
most 36 groups, all those in the same group containing the
same nail.
For each group, we may apply the result in (a) and conclude
that the polygonal figure formed from the black squares in
the group has perimeter less than 80тг centimetres. Since the
perimeter of Ф is at most the sum of the perimeters of these
polygonal figures, it is less than 36 • 80тг = 2880тг centimetres,
well short of 1 kilometre.
(c) The answer is no again.
For each black square, draw a circle of radius centimetre
whose centre coincides with that of the square. Call such
circles spikes.
We choose the largest subset of spikes no two of which inter-
sect, and suppose there are n spikes in this subset. We divide
the black squares into groups according to which spikes they
contain. If a black square contains at least two circles, it is
assigned arbitrarily to one of them.
Senior Solutions
163
A black square whose spike is chosen certainly belongs to some
group. If the spike of a black square is not chosen, it is because
it intersects some chosen one. Since
1 1 1
10 + 5 < 2’
the other spike is contained in this black square. It follows
that we have a partition of the black squares into n groups.
Since all black squares in a group contain the circular nail of
radius concentric with the spike of the group, they form a
polygonal figure with perimeter less than 80тг by (a). Hence
the overall figure has perimeter less than 80n?r centimetres.
Since it contains n disjoint spikes, its area is at least square
centimetres. It follows that the ratio of the perimeter to the
area of the overall figure is less than 8000.
(A Liu)
164
TOURNAMENT 22
Spring 2001 (О Level)
1.	The computer can be right if at k:00 pm, the distance covered is
22^7лп °f the total distance for 1 < к < 6.
At k:QQ pm, the average speed so far is 60fc^Q, and 60^4Q of the
distance is still to be covered, requiring another hour at the same
speed.
Note that between (к — 1) :00 pm and k:QQ pm, the distance covered
is
60fc - 20 60fc - 80	3600
60fc + 40 “ 60A; - 20 ~ (60A + 40)(60A - 20)
of the total distance, and these quantites are all positive.
At 6:00 pm,	of the distance has been covered, which
translates into 85 kilometres.
(A Liu)
2.	Note that IO500 has 501 digits while (IO500)3 has 1501 digits for a
total of 2002. For any integer a > IO500, a and a3 will also have at
least 2002 digits between them.
If a < IO500, then it has at most 500 digits while a3 < Ю1500 has at
most 1500 digits. Thus it is not possible for the sum of the numbers
of digits to be 2001.
(A Liu)
3.	Alternative 1
First, note that CY = AY < CZ = AB. This is evident if AY
is perpendicular to BC. If not, one of /AY В and /AYC will
be obtuse. In the former case, AB > AY. In the latter case,
CZ > CY.
Complete the parallelogram ABCD and let W on AD be such
that LWCY = /AYC. Then CY = CW, CZ = AB = CD and
Senior Solutions
165
AAYC = AWCY = LDWC. Since AB > AY, triangles ZYC and
DWG are congruent, so that
LAYC = LWCY = LDCZ.
It follows that triangles YAC and DZC are similar, so that
LZAC = LZDC.
Hence ADCZ is a cyclic quadrilateral. Now
LXBY + LXZY = LADC + LAZC = 180°,
so that BXZY is also cyclic.
(A Liu)
Alternative 2
Place a point T on YC such that TC = AZ. Since AY = CY, by
symmetry, LYZC = LYTA and AT = CZ.
Since ZC = AB, we obtain AT = AB. Hence LABT = AATB.
Hence ZYZC = LABC and XBYZ is cyclic.
(A Storozhev)
4.	We first play the game on a 3 x 4 board. The first player can force
a win by placing the first domino anywhere on the middle row.
This leaves the second player with two columns on which dominoes
can be placed, while the first player can place two more dominoes
above and below the first one.
Now divide the 3 x 1000 board into 250 3 x 4 boards. Since the
second player can only place dominoes within such a board, the
first player can force a win by adopting the earlier strategy on each
3x4 board.
(A Liu)
166
TOURNAMENT 22
5.	Connect the midpoints of two edges of the tetrahedron if and only
if they share a common vertex. This divides the solid tetrahedron
into four corner tetrahedra plus a central octahedron. If two of
the nine points lie on the surface of one of those corner tetrahedra,
then the distance between them is at most 0.5 centimetre. Hence
we may assume that each contains at most one point, leaving five
on the surface of the central octahedron. Only four of its faces
are on the surface of the original tetrahedron. By the Pigeonhole
Principle, two of the five points will lie on the same face, and the
distance between them is at most 0.5 centimetre.
(A Liu)
Senior Solutions
167
Spring 2001 (A Level)
1.	Let
р(ж) = ^001-(1-ж)2001 +j.
This is a polynomial of degree 2001 since the leading term is 2ж2001.
Now
P(x) + P(1 — x) — ж2001 — (1 — ж)2001 + | + (1 — ж)2001
-(l-(l-<001 + i
= 1
for all real numbers ж.
(A Liu)
2.	Let ai > a2 > • • • > an be the respective numbers of failures given
to the n students in the class. We will prove by induction that for
any n > 5, ai > 3(d2 + аз + • • • + an).
If n = 5, ai > 4(a2 + a3 + a4 + a5) > 3(a2 + n3 + «4 + as)-
If n > 6, by the induction hypothesis a2 > 3(аз H— • + an). Hence
«1
4(^2 + a3 + a4 + as)
3(Z2 + ^2
3(12 T 3(аз + • • • + an).
So di > 3(a2 + из + • • • + an) as required.
(A Liu)
3.	See solution to Problem 6 in Junior paper.
4.	Suppose the result is false. Let j be the smallest integer such that
the sum of the numbers in the leftmost j columns of В is less than
the sum of the numbers in the leftmost j columns of A. Then there
are more Is in column j of A than in column j of B.
Let the number of Is in column j of A be i. Divide each of A and В
into four quadrants, the dividing lines being between the (m — i)th
row and the (m — i + l)st row and between the J th column and the
(j + l)st column.
168
TOURNAMENT 22
	j columns	n — j columns
m — i	II	I
rows	quadrant	quadrant
i	III	IV
rows	quadrant	quadrant
Let the numbers of Is in the four quadrants of A be cq, cq, аз
and 0,4, and those of В be by, 62, &з and 64, respectively. Then
cq + 02 T <23 T 0,4 = b± + 62 “I- 63 T ^4 and cq T cq > T ^3, so that
cq T 0,4 < &i T 64.
Since the last i numbers in column j of A are Is, all of the numbers
in the fourth quadrant of A are Is. Hence 64 < 04, so that cq < b±.
Since the first m — i numbers in column j of A and В are Os,
a 2 =	= 0. Hence 01 + 02 <61 + 62, which is a contradiction.
(A Liu)
5.	Let there be n players. For player k, denote the first sum by Wk,
the second sum by £k and the player’s own score by Sk- Let
n
T — Sk^Wk &k)-
k=l
We claim that T = 0. Consider the game between players i and j.
If it is a tie, it contributes nothing to T. Suppose i beats j. Then
it contributes SiSj to the term si(wt — £i) while it contributes —SjSi
to the term Sj(wj — £j).
The net contribution to T is still nothing, and the same holds by
symmetry if j beats i. This justifies the claim.
(a)	Since Sfc > 0 for all k, we cannot have Wk > tk for all к as
otherwise T > 0.
(b)	Since sfc > 0 for all k, we cannot have Wk < for all к as
otherwise T < 0.
(A Liu)
6.	We construct the polyhedra as follows. Start with an infinite in-
verted cone with vertex at the origin О and axis along the pos-
itive z-axis. On the surface of the cone are equally spaced lines
£1, £2,    , ^2001-
Senior Solutions
169
For any positive number t, the plane z = t intersects these lines at
A{, A%, ..., -'4-2001 • Let ti be an arbitrary positive number. Let
Di be the disc which is the part of the plane z = t± inside the cone.
Let Bi be the midpoint of the minor arc A^A^1. Let Mi be the
convex polygon A^1 A^ ... A2oO1 .
Consider the infinite oblique prism with base Mi and lateral edges
parallel to OBi. This will eventually be truncated to yield a
convex polyhedron P±. For sufficiently large t, the distance be-
tween A^A^ and the midpoint of the minor arc A^A^ will be larger
than the diameter of Di so that Pi will not intersect the polygon
At At At
Л1Л2 • • • ^2001-
Let t2 be such a value and let D2 be the part of the plane z =
inside the cone. Let B2 be the midpoint of the minor arc A^ A32.
Let be the convex polygon A^ A^ ... A.22OO1 if it already touches
Pi. If not, insert between A^A^ an additional vertex which lies
on D2 П Pi.
Let P2 be the convex polyhedron obtained by eventually truncating
the oblique infinite prism with base М2 and lateral edges parallel
to OB2. As before, for sufficiently large t, P2 will not intersect the
polygon А{АЪ2 ... А*2001.
Let T3 be such a value, and we can continue the construction as be-
fore with М3 being the convex polygon A*3 A23 ... A2q01, expanded
if necessary, so that it touches both Pi and P2. For 1 < i < j <
к < 2001, Pi and Pj have only common boundary points on the
plane z = tj.
Since Pfc does not intersect this plane, P^, Pj and Pk have no
common points.
(A Liu)
7.	(a) We construct a directed graph as follows. Each vertex repre-
sents a distribution of chips coupled with the box from which
chips must be taken. An arc goes from vertex A to vertex В
if the state represented by A leads to the state represented by
B. The out-degree of each vertex is clearly 1.
We claim that so is its in-degree. From any given state, we
can reverse the process by taking a chip from the box which
is the last one to receive a chip, collecting 1 chip from each
subsequent box counterclockwise, and stopping when we reach
an empty box.
We can only deposit all the chips into this box, and mark it as
the one from which chips must be taken. This is the unique
170
TOURNAMENT 22
state which leads to the given one, and the claim is justified.
Since the number of vertices is finite, the directed graph is a
union of disjoint directed cycles.
It does not matter which cycle contains the vertex which rep-
resents the initial state, as all states represented by vertices
in this cycle will reappear.
(b) We construct a directed graph as follows. Each vertex repre-
sents a distribution of the chips. An arc goes from vertex A to
vertex В if it is possible to change the distribution represented
by A directly into the distribution represented by B.
The out-degree and the in-degree of each vertex are both equal
to the number of non-empty boxes in the distribution repre-
sented by that vertex. Hence the directed graph consists of
strongly connected components. It has only one component
because the distribution in which all chips are in a specific
box is reachable from any other distribution.
We simply do not take chips from that box. Hence we can
change any distribution into any other distribution.
(A Liu)
TOURNAMENT 23

TOURNAMENT 23
JUNIOR QUESTIONS
Autumn 2001 (0 Level)
1.	In the quadrilateral ABCD, AD is parallel to ВС. К is a point on
AB. Draw the line through A parallel to КС and the line through
В parallel to KD. Prove that these two lines intersect at some
point on CD.	(V Bugaenko, 4 points)
2.	Clara computed the product of the first n positive integers and
Valerie computed the product of the first m even positive integers,
where m > 2. They got the same answer. Prove that one of them
had made a mistake.	(V Senderov, 4 points)
3.	Kolya is told that two of his four coins are fake. He knows that
all real coins have the same weight, all fake coins have the same
weight, and the weight of a real coin is greater than that of a fake
coin. Can Kolya decide whether he indeed has exactly two fake
coins by using a balance twice? (NN Konstantinov, 4 points)
4.	On an east-west shipping lane are ten ships sailing individually.
The first five from the west are sailing eastwards while the other
five ships are sailing westwards. They sail at the same constant
speed at all times. Whenever two ships meet, each turns around
and sails in the opposite direction. When all ships have returned
to port, how many meetings of two ships have taken place?
(A Nikolaev, 4 points)
5.	On the plane is a set of at least four points. If any one point from
this set is removed, the resulting set has an axis of symmetry. Is it
necessarily true that the whole set also has an axis of symmetry?
(A Shapovalov, 4 points)
174
TOURNAMENT 23
Autumn 2001 (A Level)
1.	Do there exist positive integers cq <	<  • • < aioo such that for
2 < к < 99, the greatest common divisor of ak-i and a a, is greater
than the greatest common divisor of a a, and ttfc+i?
(A Shapovalov, 4 points)
2.	Let n > 3 be an integer. A circle is divided into 2n arcs by 2n
points. Each arc has one of three possible lengths, and no two
adjacent arcs have the same length. The 2n points are coloured
alternately red and blue. Prove that the n-gon with red vertices
and the n-gon with blue vertices have the same perimeter and the
same area.	(V Proizvolov, 5 points)
3.	Let n > 3 be an integer. Each row in an (n — 2) x n array consists
of the numbers 1, 2,..., n in some order, and the numbers in each
column are all different. Prove that this array can be expanded
into an n x n array such that each row and each column consists
of the numbers 1, 2, ..., n.	(S Mikhajlov, 5 points)
4.	Let n > 2 be an integer. A regular (2n + l)-gon is divided into
2n — 1 triangles by diagonals which do not meet except at the
vertices. Prove that at least three of these triangles are isosceles.
(R Zhenodarov, 5 points)
5.	Alex places a rook on any square of an empty 8x8 chessboard.
Then he places additional rooks one rook at a time, each attacking
an odd number of rooks which are already on the board. A rook
attacks to the left, to the right, above and below, and only the first
rook in each direction. What is the maximum number of rooks
Alex can place on the chessboard? (A Shapovalov, 6 points)
6.	Several numbers are written in a row. In each move, Robert chooses
any two adjacent numbers in which the one on the left is greater
than the one on the right, swaps them and then doubles each of
them. Prove that Robert can make only a finite number of such
moves.	(A Shapovalov, 8 points)
7.	It is given that 2333 is a 101-digit number whose first digit is 1.
How many of the numbers 2fc, 1 < к < 332, have first digit 4?
(G Galperin, 8 points)
Junior Questions
175
Spring 2002 (0 Level)
1.	Let a < b be positive integers. Are their values uniquely determined
if both a 49 x 51 rectangle and a 99 x 101 rectangle can be tiled by
a x b rectangles?	(S Dorichenko, 4 points)
2.	Does there exist a triangle which can be dissected into four convex
polygons: a triangle, a quadrilateral, a pentagon, and a hexagon?
(A Zaslavskiy, 5 points)
3.	Let x and у be positive integers. If x2 + xy + y2 is a multiple of
10, prove that it must actually be a multiple of 100.
(V Proizvolov, 5 points)
4.	The sides AB, BC, CD and DA of a quadrilateral ABCD are
tangent to a circle at the points K, L, M and N respectively. Let
S be the point of intersection of KM and LN. Prove that if SKBL
is a cyclic quadrilateral, then SNDM is also a cyclic quadrilateral.
(A Akopian, 5 points)
5.	(a) There are 128 coins of two different weights, 64 of each. How
can one find two coins of different weight by performing no
more than 7 weighings on a balance?	(3 points)
(b) There are 8 coins of two different weights, 4 of each. How
can one find two coins of different weight by performing 2
weighings on a balance?	(A Shapovalov, 3 points)
ч
176
TOURNAMENT 23
Spring 2002 (A Level)
1.	Let a, b and c be the sides of a triangle. Prove that
a3 + b3 + 3abc > c3.
(V Senderov, 4 points)
2.	A game is played on a 23 x 23 board. The first player controls
two white chips which start in the bottom-left and the top-right
corners. The second player controls two black ones which start
in the bottom-right and the top-left corners. The players move
alternately. In each move, a player can move one of the chips
under control to a vacant square which shares a common side with
its current location. The first player wins if the two white chips
are located on two squares sharing a common side. Can the second
player prevent the first player from winning?
(E Zinin, P Kozhevnikov, 4 points)
3.	Let E and F be the respective midpoints of sides BC and CD
of a convex quadrilateral ABCD. Segments AE, AF and EF cut
AB CD into four triangles whose areas are four consecutive positive
integers. Determine the maximal area of triangle BAD.
(S Shestakov, 6 points)
4.	There are n lamps in a row, some of which are on. Every minute,
all the lamps already on will go off. Those which were off and were
adjacent to exactly one lamp that was on will go on. For which n
can one find an initial configuration of which lamps are on, such
that at any time at least one lamp will be on?
(A Gorbachev, 7 points)
5.	An acute triangle was dissected by a straight cut into two pieces
which are not necessarily triangles. Then one of the pieces was
dissected by a straight cut into two pieces, and so on. After a few
dissections, it turned out that all the pieces are triangles. Can all
of them be obtuse?	(G Galperin, 7 points)
6.	In a strictly increasing infinite sequence of positive integers, every
term starting from the 2002-nd term divides the sum of all preced-
ing terms. Prove that every term starting from some term is equal
to the sum of all preceding terms. (A Shapovalov, 7 points)
Junior Questions
177
7.	Some domino pieces are placed in a chain according to the standard
rules. In each move, we may remove a sub-chain with equal num-
bers at its ends, turn the whole sub-chain around, and put it back
in the same place. Prove that for every two legal chains formed
from the same pieces and having the same numbers at their ends,
we can transform one to the other in a finite number of moves.
(A Shapovalov, 8 points)
178
TOURNAMENT 23
SENIOR QUESTIONS
Autumn 2001 (0 Level)
1.	An altitude of a pentagon is the perpendicular dropped from a
vertex to the opposite side. A median of a pentagon is the line
joining a vertex to the midpoint of the opposite side. If the five
altitudes and the five medians all have the same length, prove that
the pentagon is regular.	(R Zhenodarov, 4 points)
2.	There exists a block of 1000 consecutive positive integers containing
no prime numbers, namely, 1001! + 2, 1001! + 3, ..., 1001! + 1001.
Does there exist a block of 1000 consecutive positive integers con-
taining exactly five prime numbers?
(V Galperin, 4 points)
3.	On an east-west shipping lane are ten ships sailing individually.
The first five from the west are sailing eastwards while the other
five ships are sailing westwards. They sail at the same constant
speed at all times. Whenever two ships meet, each turns around
and sails in the opposite direction. When all ships have returned
to port, how many meetings of two ships have taken place?
(A Nikolaev, 4 points)
4.	On top of a thin square cake are triangular chocolate chips which
are mutually disjoint. Is it always possible to cut the cake into
convex polygonal pieces each containing exactly one chip?
(A Kanel-Belov, 4 points)
5.	The only pieces on an 8 x 8 chessboard are three rooks. Each rook
is allowed to move to a vacant square in the same row or column
without jumping over another rook. The white rook starts at the
bottom left corner, the black rook starts in the square directly
above the white rook and the red rook start in the square directly
to the right of the white rook. The white rook is to finish at the
top right corner, the black rook in the square directly to the left of
the white rook and the red rook in the square directly below the
white rook. At all times, each rook must be either in the same row
or the same column as another rook. Is it possible to get the rooks
to their destinations?	(A Shapovalov, 4 points)
Senior Questions
179
Autumn 2001 (A Level)
1.	On the plane is a triangle with red vertices and a triangle with blue
vertices. О is a point inside both triangles such that the distance
from О to any red vertex is less than the distance from О to any
blue vertex. Can the three red vertices and the three blue vertices
all lie on the same circle?	(P Kozhevnikov, 4 points)
2.	Do there exist positive integers ai <	< •   < аюо such that for
2 < к < 99, the least common multiple of a^-i and is greater
than the least common multiple of and ttfc+i?
(A Shapovalov, 5 points)
3.	An 8x8 array consists of the numbers 1, 2, ..., 64. Consecutive
numbers are adjacent along a row or a column. What is the mini-
mum value of the sum of the numbers along a diagonal?
(A Shapovalov, 6 points)
4.	Let Fi be an arbitrary convex quadrilateral. For к > 2, is
obtained by cutting Ffc_i into two pieces along one of its diagonals,
flipping one piece over and then glueing them back together along
the same diagonal. What is the maximum number of non-congruent
quadrilaterals in the sequence {F^}? (I Tokareva, 6 points)
5.	Let a and d be positive integers. For any positive integer n, the
number a + nd contains a block of successive digits which form the
number n. Prove that d is a power of 10.
(A Shapovalov, 7 points)
6.	In a row are 23 boxes such that for each k, 1 < к < 23, there is
a box containing exactly к balls. In one move, we can double the
number of balls in any box by taking balls from another box which
has more. Is it always possible to end up with exactly к balls in
the fc-th box for 1 < к < 23?	(R Zhenodarov, 7 points)
7.	The vertices of a triangle have coordinates (aq,i/i), (^2,1/2) and
(жз,?/з). For any integers h and A;, not both 0, the triangle whose
vertices have coordinates (aq +	+ A;), (X2 + h,y2 + k) and
(жз + h, уз + к) has no common interior points with the original
triangle.
(a)	Is it possible for the area of this triangle to be greater than
I?	(3 points)
(b)	What is the maximum area of this triangle?
(E Cherepanov, 6 points)
180
TOURNAMENT 23
Spring 2002 (О Level)
1.	Let x and у be positive integers. If x2 + xy + y2 is a multiple of
10, prove that it must actually be a multiple of 100.
(V Proizvolov, 4 points)
2.	Triangles ABC and A'B'C are congruent but opposite in orienta-
tion. Prove that the midpoints of A A', BB' and CC' are collinear.
(V Bugaenko, 5 points)
3.	There are 6 pieces of cheese of different weights. For any two of
these 6 pieces, it is known which one is lighter. It is also known
that three pieces may be chosen so that their total weight is equal
to the total weight of the other three. How can we make such a
choice by performing two weighings on a balance?
(A Shapovalov, 5 points)
4.	In how many ways can we place the numbers 1 to 100 in a 2 x 50
table so that any two consecutive numbers are placed in squares
with a common side.	(A Shapovalov, 5 points)
5.	Does there exist a regular triangular prism that can be covered
without overlap by equilateral triangles all of different sizes, if one
is allowed to bend the triangles around the edges of the prism?
(L Emelianov, 6 points)
Senior Questions
181
Spring 2002 (A Level)
1.	In a triangle ABC, tan A, tan В and tanC are integers. Find their
values.	(A Zaslavskiy, 4 points)
2.	Does there exist a point A on the graph of у = x3 and a point В
on the graph of у = x3 + |ж| + 1 such that the distance between A
and В does not exceed y^?
(A Spivak, A Khachaturian, 4 points)
3.	In a strictly increasing infinite sequence of positive integers, every
term starting from the 2002-nd term divides the sum of all preced-
ing terms. Prove that every term starting from some term is equal
to the sum of all preceding terms. (A Shapovalov, 5 points)
4.	The spectators are seated in a row with no empty places. Each is
in a seat which does not match the spectator’s ticket. An usher can
order two spectators in adjacent seats to trade places unless one
of them is already seated correctly. Is it true that from any initial
arrangement, the usher can eventually place all the spectators in
their correct seats?	(A Shapovalov, 5 points)
5.	Let AAi, В Bi and CCi be the altitudes of an acute triangle ABC.
Let О a, Ob and Oc be the respective incentres of triangles AB±Ci,
BAiCi and CAiBi. Let Ta, Tb and Tc be the points of tangency
of the incircle of ABC with sides BC, CA and AB respectively.
Prove that TaOcTbOaTcOb is an equilateral hexagon. (L
Emelianov, 6 points)
6.	The 52 cards in a standard deck are arranged in a 13 x 4 array. If
every two adjacent cards, vertically or horizontally, have either the
same suit or the same value, prove that all 13 cards of the same
suit are in the same row.	(A Shapovalov, 7 points)
7.	Do there exist irrational numbers a and b such that a > 1, b > 1
and [amJ = |_bnJ for no positive integers m and n?
(V Senderov, A Spivak, 8 points)
182
TOURNAMENT 23
JUNIOR SOLUTIONS
Autumn 2001 (0 Level)
1.	Let the line through A parallel to КС cut CD at H. The problem is
equivalent to proving that BH is parallel to KD. If AB is parallel
to DC, then both ABCD and AKCH are parallelograms, so that
AB = DC and AK = HC. Hence
BK = AB - AK = DC - HC = DH,
so that BHDK is also a parallelogram.
It follows that BH is parallel to KD. If AB is not parallel to
DC, we may assume that their extensions intersect at G. Then
triangles GBC and GAD are similar, as are triangles GKC and
GAH. Hence
GB GC , GA GH
GA ~ GD аП GK ~ GC'
Multiplication yields ЦЦ = so that triangles GBH and GKD
are also similar. It follows that BH is parallel to KD.
(A Liu)
2.	Suppose n! = 2mml for some m > 2. We must have n > 3 so
that both n! and ml are divisible by 3. In each product, every
third factor is a multiple of 3. In order for both products to be
divisible by the same power of 3, n! can have at most two more
terms than ml. If n — m + 1 = 2m, we have m = 1. If n = m + 2,
(m + l)(m + 2) = 2m leads to m = 0. Both contradict m > 2.
Hence either Clara or Valerie had made a mistake.
(A Liu)
Junior Solutions
183
3.	Kolya can decide as follows. Label the coins А, В, C and D. In the
first weighing, put A and В on one side and C and D on the other.
Suppose A+B=C+D. In the second weighing, put A on one side
and В on the other. If A=B, then we have A=B=C=D. If A^B,
exactly one of A and В is fake, and exactly one of C and D is fake.
Suppose A+B^C+D. In the second weighing, put A and C on one
side and В and D on the other. If A+C=B+D, then the number
of fake coins is even but not 0 or 4. If A+C^B+D, the number of
fake coins is odd.
(A Liu)
4.	Let us consider what happens when two ships meet. Each continues
where the other would have gone. Since we are interested in the
total number of meetings rather than the numbers of meetings for
individual ships, we may pretend that the ships just sail on. Since
there are 5 ships from each side, the total number of meetings is
5 x 5 = 25.
(A Liu)
5.	The answer is no.
Let ABC be a triangle with AB = AC and LCAB — 36°. Let D
be a point on AC such that BC — BD.
Then
LBDC = LBCD = LABC = 72°
so that
LABD = ADBC = 36°.
Hence BD = AD. Consider the set {А, В, C, D}. It does not have
an axis of symmetry. If A is removed, we have BC = BD. If В
is removed, A, C and D are collinear. If C is removed, we have
AD = BD. If D is removed, we have AB = AC. Each subset of
three points has an axis of symmetry.
(A Liu)
184
TOURNAMENT 23
Autumn 2001 (A Level)
1.	The answer is yes.
For 1 < к < 100, let ak = 2" + 298 + • • • + 210°-fc. Then щ <
«2 < • • • < аюо- For 2 < к < 100, the difference between ak_i
and ttfc is 2100-fc. Since it divides both ak_± and ak, 2100-fc is in
fact their greatest common divisor. Similarly, for 1 < к < 99 the
greatest common divisor of ak and ak+± is 210°_(fc+1\ which is less
than 2100-fe.
(A Liu)
2.	Let a, b and c be the three arc lengths. Let there be x arcs of length
a, у arcs of length b and z arcs of length c. Then x + у + z = 2n.
Each side of the n-gon with red vertices is subtended by an arc of
length b + с, c + a or a + b.
Of these n arcs, x contain an arc of length a, so that the number
of arcs of length b + c is n — x. Similarly, the number of arcs of
length c + a is n — y, and the number of arcs of length a + b is
n — z. Exactly the same thing can be said about the n-gon with
blue vertices. Hence the two polygons have the same perimeter.
For the same reason, the area of the part of the circle outside the
n-gon with red vertices is the same as that of the n-gon with blue
vertices.
Therefore the two polygons have the same area.
(A Liu)
3.	Each column is missing two of the numbers, and each number is
missed by exactly two columns. Construct a graph with n vertices
representing the numbers. Two vertices are joined by an edge if the
numbers they represent are both missed by the same column, so
that there are exactly n edges. Moreover, each vertex has degree 2.
This means that the graph is a union of cycles, including degenerate
cycles of length 2.
In each cycle, we orient the edges so that they are all directed
clockwise. Then each vertex has in-degree 1 and out-degree 1.
For each column in the expanded square, locate the directed edge
joining vertices representing the numbers missing from this column.
Put the number represented by the initial vertex in the (n — l)st
row and the number represented by the terminal vertex in the nth
row.
Junior Solutions
185
Clearly, all the numbers in each column are distinct. Since each
vertex has in-degree 1 and out-degree 1, each number appears ex-
actly once in the (n — l)st row and exactly once in the nth row.
(A Liu)
4.	For 2 < к < n, consider a path consisting of к consecutive edges of
the regular (2n + l)-gon. The diagonal joining the endpoints of this
path is said to have span k. Note that a diagonal of span 2 cuts
off an isosceles triangle whose equal sides are sides of the original
polygon.
If in our triangulation, there is a triangle formed by three diagonals,
then this divides the remaining parts of the original polygon into
three pieces, each of which must contain a diagonal of span 2. It
follows that we will have at least three isosceles triangles.
The only other case is that each triangle in the triangulation shares
a side with the original polygon. Thus the triangles form a sequence
such that each shares a diagonal with its neighbours. The first and
the last triangles in this sequence are cut off by diagonals of span
2, and are isosceles.
The diagonals shared by neighbouring triangles increase in span to
n from both directions.
Since there are 2n — 2 diagonals, there are two diagonals of span n,
which form the third isosceles triangle with a side of the original
polygon.
(A Liu)
5.	The answer is 63.
After three corner squares have been occupied, a rook at the fourth
corner square will always be attacking two existing rooks.
Hence at least one corner square must be empty, so that the max-
imum number of rooks that can be placed is 63.
186
TOURNAMENT 23
The diagram shows how Alex can place as many as 63 rooks in four
stages labelled А, В, C and D.
Ai	c	a2	c	A3	c	A4	
^48							D41
							
B40							D33
							
B32							B25
							
D24							B17
							
D±6							B9
							
B8							Bl
							
Bi	b2	c	B3	c	B4	c	B5
(A Liu)
6.	Let the numbers be a±, a2,..., an, and we maintain these labels
even though the values of the numbers change with the doubling.
We claim that two numbers can exchange places at most once.
It will then follow that Robert must stop after at most Q) moves.
Assuming to the contrary that there are two numbers which ex-
change places at least twice, consider such a pair of exchanges that
occur the closest together. Let the numbers be cq and aj such that
ttj > aj during the first exchange.
Then aj < aj during the second exchange. In between, aj must
have grown more than ai. In any exchange involving cq or aj with
a third number a*,, it must come between them after their first
exchange and get out before their second exchange. If a^ gets in
through one and goes out through the other, it has no effect on the
relative size of a^ and aj.
The only way aj can outgrow аг is for it to exchange twice with
some <Zfc in between its two exchanges with ai. However, this con-
tradicts the assumption that the two exchanges between ai and aj
are the closest together. This justifies the claim.
(A Liu)
7.	The answer is 33.
The number of digits is non-decreasing along the sequence {2k :
1 < к < 332}. Clearly, this number cannot increase by more than
Junior Solutions
187
1 at a time. Every time an increase occurs, the new power of 2
must have 1 as its first digit. Since 2333 is an 101-digit number,
there are exactly 99 numbers in our sequence whose first digit is 1.
When the number of digits does not change, the first digit changes
in one of the following sequences: 1-2-4-8, 1-2-4-9, 1-2-5, 1-3-6 or
1-3-7. Now the 99 numbers above divide our sequence into 100
blocks, each of length 2 or 3. Let there be x blocks of length 2 and
у blocks of length 3. Then x + у = 100 while 2ж + 3y = 233, which
yield x = 67 and у = 33.
Now each block of length 2 does not contain any number whose first
digit is 4, while each block of length 3 contains exactly one number
whose first digit is 4. It follows there are exactly 33 numbers in our
sequence whose first digit is 4.
(A Liu)
188
TOURNAMENT 23
Spring 2002 (О Level)
1.	The answer is yes.
Since both a 49 x 51 rectangle and a 99 x 101 rectangle can be tiled
by a x b rectangles, their areas must be divisible by ab. The only
common divisors of 49 x 51 = 3 x 72 x 17 and 99 x 101 = 32 x 11 x 101
are 1 and 3. Since a < b, ab > 1. So ab = 3 and we must have
a = 1 and 6 = 3.
(A Liu)
2.	If either x or у is odd, x2 +au/ + ?/2 is also odd. Hence they are both
even. If one is a multiple of 10 and the other is not, x2 + xy + y2
is not a multiple of 10.
Suppose both x and у are not multiples of 10. Then x2 and y2 end
in 4 or 6, while xy cannot end in 0. So we cannot have one ending
in 4 and the other in 6. If x2 and y2 both end in 4 or both end in
6, then xy must also end in 4 or 6.
It follows that the only possibility is for both x and у to be multiples
of 10, so that x2 + xy + y2 will indeed be a multiple of 100.
(A Liu)
3.	The answer is yes.
4.	Since BK and BL are tangents, £BKL = /.KML = £BLK.
Denote their common value by 0. Then
LLBK = 180° - 20.
Junior Solutions
189
Similarly,
LDMN = LMLN = LDNM.
Denote their common value by ф. Then
LMDN = 180° - 2ф.
Now
LKSL = LSLM + LSML = 0 + ф.
Similarly,
LMSN = 0 + ф.
Since SKBL is cyclic,
£KBL + £KSL = 180°,
and therefore 0 — ф. Then
LMDN + LMSN = 180°,
which implies that SMDN is cyclic.
(A Liu)
5.	(a) Weigh 64 of the coins against the other 64. If they balance,
discard one set. Weigh 32 of the remaining ones against the
other 32, and continue. If they always balance, then after 6
weighings, we are down to 2 coins which must consist of a
heavy one and a light one.
Suppose balance is not achieved somewhere along the way.
We may as well assume that it occurs at the first weighing.
In the second weighing, weigh 32 coins from the heavier side
against 32 coins from the lighter side. If they balance, discard
190
TOURNAMENT 23
these 64 coins. If not, discard the 64 coins not involved in the
second weighing.
Continuing this way, we will be down to 2 coins after 7 weigh-
ings. They must consist of a heavy one and a light one.
(b) Weigh 4 of the coins against the other 4. If they balance,
discard one set. Weigh 2 of the remaining 4 coins against the
other 2. If they balance, take both coins from one side.
If not, take 1 coin from each side. Suppose one side is heavier
in the first weighing. Weigh 2 of these coins against the other
2.
If they balance, all 4 are heavy. Take 1 of them and 1 from
the lighter side in the first weighing.
If they do not balance, then the heavier side consists of 2
heavy coins while the lighter side consists of 1 heavy and 1
light coin. We can accomplish the task by taking the 2 coins
on the lighter side.
(A Liu)
Junior Solutions
191
Spring 2002 (A Level)
1.	We have
a3 + b3 + 3abc — c3
—	a3 +b3 + (—c)3 — 3ab{—c)
=	(a + b + (—c))(a2 + 62 + (—c)2 — &(—c) — (—c)a — ab)
=	|(a + b - c)((& + c)2 + (c + a)2 + (a - 6)2).
This is positive since a + b — c > 0 in a non-degenerate triangle.
(A Liu)
2.	Initially, the four chips determine a rectangle, with chips of the
same colour at opposite corners. After a move by the first player
from such a position, two white chips cannot share a common side.
Moreover, the four chips will no longer determine a rectangle. How-
ever, the second player can again get a rectangle with chips of the
same colour at opposite corners in his move. Thus there is no vic-
tory for the first player.
(A Liu)
3.	The answer is 6.
Denote the area of a polygon P by [P]. Then
[BAD] = [ABEFD] - [BEFD]
= [ABE]+ [AEF] + [AFD] — 3[ECF].
In order to maximize [BAD], ECF must have the smallest area
among the four triangles whose area are four consecutive integers.
Then the maximum value of [BAD] is
[ECF] + 1 + [ECF] + 2 + [ECF] + 3 - 3[ECF] = 6.
It is easily checked that such configuration exists.
(A Liu)
192
TOURNAMENT 23
4.	Denote by 0 a lamp which is off and by 1 a lamp which is on. The
following diagram shows that for n = 1 or 3, there are no initial
configurations which lead to perpetual light.
For even n, the initial configuration 1001100110... will work since
it will alternate with 0110011001.... For odd n > 3, just add 010
to the previous configuration. It will alternate with 100 since the
third light will not go on because of the fourth. Hence this part will
alternate with 100, independent of the second part. In conclusion,
perpetual light is possible for all n except 1 and 3.
(A Liu)
5.	The answer is no.
Consider a convex n-gon with m obtuse angles. We will call the
number n — 2 — m the obtuse value of the n-gon. Suppose a convex
n-gon is cut into a convex a-gon and a convex 6-gon. There are
essentially three ways of cutting the convex n-gon: through two
vertices, through one vertex or through no vertices.
In the first case, we have a + b — n + 2, soa — 2 + 6 — 2 = n — 2.
No new obtuse angles can be created since no angle of the convex
n-gon can be divided into two obtuse angles. Hence the sum of the
obtuse values of the a-gon and 6-gon is at least the obtuse value of
the n-gon.
In the second case, we have a + 6 = n + 3, so a — 2 + 6— 2 = n — 1.
As before, the end of the cut through a vertex cannot create a new
obtuse angle, but the other end which ends on a side can create
one, but no more than one, new obtuse angle.
In the third case, we have a + 6 = n + 4 so a - 2 + 6 — 2 = n. Each
end of the cut can create one, but no more than one, new obtuse
angle.
Junior Solutions
193
It follows that the sum of the obtuse values of the a-gon and 6-gon
is always at least the obtuse value of the n-gon. Since there is
one triangle with no obtuse angles initially, the sum of the obtuse
values of the resulting triangles will be positive, and therefore it
cannot happen that all these triangles are obtuse.
(A Liu)
6.	Let the sequence be {an} and let Sn denote the sum of all the terms
up to but not including an. For n > 2002, an is a divisor of Sn.
Hence there exists a positive integer dn such that an =	.
Then
q _____ Q ,	__ + tySn
— ijn -r an —
dn
If dn+i > dn + 1, then
Sn _
&n+l —	7	—
and this contradicts the hypothesis that {an} is strictly increasing.
Hence {dn} is non-increasing for n > 2002.
However, this sequence cannot maintain a value к > 1 indefinitely
as otherwise {>Sn} becomes a geometric progression with common
ratio starting from some term.
However, к and к + 1 are relatively prime, and we can only divide
the first term of the geometric progression by к finitely many times.
It follows that dn — 1 eventually.
(A Liu)
7.	We use induction on the number n of domino pieces in the chain.
For n — 1 and 2, the result holds trivially. Consider the general
case where the first number is a. Let the first piece in the initial
chain be (a, 6) and that in the final chain be (a, c). If b — c, we can
appeal to the induction hypothesis.
Assume therefore that b c. Then the piece (a, 6) is now further
down the chain. If it has been reversed to (6, a), we simply take
the sub-chain from (a, c) to (6, a) and reverse it. Then we appeal
to the induction hypothesis.
Assume therefore that (a, b) has not been reversed. Then b a
and the final chain looks like
(a, c),..., (d, a), (a, 6),....
194
TOURNAMENT 23
From the final chain we can get (a,d),..., (c, a), (a, 6),... which we
will call chain X. The initial chain looks like (a, &),..., (a, c),....
If there is (d, a) inside it, then we can get chain X (using induction
as was noted above) and therefore the final chain. If there is (a, d)
inside the initial chain, we have two cases.
Case 1. The initial chain is (a, 6),..., (a, d),..., (a, c),....
Then the initial chain is (a, 6),..., (a, d),... ,.(e, a), (a, c),.... We
reverse the sub-chain from (a, d) to (e, a) and then we can obtain
chain X and therefore the final chain.
Case 2. The initial chain is (a, b),..., (a, c),..., (a, d),....
Then the initial chain is (a, b),..., (a, c),..., (e, a), (a, d),.... We
reverse the sub-chain from (a, c) to (e, a) and then we can obtain
the final chain.
(A Liu)
Senior Solutions
195
SENIOR SOLUTIONS
Autumn 2001 (0 Level)
1.	Let the pentagon be ABCDE. Let A', B', C, D' and E' be the
respective midpoints of CD, DE, EA, AB and BC. The median
AA1 is at least the length of the altitude from A, and since they
have the same length, AA' is also an altitude. Similarly, every
median is an altitude.
Now AA' = CC and /AA'C = 90° = /ССА. Hence triangles
АСА' and CAC are congruent, so that
CD = 2CA' = 2AC = EA.
Similarly,
EA = BC = DE = AB.
Hence ABCDE is equilateral. The congruency of АСА' and CAC
also yields /ACD = /ЕАС, and /ВСА = /CAB follows from
AB. = ВC. Hence /BCD = /ЕАВ, and it follows that ABCDE
is equiangular also. Hence it is regular.
(A Liu)
2.	The answer is yes.
Let P(n) be the number of prime numbers that is contained in
the block of 1000 consecutive postive integers n, n + 1,..., n + 999.
Then P(1001! + 2) = 0.
On the other hand, P(l) > 5. Since the difference between P(m)
and P(m+ 1) is at most 1, there exists a number к between 1 and
1001! + 2 such that P(k) — 5.
(A Liu)
196
TOURNAMENT 23
3.	See solution to Problem 4 in Junior paper.
4.	This is not always possible. The diagram below shows four congru-
ent triangles inside a square, each with a right angle, a blunt angle
and a sharp angle. The line joining the centre of the square to the
vertex of any sharp angle is blocked by the blunt angle of another
triangle. Thus the centre cannot belong to any convex polygon
containing exactly one of the triangles.
(A Liu)
5.	The answer is no.
At all times, the rooks occupy three of the four corners of a rectan-
gle. There are two kinds of moves. In the first, one dimension of
the rectangle is changed, but the rooks occupy the same corners as
before. In the second, a rook moves to the vacant corner from an
adjacent one. This does not change the cyclic order of the rooks.
Since the cyclic orders in the initial and final positions are different,
the task is impossible.
(A Liu)
Senior Solutions
197
Autumn 2001 (A Level)
1.	The answer is no.
Suppose all six vertices lie on a circle. We cannot have the red
vertices form an adjacent block and the blue ones another block, as
otherwise the two triangles will be disjoint. Hence two red vertices
Ri and R2 separate two blue vertices and B2 along the circle.
We may assume that they appear in the cyclic order Ri, B±, R2
and B2. The perpendicular bisectors of R^Bi, B1R2 and R2B2
intersect at the centre of the circle, dividing its inside into six re-
gions. Since О is inside both triangles, it is in one of these regions.
However, it is routine to verify that no matter which region it is
in, it is closer to one of B± and B2 than to one of R± and R2. This
is a contradiction.
(A Liu)
2.	The answer is yes.
We use an to denote the n-th term, even though its value may be
modified along the way. In step 1, we set agg = 9 and ащо = 10,
with Icmfygg, aioo) = 90. In step к > 1, define
o-ioo-fc — lOaioi-fc — 1
198
TOURNAMENT 23
and then redefine an for each n > 100 — к to be 10 times its former
value. Hence in step 2, we define
CI98 — 10o,99 — 1 = 89.
We also redefine 0,99 = 90 and ащо = 100. We have
lcm(a98,099) = 8010 > 900 = lcm(agg, аюо).
We continue until step 99 has been completed. Note that once we
have lcm(on_1, on) > lcm(on, an+1), this remains true thereafter
since in all subsequent modifications, each of an-i, an and an+i
is multiplied by the same number. We only have to check this
inequality when an-i is first introduced. At this point,
O'n— 1 — O"n	1 — dn-f-l
Now
10tln—1 > G>n —1 + 11 — Un+1
since an-i > 1. Hence
O'n—lj®n) 0"n—10"n + 1 ®n®n-|-l — lcm(o,n, ).
(A Liu)
3.	The answer is 88.
Since consecutive numbers occupy squares of opposite colours, we
may assume that all numbers on white squares are even and all
numbers on black squares are odd. The diagram below shows that
the sum may be as small as 1+3+5+7+9+11+13+39=88.
Senior Solutions
199
Suppose it is possible to improve on this. Assume first that the
diagonal in question contains odd numbers, then the largest would
have to be at most 37. Once this number is put down, we must
remain on the same side of this diagonal. There are exactly 16
white squares and 12 black squares on each side. However, there
are 13 odd numbers from 38 to 64 but we have at most 12 black
squares to accommodate them.
Similarly, if the diagonal in question contains even numbers, the
largest would have to be at most 30, and there are not enough
white squares on one side of the diagonal to accommodate the even
numbers greater than 30. Hence improvement over 88 is impossible.
(A Liu)
4.	The answer is 6.
Let the side lengths of Fi be a, b, c and d and the sums of the
opposite angles be x and y. Clearly the operation described in
the problem does not change the side lengths, and neither does it
change the sums of opposite angles.
Assume that we have 7 quadrilaterals in the sequence. Then with-
out loss of generality we can assume that there are two quadrilat-
erals F and G in the sequence that have side lengths a, 6, c and d
in order such that the sum of the angles between a, b and c, d is x
in each of F and G.
Let f be the length of the diagonal in F that leaves a and b on
one side of it, and c and d on the other side. If the corresponding
diagonal in G is longer then f then the sum of the angles of G on
opposite sides of this diagonal would be greater than x. It follows
that the diagonal in question in G has length / and therefore F
and G are congruent.
Thus the maximum number of non-congruent quadrilaterals in the
sequence {-FaJ is at most 6. To construct an example of a sequence
of length 6, just consider a quadrilateral with a, b, c, d all different
and x y.
(A Liu)
5.	Let m and к be the digit numbers of a and d respectively. Let t
be an integer such that t > m and t > k. Consider A = a + 10*d.
A must contain a block of successive digits that form 10*. Hence d
must end in digit 1 followed by at least m zeros.
Therefore к > m, and in the term B = n+(10* + l)d there is a
block of successive digits that form 10* + 1. This can only happen
200
TOURNAMENT 23
if the first digit of d is 1 followed by к — 1 digits which means that
d is a power of 10.
(A Liu)
6.	We shall show by induction that it is possible to get any permuta-
tion of the set 1,2,..., n by using the procedure described in the
problem.
If n = 1 or n = 2, the statement is obviously correct.
Now assume that the claim is correct for all к < n. Then we can
get any permutation of 1, 2,..., n — 1, and it suffices to show that
we get a permutation of 1,2,..., n where n changed its position.
If n is even, then n = 2m for some positive integer m. Then we
can apply the procedure to the numbers n and m.
If n is odd, then n = 2m + 1 for some positive integer m. By
applying the procedure to 2m + 1 and 2m, we get 4m and 1. Next
we use 4m and 2m — 1, and get 4m — 2 and 2m + 1. Then we use
4m — 2 and 2m — 2, and get 4m — 4 and 2m. Continuing in the
same manner, in the end we will get a permutation where 2m + 1
changed its position.
Thus the proof is completed.
(A Liu)
7.	(a) The answer is yes.
Consider a triangle such that the coordinates of its vertices
are (0,0), (|,|) and (|, |).
Then the area of this triangle is |, and it is easily checked that
no triangle whose vertices have coordinates (h, k), (|+/i, |+&)
and (| 4- h, | + k), where h and к are integers, has common
interior points with the original triangle.
(b) The answer is |.
Let ABC be any triangle with the desired properties.
Let D, E and F be the midpoints of BC, CA and AB respec-
tively.
Extend ED to G and FD to H so that ED = DG and FD =
DH.
We claim that integral translates of the hexagon BGHCEF
do not have common interior points. It will then follow that
its area is at most 1, and that the area of ABC is at most |.
Senior Solutions
201
This maximum is attained by the example in (a). Suppose
to the contrary that BGHCEF has a common point with an
integral translate B' G'H' СE'F'. We may assume that either
E' or F' is inside the quadrilateral BGHC.
There are three cases. If E' is inside triangle DBG, then В
will be inside the integral translate A'B'C! of ABC. Similarly,
if F' is inside triangle DCH, then C will be inside A'B'C.
Finally, if either E' or F' is inside triangle DGH, then A' will
be inside ABC. Since we have a contradiction in each of the
three cases, the claim is justified.
(A Liu)
202
TOURNAMENT 23
Spring 2002 (О Level)
1.	See solution to Problem 2 in Junior paper.
2.	Let M be the midpoint of AA' and N be the midpoint of CC.
Then A and A' are equidistant from MN, as are C and C. Let
A"B"C" be the reflection of ABC across MN.
Then A and A" are equidistant from MN, as are C and C". Hence
A'A" and CC" are both parallel to MN.
Now A"B"C" is congruent to ABC and opposite in orientation.
Hence it is congruent to A'B'C and in the same orientation. It
follows that A'B'C and A"B"C" may be obtained from each other
by a translation in the direction parallel to MN. Hence B' and B"
are equidistant from MN.
It follows that so are В and B', so that the midpoint of BB' indeed
lies on MN.
(A Liu)
3.	Let us assign numbers from 1 to 6 to the pieces of cheese in order
of their weights. The only possible groupings for the two groups
of three pieces to have equal weights are (126,345), (136,245),
(146,235), (156,234) and (236,145).
First weigh 146 against 235. If they balance, the task is accom-
plished. If 146 is heavier, then 156 will be heavier than 234. Then
we weigh 136 against 245. If they balance, the task is accomplished.
If 136 is heavier, then 236 will be heavier than 145. Hence 126 must
balance 345. If 136 is lighter, then 126 will be lighter than 345.
Senior Solutions
203
Hence 236 must balance 145. If in the first weighing 146 is lighter,
then 136 will be lighter than 245, 126 will be lighter than 345 and
145 will be lighter than 236. Hence 156 must balance 234.
(A Liu)
4.	The answer is 4904.
Consider a 2 x n table with two rows and n columns. Let F(n) be
the number of ways we can place the numbers 1 to 2n in this table
so that any two consecutive numbers are placed in squares with a
common side and 1 is in the first row and the first column.
If 2 is in the same row as 1, there is only one way to place the
remaining numbers. If 2 is in the same column as 1, there are
F(n — 1) ways to place the remaining numbers. So F(n) = F(n —
1) + 1 and clearly F(l) = 1. It follows that F(n) — n.
Now assume that 1 is in the zth column, where 1 < i < n. Then
if 2 is in the (i + l)th column, there are F(i — 1) ways to place
the remaining numbers, and if 2 is in the (i — l)th column, there
are F(n — i) ways to place the remaining numbers. Therefore the
number of ways to fill the table is
4(F(1) + F(2) + • • • + F(n - 2) + F(n))
= 4(1 + 2 4--------1- (n — 2) + n)
= 2(n — l)(n — 2) + 4n.
Hence for n = 50 the number of different placements is 2(n — l)(n —
2) + 4n = 4904.
(A Storozhev)
5.	The answer is yes.
The diagram below shows a net of regular triangular prism, and
how it can be covered without overlap by three equilateral triangles
of different sizes.
204
TOURNAMENT 23
(A Liu)
Senior Solutions
205
Spring 2002 (A Level)
1. First, note that we have
tan A + tan В + tan C
.	tan A + tan В
= tan A + tan В-----------------—
1 — tan A tan В
= (tan A + tan B) \ 1 — --------------— |
v	1-tanAtanB/
tan A + tan В .	_
=------------------— t an A t an В
1 — tan A tan В
= tan A tan В tan C.
Let tan A = a, tan В = b and tanC = c where a, b and c are
integers such that a + b + c = abc. ABC cannot be a right triangle.
Suppose Z A is obtuse. Then a is negative while b and c are positive.
But when a < 0 and b, c > 0, clearly b + c — abc > —a so a + b + c =
abc is impossible.
It follows that ABC is an acute triangle, so that a, b and c are all
positive. We may assume that a < b < c. Then abc = a+b+c < 3c,
so that ab < 3. We cannot have a = b = 1. Hence a = 1, b = 2 and
c = 3.
Finally, consider a triangle ABC with tan A = 1 and tan В = 2.
Then
tan A + tan В
tanC = — --------------— = 3,
1 — tan A tan В
therefore a triangle with tan A = 1, tan В — 2 and tan C = 3 does
exist.
(A Liu)
2. The answer is yes.
Consider the points A(a, a3) and B(b, b3 + b + 1) where a > b > 0.
We wish to choose a and b such that a—b < while a3 = 63+5+l.
Let t = a — b > 0. From (b + t)3 = b3 + b + 1, we have
3tb2 - (1 - 3t2)b - (1 - t3) = 0.
If t < -Aq , the constant term of this quadratic equation is negative,
so that it has one positive root and one negative root. Thus a and
b can be chosen so that AB <
(A Liu)
3. See solution to Problem 6 in Junior paper.
206
TOURNAMENT 23
4.	The answer is yes.
We use induction on the number n of spectators. The case n = 2
holds as a single switch fixes the derangement. Suppose the result
holds from 1 to n for some n > 1.
Consider the next case with n + 1 spectators. Let Sk denote the
spectator with the ticket k. Suppose Sn+i is in seat m for some m <
n. If the spectators in seats m to n + 1 constitute a derangement
among themselves, we can appeal to the induction hypothesis.
Otherwise, there exists a seat I which is the first after seat m to
be occupied by some Sx where x I — 1. This means that for
m < к < €, seat к is occupied by Sk-i-
We perform a chain of switches from seat £ back to seat m + 1,
we still have a derangement since Sk~i is now in seat к + 1 for
m < к < L This brings Sx to seat m + 1 and we can now switch
her with Sn+i, bringing the latter one seat closer to her correct
place.
We can now repeat the above process until Sn+i is in seat n + 1,
and then appeal to the induction hypothesis.
(A Liu)
5.	Since BCBiCi is cyclic, triangles ABC and ABiCi are similar.
The ratio of similarity is cos a where a = AC AB, since AB± =
AB cos a. Let О be the incentre and r the inradius of ABC, and
let T be the point of tangency of the incircle of AB±C± with AC.
Now OTb = r, OaT = r cos a, AT = АТв cos a, АТв = rcot^
and
ex,
ТТв = АТв — АТ = ATb(1 — cos a) = rcot —
a \
2 7
2 sin2
= r sina.
Senior Solutions
207
Hence
OATB = VOaT(i) 2 + TbT2 = r.
By symmetry, the other sides of the hexagon are also equal to r.
(A Liu)
6.	If two adjacent cards are of the same suit, we say that there is a
suit bond between them. If they are of the same rank instead, we
say that there is a rank bond between them.
By hypothesis, there is either a suit bond or a rank bond between
two adjacent cards, and it cannot be both since each card is unique
within a deck. So we have twelve columns each consisting of four
horizontal bonds, and three rows each consisting of thirteen vertical
bonds.
We claim that in each row and each column, the bonds are of the
same type. Assume to the contrary that there are both suit bonds
and rank bonds in a column. Then there is one of each kind in two
adjacent rows. Of the four cards in question, let the top two be the
Ace and King of Hearts.
The bottom two are of the same rank. If this rank is Ace, then
there is no bond between the King of Hearts and the card below.
Similarly, this rank cannot be King. Now not both cards at the
bottom can be Hearts. Hence one of them will not have a bond
with the card above.
This justifies our claim. Considering the types of bonds for each of
the three rows of vertical bonds, we have eight cases.
(i) All three rows are rank bonds. This yields the desired conclu-
sion.
(ii) All three rows are suit bonds. This means that the 52 cards
are in 13 groups of 4, with cards in the same group being of
the same suit. This is impossible since 13 is not a multiple of
4.
(iii) Only the top and bottom rows are suit bonds. This means
that we have 26 disjoint pairs of cards of the same suit. This
is impossible since 13 is not a multiple of 2.
(iv) Only the top and bottom rows are rank bonds. Consider the
13 inside pairs of cards in the second and the third rows, with
a suit bond between each pair.
We may assume that the first pair are Spades. There must be
a first pair which are not Spades, say Hearts. Consider first
208
TOURNAMENT 23
the case where the two outside cards in the first column are
of the same suit, which cannot be Hearts.
We may assume it is Clubs. Then the two outside cards on
the column with Hearts inside must be Diamonds. When the
inside pair change suits again, it must go from Hearts to either
Spades or Clubs. It follows that each column of 4 cards have
the same colour. However, there are 26 red cards and 26 is
not a multiple of 4.
Consider now the case where the two outside cards in the first
column are of different suits. Then they must be Diamonds
and Clubs. Then the two outside cards on the column with
Hearts inside must be Clubs and Diamonds.
It follows that all the Spades and Hearts form 13 inside pairs,
but there are 13 Spades and 13 is not a multiple of 2.
(v)	Only the top two rows are suit bonds. We may assume that
the top three cards in the first column are Spades and that
the bottom card is Clubs. This remains the case until we
encounter the first column of horizontal rank bonds. Then
the four cards in the next column must all be red. It follows
that the four cards in each column are of the same colour.
However, there are 26 red cards and 26 is not a multiple of 4.
(vi)	Only the bottom two rows are suit bonds. This is analogous
to Case (v).
(vii)	Only the top two rows are rank bonds. This means that there
are 3 cards of the same rank in each column. Since there are
only 4 cards of each rank, all 13 columns consist of different
ranks. Hence the first row of horizontal bonds are are suit
bonds, so that all columns of horizontal bonds are suit bonds.
This forces all the vertical bonds in the bottom row to be rank
bonds too, contrary to our assumption.
(viii)	Only the bottom two rows are rank bonds. This is analogous
to Case (vii).
(A Liu)
7.	The answer is yes.
Let a = л/б and b = л/З. Suppose |_amJ = \bn\ for some positive
integers m and n. Denote their common value by k. Then
k2 < 6m < k2 + 2k + 1
and
k2 < 3n < k2 + 2k + \.
Senior Solutions
209
It follows that
2k > |6m - 3n| = 3™|2™ - 3n“w|.
Clearly, n > m so that
1.
Hence 2k > 3m so that
qm
— <k2 < 6m.
4 —	“
Now the only positive integral values of m for which | < (|)m
holds are 1, 2 and 3. We have |_aj = 1, |_a2J = 6 and |_a3J = 14.
On the other hand, |_6J = 1, |_62J = 3, |_a3J = 5, |_a4J = 9 and
|_a5J = 15. It follows that	|_6nJ for any positive integers m
and n.
(A Liu)

GENERAL REFERENCES
1.	Andreescu T and Feng Z, 101 Problems in Algebra: From the Train-
ing of the USA IMO Team, AMT Publishing, Canberra, 2001.
2.	Artino RA, Gaglione AM and Shell N, The Contest Problem Book
IV, Mathematical Association of America, 1983.
3.	Atkins WJ, Problem Solving via the AMC, AMT Publishing, Can-
berra, 1992.
4.	Atkins WJ, Edwards JD, King DJ, O’Halloran PJ and Taylor PJ,
Australian Mathematics Competition, Book 1, 1978-1984, AMT
Publishing, Canberra, 1986 and 2000.
5.	Atkins WJ, Munro JEM and Taylor PJ, Australian Mathemat-
ics Competition, Book 3, 1992-1998, AMT Publishing, Canberra,
1998.
6.	Barbeau EJ, Polynomials, Springer-Ver lag, New York, 1989.
7.	Beckenbach EF and Bellman R, An Introduction to Inequalities,
Mathematical Association of America, 1961.
8.	Berzsenyi G and Maurer SB, The Contest Problem Book V, Math-
ematical Association of America, 1996.
9.	Burns JC, Seeking Solutions, AMT Publishing, Canberra, 2000.
10.	Chinn WG and Steenrod NE, First Concepts of Topology, Mathe-
matical Association of America, 1966.
11.	Coxeter HSM, Introduction to Geometry, John Wiley & Sons, New
York, 1961 and 1969.
12.	Coxeter HSM and Greitzer SL, Geometry Revisited, Mathematical
Association of America, 1967.
13.	Fomin D and Kirichenko A, Leningrad Mathematical Olympiads,
Mathpro Press, Westford, Massachusetts, 1994.
14.	Greitzer SL, International Mathematical Olympiads 1959-1977,
Mathematical Association of America, 1978.
15.	Grossman I and Magnus W, Groups and Their Graphs, Mathemat-
ical Association of America, 1964.
212
General References
16.	Gueron S, Hungary-Israeli Mathematics Competition: The First
Twelve Years, AMT Publishing, 2004.
17.	Henry JB, Dowsey J, Edwards AR, Mottershead LJ, Nakos A, Var-
daro G, Challenge! 1991-1995, AMT Publishing, 1997.
18.	Holton D, Let’s Solve Some Math Problems, Canadian Mathematics
Competition, Waterloo, Ontario, 1993.
19.	Honsberger R, From Erdos to Kiev, Mathematical Association of
America, 1996.
20.	Honsberger R, Ingenuity in Mathematics, Mathematical Assoc-
iation of America, 1970.
21.	Honsberger R, Mathematical Gems I, Mathematical Association of
America, 1973.
22.	Honsberger R, Mathematical Gems II, Mathematical Association
of America, 1976.
23.	Honsberger R, Mathematical Gems III, Mathematical Association
of America, 1985.
24.	Honsberger R, Mathematical Morsels, Mathematical Association of
America, 1978.
25.	Honsberger R, Mathematical Plums, Mathematical Association of
America, 1989.
26.	Honsberger R, Mathematical Chestnuts from Around the World,
Mathematical Association of America, 2001.
27.	Kazarinoff ND, Geometric Inequalities, New Mathematical Associ-
ation of America, 1961.
28.	Klamkin MS, International Mathematical Olympiads 1978-1985,
Mathematical Association of America, 1986.
29.	Klamkin MS, USA Mathematical Olympiads, 1972-1986, Math-
ematical Association of America, 1988.
30.	Kusczma ME, 144 Problems of the Austrian-Polish Mathematics
Competition 1978-1993, The Academic Distribution Center, Free-
land, Maryland, 1994.
31.	Kuczma ME and Windisbacher E, Polish and Austrian Mathemat-
ical Olympiads 1981-1995: Selected Problems with Multiple Solu-
tions, AMT Publishing, Canberra, 1998.
General References
213
32.	Larson LC, Problem Solving Through Problems, Springer-Verlag,
New York, 1983.
33.	Lausch H and Bosch Giral C, Asian Pacific Mathematics Olympiad,
1989-2000, AMT Publishing, Canberra, 2000.
34.	Lausch H and Taylor PJ, Australian Mathematical Olympiads 1979-
1995, AMT Publishing, Canberra, 1997.
35.	Lazarov B, Tabov JB, Taylor PJ, Storozhev AM, Bulgarian Mathe-
matics Competition, 1992-2001, AMT Publishing, Canberra, 2004.
36.	Liu A, Chinese Mathematics Competitions and Olympiads Book 1,
1981-1993, AMT Publishing, Canberra, 1997.
37.	Liu A, Chinese Mathematics Competitions and Olympiads, Book 2,
1993-2001, AMT Publishing, Canberra, 2005.
38.	Liu A, Hungarian Problem Book III: Based on the Eotvos Compe-
titions, 1929-1943, Mathematical Association of America, 2001.
39.	Niven Ivan, Mathematics of Choice - How to count without count-
ing, Mathematics Association of America, 1965.
40.	O’Halloran PJ, Pollard GH and Taylor PJ, Australian Mathematics
Competition, Book 2, 1985-1991, AMT Publishing, Canberra, 1992
and 1998.
41.	Ore O, Graphs and Their Uses, Mathematical Association of Amer-
ica, 1963, revised and updated by R Wilson 1990.
42.	Ore O, Invitation to Number Theory, Mathematical Association of
America, 1967.
43.	Plank AW and Williams NH, Mathematical Toolchest, AMT Pub-
lishing, Canberra, 1992 and 1996.
44.	Rabinowitz S, Index to Mathematical Problems 1980-1984, Math-
pro Press, Westford, Masachusetts, 1992.
45.	Rapaport E, Hungarian Problem Book I, Mathematical Association
of America, 1963.
46.	Rapaport E, Hungarian Problem Book II, Mathematical Assoc-
iation of America, 1963.
47.	Salkind CT, The Contest Problem Book, Random House, 1961.
48.	Salkind CT, The Contest Problem Book II, Random House, 1966.
214
General References
49.	Salkind CT and Earl JM, The Contest Problem Book III, Random
House, 1973.
50.	Schneider LJ, The Contest Problem Book VI, Mathematical Asso-
ciation of America, 1998.
51.	Sharygin IF, Problems in Plane Geometry, Mir, Moscow, 1988.
52.	Sharygin IF, Problems in Solid Geometry, Mir, Moscow, 1986.
53.	Slinko AM, USSR Mathematical Olympiads 1989-1992, AMT Pub-
lishing, Canberra, 1997.
54.	Tabov JB and Taylor PJ, Methods of Problem Solving, Book 1,
AMT Publishing, Canberra, 1996.
55.	Tabov JB and Taylor PJ, Methods of Problem Solving, Book 2,
AMT Publishing, Canberra, 2002.
56.	Taylor P J, International Mathematics Tournament of Towns, Prob-
lems and Solutions, Book 1, 1980-1984, AMT Publishing, Can-
berra, 1993.
57.	Taylor P J, International Mathematics Tournament of Towns, Prob-
lems and Solutions, Book 2, 1984-1989, AMT Publishing, Can-
berra, 1992.
58.	Taylor P J, International Mathematics Tournament of Towns, Prob-
lems and Solutions, Book 3, 1989-1993, AMT Publishing, Can-
berra, 1994.
59.	Taylor PJ and Storozhev A, International Mathematics Tourna-
ment of Towns, Problems and Solutions, Book 4, 1993-1997, AMT
Publishing, Canberra, 1998.
60.	Yaglom IM, Geometric Transformations, Mathematical Associa-
tion of America, 1962.
61.	Yaglom IM, Geometric Transformations II, Mathematical Associ-
ation of America, 1968.
62.	Yaglom IM, Geometric Transformations III, Mathematical Associ-
ation of America, 1973.

Tournament of Towns is an international
mathematics problem solving competition.
Small and large towns are able to participate
on an equal basis due to a democratic
formula which takes into account the town’s
population. The Tournament commenced
in the USSR in 1980 and has become
one of the most significant international
competitions. It is the only one at this
level available for students to write in their
home town.
The Tournament has attracted entries from
all parts of the world. This book is the fifth
in a series of books containing the official
versions of the problems and comprehensive
solutions by an international panel of
mathematicians which includes Andy Liu
of Canada.
Andrei Storozhev is a Research Officer at the
Australian Mathematics Trust. He gained his
PhD at Moscow State University specializing
in combinatorial group theory. He is a
member of the Australian Mathematics
Competition Problems Committee, Aust-
ralian Mathematics Olympiad Committee
and one of the editors of the journal
Mathematics Contests — The Australian
Scene.
The Australian Mathematics Trust
Enrichment Series