TOURNAMENT OF TOWNS
1993 - 1997
QUESTIONS AND SOLUTIONS
DEDICATED TO THE MEMORY OF NB VASS1L1EV
PJ TAYLOR a AM STOROZHEV
Published by
Australian Mathematics Trust
Australian Mathematics Trust
University of Canberra ACT 2601
AUSTRALIA
Copyright ® 1998 Australian Mathematics Trust
Telephone: +61 2 6201 5137
AMTOS Pty Ltd ACM 058 370 559
National Libraiy of Australia Card Number and ISSN
Australian Mathematics Trust Enrichment Series ISSN 1326-0170
Tournament of the Towns 1993-1997
ISBN 1 876420 03 0
The Australian Mathematics Trust
Enrichment Series
Editorial Committee
• Chairman
Graham H Pollard, Canberra Australia
• Editor Peter J Taylor, Canberra Australia
Warren J Atkins, Canberra Australia
Ed J Barbeau, Toronto Canada
George Berzsenyi, Terra Haute USA
Ron Dunkley, Waterloo Canada
Walter Е Mientka, Lincoln USA
Nikolay Konstantinov, Moscow Russia
Andy Liu, Edmonton Canada
Jordan В Tabov, Sofia Bulgaria
John Webb, Cape Town South Africa
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	All the Best from the Australian Mathematics Competition
JD Edwards, DJ King, PJ O’Halloran
2	Mathematical Toolchest
AW Plank & MH Williams
з Tournament of Towns questions and solutions 1984-1989
PJ Taylor
4	Australian Mathematics Competition Book 2 1985-1991
PJ O’Halloran, G Pollard, PJ Taylor
5	Problem Solving Via the AMC
W Atkins
6	Tournament of Towns questions and solutions 1980-1984
PJ Taylor
7	Tournament of Towns questions and solutions 1989-1993
PJ Taylor
8	The Asian Pacific Mathematics Olympiad
H Lauscb
9	Methods Of Problem Solving Book 1
JB Tabov & PJ Taylor
10	Challenge! 1991-1995
JB Henry, J Dowsey, AR Edwards, LJ Mottersbead,
A Makos & G Vardaro
11	0 SSR Mathematical Olympiads 1989-1992
AM Slinko
12	Australian Mathematical Olympiads 1979-1995
H Lausch & PJ Taylor
13	Chinese Mathematics Competitions and Olympiads 1981-1993
A Liu
14	Polish Et Austrian Mathematical Olympiads 1981- 1995
ME Kuczma & E Windischbacher
15	Tournament of Towns questions and solutions 1993-1997
PJ Taylor & AM Storozbev
PREFACE
The International Mathematics Tournament of Towns has continued to
prosper during the period covered by this book, the fourth in the series. A
complete history of the Tournament is to be found in the earlier books,
particularly the first published book which covered the years 1984 to
1988.
Results of the Tournament can be found on the Australian Mathematics
Trust’s web site, whose URL is
http://www.amt.canberra.edu.au
This site gives all the contact details and information about how the
Tournament is organised. A perusal shows that the Tournament has
now grown to 99 towns, located in all corners of the earth.
The Problems Committee Chairman, Kolya Vassiliev, who had been the
pre-eminent Russian problems editor (and significant problem creator)
for decades, suddenly died in May 1998. Kolya was also for many years
the problems editor of the Journal Kvant. His loss is major and it is
difficult to imagine how his special style can be replaced by the cen-
tral committee. An obituary appears eleswhere in this book, which is
dedicated to his memory.
I would like particularly to acknowledge the work of my colleague, Dr
Andrei Storozhev, who took over from me the production of the problems
and solutions (and hence this book) about three years ago. Andrei is a
graduate of the Moscow State University and his presence in Canberra,
with his native Russian and history of mathematics enrichment classes
in Russia, has taken a considerable load off me.
In keeping with previous books in this series, authors of solutions have
been identified. Unfortunately, some records were not kept for solu-
tions of Tournament 17 and 18 problems and many solutions are not
acknowledged, although it is generally believed that the unacknowledged
solutions are due to Andy Liu and Andrei Storozhev.
It is also necessary to acknowledge Professor Andy Liu, who continues
to be the other great contributor to the English solutions, and hence
the solutions which appear in this book. Andy has also supplied great
support to the Russian organisers of the Tournament, particularly the
President of the Central Organising Committee, Nikolay Konstantinov.
Peter Taylor
Chairman, Australian IMTOT Committee
19 June 1998

CONTENTS
• PREFACE	V
• TOURNAMENT 15	
Junior Questions	3
Senior Questions	9
Junior Solutions	14
Senior Solutions	30
• TOURNAMENT 16	
Junior Questions	47
Senior Questions	52
Junior Solutions	56
Senior Solutions	70
• TOURNAMENT 17	
Junior Questions	87
Senior Questions	93
Junior Solutions	99
Senior Solutions	109
• TOURNAMENT 18	
Junior Questions	125
Senior Questions	130
Junior Solutions	136
Senior Solutions	1 50
• OBITUARY	
NB Vassiliev (1940-1998)	167

ОНх < ОН2 < ...<0

TOURNAMENT 15
JUNIOR QUESTIONS
Autumn 1993 (0 Level)
1.	We are given a hexagon with a number written on each of its sides
and vertices. Each number on a vertex is equal to the sum of the
two numbers on neighbouring sides. Assume all numbers of the
sides and one vertex number were erased. Is it possible to find out
the number that had been erased from a vertex?
(Folklore, 3 points)
2.	Vertices A, В and C of a triangle are connected with points A', Bf
and Cr lying in the opposite sides of the triangle (not at vertices).
Can the midpoints of the segments AA', BBf and CCr lie in a
straight line?	(Folklore, 3 points)
3.	A natural number A is given. One may add to it one of its divisors
d (1 < d < A). One may then repeat this operation with the new
number A -b d and so on. Prove that starting from A = 4 one can
get any composite number by these operations.
(M Vyalyi, 4 points)
4.	Three players Alexander, Beverley and Catherine participate in a
tournament (all of them play the same number of games with each
other). Is it possible that Alexander gets more points than the
others, Catherine gets less points than the others, but Alexander
has a smaller number of wins than the others and Catherine has a
greater number of wins than the others? (A win scores 1 point, a
draw scores |.)	(A Rubin, 5 points)
4
TOURNAMENT 15
Autumn 1993 (A Level)
1.	10 integers are written in a row. A second row of 10 integers is
formed as follows: the integer written under each integer A of the
first row is equal to the total number of integers that stand to the
right side of A (in the first row) and are strictly greater than A. A
third row is formed by the same way under the second one, and so
on.
(a)	Prove that after several steps a “zero row” (i.e. a row consist-
ing entirely of zeros) appears.
(2 points)
(b)	What is the maximal possible number of non-zero rows (i.e.
rows in which at least one entry is not zero)?
(S Tokarev, 2 points)
2.	The square PQRS is placed inside the square ABCD in such a
way that the segments AP, BQ, CR and DS intersect neither
each other nor the square PQRS. Prove that the sum of areas of
quadrilaterals ABQP and CD SR is equal to the sum of the areas
of quadrilaterals BCRQ and DAPS.	(Folklore, 3 points)
3.	Three angles of a non-convex, non-self-intersecting quadrilateral
are equal to 45 degrees (i.e. the last equals 225 degrees). Prove
that the midpoints of its sides are vertices of a square.
(V Proizvolov, 3 points)
4.	Diagonals of a 1 by 1 square are arranged in an 8 by 8 table (one
in each 1 by 1 square). Consider the union W of all 64 diagonals
drawn. The set W consists of several connected pieces (two points
belong to the same piece if and only if W contains a path between
them). Can the number of the pieces be greater than
(a)	15,	(2 points)
(b)	20?	(NB Vassiliev, 3 points)
5.	Let S(n) denote the sum of digits of n (in decimal representation).
Do there exist three different natural numbers n, p and q such that
n -b 5(n) = p + S(p) = q + S(q)l
(M Gerver, 6 points)
Junior Questions
5
6.	Construct a set of к integer weights that allows you to get any total
integer weight from 1 up to 55 grams even if some of the weights
of the set are lost. Consider two versions:
(a)	к = 10, and any one of the weights may be lost;	(4 points)
(b)	к = 12, and any two of the weights may be lost.
(D Zvonkin, 4 points)
(In both cases prove that the set found has the property required.)
6
TOURNAMENT 15
Spring 1994 (О Level)
1.	Construct a convex quadrilateral given the lengths of all its sides
and the length of the segment between the midpoints of its
diagonals.	(Folklore, 3 points)
2.	60 children participate in a summer camp. Among any 10 of the
children there are three or more who live in the same block. Prove
that there must be 15 or more children from the same block.
(Folklore, 4 points)
3.	Let О be a point inside a convex polygon A1A2 . -. An such that
/.OAiAn < ZOA1A2, ZOA2A1 < ZOA2A3, ..., ZOAn_iAn_2 <
OAn-iAn, ^OAnAn_i < ZOAnAi and all of these angles are
acute. Prove that О is the centre of the circle inscribed in the
- polygon.	(V Proizvolov, 4 points)
4.	Ten coins are placed in a circle, showing “heads” (the tails are
down). Two moves are allowed:
(a)	turn over four consecutively placed coins;
(b)	turn over four coins placed as XX OXX (X is one of the coins
to be turned over, О is not touched).
Is it possible to have all ten coins showing “tails” after a finite
sequence of such moves?	(A Tolpygo, 5 points)
Junior Questions
7
Spring 1994 (A Level)
1.	A schoolgirl forgot to write a multiplication sign between two 3-
digit numbers and wrote them as one number. This 6-digit re-
sult proved to be 3 times greater than the product (obtained by
multiplication). Find these numbers. (A Kovaldzhi, 3 points)
2.	Two circles intersect at the points A and B. Tangent lines drawn
to both of the circles at the point A intersect the circles at the
points M and N. The lines BM and BN intersect the circles once
more at the points P and Q respectively. Prove that the segments
MP and NQ are equal.	(I Nagel, 3 points)
3.	Each of the 450 members of a parliament gives a slap in the face to
exactly one of his colleagues. Prove that after that they can choose
a committee consisting of 150 members, none of whom has been
slapped in the face by any other member of the committee.
(Folklore, 3 points)
4.	Prove that among any 10 entries of the table
0	1	2	3	...	9
9	0	1	2	...	8
8	9	0	1	...	7
1	2	3	4	...	0
standing in different rows and different columns, at least two are
equal.	(A Savin, 4 points)
5.	Does there exist a convex pentagon from which a similar pentagon
can be cut off by a straight line?	(S Tokarev, 5 points)
6.	At each integer point of the numerical line a lamp with a toggle
button is placed. If the button is pressed, a lit lamp is turned
off, an unlit one is turned on. Initially all the lamps are unlit. A
stencil with a finite set of fixed holes at integer distances is cho-
sen. The stencil may be moved along the line as a rigid body, and
for any fixed position of the stencil, one may push simultaneously
all the buttons accessible through the holes. Prove that for any
stencil it is possible to get exactly two lit lamps after several such
operations.	(B Ginsburg, 5 points)
8
TOURNAMENT 15
7.	In a 10 by 10 square grid (which we call “the bay”) you are re-
quested to place ten “ships”: one 1 by 4 ship, two 1 by 3 ships,
three 1 by 2 ships and four 1 by 1 ships. The ships may not have
common points (even corners) but may touch the “shore” of the
bay. Prove that
(a)	by placing the ships one after the other arbitrarily but in the
order indicated above, it is always possible to complete the
process;	(5 points)
(b)	by placing the ships in reverse order (beginning with the small-
er ones), it is possible to reach a situation where the next ship
cannot be placed (give an example). (KN Ignatjev, 2 points)
Senior Questions
9
SENIOR QUESTIONS
Autumn 1993 (0 Level)
1.	Consider the set of solutions of the equation
2.3	2
X = z
in positive integers. Is it finite or infinite? (Folklore, 3 points)
2.	Points M and N are taken on the hypotenuse of a right triangle
ABC so that ВС = BM and AC = AN. Prove that the angle
MCN is equal to 45 degrees.	(Folklore, 3 points)
3.	Each of the numbers 1, 2,3,... 25 is arranged in a 5 by 5 table. In
each row they appear in increasing order (left to right). Find the
maximal and minimal possible sum of the numbers in the third
column.	(Folklore, 5 points)
4.	Peter wants to make an unusual die having different positive inte-
gers on each of its faces. For neighbouring faces the corresponding
numbers should differ by at least two. Find the minimal sum of
the six numbers.	(Folklore, 5 points)
10
TOURNAMENT 15
Autumn 1993 (A Level)
1.	Two tangents CA and CB are drawn to a circle (A and В being
the tangent points). Consider a “triangle” bounded by an arc AB
(the smaller one) and segments CA and CB. Prove that the length
of any segment inside the triangle is not greater than the length of
CA = CB.	(Folklore, 3 points)
2.	The decimal representation of all integers from 1 to an arbitrary
integer n are written one after another as such:
123... 91011... 99100... (n).
Does there exist n such that each of the digits 0,1,2,... 9 appears
the same number of times in the given sequence?
(A Andzans, 3 points)
3.	Consider the hexagon which is formed by the vertices of two equi-
lateral triangles (not necessarily equal) when the triangles intersect.
Prove that the area of the hexagon is unchanged when one of the
triangles is translated (without rotating) relative to the other in
such a way that the hexagon continues to be defined.
(V Proizvolov, 3 points)
4.	A convex 1993-gon is divided into convex 7-gons. Prove that there
are 3 neighbouring sides of the 1993-gon belonging to one such 7-
gon. (A vertex of a 7-gon may not be positioned on the interior
of a side of the 1993-gon, and two 7-gons either have no common
points, exactly one common vertex or a complete common side.)
(A Kanel-Belov, 6 points)
5.	Four frogs sit on the vertices of a square, one on each vertex. They
jump in arbitrary order but not simultaneously. Each frog jumps
to the point symmetrical to its take-off position with respect to the
centre of gravity of the three other frogs. Can one of them jump
(at a given time) exactly on to one of the others (considering their
locations as points)?	(A Andzans, 6 points)
6.	If it is known that the equation
ж4 -|- ax^ -F 2ж2 -|- bx -|- 1 = 0
has a (real) root, prove the inequality
a2 + b2 > 8.
(A Egorov, 8 points)
Senior Questions
11
Spring 1994 (0 Level)
1.	A triangle ABC is inscribed in a circle. Let Ai be the point dia-
metrically opposed to A, Aq be the midpoint of the side ВC and
A 2 be the point symmetric to Ai with respect to Ao; the points B2
and C2 are defined in a similar way starting from В and C. Prove
that the three points A2, B2 and C2 coincide.
(A Jagubjanz, 4 points)
2.	The sequence of positive integers 01,02,-•• is such that for each
n = 1,2,... the quadratic equation an+2x2 + an+i^ + on = 0 has
a real root. Can the sequence consist of
(a)	10 terms,	(2 points)
(b)	an infinite number of terms? (A Shapovalov, 3 points)
3.	A chocolate bar has five lengthwise dents and eight crosswise ones,
which can be used to break up the bar into sections (one can get a
total of 9 x 6 = 54 cells). Two players play the following game with
such a bar. At each move (the two players move alternatively) one
player breaks off a section of width one from the bar along a single
dent and eats it, the other player does the same with what’s left of
the bar, and so on. When one of the players breaks up a section
of width two into two strips of width one, he eats one of the strips
and the other player eats the other strip. Prove that the player
who has the first move can play so as to eat at least 6 cells more
than his opponent (no matter how his opponent plays).
(R Fedorov, 4 points)
4.	Ten coins are placed in a circle, showing “heads” (the tails are
down). Two moves are allowed:
(a)	turn over four consecutively placed coins;
(b)	turn over four coins placed as XXOXX (X is one of the coins
to be turned over, О is not touched).
Is it possible to have all ten coins showing “tails” after a finite
sequence of such moves?	(A Tolpygo, 4 points)
12
TOURNAMENT 15
Spring 1994 (A Level)
1.	Does there exist an infinite set of triples of integers x, y, z (not
necessarily positive) such that
x1 + y1 + z2 = x3 + y3 4- z3?
(NB Vassiliev, 3 points)
2.	Consider a sequence of numbers between 0 and 1 in which the next
number after x is 1 — |1 — 2ж|. (|ж| = x if x > 0, |ж| = ~x if x < 0.)
Prove that
(a)	if the first number of the sequence is rational, then the se-
quence will be periodic (i.e. the terms repeat with a certain
cycle length after a certain term in the sequence);
(2 points)
(b)	if the sequence is periodic, then the first number is rational.
(G Shabat, 2 points)
3.	At least one of the coefficients of a polynomial P(x) is negative.
Can all of the coefficients of all of its powers (Р(ж))п,п > 1, be
positive?	(0 Kryzhanovskij, 4 points)
4.	A point D is placed on the side ВC of the triangle ABC. Circles are
inscribed in the triangles ABD and ACD' their common exterior
tangent line (other than BC) intersects AD at the point К. Prove
that the length of AK does not depend on the position of D. (An
exterior tangent of two circles is one which is tangent to both circles
but does not pass between them.)	(I Sharygin, 5 points)
5.	Find the maximal integer M with nonzero last digit (in its decimal
representation) such that after crossing out one of its digits (not
the first one) we can get an integer that divides M.
(A Galochkin, 5 points)
Senior Questions
13
6.	Consider a convex quadrilateral ABCD. Pairs of its opposite sides
are continued until they intersect: BA and CD at the point P,
BC and AD at the point Q. Let К be the intersection point of
the exterior bisectors of the angles A and C of the quadrilateral,
L be the intersection point of the exterior bisectors of the angles
В and D of the quadrilateral, and M be the intersection point of
the exterior bisectors of the angles P and Q (the exterior bisector
of an angle X is the line passing through X and perpendicular to
its ordinary bisector). Prove that the points K, L and M lie on a
straight line.	(S Markelov, 5 points)
7.	Consider an arbitrary “figure” F (non convex polygon). A chord
of F is defined to be a segment which lies entirely within F and
whose ends are on its boundary.
(a)	Does there always exist a chord of F that divides its area in
half?	(3 points)
(b)	Prove that for any F there exists a chord such that the area
of each of the two parts of F is not less than 1/3 of the area
of F.	(3 points)
(c)	Can the number 1/3 in (b) be changed to a greater one?
(V Proizvolov, 2 points)
14
TOURNAMENT 15
JUNIOR SOLUTIONS
Autumn 1993 (0 Level)
1.	Consider the numbers before any erasure.
Colour the vertex numbers alternately red and blue. Then the sum
of the reds and the sum of the blues are both equal to the sum of
the side numbers.
So after erasure, a missing red or blue number can be recovered
(because red sum = blue sum).
(MS Brooks)
2.	Let A", B", CH, D, E and F be the respective midpoints of AAf,
BBr, CCf, ВС, CA and AB. Since Af lies between В and C, A”
lies between E and F. Similarly, B" lies between F and D, and
C" lies between D and E.
Since no line can intersect the perimeter of triangle DEF in three
points, A", B" and C" cannot be collinear.
(A Liu)
3.	Let N be any composite number and p any of its prime divisors.
Since N is composite, N > 2p > 4. We can obtain 2p from 4 by
adding 2s and N from 2p by adding ps.
(A Liu)
4.	Let Alexander, Beverley and Catherine play six games against one
another. All six games between Alexander and Beverley are draws.
Both Beverley and Catherine win three games against each other.
Alexander beats Catherine twice and loses once while drawing
Junior Solutions
15
three. So Alexander has 6.5 points, Beverley has 6 and Cather-
ine 5.5, while Alexander has 2 wins, Beverley has 3 and Catherine
4.
(A Liu)
16
TOURNAMENT 15
Autumn 1993 (A Level)
1.	(a) After the first row, all integers are non-negative. The last
integer on each row from the second row on must be 0, as
there are no integers to the right of the last integer in the
preceding row. The second last integer on each row from the
third row on must be 0, as there are only Os to the right of
the second last integer in the preceding row. Similarly, the
third last integer on each row from the fourth row on must be
0, and so on. It follows that the eleventh row must consist of
only Os.
(b) The following example shows that we may have as many as
ten rows each containing at least one non-zero integer.
8967452301
10 10 10 10 10
0403020100
4030201000
0302010000
3020100000
0201000000
2010000000
0100000000
1000000000
(A Liu)
2.	We use [ ] to denote area. Drop perpendiculars PT, QU, RV and
SW respectively from P, Q, R and S towards the perimeter of
ABCD, say with T on AB, U on ВС, V on CD and W on DA.
Let EFGH be the square with sides parallel to those of ABCD,
and with P on EF, Q on FG, R on GH and S on HE. Let K, L,
M and N be the fourth vertices of the rectangles ATPK, BUQL,
CVRM and DWSN.
Then [ATP] = [AKP], [BLQ] = [BUQ], [CVR] = [CMR] and
[РЖ5] = [DAS]. Triangles ESP, FPQ, GQR and HRS are all
congruent to one another, so that [FPQ]-h[PPS] = [FSP]-h[GQP]
and ES = FP = GQ = HR.
Junior Solutions
17
Now
PT + RV = AD - EH = AB - EF = QU + SW.
It follows that we have
[TPFL] + [VRHN] = [UQGM] + [WSEK].
Adding up all the equations on area,
[ABQP] + [CDSR] = [BCRQ] + [DAPS].
(A Liu)
3.	Let ABCD be the quadrilateral with angle BCD == 225°. Extend
BC to cut AD at O. Then О AB and OCD are both isosceles
triangles. It follows that a 90° rotation about О will map A into
В and C into £>, so that AC = BD and they are perpendicular to
each other.
Let P, Q, R and S be the respective midpoints of AB, BC, CD
and DA.
18
TOURNAMENT 15
Then PQ and RS are both parallel to AC and equal to half its
length, while QR and SP are both parallel to BD and equal to
half its length. It follows that PQRS is a square.
(A Liu)
4.	Both parts are answered in the affirmative. The diagram below
shows a case with 21 pieces. The dotted diagonals are isolated, all
others are connected.
Since there are 20 isolated diagonals, we have 21 pieces.
(A Liu)
Junior Solutions
19
5.	Let
n = 9 999 999 999 992,
p = 10000000000091
and q = 10000000000100.
Then each of
n + $(n), p + S(p) and q + S(q)
is equal to 10 000 000 000 102.
(A Liu)
6.	(a) Consider a sequence of objects whose respective weights are
the terms of the Fibonacci sequence, defined by /(1) — /(2) =
1 and f(n) = f(n — 1) -hf (n — 2) for n > 3. Suppose no object
is ever missing. We claim that for any integer w, 1 < w <
f(n + 2) — 1, there is a subset of the first n objects whose total
weight is w. We prove this by induction on n. For n = 1,
/(3) — 1 = 1, and the claim is trivial. Suppose it holds for
some n > 1. Consider the first (n + l)st object. By the
induction hypothesis, there is a subset of the first n objects
having total weight w, where 1 < w < f(n + 2) — 1. Adding
the (n + l)st object, we will have a subset of total weight w
for f(n + 1) < w < f(n + 2) - 1 + f(n + 1) = f(n + 3) - 1.
We have f(n + 1) < f(n + 2) — 1 and the claim is justified.
Suppose now that one arbitrary object may be missing.
We claim that for any integer w, 1 < w < /(n 4-1) — 1, there
is a subset of the first n objects whose total weight is w.
We prove this by induction on n. For n = 1, f(n + 1) — 1 = 0,
and the claim is trivial.
Suppose it holds for some n > 1. Consider the first n + 1
objects. If the (n-hl)st object is missing, then none of the first
n is, and we have already proved that there will be a subset
having total weight w for 1 < w < f(n + 2) — 1. Suppose the
(n + l)st object is not missing. By the induction hypothesis,
there is a subset of the first n objects, minus an arbitrary one,
having total weight w, where 1 < w < f (n + 1) ~ 1. Adding
the (n + l)st object, we have a subset of total weight w, where
/(n + 1) < w < f{n + 1) - 1 + f(n + 1) > /(n + 2) - 1.
This justifies our claim. It follows that if we take 10 objects
of respective weights /(1) = 1, f (2) = 1, /(3) = 2, /(4) = 3,
/(5) = 5, /(6) = 8, /(7) = 13, f(8) = 21, /(9) = 34 and
20
TOURNAMENT 15
/(10) — 55, we have a subset of total weight w for 1 < w <
/(11) — 1 — 88, even if an arbitrary object may be missing.
(b) Consider the sequence of objects whose respective weights are
the terms of a generalized Fibonacci sequence which is defined
by g(l) = g(2) = g(3) = 1 and g(n) = g(n - 1) + g(n - 3) for
n > 4. Suppose at most one arbitrary object may be missing.
Then for any integer w, 1 < w <^(n+2) — 1, we can prove as
in (a) that there is a subset of the first n objects whose total
weight is w. Suppose now that two arbitrary objects may be
missing.
We claim that for any integer w, 1 < w < #(n -h 1) — 1, there
is a subset of the first n objects whose total weight is w.
We prove this by induction on n. For n = 1, p(2) — 1 = 0 and
the claim is trivial.
Suppose it holds for some n > 1. Consider the first n + 1
objects. If the (n + l)st object is missing, then at most one
of the first n is, and we have already indicated that there will
be a subset having total weight w for 1 < w < g(n + 2) — 1.
Suppose the (n + l)st object is not missing. By the induction
hypothesis, there is a subset of the first n objects, minus two
arbitrary ones, having total weight w for 1 < w < g(n-hl) — 1.
Adding the (n + l)st object, we have a subset of total weight
w, where p(n 4~ 1) < w < p(n +1) — 1 +p(n +1) > g(n 4-2) — 1.
This justifies our claim. It follows that if we take 12 objects
of respective weights p(l) = 1, g(2) = 1, #(3) = 1, #(4) = 2,
£/(5) = 3, <?(6) = 4, g(7) = 6, g(8) = 9, g(9) = 13, (,(10) = 19,
#(11) = 28 and #(12) = 41, we have a subset of total weight
w, 1 < w < €/(13) — 1 = 59, even if two arbitrary objects may
be missing.
(A Liu)
Junior Solutions
21
Spring 1994 (0 Level)
1.	Let А, В, C and D be the vertices of a quadrilateral and let X and
Y be the midpoints of its diagonals AC and BD respectively.
If R is the midpoint of the side BC, then RY is parallel to CD and
half its length. Similarly, RX is parallel to AB and RX — ^AB.
Therefore, the triangle XYR is defined by the data.
So we may assume that we are given the angles between opposite
sides of the quadrilateral. Hence we can construct the triangle
DEA such that ED is parallel and equal to BC.
Similarly, we are able to construct the triangle EBA as EBCD is
a parallelogram. So we know the size of £DAB and can construct
the triangle ADB. Therefore, the whole quadrilateral ABCD can
be constructed.
(A Storozhev)
2.	Let us assume that there are no blocks with 15 or more children.
We denote by N the number of blocks with at least two children.
N cannot be any greater than 4 since otherwise we could easily
find 10 children no three of whom live in the same block.
If N is less than 4, then the total number of children living in the
big blocks cannot be greater than 14 x 3 = 42. It means that the
number of blocks with 1 child is at least 60 — 42 = 18 and again
we can pick 10 children any three of whom do not live in the same
block.
The remaining possibility is N = 4, in which case the number
of blocks with 1 child is at least 60 — 14 x 4 = 4 and we come
22
TOURNAMENT 15
to a contradiction with the terms of the problem, for example, by
picking 8 children from the big blocks and 2 children from the small
ones.
Thus our assumption was wrong.
(A Storozhev)
3.	Let Hm be the foot of the perpendicular from point О to the side
of the polygon. Since
= 90 ,
the quadrilateral	is cyclic.
Therefore,
and
ZO/fm_|_i/fm = ZOAm_|_iAm.
Since ZOAm+iAm < ZOAm+iAm+2, we have ZKm+1 < AHm in
the triangle ОЯтЯш+1, which implies that OHm < OHm^. Thus
we have
ОНг < OH2 < . • < OHn < OHr.
Hence
OHX = OH2 = ... = OHn,
which means that О is the centre of the circle inscribed in the
polygon.
(A Storozhev)
4.	Let the coins be numbered consecutively from 1 to 10. We define
the weight of the ith coin as 0 if the coin shows “heads” or i if it
shows “tails”.
Junior Solutions
23
Then we define the weight of the whole configuration of coins as the
sum of their weights. It is easily seen that both the allowed moves
do not change the remainder of the weight of the configuration
divided by 2.
Since the weight of the initial configuration is equal to 0 we can-
not achieve the configuration where all coins are showing “tails”
because the weight of the latter is equal to 1 4- 2 4- ... 4- 10 = 55,
which is an odd number.
(A Storozhev)
24
TOURNAMENT 15
Spring 1994 (A Level)
1.	Let x and у be the given numbers. Then we can interpret the
data in terms of an algebraic equation as 3xy = 1000a: + y. Since
two of the three terms of this equation are divisible by ж, у is to
be divisible by x. That is, у = nx for some integer n. Clearly,
1 < n < 9 as both x and у are 3-digit numbers. The equation
Зху = ЮООж -I- у can be reduced to 3xn = 1000 + n. Therefore n
is a divisor of 1000 and simultaneously 1000 + n is divisible by 3,
which means that n ~ 2, 5 or 8. If n ~ 5 or n = 8, then we have
5ж = 335 or 8ж = 336 and x cannot be a 3-digit number. So n = 2,
x — 167 and у = 334.
(A Storozhev)
2.	The angles AQB and AM В are subtended by the same arc hence
LAQB = LAMB. Similarly, LAPB = LANB. Therefore, the
triangles AQN and AMP are similar. So the problem will be
solved if we show that AN = AP.
To show that AN = AP, we prove that LANP = LAPN. We
have LAPN = LABN as they are subtended by the same arc. But
LABN is an exterior angle of the triangle AQB whence LABN =
LAQB + LQAB. Thus LAPN = LB AN + LQAB = LQAN.
On the other hand, LAN P = LAN В -I- LBNP. By the alter-
nate segment theorem LAN В = LMAB. We also have LBNP =
LBAP because they are subtended by the same arc. So LANP =
LMAB + LBAP = ШАР.
Junior Solutions
25
But AQAN = ШАР as the triangles QAN and MAP are similar.
Hence AAPN = A AN P and thus the assertion is proved.
(A Storozhev)
3.	Start a line with any member. Except for this first member, each
one in line has been slapped by the preceding one. Eventually,
we must come across a member who has slapped one already in
the line. Then all or part of the line closes up to form a slapping
circle. Let the members in the slapping circle wear red and green
shirts alternately. If their number is odd, the last member will
wear a yellow shirt. There may be members who have slapped
those wearing coloured shirts.
We put red shirts on those who have slapped members wearing
green, and green shirts on those who have slapped members wearing
red or yellow.
Suppose not all members are wearing coloured shirts, and yet the
set of those who do cannot be enlarged. Move them aside and
look for another slapping circle as before among the remaining
members. Eventually all 450 members will be wearing red, yellow
or green shirts. By the Pigeonhole Principle, at least 150 of them
will be wearing shirts of the same colour. These members cannot
have slapped one another.
Remark: The result cannot be improved. We may have 150 slap-
ping circles with 3 members in each. Then for each of red, yellow
and green, exactly 150 members are wearing shirts of that colour.
(A Liu)
4.	Let us consider 10 entries of the table standing in different rows
and different columns and let ij be the number of the column of the
entry in the г-th row. Assuming that these entries are all different,
we see that all the differences (i — ij) have different residues modulo
10. Therefore, the sum
(1 — 21) + (2 — 22) + . . - + (10 — 2io)
= 0+1 + ... + 9
= 5 (mod 10)
But simultaneously,
(1 — 2i) + (2 — 22) + ... + (10 — 210)
= (1 + 2 + ... + 10) — (21 + 22 + .. * + iio)
= 0
26
TOURNAMENT 15
as all ij are different. So we have come to the conclusion that 0 = 5
(mod 10) which is not true.
(A Storozhev)
5.	Alternative 1
In this solution we will call a “special” pentagon a pentagon whose
sides are parallel to the sides of a regular pentagon. It is easily seen
that if three consecutive sides of one special pentagon are respec-
tively equal to three consecutive sides of another special pentagon,
then these two special pentagons are congruent. In particular, if
three sides of a special pentagon are proportional to three consecu-
tive sides of another special pentagon, then these special pentagons
are similar. Let us consider a special pentagon ABC DE such that
AB = a, BC = ka and CD = k2a where | < к < 1.
Since BC > CD, £DBC < £BDC. Hence IABD > AEDB.
Hence ED > AB. Therefore we can find on ED the point Ei
such that DEi = k3a. Thus the special pentagons ABC DE and
BCDEiAi (Ai on AB) are similar and the latter is cut off the
former by a straight line.
(A Storozhev)
Alternative 2
Let MAN be an equilateral triangle of side 1 4-t, where t < 1 is a
positive real number to be chosen later. Draw equilateral triangles
Junior Solutions
27
BAF, NBC and MED inside ABC, with В on AN, C and D on
MN, and E and F on AM, where BF = 1, BC = t and DE = t3.
We choose t so that CD = BF-MD = t2. In other words, t is the
real root of/(t) = t3-H2 —1. Since f(0) = —1 and/(l) = 1, there is
such a t between 0 and 1. Moreover, EF = BC — ME — t — t3 = t4,
and EA = t4 -h 1. The convex pentagons ABCDE and BCDEF
have corresponding angles equal. In order for them to be similar,
we must have
AB _ BC _ CD _ DE _ EA
BC ~ CD ~ DE ~ ~EF ~ ~FB *
The common value of these ratios is obviously 1/t, provided that
t4 4-1 = 1/t This is indeed the case as
t5 +1 - 1 = (? - t + l)(t3 +t2 - 1) = 0.
We can obtain BCDEF from ABCDE with a straight cut.
(A Liu)
6.	To make the terms of the problem more algebraical, we regard the
lit lamps as Is placed at the corresponding point of the numerical
line and the unlit lamps as Os. Also, we consider the holes of the
stencil as Is and put Os at integer distances from the holes.
Now we describe an algorithm to obtain a configuration with only
two Is on the line.
First, we apply the stencil to the line with Os only. If we obtain a
configuration with only two Is, then we have finished our process.
28
TOURNAMENT 15
If it is not the case, we move the stencil to the right so that the first
1 of the stencil is at the same place as the second 1 of the configura-
tion and then use the stencil. If we do not succeed, we repeat this
operation. At each step, we obtain a configuration starting with 1,
then containing Os and ending at a sequence consisting of Is and
Os of length n — 1, where n is the length of the stencil. Since we
may do as many steps as necessary, we can find two configurations
with the same ending sequences.
Going back step by step, we come to the conclusion that at some
stage we had a configuration with the same sequence of the last
n — 1 digits as that of the stencil.
But according to the algorithm described above, such a configura-
tion might arise only if the previous one contained only two Is. So
at some stage, we must obtain a required configuration.
(A Storozhev)
7.	(a) Clearly we can place the 1x4 ship. On the bay, mark eight
1x3 ships that are parallel to each other and separated by
two cells. Of these eight marked ships, at most two can have
common points with the placed ship.
Hence we can place a 1 x 3 ship in the bay so that it does
not have common points with the 1x4 ship. Similarly, if we
have one 1x4 ship and one 1x3 ship, at most four of the
marked ships can have common points with the placed ships.
Therefore we can place another 1x3 ship in the bay so that
it does not have common points with the placed ships.
Now assume that we have already placed one 1x4 ship, two
1x3 ships and less than three 1x2 ships. Mark twelve 1x2
ships that are parallel to each other and separated by two cells.
Then there are at most ten marked ships that have common
points with the placed ships. Therefore we can place one more
1x2 ship in the bay.
Finally, assume that we have placed one 1x4 ship, two 1x3
ships, three 1x2 ships and less than four lxl ships in the
bay. Mark sixteen lxl ships that are separated by two cells.
Then there are at most 15 marked ships that have common
points with the placed ships. Hence we can place one more
lxl ship in the bay.
(b) One of many possible configurations is shown on the following
Junior Solutions
29
picture.
Clearly there is no room for a 1 x 4 ship.
(A Liu)
30
TOURNAMENT 15
SENIOR SOLUTIONS
Autumn 1993 (0 Level)
1.	Alternative 1
We rewrite the equation as
2	2
z — x =
Set z + x = y2 and z — x = y. Then
are both integers for any integer y. Hence the original equation has
infinitely many positive solutions in integers.
(A Liu)
Alternative 2
Since I2 + 23 = З2, (&3, 2k2, 3/c3) is a solution to x2 4- y3 = z2 for
every positive integer k. Hence the equation has infinitely many
solutions in positive integers.
(Anthony Fok)
2.	Since ВС = BM and AC = AN, LBMC = 90° - B/2 and
LANC = 90° — A/2.
Hence
IMCN = 180° - /BMC - /ANC = ^A+nB>l = 45°.
2
(A Liu)
Senior Solutions
31
3.	Let the number in the i-th row and 7-th column be denoted by
а(г, j).
We are given that a(i,j) < a(i, k) whenever j < k. We may assume
that а(г,3) < a(/c,3) if i < k. The maximum value of a(5,3) is 23
since a(5,3) < a(5,4) < a(5, 5). The maximum value of a(4,3) is
20 since a(4, 3) < a(4,4) < a(4, 5) and a(4, 3) < a(5,3). Similarly,
the maximum values of a(3, 3), a(2, 3) and a(l, 3) are 17, 14 and 11
respectively. It follows that the sum of the five numbers in column
three is at most
23 + 204- 17+ 14+ 11 = 85.
Using an analogous argument, we can show that the sum is at least
3 + 6 + 9 + 12 + 15 = 45.
Both are attainable as shown below.
1	6	11	12	13	1	2	3	16	21
2	7	14	15	16	4	5	6	17	22
3	8	17	18	19	7	8	9	18	23
4	9	20	21	22	10	11	12	19	24
5	10	23	24	25	13	14	15	20	25
(A Liu)
4.	Peter cannot use three consecutive numbers n — 1, n and n + 1,
since both n — 1 and n + 1 have to be on the face opposite to the
face on which n is.
It follows that the best Peter can do is to use 1, 2, 4, 5, 7 and 8,
by putting the consecutive numbers on opposite faces. Hence the
minimum sum of the six numbers is 27.
(A Liu)
32
TOURNAMENT 15
Autumn 1993 (A Level)
1.	Let d — CA — CB. We may assume that the segment inside
the curved triangle has both endpoints on its perimeter. If one
endpoint is A or B, the other can only be C, and its length is d.
Suppose the segment is CF with F between A and В on the given
circle. Since this segment is inside the circle with centre C and
radius d, CF < d.
Suppose the segment is DE with D on BC and E on CA. We
may assume that it is tangent to the given circle at a point F.
Otherwise, a parallel displacement of DE towards the given circle,
with D staying on ВC and E on CA, will increase its length. We
now have
2DE = DF + FE + DE<DB+EA + CD+CE = 2d
or DE < d.
Senior Solutions
33
Finally, suppose the segment is EF with E on CA and F on the
arc AB. Perform a parallel shift of EF towards C to EfF', with
Ef on AC and F' on the arc AB, until either E' = C or E'Ff
is tangent to the given circle (as shown in the diagram above).
In the first case, we have EF < CF' < d. In the second case,
EF < E'Ff < EfD' < d, where D' is the point of intersection of
E'F' with BC.
(A Liu)
2.	Let a(n), b(n) and c(n) denote the respective numbers of Os, Is
and 9s in the collection of the digits of the integers from 1 to n. If
n — 10m — 1 for some positive integer m, we have d(n) = c(n) by
symmetry.
As n moves on to 10m, 10^m+1\ and so on, b(n) will move ahead,
and c(n) cannot catch up until we reach n —	— 1. It follows
that b(n) = c(n) if and only if n — 10m — 1 for some positive integer
m. Had we started with 0 instead of 1, and fill in the leading Os so
that every number has m digits, we would have a(n) = b(n) = c(n)
at this point by symmetry. Since this is not the case, a(n) is less
than b(n) = c(n). It follows that there does not exist a positive
integer n for which a{n) = b(n) = c(n).
(A Liu)
3.	We use [ ] to denote area. Let О be a point inside both ACE and
BDF such that when it is translated to O' along with B'D'F1, O'
is still inside ACE.
Let x be the angle between AC and BO. Then it is also the angle
between AC and B'O'.
34
TOURNAMENT 15
Hence
[OABC] = ||OB|.|AC'|sina:= ||O'B'|.|AC| sinz = [О'АВ'С}.
Similarly, we have
[OCDE] = [O'CD'E]
and
[OEFA] = [O'EF'A].
Adding these together,
[ABCDEF] = [AB'CD'EF'].
(Murray Klamkin)
4.	Let n be the number of 7-gons. Let v and e be respectively the
numbers of vertices and edges in the interior of the 1993-gon. The
7-gons among them have 7n sides. Each side of the 1993-gon con-
tributes 1 to this total, while each interior edge contributes 2.
Hence 7n = 1993 4- 2e.
The sum of the angles of the 7-gons is 5n?r. The sum of the angles
of the 1993-gon is 1991тг, while that around each interior vertex is
2тг. Hence 5n = 1991 4- 2v.
Eliminating n from these two equations, we have 14v 4-3972 — lOe.
Let b be the number of vertices of the 1993-gon incident with at
least 1 interior edge. Since the 7-gons are convex, each interior
vertex is incident with at least 3 interior edges. It follows that
2e > 3v 4- b, so that 3972 > 56 4- v > 56 or b < 794.
Senior Solutions
35
If no 3 consecutive sides of the 1993-gon belong to the same 7-gon,
at least every other vertex must be incident with at least 1 interior
edge. This would mean that b > 997, which is not the case. Hence
some 3 consecutive sides of the 1993-gon belong to the same 7-gon.
(A Liu)
5.	We may assume that no frogs jump twice in succession, as two
such jumps clearly cancel each other. Let (ж(г,п), t/(i,n)) be the
positions of the г—th frog after the n-th jump. We may take
O(i.o),j,(i>o)) = (i,i),
0(2,0), y(2,0)) = (1,2),
(a?(3, 0), 2/(3, 0)) = (2,1)
and (a?(4,0), ?/(4,0)) = (2,2).
Suppose the (n 4- l)st jump is taken by the fourth frog. Then we
have
x(i, n + 1) = x(i, n) and y(i, n + 1) = y{i, n)
for 1 < i < 3, while
(2x(l, n) 4- 2x(2, n) 4- 2x(3, n) — Зж(4, n))
ж(4, n 4-1) = -----------------------------------------
о
and
, 1\	(2y(l, n) + 22/(2, n) +22/(3, n) - 32/(4, n))
We claim that for all n 1, if the j-th frog has just jumped,
then x(j,n) and are of the form m/3n for some integer m
not divisible by 3, while x(i,ri) and i j, are of the form
k/3^n~^ for some integer k. It will then follow that no frogs will
ever land on top of another.
We shall justify our claim by induction on n. The case n = 1 is
trivial.
Suppose it holds for some n > 1. We may assume that the first
frog has taken the n-th jump, and the fourth one is going to take
the (n 4- l)st jump. Then x(i,n 4- 1) and y(i,n 4- 1), 1 < i < 3,
are all of the form к/Зп for some integer k. On the other hand,
2ж(1,п)/3 is of the form m/3^n+1\ m not divisible by 3, while
(2x(2, n) 4- 2x(3, n) — 3x(4, n))
3
36
TOURNAMENT 15
is of the form fc/3n. Hence ж (4, n 4-1) is also of the form m/^n+1\
m not divisible by 3, as is ?/(4, n 4-1). This completes the inductive
argument.
(A Liu)
6.	Alternative 1
Let r be a real root of the equation. We then write the equation as
ar2 4- b =
r
By Cauchy’s Inequality,
(r4 4- l)(a2 4- b2) > (ar2 4- b)2.
Hence
a2 4-b2
r2(r4 4- 1)
(r8 4- 2r4 4-14- 4r4 4- 4r6 4- 4r2)
(r4 4- 1)	4r2
----9-----b ------TV "b
r% (r4 4- 1)
4 4-4
by the Arithmetic-Mean Geometric-Mean Inequality.
(Murray Klamkin)
Alternative 2
Any real quartic is the product of two real quadratics. Write
ж4 4- ax3 4- 2x2 4- bx 4- 1 = (x2 4- px 4- 7) (x2 4- sx 4-1)	(1)
where p.q^s.t are real. By assumption at least one of the quadrat-
ics, say the second, has a real root. So s2 > 4t. Equating coeffi-
cients in (1) gives
a = p 4- s;
2 = q + t+ps;
b = pt 4- qs\
1 = qt.
Senior Solutions
37
So
a2 + b2 = p2 + s2 + 2ps + p2t2 + q2s2 + 2ptqs
= p2(l + t2) + s2(l + q2) + 4ps
> p2(l +12) +4(t + g +ps)
> 8.
(MS Brooks)
Alternative 3
The set of “points” (a, b) in consideration is the set of all the points
on the family of lines
r x -h ry — —\r -h 1)
where r is a real parameter. The minimum value of a2 4- b2 is thus
the square of the distance from the origin to the closest of these
lines; i.e.
By calculus the minimum occurs when
(r6 4- r2)4(r2 4- l)32r — (r2 4- l)4(6r5 4- 2r) = 0
(note that r cannot be zero). Simplification gives
2r(r2 4-l)3(r2 — I)2 = 0.
So r2 = 1 and the minimum value is 24/2 = 8.
(MS Brooks)
Alternative 4
If x is a root then x 0 and
x2 4- ax 4- 2 4-1--~ = 0.
x x£
That is,
Since x is real the LHS is non-negative, so that
a2 4- b2 > 8.
(D Paget)
38
TOURNAMENT 15
Spring 1994 (О Level)
1.	Clearly, A1B1 is parallel and equal to AB and AqBq is parallel to
and has half the length of AB.
A
Ai
So the segments AiAq and BiBo produced meet at the point that
is symmetric to Ai and B± with respect to Ao and Bq respectively.
It means that the points A% and B% coincide. Similarly A2 and C2
coincide, hence all the points A2, В2 and C2 coincide.
(A Storozhev)
2.	The fact that the quadratic equation an+2X2 -h an+ix 4-an = 0 has
a real root implies the inequality a^+1 > 4an+2«n- It means that
bn+i > 4&n where bm —	Therefore, bm > 4m-1b1 and
hence
— = M2 • • • bk > 4l+2+-+(*-l)b* = (2*=-lbl)*= .
Thus afc+i < ai/(2fe-1di)A:. So however large ai is and no matter
how small is, we can find к such that ajt+i < 1 which is impossi-
ble because a^+i is a positive integer. Thus there does not exist a
sequence consisting of an infinite number of terms. To produce a se-
quence of 10 terms that fits the data, we just put аю = 1, ад = 49,
«8 = 49+8, «7 = 49+8+7, ..., «2 = 49+8+-+2, ar = 49+8+-+1.
(A Storozhev)
3.	To eat exactly 6 cells more than his opponent, the first player breaks
off a section of the 6x1 type and then just repeats all moves of
the second player.
(A Storozhev)
4.	See the solution to Question 4 of the Junior О level paper.
Senior Solutions
39
Spring 1994 (A Level)
1. Let у — —x. Then the equation becomes x3 = x2 4- 2г/2. We define
у = mx. It yields x ~ 1 4- 2m2. Since m may be any integer, the
equation given has an infinite set of solutions.
(A Storozhev)
2. (a) Let the first number of the sequence be rational. Then it
can be represented in the form mi/n where 0 < mi < n.
The number 1 — |1 — 2mi/n| also can be represented in the
form mz/n where 0 < m2 < n. Thus we have a sequence
of numbers mi, m2,... such that 0 < mi < n for every i —
1,2,.... Therefore, we can find in this sequence two equal
terms. It implies that the sequence mi, m2,... is periodic and
hence the sequence mi/n,m2/n,... is too.
(A Storozhev)
(b) If the sequence is periodic, then there is a number x in the
sequence such that x is the solution of a linear equation у =
a 4- bx where b Ф 1 and a, b are integers. Therefore x is a
rational number. Let у be the first number in the sequence.
Then у is the solution of a linear equation d 4- cy = x where
c 0 and d, c are integers. Hence у is rational too.
(A Storozhev)
3. We consider the polynomial Q(x) = 1 4- x 4- x3 4- x4 *. It is easily
seen that all coefficients of the polynomials (Q(x))2 and (Q(x))3 are
greater than or equal to 1. Let N be the greatest of all coefficients
of Q(x) and (Q(x))2. We can find a number к such that 10fe > 4A.
Now we put P(x) — Q(x) — 10-fex2. Then
(P(x))2 = (Q(x))2 - 2Q(z)10“*:z2 4- 10“2V
and
(P(x))3 - (Q(x))3 - 3(Q(z))210“S;2 4- 3Q(X)10“2M - 10"3/cx6
and hence all coefficients of (P(x))2 and (P(x))3 are positive.
Therefore all of the coefficients of all powers (P(x))n are positive.
(A Storozhev)
40
TOURNAMENT 15
4.	Let Ai, Ci, Di and Л2, B2, P2 be the points of contact of the
circles and corresponding sides of the triangles ACD and ABD.
Let AC — b, AB = c, BD = u, DC = v and AD = d. Let G and
H be the points of contact of the circles, inscribed in the triangles
ACD and ABD respectively, and their common exterior tangent
other than BC. (In the diagram, Z>2, H, Ci and G have been
shown by bullets to emphasise their distinct locations.)
Then
2AK
(AC1-GK) + (AB2-HK)
AC1 + AB2-GH
ADi 4- j4Z)2 — ?1ij42
ADi AD2 — DAi — DA2.
But
and
Therefore
2AK
b + d — v + c + d — u — d — v + b — d — u + c
2
b -h с — и — v
AC +AB - BC
Senior Solutions
41
Hence the length of AK does not depend on the position of D.
(A Storozhev)
5.	We can represent M in the form M = 10nX 4- 10mY 4- Z where
the digits of M are the digits of X, Y and Z taken consecutively.
After crossing out the digit Y in the decimal representation of M,
we get the number N = 10n~xX 4- Z. Since N divides M, the
number M ~ 10A is divisible by N. Therefore, X must be a one
digit number as otherwise M — 10A < N which would mean that
M = 10A and hence the last digit of M would be zero.
So M = 10nX + 10n-xY 4- Z where 1 < X < 9 and 0 < Y < 9.
Clearly, 2 < M/N < 19, hence 1 < (M - N)/N < 18.
But M — N = (9X 4- Y)10n-x and M — N is divisible by N so
N = ab where a divides 9X 4- Y and b divides 10n-x.
As the last digit of N is non-zero, b can be a power of 2 or 5 only.
Therefore, 10n"1/5n"1 < 18 or 10n~1/2n-1 < 18 hence n - 1 < 4.
Thus if we find the maximal six digit number in question, we will
solve the problem.
Let n — 5, then b = 54 and a = 9X 4- Y since otherwise (M —
N)/N > 20. Hence 625(9X 4-Y) > 104X. Hence Y > 7X which
means that X = 1 and Y > 8. But a cannot be even because
the last digit of N is non-zero, therefore Y = 8. Since 180 625 =
17 x 10 625, the answer to the problem is 180 625.
(A Storozhev)
6.	Let the straight lines CK and Q M meet in G, A К and MP in G\
CK and DL in Я, AK and BL in H', QM and DL in F, PM and
BL in Ff. Clearly F is an excentre of the triangle QDC.
Hence CF bisects the angle DCB. Similarly CF! bisects the angle
DCB. Hence FFf passes through C and bisects the angle DCB.
Similarly GG' passes through D and bisects the angle ADC; and
HH' passes through Q and bisects the angle CQD.
Therefore FF', GG' and HH' pass through an excentre of the
triangle QDC.
42
TOURNAMENT 15
Thus FF', GG' and HH' are concurrent which means that the
triangles FGH and F'G'H' are perspective from a point.
Hence by Desargues’s theorem К, L and M are collinear.
7.	(a) Let ABC be an equilateral triangle, D, E and F be the re-
spective midpoints of BC, CA and AB, and О be the centre
of ЛВС.
Take the segments OD, DC, OE, EA, OF and FB together
with the infinite regions bound by the extensions of CA and
BA, of AB and CB, and of BC and AC.
Senior Solutions
43
This can be modified, as shown above, into a non-convex poly-
gon by enlarging the segments into narrow strips and truncat-
ing the infinite regions.
(A Liu)
(b) Let AB be a chord of F such that AB divides F into Fy and
F% so that the area of Fy is less than | of the area of F and
Fi contains the maximal possible number of vertices of F.
There exists a chord DC such that DC is parallel to AB and
DC divides F into F[ and F% so that F[ contains F± and the
number of vertices of F in F[ is the smallest possible with
respect to the restriction that it is greater than the number
of vertices of F in F±. Then ABCD is a trapezium such that
there are no vertices of F inside it. The area of F[ is greater
than | of the area of F.
Now assume that we cannot find a chord in question. We can
also assume that the sum of the areas of AB CD and F± is
less than | of the area of F. At least one of AD and BC is a
chord of F. Assume that AD is a chord. Then the part of F
that is cut off by BD and contains Fi covers more vertices of
F than Fi does.
Hence the area of this part is greater than | of the area of F.
Therefore its area is greater than | of the area of F. Hence
the area of the part of F that is cut off by AD and does not
contain Fi is greater than | of the area of F. Therefore its
area is greater than | of the area of F. Hence the area of the
other part is less than | of the area of F.
44
TOURNAMENT 15
Since this part contains more vertices of F than F± does, we
come to a contradiction.
(A Storozhev)
(c) By making the truncated portions sufficiently large, we can
show that the constant of 1/3 in (b) cannot be enlarged.
(A Liu)
н
^'А
A Q в

TOURNAMENT 16
JUNIOR QUESTIONS
Autumn 1994 (0 Level)
1.	Several boys and girls are dancing a waltz at a ball. Is it possible
that each girl can always get to dance the next dance with a boy
who is either more handsome or more clever than for the previous
dance, and that each time one of the girls gets to dance the next
dance with a boy who is more handsome and more clever? (The
numbers of boys and girls are equal and all are dancing.)
(AY Belov, 3 points)
2.	Two circles, one inside the other, are given in the plane. Construct
a point O, inside the inner circle, such that if a ray from О cuts the
circles at A and В respectively, then the ratio OA/OB is constant.
(Folklore, 3 points)
3.	Find five positive integers such that the greatest common divisor
of each pair is equal to the difference between them.
(SI Tokarev, 5 points)
4.	There are 20 pupils in the Backwoods school. Any two of them
have a common grandfather. Prove that there exist 14 pupils all of
whom have a common grandfather. (AV Shapovalov, 5 points)
48
TOURNAMENT 16
Autumn 1994 (A Level)
1.	Nuts are placed in boxes. The mean value of the number of nuts
in a box is 10, and the mean value of the squares of the numbers
of nuts in the boxes is less than 1000. Prove that at least 10% of
the boxes are not empty.	(AY Belov, 3 points)
2.	An 8 by 8 square is divided into 64 1 by 1 squares, and must be
covered by 64 black and 64 white, isosceles, right-angled triangles
(each square must be covered by two triangles). A covering is said
to be “fine” if any two neighbouring triangles (i.e. having a common
side) are of different colours. How many different fine coverings are
there?	(NB Vassiliev, 4 points)
3.	Two-mutually perpendicular lines I and m intersect each other at
a point of the circumference of a circle, dividing it into three arcs.
A point Mi (i = 1,2,3) is taken on each arc so that the tangent
line to the circumference at the point Mi intersects I and m in two
points at the same distance from Mi (that is Mi is the midpoint of
the segment between them). Prove that the triangle M1M2M3 is
equilateral.	(Przhevalsky, 4 points)
4.	From the sequence 1, |,	. can one choose
(a)	a subsequence of 100 different numbers,
(3 points)
(b)	an infinite subsequence	(SI Tokarev, 2 points)
such that each number (beginning from the third) is equal to the
difference between the two preceding numbers (аь = ak-2 ~ «fc-i)?
5.	The periods of two periodic sequences are 7 and 13. What is the
maximal length of initial sections of the two sequences which can
coincide? (The period p of a sequence • • • is the minimal p
such that an = an+p for all n.)	(AY Belov, 6 points)
6.	The sum of sixth powers of six integers minus 1 is six times greater
than the product of these six integers. Prove that one of them is 1
or —1 and all others are 0s.	(LD Kurliandchik, 6 points)
Junior Questions
49
7.	The figure F is the intersection of N circles (they may have differ-
ent radii). Find the maximal number of curvilinear “sides” which
F can have. Curvilinear sides of F are the arcs (of the given cir-
cumferences) that constitute the boundary of F. (Their ends are
the “vertices” of F — the points of intersection of given circumfer-
ences that lie on the boundary of F.)
(N Brodsky, 9 points)
50
TOURNAMENT 16
Spring 1995 (О Level)
1.	Sonia has 10, 15 and 20 cent stamps with total face value of $5.
She has 30 stamps altogether. Prove that she has more 20 cent
stamps than 10 cent stamps.	(3 points)
2.	Three grasshoppers A, В and C are placed on a line. Grasshopper
В sits at the midpoint between A and C. Every second, one of the
grasshoppers jumps over one of the others to the symmetrical point
on the other side (if X jumps over Y to point Xf, then XY = YX').
After several jumps it so happened that they returned to the three
initial points (but maybe in different order). Prove that in this case
В returns to his initial middle position.
(AK Kovaldzhy, 3 points)
3.	Suppose L is the circle inscribed in the square Ti, and T2 is the
square inscribed in L, so that vertices of T\ lie on the straight lines
containing the sides of T2. Find the angles of the convex octagon
whose vertices are at the tangency points of L with the sides of T±
and at the vertices of T2.	(S Markelov, 4 points)
4.	Prove that the number 40... 09 (with at least one zero) is not a
perfect square.	(VA Senderov, 4 points)
Junior Questions
51
Spring 1995 (A Level)
1.	Prove that if a, b and c are integers and the sums
a	b с ,	a c b
-—I 1—	and	—F — H—
b с a	c b a
are also integers, then we have |a| = |&| = |c|.
(A Gribalko, 4 points)
2.	From a regular 10-gon ABCDEFGHIJ of side length 1 a straight
line cuts off a triangle PAQ such that PA + AQ = 1. Find the sum
of angles under which the segment PQ is seen from the points B,
C, D, E, F, G, H, I and J.	(V Proizvolov, 4 points)
3.	Given the equilateral triangle ABC, find the locus of all points P
such that the segments of the lines AP and BP lying inside the
triangle are equal.	(4 points)
4.	Can the number a + H c-H be prime if a, b, c and d are positive
integers and ab = cd?	(5 points)
5.	Four equal right-angled triangles are given. We are allowed to cut
any triangle into two new ones along the altitude dropped on to
the hypotenuse. This operation may be repeated with any of the
triangles from the new set. Prove that after any number of such
operations there will be congruent triangles among those obtained.
(AV Shapovalov, 8 points)
6.	Can it happen that 6 parallelepipeds, no two of which have com-
mon points, are placed in space so that there is a point outside
of them from which no vertex of a parallelepiped is visible? (The
parallelepipeds are not transparent.) (V Proizvolov, 8 points)
7.	A team of geologists on a field expedition have taken with them 80
tin cans of provisions. The 80 cans have different weights, which
are known (there is a list). After a while the names of the contents
of the cans have become illegible. The cook knows what is in each
can and claims that he can prove it without opening any can and
only using the list and a balance which indicates the difference of
weight of the objects placed on its two pans. Show that in order
to do so,
(a) four weight measurements will be enough,	(4 points)
(b) three will not.	(AK Tolpygo, 4 points)
52
TOURNAMENT 16
SENIOR QUESTIONS
Autumn 1994 (0 Level)
1.	Several boys and girls are dancing a waltz at a ball. Is it possible
that each girl can always get to dance the next dance with either
a more handsome or more clever boy than for the previous dance,
and that each time at least 80% of the girls get to dance the next
dance with a boy who is more handsome and more clever? (The
numbers of boys and girls are equal and all are dancing.)
(AY Belov, 3 points)
2.	Prove that one can construct two triangles from six edges of an
arbitrary tetrahedron.	(VV Proizvolov, 4 points)
3.	Let a, 6, c and d be real numbers such that
4~	4-	= (24_b4_c4_d — 0.
Prove that the sum of a pair of these numbers is equal to 0.
(LD Kurliandchik, 4 points)
4.	A rectangular 1 by 10 strip is divided into 10 1 by 1 squares. The
numbers 1, 2,3,..., 10 are placed in the squares in the following
way. First the number 1 is placed in an arbitrary square, then 2 is
placed in a neighbouring square, then 3 is placed into a free square
neighbouring one of the squares occupied earlier, and so on (up to
10). How many different permutations of 1,2, 3,..., 10 can one get
in this way?	(A Shen, 5 points)
Senior Questions
53
Autumn 1994 (A Level)
1.	Coefficients p and q of the equation x2 4- px 4- q = 0 are changed
and the new ones differ from the old ones by 0.001 or less. Can the
greater root of the new equation differ from that of the old one by
1000 or more?	(3 points)
2.	Show how to divide space into
(a)	congruent tetrahedra,	(2 points)
(b)	congruent “equifaced” tetrahedra. (NB Vassiliev, 2 points)
(A tetrahedron is called equifaced if all its faces are congruent
triangles.)
3.	The median AD of triangle ABC intersects its inscribed circle (with
center □) at the points X and Y. Find the angle XOY if AC =
AB + AD.	(A Fedotov, 4 points)
4.	Prove that for all positive ai, az,. ., an the inequality
2 \ /	2 \	/	2 \
14—- ) [1-1—-)...( 1 4—— ) >(14- tz-i)(1 4- az) ... (1 4- an)
a2 / \ аз/ \ а г /
holds.	(LD Kurliandchik, 5 points)
5.	The periods of two periodic sequences are coprime (i.e. relatively
prime) numbers m and n. What is the maximal length of initial
sections of the two sequences which can coincide? (The period p of
a sequence ax, az,... is the minimal p such that an — an+p for all
n.)	(AY Belov, 6 points)
6.	Let cn be the first digit of 2n (in decimal representation). Prove
that the number of different 13-tuples < с&,..., сь+х2 > is equal to
57.	(AY Belov, 7 points)
7.	The figure F is the intersection of N circles (they may have differ-
ent radii). Find the maximal number of curvilinear “sides” which
F can have. (Curvilinear sides of F are the arcs (of the given cir-
cumferences) that constitute the boundaiy of F. Their ends are
the “vertices” of F — the points of intersection of given circumfer-
ences that lie on the boundary of F.)
(N Brodsky, 8 points)
54
TOURNAMENT 16
Spring 1995 (О Level)
1.	Let a, 6, c and d be points of the segment [0,1] of the real line (this
means numbers x such that 0 < x < 1). Prove that there exists a
point x on this segment such that
1 1 1
|x — a| + jrr — b\ + |x — c|
1
+ |rr — d\
< 40.
(LD Kurliandchik, 3 points)
2.	Four grasshoppers sit at the vertices of a square. Every second,
one of them jumps over one of the others to the symmetrical point
on the other side (if X jumps over Y to the point X', then X, Y
and Xf lie on a straight line and XY = YX'). Prove that after
several jumps no three grasshoppers can be:
(a)	on a line parallel to a side of the square;	(3 points)
(b)	on a straight line.	(AK Kovaldzhy, 3 points)
3.	Triangle ABC is inscribed in a circle with center O. Let q be the
circle passing through A, О and B. The lines CA and С В intersect
q at the points D and E (different from A and B). Prove that the
lines CO and DE are perpendicular to each other.
(S Markelov, 4 points)
4.	Prove that a0... 09 (in which a > 0 is a digit and there is at least
one zero) is not a perfect square.	(VA Senderov, 4 points)
Senior Questions
55
Spring 1995 (A Level)
1.	Does there exist a sphere passing through only one rational point?
(A rational point is a point whose Cartesian coordinates are all
rational numbers.)	(A Rubin, 4 points)
2.	For what values of n is it possible to paint the edges of a prism
whose base is an n-gon so that there are edges of all three colours
at each vertex and all the faces (including the upper and lower
bases) have edges of all three colours? (AV Shapovelov, 4 points)
3.	The non-parallel sides of a trapezium serve as the diameters of two
circles. Prove that all four tangents to the circles drawn from the
point of intersection of the diagonals are equal (if this point lies
outside the circles).	(S Markelov, 5 points)
4.	Some points with integer coordinates in the plane are marked. It is
known that no four of them lie on a circle. Show that there exists
a circle of radius 1995 without any marked points inside.
(AV Shapovelov, 6 points)
5.	(a) Divide the line segment [0,1] into smaller black and white seg-
ments so that, for any polynomial p(x) of degree no greater
than two, the sum of increments of р(т) along all the black seg-
ments is equal to that along the white ones. (The increment
of p(x) along the segment [a, b] is the number p(b) — p(a).)
(3 points)
(b) Can this be done for all polynomials of degree no greater than
1995?	(Burkov, 4 points)
6. Does there exist a nonconvex polyhedron such that not one of its
vertices is visible from a point M outside it? (The polyhedron is
made out of an opaque material.)
(AY Belov, S Markelov, 8 points)
7. Prove that in a group of 50 people there are always two who have
an even number (possibly zero) of common acquaintances within
the group.	(SI Tokarev, 10 points)
56
TOURNAMENT 16
JUNIOR SOLUTIONS
Autumn 1994 (0 Level)
1.	There are arrangements for which it is possible. For example sup-
pose there are 4 boys and 4 girls, the boys are numbered, in order
of being handsome, from 1 (least handsome) to 4(most handsome)
and these are consecutively 4, 1, 2, 3 (4 being most clever) in order
of being clever. Each girl dances with each boy in turn, in increas-
ing order of cleverness, reverting to number 1 after dancing with
number 4. For each dance two girls dance with a boy more hand-
some and more clever than for the previous dance, while the other
two dance with a boy who is either more clever or more handsome.
(A Storozhev)
2.	Construct the centre P of the smaller circle and Q of the larger.
If P = Q, then this point can serve as O. Suppose P Q. Let
the line PQ cut the smaller at E and G and the larger one at F
and H, so that the points on this line are in the order F, E, F, Q,
G (or G, Q) and Я. Take any point C on the smaller circle other
than E and G. Draw a line through Q parallel to PC, cutting the
larger circle at a point D on the same side of PQ as C.
Since PC < QD, PCDQ is not a parallelogram, so that the lines
PQ and CD meet at a point O. We claim that О has the desired
Junior Solutions
57
property. Note that triangles OPC and OQD are similar. Hence
OP r
OQ~ R"
where r is the radius of the smaller circle and R of the larger.
Now
r — OP r r + OP OG
OE OF = ---------= - =----------= -----.
1 R~OQ R R + OQ OH
Let A be any point on the smaller circle other than С, E and G.
Draw a line through Q parallel to PA, cutting the larger circle at
a point В on the same side of PQ as A. Then triangles OP A and
OQB are similar. Hence
О A r
СЁВ ~ R'
and О, A and В are collinear. Thus our claim is justified.
(A Liu)
3.	Let the numbers bea<b<c<d<e. We choose b — a — c~ b ~ 1
so that c—a = 2. Take d—c = 2, the least common multiple of 1 and
2. Then d — b = 3 and d — a = 4. Take e — d = 12, the least common
multiple of 2, 3 and 4. Then e — c — 14, e — b ~ 15 and e — a = 16.
Take e = 1680, the least common multiple of 12, 14, 15 and 16.
Then d = 1668, c = 1666, b = 1665 and a = 1664. It is routine to
verify that these five numbers have the desired properties.
(A Liu)
Editors’ Note: There are many smaller solutions, which can be
found by less systematic approaches, such as {36,40,42,45,48},
{40,42,44,45,48}, {40,45,48, 50,60} and {60, 72,75,80, 90}.
4.	A child whose grandfathers are A and В is called (A,B). There
may be several such children. Any of the other children must have
either A or В as a grandfather. We may as well assume that not all
20 children have a common grandfather. Then there is at least one
child who does not have В as. a grandfather. We may assume that
she is (A,C). Similarly, there is at least one child who does not
have A as a grandfather. Since he has a common grandfather with
both (A,B) and (A,C), he must be	It follows that every
child is one of (А, В), (A, C) or (В, C). Now the 20 children have 40
grandfathers, counting multiplicity. By the Pigeonhole Principle,
at least one of A, В and C is a grandfather of at least 14 children.
(A Liu)
58
TOURNAMENT 16
Autumn 1994 (A Level)
1.	Let the number of nuts in the n boxes be ai, a<2,..., ani respectively.
Let ai, 1 < i < к be positive and ai = 0 for к < i < n. By the
Root-Mean-Square Arithmetic Mean Inequality,
lOOOn > /a2 + «2 + * • • +	> ai + a2 + • • • + ak 10n
к ~ V к ~ к	к ’
which is equivalent to
n ~ 10'
(A Liu)
2.	There are two ways in which a diagonal can be drawn on a square
and then two possible colourings, So each square can be coloured
in 2 x 2 — 4 ways.
Once two squares which join diagonally to each other such as
the square wedged between them (marked A in diagram) is totally
determined for colouring. We can now proceed in several ways. For
example
Alternative 1
The 8 diagonals can be coloured in 48 — 216 ways. But then every
square in the adjacent diagonals and by continuing the argument,
off the diagonal is totally determined.
The total number of colourings is 216.
Alternative 2
The top left hand corner can be coloured in 4 = 22 ways. The
remaining squares in each of the other 7 squares in the first row and
the other 7 squares in the first column can then be coloured each
in 2 ways. After that the remaining 49 colourings are determined.
This gives 22 x 27 x 27 = 216 ways.
(PJ Taylor)
Junior Solutions
59
3.	Let the perpendicular lines be AC and BC, with A, В and C on
the circle. Let M±, М2 and М3 be the relevant points on arcs AB,
BC and CA respectively.
Let the tangent at М3 cut AC at P and BC at Q, Then М3 is the
circumcentre of triangle CPQ. Let £M^CP = 0.
Since M$C = M$P, LM^PC = 0. Since M$P is a tangent,
ZAM3P — 0, by the alternate segment theorem.
By the exterior angle theorem, £M$AC ~ 20.
By Thales’ Theorem, ZM3BA = 0 and £M^BC = 26, so that
ZM3BA = IZABC. Let the tangent at Mi cut BC at R. By an
analogous argument, LM^BA = ±£RBA, so that Z Mi М2 М3 =
Ш{ВМ3 = 60°. Similarly, ZM1M3M2 = 60°.
Hence Mi М2 М3 is equilateral.
(A Liu)
4.	(a) Let &юо = Ц9 = 1 and &fc_i = bk + 6^+1 for 2 < fc < 99.
Let m be the least common multiple of bk, 1 < к < 100. Let
ak = m/bk for 1 < к < 100. Then we have
1________1_ _ bk-i _bk_ _ bk+i _	1
CL к—1	ak П2 П2	^fc-f-1
for 2 < к < 99.
(A Liu)
60
TOURNAMENT 16
(b) Suppose we have an infinite sequence
1 1 1
ai ’ a2 ’ аз ’
such that ak is a positive integer for к > 1 and
1_____1_ _ 1
ak—1	ak ak+l
for к > 2. Let m be the least common multiple of ai and a2.
We prove by induction that m is a multiple of ak for all k.
The result holds for к = 1 and к — 2. Suppose it holds for
1,2,. .., к for some к > 2. Let 6fc-i = m/ak_i and bk — m/ak.
Then 6fc-i and bk are integers. We have
i = i __ 2 =	" bk
afc-f-i dk—i dk	m
so that m is indeed a multiple of a^+i. Since the sequence
ai, а2, аз,... increases without bound, m cannot be a multiple
of ak for all k. This contradiction shows that such an infinite
sequence
1 1 1
ai’ a2’ аз’
cannot exist.
(A Liu)
5.	The answer is 18. First, we shall show that there exist sequences
ai, a2,... and &i, 62,  • • with periods 7 and 13 respectively such
that their initial sections of length 18 coincide. Let ai = 1, a2 =
1,..., as = 1, a$ = 2, (27 = 1 and bi = 1, 62 = 1,..., 65 =
1, 66 = 2 b7 = 1,..., 6i2 = 1, 613 = 2.
Then it is easily seen that the initial sections of both sequences of
length 18 are the same.
Now let us assume that there are sequences ai, a2, -.. and &i, b2,...
with periods 7 and 13 respectively such that their initial sections
of length 19 coincide.
Then aQ = be = big = ai9 — a$. Also <25 = 65 = big = dig = a 4.
Similarly we can get a4 = <23, dg ~ a2 and a2 = d±. But ai = bi =
6i4 ~ a 14 — d7.
Therefore all terms of the sequence аг, a2,... are equal which
means that the period of <21, a2,... is 1. Hence we arrived at a
contradiction.
(A Storozhev)
Junior Solutions
61
6.	By the Arithmetic Mean - Geometric Mean Inequality
6abcdef = a6 + fe6 + c6 + d6 + e6 + f6 - 1 > 3a2b2c2 + 3d2e2/2 - 1,
or
1 > 3(a6c — def)2.
Since a, 6, c, d, e and f are integers, we must have abc = def.
By symmetry, the product of any three of them is equal to that of
the other three. If none of them is 0 then they must all be equal.
However 6a6 = 6a6 — 1 cannot then hold. Hence, at least one of
them is 0, so that Gabcdef = 0. From
a + b + c + d + e -h f = 1,
we must have five of them equal to 0 and the other equal to ±1.
(A Liu)
7.	First note that the “circles” in this question are really “circular
discs”. In this solution they will be referred to simply as “discs”,
and the word “circle” will be reserved for the boundary of a disc.
So the figure F is the (set-theoretic) intersection of N discs, and
the boundary of F is made up of arcs from the boundaries of some
or all of these discs.
I claim that for N > 1 F has at most 2 (N — 1) sides. The gist of my
argument is that if you start with a smallest disc and progressively
consider intersections with discs of non-decreasing size then at most
two new vertices are introduced into the joint intersection for each
extra disc; the result then follows because F, the (joint) intersection
of all N discs, has as many sides as vertices.
Before giving the details, here is a construction which shows that
2(7V —1) sides is achievable. Choose discs Z>i,..., whose bound-
ary circles Ci,..., Cn have radii 1,..., N respectively. Place D±
arbitrarily and then place D% so that Ci and C2 intersect at two
points, say Pi and Q±. Now place D3 so that C3 intersects C2
at two points, say P2 and Q2 between Pi and Qi (and inside
Ci). For i = 3...7V — 1 continue in this manner placing
so that Ci+i intersects Ci at two points, say Pi and Qi, between
Pi-1 and Qi-i (and inside Ci). Then F has 2(N — 1) vertices
Pi,..., Pjv-i, QАг-i,..., Qi and hence 2(N — 1) sides. (Note that
the Pi,...,Рдг-1 and Qi,... ,Qдг-i are all vertices of F because
the radii are increasing.)
62
TOURNAMENT 16
Now suppose that the N discs are given. Label them £>i,...
in order of size, from small to large. For n — 1,..., N let Fn be the
(joint) intersection of Di,..., Dn, so that F = F^. I claim that
for each n, Fn has at most 2(n — 1) vertices. Since F± = has no
vertices, and since Fn+i = ГпПРп+ь the claim may be established
inductively by showing that the boundary Cn+i of Dn+i cuts the
boundary of Fn at most twice, and so can introduce at most two
new vertices. The proof depends on the concept of “fc-convexity”:
a figure К is fc-convex if for any two points A and В in К both
“short fc-arcs” from A to В are entirely in K. Here “fc-arc” is
shorthand for “arc of a circle of radius fc” and “short” means that
it is not more than half the circle.
The following properties of fc-convexity are needed:
(a)	If r < R then any disc of radius r is Я-convex.
(b)	If figures К and L are fc-convex then so is Of.
(c)	If К is fc-convex then any circle of radius к cuts the boundary
of К at most twice.
Properties 1 and 2 hardly require proof. To prove property 3 sup-
pose to the contrary that C is a circle of radius к which cuts the
boundary of К at points, in order, P1?	P3,.... Then the fc-arcs
P1P2, P2P3, • • • must alternately be inside and outside К (except
that the end points of the arcs are all on the boundary of K). So
there must be as many outside arcs as inside ones, and in particular
there must be at least two outside ones. But, from the definition
of “short”, at most one arc can be non-short, so there must be
at least one short outside arc, contradicting the fc-convexity of K.
This contradiction established property 3.
Now to finish the solution by proving that Cn+i cuts the boundary
of Fn at most twice: For i = 1... N let Ci have radius 74. Then
7*1 < r2 < • • - < f'N and so by properties 1 and 2 Fn is rn+i-convex.
The result follows by property 3.
(MS Brooks)
Junior Solutions
63
Spring 1995 (0 Level)
1.	Let the numbers of the 10c, 15c and 20c stamps be a, b and c
respectively. Then the following two equations hold.
10a Ч- 156 Ч- 20c = 500
a + & + c = 30 .
By subtracting the second equation, multiplied by 15, from the first
one, we obtain
5c — 5a = 50.
Hence c — a = 10 which implies c > a.
(A Storozhev)
2.	Let us consider the straight line where the three grasshoppers move
as a number line such that the numbers corresponding to the initial
positions of the grasshoppers are 0, 1 and 2. Let also xn, yn and
zn denote the numbers corresponding to the positions of the-first,
second and third grasshoppers respectively after the nth second.
Clearly each of the numbers тп, yn and zn is an integer.
We shall prove by induction that xn is even, yn is odd and zn is
even for any integer n > 0.
If n = 0, then xn — 0, yn = 1 and zn = 2.
Now assume that xk is even, yk is odd and zk is even for some
к > 0.
Suppose that the first grasshoppers skips over the second. Then
хк+1 = yk + (Ук ~	= 2yk ~ xk which means that xk+i is even
as xk is even.
We can consider the other cases in a similar manner and show that
xk+i is even, yk+i is odd and zk+i is even.
Therefore xn is even, yn is odd and zn is even for any integer n > 0.
Now if after mth second the grasshoppers are at the initial points
but possibly in a different order, then ym = 1 because ym must be
odd and the only odd number in the set 0, 1, 2 is 1.
(A Storozhev)
3.	Let А, В, C and D be the vertices of the square and P,Q,R,S
be the vertices of the square T2 so that A, P and Q lie on a straight
line; B, Q and R lie on a straight line and X, Y, Z, W are the
64
TOURNAMENT 16
points of contact of the circle and AB, BC, CD, DA respectively.
Then we have an octagon XQYRZSWP such that both PQRS
and XYZW are squares.
Since WPXZ is a cyclic quadrilateral, LWPX + LWZX = 180°.
Since XYZW is a square, LWZX = 45°.
Hence LWPX = 180° - 45° = 135°.
Similarly the other angles of the octagon are 135°.
(A Liu)
4.	See the solution of question 4 in the Senior 0 level paper.
Junior Solutions
65
Spring 1995 (A Level)
1. Alternative 1
Let
a	b	c
P ~ 7 “I----1—
b	c	a
and
a	c	b
q — —Ь 7 H—•
c	b	a
Then the roots of x3 — px2 4- qx — 1 = 0 are a/b, b/c and с/a.
Since the coefficients are integral and the roots are rational, the
only possible roots are ±1. Hence |a| = |6| = |c|.
(M Klamkin)
Alternative 2
Clearly, we may assume that the greatest common divisor of a, b
and c is 1. The fact that a/b + b/c + c/a is an integer means that
a2c 4- b2a + c2b is divisible by abc. Hence a2c is divisible by b.
Similarly, the fact that a/c + c/b 4- b/a is an integer implies that
a2b 4- c2a 4- b2c is divisible by abc and that c2a is divisible by b.
Thus we see that a2c is divisible by b and simultaneously c2a is
divisible by b. Therefore ac is divisible by b as the greatest common
divisor of a, b and c is 1.
Hence a2c is divisible by ab and c2b is divisible by ab as a2c + b2a 4-
c2b is divisible by abc. Therefore c2 is divisible by a. Hence b and
a are relatively prime.
By similar reasons, any two of a, b and c are relatively prime. Hence
|&| = 1 as c2 is divisible by b. Similarly, |a| = 1 and |c| = 1.
(A Storozhev)
2. Since PA 4- AQ = 1, we can construct a regular 10-gon
PQRSTUVWXY
such that all its vertices lie on the sides of ABCDEFGHIJ.
66
TOURNAMENT 16
Then we see that the triangle QCP is congruent to the triangle
PBY, QDP to YBX,..., Q JP to RBS.
Hence the sum of angles under which the segment PQ is seen from
the points B,C,D,E,F,G,H,I and J equals the angle ABC,
that is, 144°.
(A Storozhev)
3.	Let P be a point. Then the segments of the straight lines AP
and BP lying inside the triangle are equal if and only if either
AABP = ABAP or AABP = APAC.
If AABP = ABAP, then P is a point on the median CM. If
AABP = APAC, then AABP 4- ABAP — 60° which implies
AAPB = 120°.
В
Hence P lies on the arc, which is inside the triangle, of the circle
that is symmetric to the circumcircle of the triangle ABC with
respect to the side AB.
Therefore, the locus in question is the union of the median CM
and the arc described above.
(A Storozhev)
Junior Solutions
67
4.	Alternative 1
Note that we have
a2 4- cd 4- ac 4- ad (a 4- c)(a 4- d)
a-\-b-{-c-\-d — -----------------~	,
a	a
which is clearly composite since each factor in the numerator is
larger than the denominator.
(A Liu)
Alternative 2
The answer is no.
Let p be the greatest common divisor of a and c. Let a = pq and
c = ps so that q and s are relatively prime. Since pq divides cd, q
divides sd, and hence q divides d. Let d = qt. Then we must have
b = pt.
Now a 4- b + c 4- d = (p 4- t)(q 4- s) is composite.
(A Storozhev)
5.	Proof by contradiction.
Assume that we cut the triangles so that there are no two congruent
triangles among those obtained.
Let the area of each of the four original triangles be 1. It is easily
seen that there exist two positive numbers, say a and &, such that if
the area of one of the triangles, which was obtained at some stage,
is x, then the areas of two new triangles obtained by cutting this
triangle are xa and xb.
Let S be the set of all numbers that were areas of the triangles
which appeared at some moment during the cutting (including the
four original triangles). Let akbk be an element of S such that
there were at least four triangles with area equal to akbk and к is
the maximal number satisfying this condition.
Then at least three of the triangles with area akbk had to be cut.
Hence there were at least three triangles with area ak+1bk and at
least three triangles with area akbk+1.
Therefore at least two triangles with area ak+1bk had to be cut and
also at least two triangles with areaafc6fc+1 had to be cut.
Hence there were at least four triangles with area ak+1bk+1. Thus
к is not maximal, which is a contradiction.
(A Storozhev)
68
TOURNAMENT 16
6.	The answer is yes.
We will describe one of possible sets of such 6 parallelopipeds in
terms of coordinates of vertices of each of the parallelopipeds.
First parallelepiped: (±3, ±0.9,1), (±3, ±0.9, 2).
Second parallelepiped: (±3, ±0.9, —1), (±3, ±0.9, —2).
Third parallelepiped: (1, ±3, ±0.9), (2, ±3, ±0.9).
Fourth parallelepiped: (—1, ±3, ±0.9), (—2, ±3, ±0.9).
Fifth parallelepiped: (±0.9,1, ±3), (±0.9, 2, ±3).
Sixth parallelepiped: (±0.9, —1, ±3), (±0.9, —2, ±3).
Then it is easily seen that no vertex of any of the parallelopipeds
is visible from the point (0,0,0).
(A Storozhev)
7.	(a) Introduce an empty can numbered 0. Convert everything into
four-digit numbers in base 3, which will run from 0000 to 2222.
In the ith weighing, 1 < i < 4, put in one pan all cans with
the digit 0 in the zth position of their base 3 numbering, and
in the other pan all cans with the digit 2 there. Thus 27 cans
are put on each pan each time.
In the first weighing, we obtain the maximum possible differ-
ence in weight between any two subsets of 27 cans. Hence the
first digits are correct.
In the second weighing, we obtain the maximum possible dif-
ference in weight between two subsets of 27 cans, consisting
of 9 cans whose base-3 numbering starts with each of 0, 1 and
2. Hence the second digits are also correct.
In the third weighing, we obtain the maximum possible differ-
ence in weight between two subsets of 27 cans, consisting of 3
cans whose base-3 numbering starts with each of 00, 01, 02,
10, 11, 12, 20, 21 and 22. Hence the third digits are correct
too.
In the fourth weighing, we obtain the maximum possible dif-
ference in weight between two subsets of 27 cans, no two
within the same subset having the same first three digits in
their base-3 numbering. This proves that the cook has made
no mistakes.
(A Liu, A Storozhev)
Junior Solutions
69
(b) In one weighing, we can only classify a can as being on one
pan, on the other, or not on either. Thus we can divide the
cans into three subsets. With only three weighings, we can
get 27 subsets. Since we have more than 27 cans, at least one
subset has at least 2 cans. It is not possible to prove that the
numbers on these two cans have not been transposed.
(A Liu, A Storozhev)
70
TOURNAMENT 16
SENIOR SOLUTIONS
Autumn 1994 (0 Level)
1.	Same as solution to question 1 in the Junior 0 level paper, but with
n boys and n girls, boys numbered from 1 to n in order of cleverness
(increasing), the same boys numbered 2, ...,n,l respectively for
being handsome, and n large enough. For each dance n — 2 girls
get to dance with a boy who is more clever and more handsome
than on the previous dance while the other 2 get to dance with a
boy who is either more handsome or more clever. We need
i.e. n — 2 > 0.8n, or 0.2n > 2, or n > 10.
(A Storozhev)
2.	Let the tetrahedron be ABCD, with AB as the longest edge.
If AB < AC + AD, we can form a triangle with these three edges
to go along with triangle BCD.
Suppose AB > AC + AD. We have AC + BC > AB and AD +
BD > AB. Addition yields BC + BD > AB. We can form a
triangle with these three edges to go along with triangle ACD.
(A Liu)
3.	We have d3 + c3 + d3 = —a3 = (—a)3 = (6 + c + d)3. Expansion,
simplification and factorization yield (b + c)(c + d)(d + b) = 0. The
desired conclusion follows immediately.	(A Liu) 4
4. More generally, denote the number of such permutations on a 1 x n
board by an. The largest number n must be and can be at either
end of the board. When it is removed, we have one of the an_i
permutations obtainable on a 1 by n — 1 board. Hence an = 2an_i
for all n > 2. Since <ii = 1, we have an = 2n 1. In particular,
аю ~ 512.
(A Liu)
Senior Solutions
71
Autumn 1994 (A Level)
1. The answer is yes. Let the original equation be
x2 + px + q = (x — 7)2 — 0.
Then p = — 27 and q = 72. Let the new equation be
x2 + p x + q = (x — 71)(ж - 72) = 0.
We choose
71 = 7 + 103 * * + 10~3
and
72 — 7 — 103
so that
P — ~(7i + 72) —	- 1(T3 — p — 1(T3.
Now
q = 7172 = 72 + 10"37 - (106 + 1) = q + 10-37 - (106 + 1) = q
if we choose 7 so that 10-37 = 106 + 1 or 7 = 109 + 103. Hence
p = -27 = -2.103(106 + 1)
and
q = 72 = 106(106 + I)2.
(A Liu)
2. (a) Consider a cube ABCD — EFGH as shown in Figure 1. It
can be divided into three congruent square-based pyramids
A - EFGH, A - BCFG and A -CDHG, the first of which
is shown in Figure 2.
72
TOURNAMENT 16
Each can further be divided into two congruent tetrahedra,
as illustrated in Figure 2 where the plane AGE divides A —
EFGH into A - EFG and A - GHE.
Since space can be divided into congruent cubes, it can be
divided into congruent tetrahedra.
(A Liu)
(b) We first divide space into congruent cubes. Then we divide
each cube into six congruent pyramids, each based on one face
of the cube and having a common vertex at the centre.
Next, we glue each pyramid to the one in the next cube sharing
a common base, so that space is now divided into congruent
octahedra. One of them, E — ABCD — F, is shown in Figure
3.
Figure 3
Finally, we divide it into four congruent tetrahedra E — AB —
F, E — BC — F, E — CD — F and E — DA — F by the planes
EACF and EBDF.
Since AB = EF = 1 and EA = EB = FA = FB = the
tetrahedra are equifaced.
(A Liu)
Note: Of course, the solution to (b) serves as an alternate solution
to (a). There are still others. Another is obtained if we divide the
pyramid E — AB CD in Figure 3 into two congruent tetrahedra
E — ABC and E — CD A by the plane ACE.
3.	Alternative 1
Let AB = с, BC = a, CA = b and AD = m. Let r be the inradius
and h be the distance from О to AD. The area of ABC is
a + b + c a + 2c + m
---	r — 	-r
2----------------------2
Senior Solutions
73
and that of BAD is
Since the former is twice the latter, we have h = r/2. Hence
LOXY = 30° and LXOY = 120°.
(A Liu)
Alternative 2
Let Q and R be the feet of the perpendiculars from О to AC and
A£>, respectively. Let P be symmetric to В with respect to the
bisector AO. So P is on AC and AP = AB.
We then note that CP = AC — AP = AC — AB = AD. Let T be
the point of intersection of BP and AO.
Now ВТ = TP and BD = DC so
CP AD
TD = —— = —-
2	2
and TD || AC. Thus LTD A = LDAC = LQOR (the quadrilateral
QAOR is cyclic).
74
TOURNAMENT 16
As LOAR = LOQR, we see that triangles OQR and TAD are
similar. Since TD —	follows that
1 т
OR=-.OQ = -
(where r is the inradius).
Then
Z.XOY	OR	~	1
cos —-— = cos ZXOR = -------= — =
2	OX	r	2
i.e.
^ = 60".
or LXOY = 120°.
(Antonia Caminha)
4.	The desired inequality is equivalent to
(a2 4- «1)(a3 4- «2) •••(«! + an) — (ai 4- a?)(«2 4- a^) . •. (an + anY
We shall prove this by induction on n.
The result is trivial for n = 1.
Suppose it holds for some n > 1. Consider the next case with n -h1
terms. We may assume that an+1 is the largest. Then
(O'nH-l al)(an4-l an)(an4-l “b an) — 0
or
(an+i 4- «n)(ai 4-	> («1 4- a^)(an+i + a^+1).
Combining this with the induction hypothesis yields the desired
result.
(A Liu)
5.	First, we shall prove by induction that the maximal length in ques-
tion cannot be equal to m + n — 1.
Let a1? a2> • • • be a sequence with period n and &i,62,•• • a sequence
with period m. If n > m = 1 and the initial sections of both
sequences of length n are the same, then we have ai = a2 = • • • =
an which means that the sequence ai, a2> • • • has period 1.
Now assume that n > m > 1 and the initial sections of both se-
quences of length n + m — 1 are the same. Let n = mk + r where
Senior Solutions
75
r < m. Since m and n are relatively prime, r and m are rela-
tively prime and r 0. Consider the sequence akm+i,akm+2, • ♦ ••
We see that the initial sections of this sequence and the sequence
bi, 62, • • • °f length r 4- m — 1 are the same. It is also easily seen
that abn+i, afcm+2, • • • has period r (or a factor of r). Therefore by
induction we come to a contradiction.
Next we shall show that given m and n, it is possible to find two
sequences of periods m and n respectively such that the initial
sections of these two sequences of length n + m — 2 coincide. Again
we have n = mk -h r where r < m. By induction, we can find
sequences bi, .. and ci, C2,... such that the first sequence has
period m, the second sequence period r and their initial sections of
length m -hr — 2 coincide. Now let	. be a sequence of period
n such that a-im+j = bj for 0 < г < к, 1 < j < m, and а^т+з — cj
for 1 < j < r. Then we can see that the initial sections of length
m-hn—2 of the sequences ai, a%, ... and bi, 62,... coincide. The only
thing that we need to check in order for the induction arguments
to work is the case when m = 1. In this case we put ai = .1 for
1 < г < n — 1, an = 2 and bi = 1. Then the period of	.
is n and the initial sections of length m -h n — 2 of the sequences
ai, а2? • • • and bi, 62,... coincide.
(A Storozhev)
6.	Suppose x is a power of 2 with first digit 1. We compute the
range of x for which the first digit of 2kx has a specific value,
0 < & < 15. We summarize this analysis in the following table,
with the ranges correct to 3 decimal places. (Note that in the table
below, 1.000 — 1.999 would mean 1.000 x 10n < x < 1.999 x 10n
for some n.)
76
TOURNAMENT 16
X	CD	1.000 -	1.999
2x	@	1.000 -	1.499 (?) 1.500 - 1.999
2^x		1.000 -	1.249 (?) 1.250 - 1.499 (?) 1.500 - 1.749
	(7)	1.750 —	1.999
23x		1.000-	1.124 (?) 1.125 — 1.249 (?) 1.250 - 1.999
24ж		1.000-	1.249 g) 1.250 - 1.874 (?) 1.875 - 1.999
25x		1.000-	1.249 (4) 1.250 - 1.562 (?) 1.563 - 1.874
	®	1.875 -	1.999
26x	®	1.000-	1.093 (?) 1.094 - 1.249 (?) 1.250 - 1.406
	®	1.407-	1.562 (?) 1.563- 1.999
27x	®	1.000 -	1.562 (?) 1.563 - 1.999
2sx	®	1.000 -	1.171 (?) 1.172 - 1.562 (?) 1.563 - 1.953
	®	1.954-	1.999
29x	®	1.000 -	1.171 (?) 1.172 - 1.367 (?) 1.368 - 1.562
	®	1.563-	1.757 (?) 1.758- 1.953 (T) 1.954- 1.999
210x	®	1.000 -	1.953 (?) 1.954- 1.999
2nx	®	1.000 -	1.464 (?) 1.465 - 1.953 (?) 1.954 - 1.999
212x	®	1.000 -	1.220 (?) 1.221 - 1.464 (?) 1.465 - 1.708
	®	1.709 -	1.999
213x	®	1.000 -	1.098 (?) 1.099 - 1.220 (?) 1.221 - 1.999
2ux	®	1.000-	1.220 (?) 1.221 - 1.831 (?) 1.832 - 1.999
215x	®	1.000 -	1.220 (4) 1.221 - 1.299 (truncated)
This divides [1.000,1.999] into 18 subintervals:
[1.000,1.093), [1.094,1.098), [1.099,1.124), [1.125,1.171),
[1.172,1.220), [1.221,1.249), [1.250,1.367), [1.368,1.406),
[1.407,1.464), [1.465,1.499), [1.500,1.562), [1.563,1.708),
[1.709,1.749), [1.750,1.757), [1.758,1.831), [1.832,1.874),
[1.875,1.953), [1.954,1.999).
Senior Solutions
77
The terms circled can serve as the leading term of a subsequence of
{Cn} consisting of 13 consecutive terms, and there are 57 of them.
To prove that all 57 are possible, we need show that for each of
the 18 intervals listed before, there is an (n -h 1)—digit number x
for some n such that x is a power of 2 and ж/10п lies within that
interval. This follows from a stronger result that given any finite
sequence of digits, there is a power of 2 which begins with that
sequence in the base 10 representation.
For a proof, see Challenging Mathematical Problems and Elemen-
tary Solutions (Volume I), by AM Yaglom and IM Yaglom, Dover
Publications (1987) 199-200.
(A Liu)
7.	See the solution to Question 7 in the Junior A level paper.
78
TOURNAMENT 16
Spring 1995 (О Level)
1.	If the points 0,1/8, 3/8, 5/8, 7/8,1 are removed from the segment
[0,1], there are five non-overlapping intervals left: two of the in-
tervals are of length 1/8, the others of length 1/4. Clearly, there
exists an interval I such that none of the points a, b, c and d lies
in it.
Let x lie in I (or be one of its endpoints) and be 0 or 1 if the length
of I is 1/8, and be the midpoint of I otherwise. Then |x — a| > 1/8,
|ж — b\ > 1/8, |x — c| > 1/8, |ж — d\ > 1/8 as none of a, &, c and d
lies in I.
Hence
|ж — a| |x — b\ |ж — c| |x — d\
(A Storozhev)
2.	Let us introduce a system of coordinates in the plane where the four
grasshoppers move so that the coordinates of the initial positions
of the first, second, third and fourth grasshoppers are (0,0), (0,1),
(1,0) and (1,1) respectively.
Also let (^m, ^m), (cm» (^т,2/тп) and ('W'/nj^m) he the coordi-
nates of the positions of the first, second, third and fourth grasshop-
pers respectively after mth second. It can be easily proved by in-
duction that none of the numbers am:bm.cm,dmam,ym,um,vm
changes its parity. Now assume that the first, second and third
grasshoppers happen to lie on a straight line after mth second.
Then (<2m cm)(bm Ут) = (^m	dm)(<2m э?т) which is not
possible as on the lefthand side of this equation there is an even
number whereas on the other side there is an odd number. In the
same manner we can show that no three of the grasshoppers can
lie on a straight line after any number of seconds.
(A Storozhev)
3.	Let LDEC = a. Then LB AC = a as EBAD is a cyclic quadrilat-
eral. Hence LB ОС = 2a as LB ОС is an angle at О subtended by
the same arc as LB AC.
Senior Solutions
79
Therefore ZBCO = (180° - 2a)/2 = 90° - a. Hence £CED +
LECO — 90° which means that ED is perpendicular to ОС.
(A Storozhev)
4.	We prove by contradiction.
Assume that some number aO ... 09 is a perfect square. Then
a x 10” + 9 = t2
where n > 2. It can be easily checked that none of the numbers 109,
209, 309, 409, 509, 609, 709, 809, 909 is a perfect square. Hence
we may assume that n > 3.
We can rewrite the above equation as a x 10n = (t — 3)(£ + 3). Since
the difference between t — 3 and t 4- 3 is 6, these two expressions
cannot be divisible by 5 simultaneously.
Hence one of t — 3 and t -h 3, say t + 3, is divisible by 5n which
entails t + 3 > 5n.
Therefore t—3 < ax2n < 10x2n = 80x2”~3. But 5” = 125x5”-3.
Hence (t + 3) — (t — 3) = 125 x 5”-3 — 80 x 2”-3 > 6 which is a
contradiction.
Therefore a0... 09 cannot be a perfect square.
(A Storozhev)
80
TOURNAMENT 16
Spring 1995 (A Level)
1.	Alternative 1
The answer is yes. Let a be any irrational number. Consider the
sphere x2 + y2 + (z — a)2 = a2. It is tangent to the xy~plane at
(0,0,0). For any other point (x,y,z) on this sphere, z 0 and
2i2	2
Ж + У — %
a — ----- ------
2z
Since a is irrational, not all of x, у and z can be rational.
(A Liu)
Alternative 2
The answer is yes.
One of possible examples of such a sphere is the one that is defined
by the equation
(x — y/2)2 + (у — л/З)2 + (г — \/5)2 = 10.
Clearly, the sphere contains a rational point, namely (0,0,0).
Assume that a rational point (p, g,r) lies on the sphere.Then
p2 + <?2 + r2 = 2pV2 + 2дл/3 + 2rV§.
Therefore
p2 4- q2 -h r2 — 2r\/5 = 2pV2 + 2дл/3.
By squaring both sides of this equation, we obtain that r(p2 + q2 +
r2)\/5 + 2рдд/б is rational, which yields p = q = r — 0.
(A Storozhev)
2.	Let the top face be
A1A2...
and the bottom face be
B1B2 ... Bn,
with Ai above Bi for 1 < i < n. Suppose a desirable colouring
exists. Then on each rectangular face, two opposite edges are of
the same colour, while the remaining edges are of the other two
colours. There are two cases.
Senior Solutions
81
(1)	Suppose AiBi and A2B2 are red, A1A2 is yellow and B1B2 is
green. Then A2A3 must be green and B2B3 must be yellow,
so that A3B3 is red again. It follows that AiBi is red for all
i and neither the top nor the bottom face has any red edges.
This is clearly impossible.
(2)	Suppose A1A2 and B1B2 are red, AiB± is yellow and A2B2 is
green. Then A2A3 and B2B3 must be yellow, so that A3B3 is
red. Similarly, A3A4 and B3B4 must be green, so that A4B4
is yellow.
It follows that AiBi are cyclically yellow, green and red, and this
is possible if and only if n is a multiple of 3. The answer is all n
such that n is divisible by 3 and n > 3.
(Matthew Wong)
3.	Let ABCD be a trapezium, AD and BC its parallel sides and О
the point where its diagonals meet. Also let X be the point distinct
from A where the circle with diameter AB cuts the diagonal AC
and Y be the point distinct from D where the circle with diameter
CD cuts the diagonal BD.
The problem will be solved if we show that OX x О A — OY xOD.
Since the triangles AOD and COB are similar, we have
OA __ ОС
OD ~ OB'
Also since the triangles OBX and OCY are similar, we have
ОС _ ОУ
OB ” ox'
Therefore
OA _ OY
OD ~ OX’
82
TOURNAMENT 16
as required.
(A Storozhev)
4.	First of all, we assume that any circle of radius 1995 contains at
least one marked point inside it.
Then we tessellate the plane with squares such that their vertices
have integer coordinates, sides are parallel to the axes of coordi-
nates and the side length of each of the squares is 3990.
Obviously, there is at least one marked point inside each of the
squares. Two points with integer coordinates (a, b) and (c, d) are
said to be of the same type if a = c (mod 3990) and simultaneously
b=d (mod 3990).
Clearly, there are only 39902 different types of points. Let us con-
sider one column of the squares. There are infinitely many squares
in this column which contain marked points of the same type, say
type 1.
Now we remove all rows of squares that contain a square which
belongs to this column but has no points of type 1 inside. Thus
we obtain another tessellation that has a column such that each
square in this column contains a marked point of type 1. Since no
four of the marked points lie on the circumference of a circle, the
other columns of this new tessellation contain at most one square
with a marked point of type 1.
By removing the column with infinite set of points of type 1, we
obtain another tessellation of which all columns contain at most
one point of type 1. By repeating this procedure as many times as
possible, we obtain a tessellation of the plane such that its columns
contain at most one point of each type, which is a contradiction.
(A Storozhev)
5.	(a) Let the segments [0,1/4] and [3/4,1] be black and [1/4,3/4]
be white.
Then it is easily seen that for any polynomial p(x) of degree
no greater than two, the sum of increments of p(x) along all
the black segments is equal to that along the white ones.
(A Storozhev)
(b) We shall prove by induction that it is possible to divide any
segment [a, b] into white and black segments so that for any
polynomial p(x) of degree at most n the sum of increments of
Senior Solutions
83
p(x) along all the black segments is equal to that along the
white ones.
Clearly, this is true if n = 0.
Now assume that this is true for all polynomials of degree at
most к — 1.
If к is even, we consider the segment [a, and partition
it into white and black segments so that for any polynomial
p(x) of degree at most к — 1 the sum of increments of p(x)
along all the black segments is equal to that along the white
ones. Then we take the mirror image of this partition on the
segment b]. It easily checked that the combined partition
of [a, 6] satisfies the requirements for all polynomials of degree
at most к — 1. Also this partition satisfies the requirements
for all polynomials of the form c(x — where c can be any
number. Since any polynomial of degree к can be represented
as c(x —	+p(x) where p(x) is of degree at most к — 1, the
partition of [a, 6] satisfies the requirements for all polynomials
of degree at most k.
Similarly we can consider the case when к is odd. The only
change in constructing a required partition of [a, 6] is that
when we take the mirror image of the [a, partition on the
segment 6], the colours of the segments on the mirror
image have to be changed: white to black and black to white.
(Jury solution which also proves (a))
6.	The answer is yes.
A required polyhedron can be easily constructed by using the par-
allelopipeds described in the solution of Problem 6 from the Junior
Paper.
(A Storozhev)
7.	We use a graph to model the situation, with the vertices represent-
ing the people and the edges acquaintancy. Define a link to be any
path of length 2.
Suppose, contrary to the claim of the question, that every two
vertices are joined by an odd number of paths of length 2.
Consider a particular vertex p. Divide the remaining vertices into
its neighbours A and its non-neighbours N. Each a in A is linked
to p only via other vertices in A. Hence it must have odd degree
within A, and it follows that A has an even number of vertices.
84
TOURNAMENT 16
Then p has even degree, as do all other vertices since any can play
the role of p. It follows that each a in A is joined to an even number
of vertices in TV, so that the total number of edges between A and
N is even.
Now each n in N is linked to p only by vertices in A. Hence it
is joined to an odd number of them. It follows that N also has
an even number of vertices, so that the total number of vertices is
odd.
If the graph has 50 vertices, there must be two which are joined by
an even number of links.
(A Liu)


TOURNAMENT 17
JUNIOR QUESTIONS
Autumn 1995 (0 Level)
1.	A square is placed in the plane and a point P is marked in this
plane with invisible ink. A certain person can see this point through
special glasses. One can draw a straight line and this person will
say on which side of the line the point P lies. If P lies on the line,
the person says so. What is the minimal number of questions one
needs to find out if P lies inside the square or not?
(Folklore, 3 points)
2.	Do there exist 100 positive integers such that their sum is equal to
their least common multiple?	(S Tokarev, 3 points)
3.	A paper rectangle ABCD of area 1 is folded along a straight line
so that C coincides with A. Prove that the area of the pentagon
thus obtained is less than 3/4.	(3 points)
4.	From the vertex A of a triangle ABC, three segments are drawn:
the bisectors AM and AN of its interior and exterior angles and the
tangent AK to the circumscribed circle of the triangle (the points
M, К and N lie on the line BC). Prove that MK = KN.
(I Sharygin, 5 points)
88
TOURNAMENT 17
Autumn 1995 (A Level)
1.	Prove that inside any acute-angled triangle, there exists a point
P such that the feet of the perpendiculars dropped from P to the
sides of the triangle are the vertices of an equilateral triangle.
(NB Vassiliev, 5 points)
2.	The first five terms of a sequence are 1, 2, 3, 4 and 5. From the sixth
term on, each term is 1 less than the product of all the preceeding
ones. Prove that the product of the first 70 terms is equal to the
sum of their squares.	(LD Kurliandchik, 5 points)
3.	Let AK, BL and CM be the angle bisectors of a triangle ABC,
with К on BC. Let P and Q be the points on the lines BL and
CM respectively such that AP = PK and AQ = QK. Prove that
£PAQ = 90° — | ZB AC.	(I Sharygin, 5 points)
4.	A journalist is looking for a person Z at a meeting of n persons. He
has been told that Z knows all the other people at the meeting but
none of them knows Z. The journalist may ask any person about
any other person: “Do you know that person?” One person can be
questioned many times. All answers are truthful.
(a)	Can the journalist always find Z by asking less than n ques-
tions?
(3 points)
(b)	What is the minimal number of questions which are needed
to find Z?	(G Galperin, 3 points)
5.	A simple polygon in the plane is a figure bounded by a closed non-
self-intersecting broken line.
(a)	Do there exist two congruent simple 7-gons in the plane such
that all the seven vertices of one of the 7-gons are the vertices
of the other one and yet these two 7-gons have no common
sides?	(5 points)
(b)	Do there exist three such 7-gons? (V Proizvolov, 2 points)
Junior Questions
89
6.	A game is played on a 1 x 1000 board. There are n chips, all of
which are initially in a box near the board. Two players move in
turn. The first may choose 17 chips or less, from either on or off
the board. She then puts them into unoccupied cells on the board
so that there is no more than one chip in each of the cells. The
second player may take off the board any number of chips occupying
consecutive cells and put them back in the box. The first player
wins if she can put all n chips on the board so that they occupy
consecutive cells.
(a)	Show that she can win if n — 98.	(4 points)
(b)	For what maximal value of n can she win?
(A Shapovalov, 5 points)
90
TOURNAMENT 17
Spring 1996 (О Level)
1.	In an acute-angled triangle, each angle is an integral number of
degrees, and the smallest angle is one-fifth of the largest one. Find
these angles.	(G Galperin, 2 points)
2.	Does there exist an integer n such that all three numbers
(a)	n — 96, n and n + 96	(2 points)
(b)	n — 1996, n and n + 1996	(V Senderov, 2 points)
are positive prime numbers?
3.	The two tangents to the incircle of a right-angled triangle ABC
that are perpendicular to the hypotenuse AB intersect it at the
points P and Q. Find /.PCQ.	(M Evdokimov, 4 points)
4.	All vertices of a hexagon, whose sides may intersect at points other
than the vertices, lie on a circle.
(a)	Draw a hexagon such that it has the largest possible number
of points of self-intersection.	(3 points)
(b)	Prove that this number is indeed maximum.
(NB Vassiliev, 3 points)
5.	A game is played between two players on a 10 x 10 checkerboard.
They move alternately, the first player marking Xs on vacant cells
and the second Os. When all 100 cells have been marked, they
calculate two numbers C and Z. C is the total number of five con-
secutive Xs in a row, a column or a diagonal, so that 6 consecutive
Xs contribute a count of 2 to C, 7 consecutive Xs contribute 3, and
so on. Similarly, Z is the total number of five consecutive Os. The
first player wins if C > Z, loses if C < Z and draws if C = Z.
Does the first player have a strategy which guarantees
(a)	a draw or a win	(3 points)
(b)	a win	(A Belov, 3 points)
regardless of the counter-strategy of the second player?
Junior Questions
91
Spring 1996 (A Level)
1.	Prove that if a, b and c are positive numbers such that
a2 + b2 — ab = c2,
then (a — c)(6 — c) < 0.	(A Egorov, 3 points)
2.	An exterior common tangent to two non-intersecting circles with
centers and О 2 touches them at the points Ai and A 2 respec-
tively. The segment O1O2 intersects the circles at the points
and B2 respectively. C is the point where the straight lines A^B^
and A2B2 meet. D is the point on the line АМ2 such that CD is
perpendicular to B1B2. Prove that A±D = DA2. (3 points)
3.	Prove that from any sequence of 1996 real numbers ai, 02, • • • > ai996
one can choose one or several numbers standing successively one
after another so that their sum differs from an integer by less than
0.001.	(A Kanel, 3 points)
4.	A rook stands at a corner of an m x n squared board. Two play-
ers move the rook in turn (vertically or horizontally through any
numbers of squares). As the rook moves, it paints the squares that
it visits (stopping or passing through). The rook is not allowed
to pass through or stop at the painted squares. The player who
cannot move, loses. Who has a guaranteed win: the first player
(who starts the game) or the other, and how should he/she play?
(B Begun, 5 points)
5.	Eight students were asked to solve 8 problems (the same set of
problems for each of the students).
(a)	Each problem was solved by 5 students. Prove that one can
find two students so that each of the problems was solved by
at least one of them.	(3 points)
(b)	If each problem was solved by 4 students, then it is possible
that no such pair of students exists. Prove this.
(S Tokarev, 3 points)
92
TOURNAMENT 17
6.	In an equilateral triangle ABC, let D be a point on the side
AB such that AD = AB/n. Prove that the sum of n — 1 an-
gles ZPPiX, ADP2A,..., ADPn_±A where Pi, P2, •.., Pn-i are the
points dividing the side BC into n equal parts, is equal to 30 de-
grees if
(a)	n = 3;	(3 points)
(b)	n is an arbitrary integer, n > 2. (V Proizvolov, 5 points)
Senior Questions
93
SENIOR QUESTIONS
Autumn 1995 (0 Level)
1.	A square is placed in the plane and a point P is marked in this
plane with invisible ink. A certain person can see this point through
special glasses. One can draw a straight line and this person will
say on which side of the line the point P lies. If P lies on the line,
the person says so. What is the minimal number of questions one
needs to find out if P lies inside the square or not? (3 points)
2.	Do there exist
(a)	four	(2 points)
(b)	five	(2 points)
distinct positive integers such that the sum of any three of them is
a prime number?	(V Senderov)
3.	The first digit of a 6-digit number is 5. Is it true that it is always
possible to write 6 more digits to the right of this number so that
the resulting 12-digit number is a perfect square?
(A Tolpygo, 3 points)
4.	Three different points A, В and C are placed in the plane. Con-
struct a line m through C so that the product of the distances from
A and В to m has the maximal value. Is m unique for every triple
A, В and C?
(NB Vassiliev, 5 points)
94
TOURNAMENT 17
Autumn 1995 (A Level)
1.	If P is a point inside a convex quadrilateral ABCD, let the angle
bisectors of ZAPB, /.BPC, LCPD and LDP A meet AB, BC, CD
and DA at К, L, M and N respectively.
(a)	Find a point P such that KLMN is a parallelogram.
(3 points)
(b)	Find the locus of all such points P. (S Tokarev, 2 points)
2.	Let p be the product of n real numbers xi,X2,... ,xn. Prove that
if p — Xk is an odd integer for к = 1, 2,..., n, then each of the
numbers rci, x%,... ,xn is irrational.	(G Galperin, 5 points)
3.	A rectangle with sides of lengths a and b (a > b) is cut into right-
angled triangles so that any two of these triangles either have a
common side, a common vertex or no common points. Moreover,
any common side of two triangles is a leg of one of them and the
hypotenuse of the other. Prove that a > 2b.
(A Shapovalov, 5 points)
4.	Along a track for cross-country skiing, 1000 seats are placed in a
row and numbered in order from 1 to 1000. By mistake, n tick-
ets were sold, 100 < n < 1000, each with one of the numbers
1,2,..., 100 printed on it. Also for each number 1,2,..., 100 there
exists at least one ticket with this number printed on it. Of course,
there are tickets that have the same seat numbers. These n spec-
tators arrive one at a time.
Each goes to the seat shown on his ticket and occupies it if it is
still empty. If not, he just says “Oh” and moves to the seat with
the next number. This is repeated until he finds an empty seat
and occupies it, saying “Oh” once for each occupied seat passed
over but not at any other time. Prove that all the spectators will
be seated and that the total number of the exclamations “Oh”
that have been made before all the spectators are seated does not
depend on the order in which the n spectators arrive, although it
does depend on the distribution of numbers on the tickets.
(A Shen, 6 points)
Senior Questions
95
5.	Version for Nordic Countries
Six pine trees grow on the shore of a circular lake. It is known that
a treasure is submerged at the mid-point T between the intersection
points of the altitudes of two triangles, the vertices of one being
at three of the 6 pines, and the vertices of the second one at the
other three pines. At how many points T must one dive to find the
treasure?
Version for Tropical Countries
A captain finds his way to Treasure Island, which is circular in
shape. He knows that there is treasure buried at the midpoint of
the segment joining the orthocentres of triangles ABC and DEF,
where А, В, C, D, E and F are six palm trees on the shore of the
island, not necessarily in cyclic order. He finds the trees all right,
but does not know which tree is denoted by which letter. What is
the maximum number of points at which the captain has to dig in
order to recover the treasure?	(S Markelov, 7 points)
6.	Does there exist an increasing arithmetic progression of
(a)	11
(b)	10000
(c)	infinitely many
(3 points)
(4 points)
(2 points)
positive integers such that the sums of their digits in base 10 also
form an increasing arithmetic progression? (A Shapovalov)
96
TOURNAMENT 17
Spring 1996 (О Level)
1.	People are asked “Do you think that the new president will be
better than the most recent one?” Suppose a people say “better”,
b say “the same” and c “worse”. Sociologists then calculate two
measures of “social optimism”: m = a + | and n = a — c. Suppose
exactly 100 people respond to this survey and it turns out that
m = 40. Find n.	(A Kovaldji, 3 points)
2.	The digits 1,2, 3,..., 9 are written down in some order so that they
form a 9-digit number. Consider all triples of consecutive digits and
find the sum of these seven 3-digit numbers. What is the largest
possible value of this sum?	(A Galochkin, 3 points)
3.	Consider the factorials of the first 100 positive integers, namely,
1!, 2!,..., 100!. Is it possible to delete one of them so that the
product of the remaining ones is a perfect square?
(S Tokarev, 4 points)
4.	Is it possible to tile space using a combination of regular tetrahedra
and regular octahedra?	(A Belov, 4 points)
5.	The squares AB MN ,BCKL and ACPQ are constructed outside
triangle ABC. The difference between the areas of AB MN and
BCKL is d. Find the difference between the areas of the squares
with sides NQ and PK respectively, if /ABC is
(a)	a right angle;
(b)	not necessarily a right angle.
(3 points)
(A Gerko, 2 points)
Senior Questions
97
Spring 1996 (A Level)
1.	Does there exist a cube in space such that the perpendiculars
dropped from its eight vertices to a given plane are of length 0,
1, 2, 3, 4, 5, 6 and 7?	(V Proizvolov, 4 points)
2.	The square 0 < я < 1, 0 < у < lis drawn in the plane Oxy.
A grasshopper sitting at a point M with noninteger coordinates
outside this square jumps to a new point which is symmetrical to
M with respect to the leftmost (from the grasshopper’s point of
view) vertex of the square. Prove that no matter how many times
the grasshopper jumps, it will never reach the distance more than
lOd from the center C of the square, where d is the distance between
the initial position M and the center C. (A Kanel, 5 points)
3.	The angle LA of an isosceles triangle ABC (AB = AC) equals a.
Let D be a point on the side AB such that AD = AB/n. Find
the sum of n — 1 angles LDP^A, LDPzA,..LDPn-iA, where
Pi, P2,..., Pn-1 are the points dividing the side BC into n equal
parts if
(a)	n = 3;	(3 points)
(b)	n is an arbitrary integer, n > 2. (V Proizvolov, 4 points)
4.	There are two very strict laws in the country of Militaria.
(i)	Anyone who is shorter than 80% (or more) of his “neighbours”
(i.e. men living at distance less then r from him) is freed from
the military service.
(ii)	Anyone who is taller than 80% (or more) of his “neighbours”
(i.e. men living at distance less then R from him) is allowed
to serve in the police.
A nice thing is that each man X may choose his own (possibly
different) positive numbers r = r(X) and R = R(X). Can it
happen that 90% (or more) of the men in Militaria are free from
the army and, at the same time, 90% (or more) of the men in
Militaria are allowed to serve in the police? (The places of living
of the men are fixed points in the plane.)
(N Konstantinov, 6 points)
98
TOURNAMENT 17
5.	Prove that there exist an infinite number of triples n — 1, n, n + 1
such that
(a)	n can be represented as the sum of two squares of natural
numbers but neither of n — 1 and n + 1 can; (3 points)
(b)	each of these three numbers can be represented as the sum of
two squares.	(V Senderov, 5 points)
6.	At first all 2n rows of a 2n x n table were filled with all different
n-tuples of numbers +1 and —1. Then some of the numbers were
replaced by Os. Prove that one can choose a (non-empty) set of
rows such that:
(a)	the sum of all the numbers in all the chosen rows is 0;
(4 points)
(b)	the sum of all the chosen rows equals the zero row, that is,
the sum of numbers in each column of the chosen rows equals
0.	(G Kondakov, V Chernorutskii, 5 points)
Junior Solutions
99
JUNIOR SOLUTIONS
Autumn 1995 (0 Level)
1.	The answer is three questions.
Assume that P is inside the square and suppose that only two
questions have been asked. Then regardless of the location of the
square in the plane, there exists a point outside the square such that
if one asked the same two questions about this point, the answers
would be the same. This means that one cannot find out whether
P is inside the square or not by asking only two questions.
On the other hand, it is easily seen that three question are sufficient.
For example, let the first line be along one of the diagonals of the
square. Then depending on the answer, the next two lines are along
the sides of the square that are on the same side of the first line as
P.
2.	The answer is yes.
We choose 1,2,22, 23,..., 22n+1 and 3, 3 • 2, 3 • 23, 3 • 25,..., 3 • 22n~r.
The least common multiple of these 3n + 3 numbers is clearly
3 • 22n+1 and their sum is given by
22n+2 _ ! + з + 2(22n _ !) = 3.22n+1.
If n = 33, we have 102 numbers 1, 2,4,8,16, 32, 64,..., 267 and
3, 6,24,96,..., 3 • 265. When we replace 4 and 8 by 12, and 16 and
32 by 48, we have 100 distinct positive integers with the desired
property.
3.	Let the fold be along EF with E on BC and F on DA. Then
the midpoint of EF is the centre of ABCD. Hence AECF is a
rhombus. Since СЕ — AE > BE, the area of ABE is less than
100
TOURNAMENT 17
Now the area of the pentagon is the sum of that of ABE and
CEFD. Since the latter is equal to the area of the pentagon is
less than
4.	Note that we have
LKAM = LKAC + LCAM = LABC + LB AM = LKMA.
Since LMAN = 90°, LKAN = LKNA. Hence KM = KA =
KN.
Junior Solutions
101
Autumn 1995 (A Level)
1.	Let ABC be any triangle. Construct P as the second point of
intersection of two arcs, one being the locus of the points X such
that LAX В — 240° — LCAB — LABC and X is on the same side
of AB as C, and the other the locus of the points X such that
LAXC = 240° — LBCA — LCAB and X is on the same side of AC
as B.
Since the sum of these two angles is equal to 300° — LCAB > 180°,
the point P is inside ABC. Drop perpendiculars PD, PE and PF
onto ВС, CA and AB respectively. Then
LEFD = LEFP + LPFD
= LEAP + LPBD
= LCAB - LPAB + LABC - LPBA
= LCAB + LABC - (180° - LAPB)
= 60°.
Similarly, LDEF = 60° so that DEF is equilateral.
102
TOURNAMENT 17
2.	Denote the n-th term by an. Note that = 119. For n > 6,
®n+l “ anan~ 1 ' " * °1	1 = Лп(ОП “bl) 1’
Hence an+i — an + 1 — a2n. Summing this from n = 6 to n = 70,
we have
70	70
«71 - «6 + 65 = 5? an = 5? an - 55.
n=6	n=l
It follows that
70
й'п = <171 “ 119 + 120 = 071 + 1 — a70O69 ' * * al-
n=l
3.	Let BL meet the circumcircle of triangle BAK again at Pf. Then
LP'AK = /.P'BK = AP'BA = LP'KA
so that PfA = P'K. It follows that Pf = P,
Hence LPAK — ^LABC. Similarly, LQAK — ^LBCA^ so that
LPAQ = ^(LABC + ZBCA) = 90° - |z<7AB.
4.	(a) The answer is yes.
Let the journalist ask a person X about a person Y. If the
answer is “Yes”, Y is eliminated. If the answer is “No”, X
is eliminated. After n — 1 questions, the only one left must
be Z. Thus the journalist can find Z by asking less than n
questions.
Junior Solutions
103
(b) The answer is n — 1.
One can only find Z by eliminating all the others. Hence n — 1
questions are necessary as well as sufficient.
We utilize reflectional symmetry in a line €. Let ABB' be a
triangle such that A is on € while В1 is obtained by reflecting В
in A Let CC'D'D be a rectangle inside ABB' such that C and
C' are symmetric in as are D and Df. Now ABD'B'C'DC
and AB'DBCD'C' are the 7-gons with the desired properties.
(b) The answer is yes.
We utilize three-fold rotational symmetry. Let AA1A2 and
BB1B2 be equilateral triangles with centre О as shown. Then
104
TOURNAMENT 17
OABiВ A1A2B24 О A1B2B1A2AB and О A%B B2AA1B1 are
the 7-gons with the desired properties.
6. (a) Let the players be Alice and Bob. Alice can build up any
configuration with n or less chips as long as it does not contain
any block of chips longer than 16, because she can replace
what Bob removes and continue building. Thus she can have
12 blocks of 8 chips each, with a gap of one space between any
two adjacent blocks. In her next move, she can convert it to
8 blocks of 8 chips each in between 2 blocks of 17 chips each.
She can now win in her next move. If Bob removes a block of
8, Alice can replace it and take 9 chips from the ends to fill in
the gaps. If he removes a block of 17, she can use 8 chips to
fill in the gap and add the remaining ones to the ends. If he
removes part of a block, she can remove the remaining part of
that block for him if necessary.
(b) The answer is 98.
Suppose that the players played for a while and there are more
than 98 chips. Let the configuration on the board after the
first player made her last move be ai — «2 —	— a к where
ai, «2,. •., ak are positive integers which means that there are
ai chips occupying consecutive cells, then an empty cell, then
a2 chips occupying consecutive cells, then again an empty cell
and so on.
Assume that the first player can always win when making her
next move. Without loss of generality, we can assume that
all the chips are on the board. Then ai < 17 and ak < 17
otherwise the second player can take off the board more than
17 chip which means that the first player cannot win when
making her next move.
Since ai < 17 and ak < 17, there is i such that 1 < i < к and
a^k-2) >99 — 17 — 17 = 65.
Therefore
as the first player wins when she makes her next move. But
65	/—
----- + к - 1 > 2\/65 + 1 > 17
к — 2
which is a contradiction.
Junior Solutions
105
Spring 1996 (0 Level)
1.	Let the smallest angle be 0. Then the largest angle is bO. Since the
triangle is acute-angled, bO < 90° so that 0 < 18°. Since the third
angle is less than 50, we have 110 > 180° which implies 0 > 16°.
Hence 0 = 17°, the largest angle is 85° and the third one 78°.
2.	(a) For the prime number n = 101, n — 96 = 5 and n 4- 96 — 197
are both prime numbers. So the answer is yes.
(b) Note that the three numbers are congruent modulo 3 to 0, 1
and 2 in some order, meaning that one of them is divisible by
3. If such a number is to be a prime number, it must be 3
itself. However, if n — 1996 = 3, then n -h 1996 = 3995 is not
a prime number. Hence such n cannot exist.
3.	Let I be the incentre of triangle ABC. Then /СВ1 — /ABl. Let
the extension of BI cut CA at S, and drop the perpendicular ST
from S to AB. Then triangles CBS and TBS are congruent, so
that SC = ST. Since SC is tangent to the incircle, so is ST by
symmetry.
Hence T is in fact one of P and Q, say P. Similarly, if the tangent
through Q cuts BC at R, then we have RC = RQ. Drop the per-
pendicular CD from C to AB. Then /PCS = /CPS = /PCD,
and LQCR = LCQR = LQCD. Hence £PCQ = 1/.SCR = 45°.
4.	(a) The configuration, when the number of points of self-intersect-
ion is seven, is shown in the diagram.
106
TOURNAMENT 17
The fact that seven is the largest possible number is proven
in (b).
(b) For each edge I of the hexagon, we count the largest possible
number of self-intersect ion points on it. We consider three
cases according to the positions of the other four vertices rel-
ative to If they are all on the same side of it, t cannot
have any self-intersection point on it. If one is on one side
and three are on the other, then any self-intersection point on
£ must involve the first point, and therefore there are at most
two self-intersection points on £.
If the other four vertices are divided two and two, there are at
most three self-intersection points on I because some of these
four vertices must be joined to the endpoints of £. Note that
at most three edges of the hexagon satisfy the condition of
the last case. If we count the self-intersection points edge by
edge, we get at most 3-1-3-1-34-2-1-24-2 = 15. However,
this number must be even since every self-intersection point
is counted exactly twice. Hence 14 — 2 = 7 is indeed the
maximum.
5.	(a) The first player has a strategy which guarantees a draw. Start
on any cell, and play symmetrically to the second player’s
moves with respect to a centre line dividing the board into
two 10 x 5 halves. If the second player marks a cell symmetric
to a marked one, then mark any vacant cell and repeat the
process.
At the end, we have a symmetric pattern which guarantees
that F = S.
(b) The second player can use the same symmetry strategy to
guarantee that F = S', so that it is not possible for the first
player to force a win.
Junior Solutions
107
Spring 1996 (A Level)
1.	Alternative 1
Without loss of generality we can assume that a > c. Then it
suffices to show that c > b.
We have a2 + b2 — ab < a2. Hence a > b as b is positive. Therefore
a2 -h b2 — ab > b2 as a is positive. Thus c > b as required.
Alternative 2
Let us consider a triangle ABC such that BC = a, AC = b and
LAC В = 60°. Then AB = c. Also LA + LB = 120°. Therefore
either LA < LC < LB qt LA > LC > LB which means that either
a < c < b or a > c > b. Hence (a — c)(b — c) < 0.
2.	Since OiAi = O^Bi, LOiAiB-l — LO\BXA\. Therefore
LDArC = 90° - ZOMiBi = 90° - ZOiBMi = LA^CD
Hence AiD = CD.
Similarly A%D = CD. Hence A±D = A%D.
3.	Let [ж] be the biggest integer that does not exceed x and {ж} =
x — [ж]. Now we construct a new sequence bi, • • • ? ^1996 such
that bi = {ai}, &2 = {oi + 02}, &3 = {fli 4- 02 + 03}, • • •? &1996 =
{ai -h a 2 4-----4- О199б}. By the Pigeon-hole Principle, we can find
two numbers bi and bj, say, such that their difference is less than
0.001. Therefore from the sequence ai, 02, • • •, 01995 we can choose
one or several numbers standing successively one after another so
that their sum differs from an integer by less than 0.001.
108
TOURNAMENT 17
4.	Let the horizontal dimension n be greater than or equal to m. The
first player can force a win by always moving the rook horizontally
as far as possible, so that the second player can only respond with
vertical moves. Clearly, if the second player has a response after
the first player’s fc-th move, then the first player has a response
after the second player’s fc-th move as m < n. Thus the first player
always wins with the above strategy.
5.	(a) Assume that we cannot find two students so that each of the
problems was solved by at least one of them. Then for ev-
ery pair of students there is a problem such that neither of
the students in the pair solved it. Since there are 28 pairs of
students and 8 problems, by the Pigeon-hole Principle there
exists a problem and four pairs of students such that none
of the students in the pairs solved the problem. Hence this
problem was solved by fewer than 5 students which is a con-
tradiction.
(b) Let the first student solve problems 1, 2, 3, 4, the second
student the problems 1, 2, 5, 6, the third 3, 4, 5, 6, the fourth
1, 3, 7, 8, the fifth 2, 4, 7, 8, the sixth 2, 5, 6, 7, the seventh
1, 4, 5, 8 and the eighth 3, 6, 7, 8. Then it is easily seen that
each problem was solved by 4 students but any two students
solved at most seven problems altogether.
6. See solution to Problem 3 in Senior paper.
Senior Solutions
109
SENIOR SOLUTIONS
Autumn 1995 (0 Level)
1.	See solution to Problem 1 in Junior paper.
2.	(a) The answer is yes.
The sums of any three of the numbers 1, 3, 7 and 9 are the
primes 11, 13, 17 and 19 as required.
(b) The answer is no.
Suppose that we have five numbers with the required property.
We put each of the five integers into class 0, 1 or 2 according
to the remainder it leaves when divided by 3. If three of the
five numbers belong to different classes, then their sum is a
multiple of 3, which cannot be prime unless it is 3. However,
this is impossible since the positive integers are distinct. If
the five numbers are in at most two classes, then the Pigeon-
hole Principle guarantees that there will be three in the same
class. Once again, their sum will be a multiple of 3. This
contradiction shows that the answer to (b) is negative.
3.	There are 105 six-digit numbers beginning with 5. If the task is al-
ways possible, there must be at least 105 squares among the twelve-
digit numbers beginning with 5. However, if we have 50 • IO10 <
n2 < 60-IO10, then 49-IO10 < n2 < 64-IO10 or 7-105 < n < 8-105.
This yields less than 105 values of n, a contradiction. Thus the
task is not always possible.
4.	Let BC — a, AC = b and ZBCA = 7. First draw a line through C
so that A and В are on the same side of it. Let 0 denote the angle
between this line and CA.
110
TOURNAMENT 17
Then the desired product is given by
afrsin0 sin(0 + 7) = ^(cos7 — cos(7 + 20)).
Its maximum value of
ab .	_
— (cos 7 + 1)
Zu
is attained at 0 = In other words, the line we seek is the
external bisector of LBCA. If we draw this line so that A and
В are on opposite sides of it, similar calculations show that the
maximum value of
y(l-COS7)
is attained when this line is the internal bisector of LBCA. Clearly,
cos 7 + 1 > 1 — cos 7
unless 7 > Thus the line should be the external bisector of
LBCA if it is acute, its internal bisector if obtuse, and either if
LBCA is a right angle.
Senior Solutions
111
Autumn 1995 (A Level)
1.	(a) Let P be the point of intersection of the perpendicular bi-
sectors of the diagonals AC and BD. Then AP = PC and
BP = PD.
Since PK bisects /LAPВ and PN bisects £APD, we have
AK AP , AN AP
KB PB ND PD
KB ND
as PB = PD. Therefore KN is parallel to BD. Similarly
LM is parallel to BD, KL to AC and MN to AC. Hence
KN is parallel to LM and KL is parallel to NM which means
that KLMN is a parallelogram.
(b) There is only one point in question, namely the point of in-
tersection of the perpendicular bisectors of the diagonals. To
prove this, we assume that BP < PD. Then in the same way
as in (a), we obtain
AK AN	CL CM
--- > 	 and -> ---
KB ND----------------------LB MD
Therefore NК and ML extended meet the line DB extended
at points which are on the same side of В which means that
KN is not parallel to LM. Hence BP = PD and similarly
AP = PC. Therefore P is the point of intersection of the
perpendicular bisectors of AC and BD.
112
TOURNAMENT 17
2.	Assume that one of Xi, i = 1,2,..., n, is rational. Then p is rational
too. Let = p — x^ for A; — 1,2,..., n. Then x^ = p — a>k and
therefore (p — ai)(p — 02) • • • (p — an) = p. Thus p is a rational
root of an equation f (p) = 0 where /(p) is a polynomial of degree
n. Since the coefficient of the pn term in /(p) is 1, p must be an
integer. But neither even nor odd values of p satisfy the equation
(p — ai)(p — «2) • ’ * (p — an) = p as all a^, i = 1,2,..., n, are odd.
Now we come to a contradiction which means that none of x^
i = 1,2,..., n can be rational.
3.	First we shall show that not one of the vertices of the triangles is
inside the rectangle. Assume that X is a vertex inside the rectangle.
Let XAi be a side of one of the triangles. Clearly XAi is the
hypotenuse of one of the triangles. Let X A2 be a leg of this triangle.
Then XA2 < XAi. Also XA2 is the hypotenuse of another triangle
and we can repeat the above reasons and obtain a sequence of sides
XAi,XA2,XA3, ... such that XAi > XA2 > XA3 > .... Hence
we cannot come back to XAi, which is a contradiction.
Next we prove that there exists a triangle such that its hypotenuse
lies on a side of the rectangle. Let di be a hypotenuse which is
inside the rectangle. Then there exists a triangle with hypotenuse
d2 such that one of its legs is di. Then d2 > di. Similarly, we can
find a hypotenuse d3 such that d3 > d2. Thus we have a sequence
of hypotenuses di,d2,d3,... without repetitions which means that
the last term of this sequence is a hypotenuse lying on a side of the
rectangle.
Now let us consider a triangle of which the hypotenuse lies on a
side of the rectangle. Then the vertex which is opposite to the
hypotenuse lies on the opposite side of the rectangle as not one of
the vertices is inside the rectangle. Hence the other two sides of
the rectangle are equal to the height of the triangle from its right
angle. Since the height of a triangle from its right angle cannot be
longer than half its hypotenuse, we see that a > 2b.
4.	First of all, we shall prove that all the spectators will be seated.
Assume that one of the spectators could not find a seat. Then all
the seats from 101 to 1000 are occupied. If, of the first 100 seats,
only к are occupied, then at least 100 — к more spectators are not
seated. Hence there are at least 900 + к -h 100 — к + 1 = 1001
spectators with tickets, which is a contradiction.
Next we shall count the number of “Oh’s. For 1 < i < n, let f (z)
denote the number of spectators holding tickets numbered between
Senior Solutions
113
1 and i inclusive. Since there is at least one ticket numbered j for
1 < j < 100, we have f (i) > i. Consider a fixed i. Nobody other
than these f(i) spectators may occupy the г-th seat and i of them
will take up the first i seats. It follows that f(i) — i of them will
say “Oh” to the i-th seat, and the total number of times “Oh” is
said is /(0 — This depends only on the distribution
of the numbers on the tickets but not on the order in which the n
spectators arrive.
5.	The answer is one point.
Alternative 1
Label the trees А, В, C, D, E and F arbitrarily. Consider triangles
ABC and DEF. Denote the centroids of these triangles by Ti and
T2, and their orthocentres by Hi and Я2. Then the homothety with
centre Ti and coefficient —2 maps the centre О of the island to Hi
(because it maps ABC to the triangle A'B'C' such that А, В, C
are the midpoints of BfCf, C'A', AfBf and Hi is the circumcentre
of A'S'C'), and the homothety with centre T2 and coefficient —2
maps О to Я2. So the midpoint T between Ti and T2 lies on the
segment ОH where Я is the midpoint between Hi and Я2 and
OH = SOT. Since T is the centre of gravity for all six given points
and does not depend on the way we label the six trees, the Captain
needs to dig only one hole.
(A Liu)
Alternative 2
Let us consider four points А, В, C and D on the circumference
of a circle. We shall prove that if X and Y are the orthocentres
of the triangles ABC and BCD respectively, then AXYD is a
parallelogram.
Let S and T be the feet of the altitudes of the triangles ABC and
DBC from A and D respectively. Also let AS and DT extended cut
the circle again in P and Q respectively. Since BX is perpendicular
to AC, we have LXBS = 90° - LACB. Similarly LCAS = 90° -
LACB. Hence LXBS = /CAS. But ZCAP = ZCBP as these two
angles are subtended by the same arc. Therefore /.XBS = /.PBS.
Hence the right-angled triangles XSB and PS В are congruent
which implies that XS = PS. Similarly YT — QT. Since TS
is perpendicular to YQ and IP.we see that /YXS = /QPS.
114
TOURNAMENT 17
Since the line joining the midpoints of AP and DQ is perpendicular
to AP and DQ, LDAP = LQPA. Hence LDAP = LYXP which
means that AD is parallel to XY. Thus AXYD is a parallelogram
as AP is parallel to DQ.
Now suppose that we have two different pairs of triangles such that
the vertices of the triangles are some of the six palm trees and the
two triangles from one pair have no common vertices. Without
loss of generality, we can assume that one triangle from one pair
is ABC and one triangle from the other pair is BCD. Then if
X and Y are the orthocentres of the triangles ABC and BCD
respectively, the quadrilateral AXYD is a parallelogram. Since the
other triangles in the first and the second pairs are DEF and EFA
respectively, we see that AD MN is a parallelogram where M and
N are the orthocentres of the triangles DEF and EFA respectively.
Therefore XYMN is a parallelogram. Hence the midpoints of XM
and Y N coincide which means that all the midpoints in question
coincide and the captain has to dig only at one point.
(A Storozhev)
Alternative 3
Let the given circle be the unit circle in the complex plane. Then we
can identify positions of the trees as complex numbers z\, z^,..., zq.
Since 0, zm, zn, zm + zn are vertices of a rhombus, zm + zn is
perpendicular to the line joining zm and zn. Therefore for a triangle
with vertices zfc, zm, zn, every point z on the line perpendicular to
zmzn passing through zk can be expressed in the form
z — zk	"h zn\
Senior Solutions
115
where t is a real number. Hence the orthocentre hkmn of the tri-
angle with vertices zm, zn is
hkmn — zk Zm “h Zn
and the midpoint p of the segment joining the orthocentres of any
two triangles with vertices zfc, zm, zn and zr, zs, zt respectively
(where (fc, m, n, r, s, t) is any permutation of (1,2, 3,4, 5, 6)) is
hkmn + hrst Z1 + Z2 + Z3 + Z4 4- Z5 + Zq
P ~	2	~	2	’
Therefore it is at one single point where the captain has to dig.
(G Perz)
6.	(a) The answer is yes.
Let 9 be the first term and 109 the difference of an arithmetical
progression. Then the digit sums of the first eleven terms of
this progression form an increasing arithmetical progression.
(b) The answer is yes.
Let 1 + 2 x 105 + 3 x IO10 + 4 x 1015 + • • • + Ю4 x 1049995 be
the first term and 1 + 105 + IO10 + 1015 + • • • + 1049995 the
difference of an arithmetical progression. Then the digit sums
of the first 10 000 terms of this progression form an increasing
arithmetical progression.
(c) The answer is no.
Assume that the digit sums of the terms of an increasing infi-
nite arithmetical progression with first term a and difference
d form an increasing arithmetical progression. Let a be a
fc-digit number. Then the terms a + d x 10fc and a + d x 102fc
have the same digit sums which is a contradiction.
116
TOURNAMENT 17
Spring 1996 (О Level)
1.	Since exactly 100 people respond to the survey, we have a + b + c =
100. Also 2a + b = 2m = 80. By subtracting a + b + c = 100 from
2a + b — 80, we obtain n — a — c = —20.
2.	Let the digits be a, b, c, d, e, /, g, h and i in that order. Then the
sum of the three-digit numbers in question equals
100a + 110b + Ul(c + d + c + f + g^ + lib, + i-
It follows that this sum has the largest possible value if a = 3, b — 4,
h = 2 and i = l, while c, d, e, f and g can be any permutation of
5, 6, 7, 8 and 9. The maximum value of the sum is 300 4- 440 +
111(5 + 6 + 7 + 8 + 9) +22 + 1 = 4648.
3.	The answer is yes.
Let us throw out perfect squares from the product of the factorials
of the first 100 positive integers. Since 3! = 3-2!, we can replace
3! and 2! with a single 3. Similarly, we can replace 4! and 5! by 5,
6! and 7! by 7, and so on. We will be left with 1 • 3 • 5 • • • 99 • 100!.
We can now throw out all the odd numbers and will be left with
2 • 4 • 6 • • • 100 ~ 250 • 50!. Throwing out the perfect square 250,
we will be left with 50!. It follows that if we throw out 50! at the
start, we will be left with a perfect square.
4.	The answer is yes.
Let ABC DA' B'C' Df be a parallelopiped such that LBAD =
LBAA' = LDAA' = 60° and all the edges of ABCDA'B'C'D'
are of the same length. Then ABC DA' B'C' D' can be cut into two
Senior Solutions
117
regular tetrahedra ABDA' and C'B'D'C and one regular octahe-
dron A'BB'D'DC. Since the space can be tiled by parallelepipeds
congruent to ABC DA' B'C' D', the space can be tiled by regular
tetrahedra and regular octahedra.
5.	The answer is 3d regardless of whether /ABC is a right angle or
not.
By the Cosine Law, we have
NQ2 = AN2 + AQ2 — 2AN  AQ cos N AQ
= AB2 + AC2 -2AB  AC cos NAQ
and
ВС2 = AB2 + AC2 - 2AB  AC cos В AC.
Since /.NAQ -h /ВАС = 180°, the sum of their cosines is 0.
It follows that NQ2 + BC2 — 2AB2 + 2AC2. Similarly PK2 +
AB2 = 2BC2 + 2AC2. Hence NQ2 - PK2 = ЗАВ2 - 3BC2 = 3d.
118
TOURNAMENT 17
Spring 1996 (A Level)
1.	The answer is yes.
It is easily checked that the vertices
(0,0,0), (0,24/5,1),
determine a cube that satisfies the requirements.
2.	Let us divide the plane Oxy into squares n<x<n + l,m<
у < m + 1 where m and n are integers. We shall call the number
|m| + |n| the distance between the squares 0 < ж < 1, 0 < 3/ < 1
and m < .x < m + 1, n < г/ < n + 1.
It is easily seen that if we construct a square which is symmetrical
to the square m < ж < m + 1, n < у < n + 1 with respect to
the leftmost vertex of the square 0<ж<1,0<?/<1, then the
distance from this new square to the square 0<ж<1,0<?/<1
will be |m| + |n|. If the grasshopper was originally in the square
m < a? < m + 1, n < у < n + 1 with m 0, n we have
Let f be the maximal distance that the grasshopper can jump from
C. Then
f2< (и + |)2+(ы + |У
\	/	\	£ J
for some p and q such that |p| + |q| = |m| + |n|. Since
we see that
/	1 \ 2	/1 \ 2
/2<(м + |п| + -) Ц-) .
Therefore f < lOd as
2
Senior Solutions
119
Now assume that one of m and n, say m, is 0. Then
/	1\2
d2 - (|n| " 2)
and
Hence f < lOd as
3.	We shall prove the required statement for an arbitrary n, n > 2.
Let Di be a point on AC such that DD± is parallel to BC. Denote
the desired sum by S. By symmetry,
S = AAP1D1 + AAP2Dr + - • • + AAPn-rDi.
Hence
2S = AAP^D + AAP2D + * * - + AAPn_±D
+AAP1D1 Я- AAP2Di +  •  + AAPn—±Di
= ADP1D1 + AD P2Di + • • • + AD Pn—iDi.
Also let Pn = C. Then
S = |(ZPP1Pi + ZPP2Pi + --- + ZPPn_1P1)
= |(ZPi£>1P2 + ZP2£>1P3 + --- + ZPn_1Z>1Pn)
= jzPrPiC
2*
Thus the answer is
The following diagram illustrates the case n = 5.
120
TOURNAMENT 17
4.	The answer is yes.
Consider the following example. The men of Militaria live in points
of one line. They are grouped into settlements. Each settlement is
determined by parameters s, d, B, a, h and consists of 10 men.
Let us describe an (s, d, R, a, /i)-settlement (we assume that d > 0,
a > 0, h > 0, a > 97г). The men of this settlement live in the points
d	d	d
s +d,s +	+ -,... ,s +
о	9
Their heights are a, a — /г, a — 2h,... , a — 97г and the values R
chosen by them are
d d d
d,3’ 9’	’ 35
respectively.
Note that nine of them, except the last one, are taller than all of
their neighbours in the settlement. Now consider 100 settlements
Bq, Bi,..., B99. For each settlement Bi, its parameters are
Si = di = ai = 100 + i, h = 0.1.
Let these 100 settlements form Militaria, so that the total number
of men in Militaria is 1000. All neighbours of each man within R
live in his settlement. Hence only 100 men are not accepted by the
police service (the rightmost ones in each settlement).
Each man in the settlement Bi chooses
100
r —	•
Зг
Senior Solutions
121
Then he is taller than at most 9 of his neighbours (they are all
from his settlement). The rest of his neighbours are all men from
the settlements Bj with j > i and they are taller than him. Their
number is at least 50 when i < 95. Therefore all men from the
settlements Bi with i < 95 are free from the army service and their
total number is 950.
5.	(a) It is easily checked that the possible remainders of the sum
of any two squares when it is divided by 16, are 0, 1, 2, 4,
5, 8, 9, 10, 13. Therefore every triple n — l,n,n 4- 1 with
n = (8k + 2)2 + (8k 4- 3)2 satisfies the requirements.
(b) Let x be a natural number. Denote a = ж2 — x. Therefore the
triple
77, — 1	=	2(Z2	” (22 4~ Q2
n	=	2a2	+ 1 = 2(x2 - x)2 +	1
=	(x2 - 2x)2 + (x2 -	I)2
77, -j- 1	=	2a2	+ 2 — (a 4- 1)^ Ч- (cl	—	1)^.
satisfies the requirements.
6. We shall prove that one can choose a non-empty set of rows such
that the sum of all the chosen rows equals the zero row.
To make the explanations shorter, we introduce the following nota-
tion. Let ai, <22? • • •, cL2n be the rows of the original (without zeros)
table so that ai = (1,1,, 1) and «2™ = (—1? —1? • • •, —1), and let
f (a^ be the corresponding row of the table with zeros. If x is an
arbitrary row consisting of Is, —Is and Os, let g(x) denote the row
of the original table that has — Is exactly at the same places where
x has Is.
Now we construct the following sequence of rows:
bl = /(«i),b2 = bl + f (p(bi)),i>3 = b2 + №(*>2))
and so on up to
= 62^-1 + f(g(^2n-i))-
It is easily seen that each bi contains only Is and Os. So there are at
most 2n different terms of the sequence {bi}. Hence if this sequence
does not contain the zero row, by the pigeon-hole principle there
exist two terms, bm and bn say, such that bm = bn.
122
TOURNAMENT 17
Without loss of generality we can assume that \m — n| has the
minimal possible value. It follows then that
/(P(bm)),/(p(bm+l)), - . . , f (p(bn-l))
are different rows of the table with zeros such that their sum is the
zero row.
Thus it remains to study the case when one of the terms, say bi, is
the zero row and any two of the terms are different. In this case we
can see that bi is the sum of different rows of the table with zeros
so the proof is completed.
в

TOURNAMENT 18
JUNIOR QUESTIONS
Autumn 1996 (0 Level)
1.	Do there exist 10 consecutive positive integers such that the sum of
their squares is equal to the sum of squares of the next 9 integers?
(Inspired by a diagram in an old text book, 3 points)
2.	For what positive integers n is it possible to tile an equilateral
triangle of side n with trapezoids each of which has sides 1, 1, 1,
2?	(NB Vassiliev, 3 points)
3.	(a) Can it happen that in a group of 10 girls and 9 boys,.all the
girls know a different number of boys while all the boys know
the same number of girls?	(2 points)
(b) What if there are 11 girls and 10 boys?
(NB Vassiliev, 2 points)
4.	A circle cuts each side of a rhombus twice thus dividing each side
into three segments. Let us go around the perimeter of the rhombus
clockwise beginning at a vertex and paint these segments succes-
sively in red, white and blue. Prove that the sum of lengths of the
blue segments equals that of the red ones.
(V Proizvolov, 4 points)
126
TOURNAMENT 18
Autumn 1996 (A Level)
1.	Can one paint four points in the plane red and another four points
black so that any three points of the same colour are vertices of a
parallelogram whose fourth vertex is a point of the other colour?
(NB Vassiliev, 3 points)
2.	Do there exist three different prime numbers p, q and r such that
p2 + d is divisible by gr, q2 + d is divisible by rp and r2 + d is
divisible by pg, if
(a)	d = 10;	(2 points)
(b)	d = 11?	(V Senderov, 2 points)
3.	Prove that
2	7	14	23 k2 - 2	9998	o
2! + 3!	+ ¥	+ 5?	+ " ’+ —кГ~ +	’''+ looT <
where n! = 1 x 2 x ••• x n.	(V Senderov, 5 points)
4.	(a) A square is cut into right triangles with legs of lengths 3 and
4. Prove that the total number of the triangles is even.
(2 points)
(b) A rectangle is cut into right triangles with legs of lengths 1
and 2. Prove that the total number of the triangles is even.
(A Shapovalov, 4 points)
5.	Does there exist a 6^digit number A such that none of its 500 000
multiples A, 2A, ЗА, ..., 500 000A ends in 6 identical digits?
(S Tokarev, 8 points)
6.	The integers from 1 to 36 are written on a “mathlotto” ticket.
When you buy a “mathlotto” ticket, you choose 6 of these 36 num-
bers. Then 6 of the integers from 1 to 36 are drawn, and a winning
ticket is one which does not contain any of them. Prove that
(a)	if you buy 9 tickets, you can choose your numbers so that
regardless of which numbers are drawn, you are guaranteed
to have at least one winning ticket;	(5 points)
(b)	if you buy only 8 tickets, it is possible for you not to have any
winning tickets, regardless of how you choose your numbers.
(S Tokarev, 5 points)
Junior Questions
127
Spring 1997 (0 Level)
1.	How many integers from 1 to 1997 have the sum of their digits
divisible by 5?	(AI Galochkin, 3 points)
2.	Baron Munchausen plays billiards on a table with the shape of an
equilateral triangle. He claims to have shot a ball from one of the
sides of this table so that it passed through a certain point three
times in three different directions and then returned to the original
point on the side. Can that be true, assuming that the usual law
of reflection holds?	(M Evdokimov, 3 points)
3.	The vertical diameter of a circle is moved a centimetres to the right,
and the horizontal diameter of this circle is moved b centimetres
up. These two lines divide the circle into four pieces. Consider the
sum of the areas of the largest and the smallest pieces, and the sum
of the areas of the other two pieces. Find the difference between
these two sums.	(G Galperin, NB Vassiliev, 4 points)
4.	A square is cut into 25 smaller squares, exactly 24 of which are
unit squares. Find the area of the original square.
(V Proizvolov, 4 points)
5.	E is the midpoint of the side AD of a parallelogram ABCD. F
is the foot of the perpendicular from the vertex В to the line CE.
Prove that ABF is an isosceles triangle.
(MA Bolchkevich, 4 points)
128
TOURNAMENT 18
Spring 1997 (A Level)
1.	One side of a triangle is equal to one third of the sum of the other
two. Prove that the angle opposite the first side is the smallest
angle of the triangle.	(AK Tolpygo, 3 points)
2.	You are given 25 pieces of cheese of different weights. Is it always
possible to cut one of the pieces into two parts and put the 26
pieces in two packets so that
•	each packet contains 13 pieces;
•	the total weights of the two packets are equal;
•	the two parts of the piece which has been cut are in different
packets.	Dolnikov, 5 points)
3.	In a chess tournament, each of 2n players plays every other player
once in each of two rounds. A win is worth 1 point, a draw is worth
point and a loss is worth nothing. Prove that if for every player,
the total score in the first round differs from that in the second
round by at least n points, then this difference is exactly n points
for every player.	(B Frenkin, 5 points)
4.	AC' BA'C B' is a convex hexagon such that AB' = AC', BC' —
BA', CA' = CB' and LA + LB + LC = LA' + LB' + LC'. Prove
that the area of the triangle ABC is half the area of the hexagon.
(V Proizvolov, 6 points)
5.	Prove that the number
(a)	9797;
(b)	199717
(4 points)
(AA Egorov, 4 points)
cannot be equal to a sum of cubes of several consecutive integers.
6.	Let P be a point inside the triangle ABC such that AB = BC,
LABC = 80°, LPAC = 40° and LACP = 30°. Find LBPC.
(G Galperin, 7 points)
Junior Questions
129
7.	You are given a balance and one copy of each of ten weights of 1,
2, 4, 8, 16, 32, 64, 128, 256 and 512 grams. An object weighing M
grams, where M is a positive integer, is put on one of the pans and
may be balanced in different ways by placing various combinations
of the given weights on either pan of the balance.
(a)	Prove that no object may be balanced in more than 89 ways.
(5 points)
(b)	Find a value of M such that an object weighing M grams can
be balanced in 89 ways.
(A Shapovalov, A Kulakov, 4 points)
130
TOURNAMENT 18
SENIOR QUESTIONS
Autumn 1996 (0 Level)
1.	Consider three edges a, 6, c of a cube such that no two of these
edges lie in one plane. Find the locus of points inside the cube
which are equidistant from a, b and с, (V Proizvolov, 3 points)
2.	Can a paper circle be cut into pieces and then rearranged into a
square of the same area, if only a finite number of cuts is allowed
and they must be along segments of straight lines or circular arcs?
(A Belov, 3 points)
3.	The parabola у = x2 is drawn in the coordinate plane and then the
axes are erased so that the whole parabola stays on the picture but
the origin is not shown on it. Reconstruct the axes with compass
and ruler alone.	(A Egorov, 4 points)
4.	For what integers n > 1 can it happen that in a group of n -h 1 girls
and n boys, all the girls know a different number of boys while all
the boys know the same number of girls? (NB Vassiliev, 4 points)
Senior-Questions
131
Autumn 1996 (A Level)
1.	Can one paint four vertices of a cube red and the other four points
black so that any plane passing through three points of the same
colour contains a vertex of the other colour?
(Mebius, Sharygin, 3 points)
2.	(a) Prove that
2	22 - 2	32 - 2 n2 - 2 o
3 ~ 7----ni <	-----1--4i----1-----1---i— < 3*
(n — 1)!	2!	3!	n!
(3 points)
(b) Find some positive integers a, b and c such that for any n > 2,
с 23 — a 33 — a	n3 — a
Ь ~ (^2)! < ~2T + ~3!~ + ’ ’' +	< b•
(V Senderov, NB Vassiliev, 3 points)
3.	Let А', В', C', B', E' and F' be the midpoints of the sides AB, BC,
CB, DE, EF and FA of an arbitrary convex hexagon ABCDEF
respectively. Express the area of ABCDEF in terms of the areas
of the triangles ABC', BCD', CDE', DEF', EFA' and FAB'.
(A Lopshitz, NB Vassiliev, 5 points)
4.	Prove that for any function /(ж), continuous or otherwise,
/(/(я)) = x2 - 1996
cannot hold for all real numbers x.
(S Bogatiy, M Smurov, 10 points)
132
TOURNAMENT 18
5.	A certain island has some ports along the coast and some towns
inland. All roads on this island are one-way, and they do not meet
except at a port or a town. Moreover, once you leave a certain port
or town by road, there is no way you can return there by road. For
any two ports i and j, let fij denote the number of different routes
along the roads between i and j,
(a)	Suppose there are four ports on the island: 1, 2, 3 and 4, in
clockwise order. Show that /14/23 > /13/24-	(4 points)
(b)	Suppose there were six ports on the island: 1, 2, 3, 4, 5 and
6, in clockwise order. Show that
/16/25/34 + /15/24/36 + /14/26/35
> /16/24/35 + /15/26/34 + /14/25/36-
(S Fomin, 6 points)
6.	The integers from 1 to 100 are written on a “mathlotto” ticket.
When you buy a “mathlotto” ticket, you choose 10 of these 100
numbers. Then 10 of the integers from 1 to 100 are drawn, and a
winning ticket is one which does not contain any of them. Prove
that
(a)	if you buy 13 tickets, you can choose your numbers so that
regardless of which numbers are drawn, you are guaranteed to
have at least one winning ticket;	(5 points)
(b)	if you buy only 12 tickets, it is possible for you not to have any
winning tickets, regardless of how you choose your numbers.
(S Tokarev, 5 points)
Senior Questions
133
Spring 1997 (0 Level)
1.	A cube is cut into 99 smaller cubes, exactly 98 of which are unit
cubes. Find the volume of the original cube.
(V Proizvolov, 3 points)
2.	Let a and b be positive integers. If a2 4- b2 is divisible by a6, prove
that a — b.	(BR Frenkin, 3 points)
3.	A circle centred at (a, 6) contains the origin (0,0). Denote by S+ the
total area of the parts of the circle in the first and third quadrants,
and by S~ the total area of the parts of the circle in the second
and the fourth quadrants. Compute S+ — S~.
(G Galperin, 4 points)
4.	All edges of a tetrahedron ABCD are equal. The tetrahedron
ABCD is inscribed in a sphere. CC' and DD' are diameters. Find
the angle between the planes ABC' and ACDf.
(A Zaslavskiy, 4 points)
5.	In a game, the first player paints a point on the plane red; the
second player paints 10 uncoloured points on the plane green; then
the first player paints an uncoloured point on the plane red; the
second player paints 10 uncoloured points on the plane green; and
so on. The first player wins if there are three red points which
form an equilateral triangle. Can the second player prevent the
first player from winning?	(A Kanel, 4 points)
134
TOURNAMENT 18
Spring 1997 (A Level)
1.	You are given 25 pieces of cheese of different weights. Is it always
possible to cut one of the pieces into two parts and put the 26
pieces in two packets so that
•	each packet contains 13 pieces;
•	the total weights of the two packets are equal;
•	the two parts of the piece which has been cut are in different
packets?
(VL Dolnikov, 4 points)
2.	D and E are points on the sides BC and AC of a triangle ABC
such that AD and BE are angle bisectors of the triangle ABC. If
DE bisects /ADC, find /А.	(SI Tokarev, 5 points)
3.	You are given 20 weights such that any object of integer weight
m, 1 < m < 1997, can be balanced by placing it on one pan of a
balance and a subset of the weights on the other pan. What is the
minimal value of largest of the 20 weights if the weights are
(a)	all integers;	(3 points)
(b)	not necessarily integers?	(M Rasin, 3 points)
4.	A convex polygon G is placed inside a convex polygon F so that
their boundaries have no common points. A segment s joining two
points on the boundary of F is called a support chord for G if s
contains a side or only a vertex of G. Prove that
(a)	there exists a support chord for G such that its midpoint lies
on the boundary of G,
(6 points)
(b)	there exist at least two such chords. (P Pushkar, 2 points)
5.	Prove that
1 1 1
---------- _|_ ------- _]_-------- <C 1
1 -|- (2 -|- 6	1 4“ 6 “h C 1 “h C “h (2
where a, b and c are positive numbers such that abc = 1.
(G Galperin, 8 points)
Senior Questions
135
6.	Prove that if F(x) and G(x) are polynomials with coefficients 0
and 1 such that
F(o;)G(a:) = 1 + rc + x2 4----+ a:”-1
holds for some n > 1, then one of them can be represented in the
form
(1 + x + x2 4----+ a?fe-1) T(x)
for some к > 1 where Т(ж) is a polynomial with coefficients 0 and
1.	(V Senderov, M Vialiy, 8 points)
7.	Several strips and a circle of radius 1 are drawn on the plane. The
sum of the widths of the strips is 100. Prove that one can translate
each strip parallel to itself so that together they cover the circle.
(M Smurov, 8 points)
136
TOURNAMENT 18
JUNIOR SOLUTIONS
Autumn 1996 (0 Level)
1.	Let these 10 integers be n — 9, n — 8,..n so that the next 9
integers are n + 1, n + 2,..n + 9. Now
(n - 9)2 + (n - 8)2 H-+ n2 = (n + I)2 + (n + 2)2 H---+ (n + 9)2
simplifies to
n2 = 2(2n + 4n + • • • + 18n) = 180n
or n = 180. Hence the 10 integers are 171, 172, ..., 180.
2.	Let the area of an equilateral triangle of side 1 be S'. Then a
trapezoid which has sides 1, 1, 1, 2 has area 3S as it can cut into
three equilateral triangles of side 1 as shown.
The area of an equilateral triangle of side n is n2S. Therefore an
equilateral triangle of side n can be tiled with trapezoids each of
which has sides 1, 1, 1, 2 only if n is a multiple of 3. An equilateral
triangle of side 3 is easily divided into three trapezoids of the given
shape.
If the side length of an equilateral triangle is n — 3k for some integer
k, it can be divided into k2 equilateral triangles of side length 3,
each of which can be divided into three desired trapezoids. Hence
the answer is all positive integers n that are divisible by 3.
Junior Solutions
137
3.	(a) The numbers of boys known to the girls must be 0, 1, ..., 9.
Thus the total number of acquaintances between a boy and a
girl is 0 + 1 + • • • + 9 = 45. It follows that each boy knows
5 girls. Number the girls from 0 to 9 and the boys from 1 to
9. Girl number 0 knows no boys. For 1 < к < 4, girl number
к knows boys numbered 1 to fc. For 5 < к < 9, girl number
к knows boys numbered 10 — к to 9. It is easy to check that
each boy indeed knows 5 girls.
(b) The numbers of boys known to the girls must be 0, 1, ..10.
Thus the total number of acquaintances between a boy and a
girl is 0 +1 + • • • +10 = 55. Since this is not divisible by 10, it
is not possible for each boy to know the same number of girls.
4.	Let ABCD be the rhombus.
Suppose that the circle cuts the sides of the rhombus in E, F, G,
H, I, J, К and L so that AE, BG, CI, DK are the red segments
and FB, HC, JD, LA are the blue ones. Also let P, Q, R and S
be the midpoints of EF, GH, IJ and KL respectively. If О is the
centre of the circle, then OP is perpendicular to AB and OP is
perpendicular to CD. Hence PR is perpendicular to AB and CD.
Similarly QS is perpendicular to BC and AD. Since ABCD is a
rhombus, we have
AP - DR = AS - BQ = CQ - DS = CR - BP.
Hence
AP + BQ + CR + DS - PB - QC - RD - SA = 0.
Therefore
AE - FB + BG - HC + CI - JD + DK - LA = 0
138
TOURNAMENT 18
as P, Q, R and S are the midpoints of the middle segments. Thus
the sum of lengths of the blue segments equals that of the red ones.
Junior Solutions
139
Autumn 1996 (A Level)
1.	This is possible, as shown in the diagram below.
The desired parallelograms are ACD — B, ACG — E, ADG — F,
CDG - H, BEF - А, ВЕН - C, BFH - D and EFH - G.
2.	(a) Suppose p, q and r have the desired properties. We may as-
sume that p > q > r.
We cannot have r = 2 since r2 4- 10 = 2 • 7 and p > q > 2.
We cannot have r — 3 either since r2 + 10 = 19 is prime.
Hence r > 5. It follows that q > r 4- 2. Moreover, p > r 4- 6
since one of three consecutive odd integers is divisible by 3.
Now
r2 -|- 10 > pq > (r 4- 6)(r 4- 2) = r2 4- 8r 4- 12,
which is a contradiction. Hence no such prime numbers exist.
(b) We can have p = 5, q = 3 and r = 2. Then p2 4- 11 = 36 is
divisible by qr = 6, q2 + 11 = 20 is divisible by pr = 10 and
r2 4- 11 = 15 is divisible by pq — 15.
3.	For n > 2, let
2	7	n2 — 2
~ 3 " 2! " 3!
Then
4	(n 4-1)"
^2 = and cZn_|_j — dn -	 ;
2!	\n 4-.
We prove by induction that
n 4~ 2
140
TOURNAMENT 18
This is certainly the case for n = 2. Suppose it holds for some
n > 2. Then
n + 2 (n +	— 2 (n + 1) + 2
n+1 n! (n + 1)! (n +1)!
Since dn > 0 for all n > 2, the desired result follows.
4.	(a) The hypotenuse of a triangle with legs of length 3 and 4 has
length 5. Since all three sides of the triangle have integral
length, the length of each side of the square is an integer n.
Now the area of the square is n2 while the area of each triangle
is 6. Hence n must be divisible by 2 and 3, so that n = 6m
for some integer m. The number of triangles is therefore 6m2,
which is an even number.
(b) The rectangle is partitioned into triangles by segments. On
each side of the segment, we have complete legs and hypo-
tenuses of triangles. For any segment, let the numbers of
triangles with hypotenuses on it be b and d on the respec-
tive sides. Each triangle has legs of integral lengths and a
hypotenuse of length л/5. Hence the length of the segment is
a + by/б = c + dy/б for some integers a and c. Then
/- a — c
v 5 = -----.
d-b
Since a/5 is irrational, we must have d = b. It follows that the
number of triangles with hypotenuses inside the rectangle is
even. The same conclusion can be drawn about the number of
triangles with hypotenuses on the perimeter of the rectangle
if we treat each pair of opposite sides of the rectangle as a
single segment. Hence the total number of triangles is even.
5.	The answer is yes, the number in question exists.
Let A — 1000000 — 111111 = 888889 and assume that kA ends in
six identical digits. Then kA — 111111m is divisible by 1000000 for
some m such that 0 < m < 9. Hence 111111(A; + m) is divisible by
1000000 which means that к + m is divisible by 1000000. There-
fore m must be greater than 500000. Thus none of A, 2А, ЗА, ...,
500000A ends in 6 identical digits.
6.	(a) We buy the following 9 tickets: (1—6), (1—3,7—9), (4—9),
(10—15), (10—12,16—18), (13—18), (19—24), (25—30) and
Junior Solutions
141
(31—36). It takes 2 numbers to prevent a win by one of the
first 3 tickets, 2 more to prevent the next 3, and another 3 to
prevent the last 3. Since the three groups of tickets have no
numbers in common, and only 6 numbers are drawn, we must
have at least one winning ticket.
(b) Suppose only 8 tickets are bought. If one of the numbers ap-
pears on at least 3 tickets, it may be drawn along with one
number from each of the remaining tickets, and we will not
have a winning one. So assume that each of the numbers ap-
pears on at most 2 tickets. Then there are 6 x 8 — 36 = 12
numbers that appear on exactly two tickets. Now consider two
tickets with a common number. There are at most eleven num-
bers that appear on at least one of these two tickets. Therefore
there are another two tickets that have a common number.
Hence we can take a common number for the first pair of tick-
ets, a common number for the second pair and one number for
each of the remaining tickets, and we will not have a winning
ticket.
142
TOURNAMENT 18
Spring 1997 (О Level)
1.	Among the numbers from 1 to 9, only 5 has the desired property.
Consider the numbers from lOn to 10n-h9, 1 < n < 198. Regardless
of the sum of the digits of lOn, exactly two numbers among these
ten have the desired property. Among the numbers from 1990 to
1997, only 1991 and 1996 have the desired property. This yields a
total count of 399.
2.	Consider the lines which divide the billiards table into nine con-
gruent equilateral triangles.
They form a closed path which obeys the usual law of reflection and
passes through the centre of the table three times in three different
directions. Hence the answer is affirmative.
3.	Draw a line a centimetres to the left of the vertical diameter and
a line b centimetres below the horizontal diameter. Together with
the other two lines, they divide the circle into nine parts.
The parts labeled with the same digit on the diagram are congruent.
Hence their areas are equal. Therefore the difference between the
two sums is the area of a rectangle 2a centimetres by 2b centimetres.
Hence the difference is 4a6 centimetres.
Junior Solutions
143
4.	Let the original square have side m and the smaller square which
is not a unit square have side n. Clearly, there is a side of the
bigger square which has no common points with the square with
side n. Hence this side consists of sides of length 1. Therefore m
is an integer which implies that n is an integer too. Now we have
24 = m2 — n2 = (m + n)(m — n). Since m and n are integers,
m -bn and m — n must either be both odd or both even. Since their
product is 24, they are both even. It follows that either m +n = 12
and m — n = 2, or m 4- n = 6 and m — n = 4. In the first case,
m = 7 and n = 5. In the second case, m = 5 and n = 1, but we
cannot have n = 1. Hence the area of the original square is 49.
5.	Let G be the midpoint of the side BC. Then AG is parallel to CE
and therefore perpendicular to BF.
Moreover, since BG = GC, AG passes through the midpoint of
BF. It follows that AG is the perpendicular bisector of BF, and
we have AB = AF.
144
TOURNAMENT 18
Spring 1997 (A Level)
1.	It suffices to show that the first side is the shortest side of the
triangle. Let a, b and c be the sides of the triangle and
b + c
a = I-’
Then 3a = b + c. Assume that a > b. Then
c = 3a — b > 2a > a + b
which is not possible as a, b and c are the sides of a triangle. Hence
a is the shortest side of the triangle.
2.	Let the 25 pieces be ai, a2, .a25- First we put the pieces ai,
a2,..a 12 in one packet and the remaining pieces in the other one.
Assume that the total weight of the pieces in the first packet is less
than that in the second one. Now we start doing the following. We
take a25 from the second packet and put it in the first one. Then
we take ai from the first packet and put it in the second one. Then
we move a24 from the second packet to the first. Then we move a2
from the first packet to the second and so on.
At the end of this process we see that all the pieces from the second
packet are in the first one and vice versa. Thus now the first packet
is heavier than the second. This means that at some stage the first
packet contained 12 pieces and was lighter than the second but
after we moved ai from the second packet to the first, the first
packet got heavier. Hence we can cut ai into two parts and put the
26 pieces in the two packets as required.
3.	Alternative 1
Suppose m players did better in the first round than in the second.
Let their combined score in the two rounds be F± and F2 respec-
tively. Then the other 2n — m players did better in the second
round than in the first. Let their combined score in the two rounds
be Si and S2 respectively. We have
Fi — F2 > nm
while
S2 — Si > n(2n — m),
so that
(Fl + S2) — (F2 + Si) > 2n2.
Junior Solutions
145
Since
(Fl 4- S2) 4- (F2 + Si) = 2n(2n — 1),
we have
F2 4- Si < n2 — n.
On the other hand,
while
Si > — (2n — m)(2n — m — 1).
This simplifies to
0 > (m — n)2,
which implies that equality holds throughout. In particular, the
difference of the scores in the two rounds of each player is exactly
n.
Alternative 2
We divide the players into two groups: group 1 consists of the
players who improved their results in the second round and the
remaining players form group 2. There exists a player from group
1 whose total score against the players from the same group in the
second round was the same as or worse than that in the first round.
Then this player improved his or her score only by showing better
results when playing with the players from group 2 in the second
round. Hence there are at least n players in group 2.
By symmetry, there are at least n players in group 1 which means
that there are exactly n players in each group and for every player,
his or her total score against the players from the same group in the
first round was the same as that in the second round. Therefore
for every player, the total score in the first round differs from that
in the second round by exactly n.
4.	Let us cut the hexagon into four triangles: AC'B, BA'C, CB'A
and ABC. Since AB' = AC', BC' = BA', CA' = CB' and
LA + ZB + LC = LA' + LB' + LC' = 360°
we can rearrange the triangles AC'В, BA'C and CB'A into a tri-
angle XYZ such that XY = AB, YZ = BC and ZX — CA.
146
TOURNAMENT 18
Hence the triangles XYZ and ABC are congruent which implies
that their areas are equal. Therefore the area of the triangle ABC
is half of the area of the hexagon.
5.	Alternative 1
We claim that pk is not a cube or a sum of consecutive cubes for any
prime p / 3 and any positive integer к not divisible by 3. Suppose
to the contrary that
('„д.ПЗ , / , 9\3 ,	. 3	/n(n + 1)\2
p = (n + 1) 4-(n4-2) 4-----\-m = I ----------- I —I --------- I .
Then
4pfc = (m(m 4-1) 4- n(n 4-1))(^ 4- 4- 1)(тп — n).
Since the first factor is even, m — n = 1, 2, ph or 2ph for some
positive integer h < k. Suppose m = n 4- 1. Then the equation
simplifies topfc = (n + l)3, which cannot hold since к is not divisible
by 3. Suppose m = n 4- 2. Then the equation simplifies to
pk = (2n 4-3)(n2 4-3n 4-3).
Hence p divides both 2n 4- 3 and n2 4- 3n 4- 3. It follows that it
divides
4(n2 + 3n + 3) - (2n 4- 3)2 = 3.
This is a contradiction since p 3. Suppose m == n +ph. Then the
equation becomes
(2n2 4- 2n 4- ph(2n 4-1 4- ph))(2n 4-1 4- ph)ph = 4pfc.
Junior Solutions
147
Hence p divides both 2n2 + 2 and 2n + 1. It follows that it divides
(2n + I)2 — 2(2n2 +2n) = 1,
which cannot be. Finally, suppose m = n + 2ph. Then the equation
becomes
(2n2 + 2n + 2ph(2n + 1 + 2ph))(2n + 1 + 2ph)2ph = 4pk.
This can be handled in exactly the same way as in the preceding
case, completing the argument.
Alternative 2
(a)	When divided by 9, 9797 gives remainder 7. But no sum of
cubes of consecutive integers can have remainder 7 when di-
vided by 9 as the only possible remainders are 0, 1 and 8.
Hence 9797 cannot be equal to a sum of cubes of several con-
secutive integers.
(b)	When divided by 7, 199717 gives remainder 4. But no sum
of cubes of consecutive integers can have remainder 4 when
divided by 7 as the only possible remainders are 0, 1, 2, 5 and
6. Hence 199717 cannot be equal to a sum of cubes of several
consecutive integers.
6.	Let H be the foot of the altitude from В and let О be the point
where BH and CP meet. Since AB = ВС, /.OBC — 40° and
ZOAB = 20°. Hence LPOB = LOBC + LOCB = 60°. Also
LPOA = LOAC + LOCA = 60°.
Now we see that PO bisects LAO В and PA bisects LB AO. There-
fore BP bisect LABO. Hence LPBC = 60° and LBPC = 100°.
148
TOURNAMENT 18
7.	Let //c(m) denote the number of ways of balancing an object of
weight m using the weights 2°, 21,..2k. Then ffc(rn) = 0 for all
m > 2fc+1. We have Уо(1) = 1 and for к > 1, we can see that
ffc(2fc +1) = 0 + A_i(t) for 1 < t < 2fc;
A(2fc) = 0 + 1;
fk(2k~4t) = ffc_i(2fc-1+t)+/fc-i(2fc-(2fc-1+t)) for 1 < t < 2k~\
fk(2k~1)=l + l;
fk(t) =	+ A-i(2fc - t) for 1 < t < 2fc-X.
In each equation, the first term of the right-hand side is the number
of ways of balancing the object without using the weight 2fc, and
the second is the number of ways when using it. Suppose к > 2.
Applying the first of the above equations to the third and the fifth,
we obtain
fk(2k-' + t) = /fe_2(t) + fk-i(2k - (2k~r + t)) for 1 < t < 2k~\
fk(t) = /fc-i(0 + /fc-2(2fc-x - t) for 1 < t < 2fc-\
(a)	Consider the Fibonacci numbers defined by Fq — 1, F± = 2
and Ffc —	+ Ffc-2 for к > 2. We claim that for a fixed
к and any m, A(m) < Ffc. Since Fg = 89, it will follow that
no object may be balanced in more than 89 ways. We use
induction on k. The bases к = 0 and к = 1 are easily verified.
For the inductive step к > 2, we have F^-z > 1. The desired
result follows from the above equations.
(b)	We have fo(l) = -Fo and /1(1) = Fi-
Since
/fc (2fc-x + t) = /fe_2(t) + /fc_! (2fc - (2fc-x + t))
for 1 < t < 2fe-x, we have
/2(3)	= Л(1)	+	/1(1)	= F2-
/з(5)	= Л(1)	+	/2(3)	= F3;
/4(И)	=	/2(3)	+	/з(5)	= F^
/s(21)	=	/з(5)	+	/4(И)	= f5-,
/б(43)	= /4(11)	+	Л(21)	= F6-
Л(85)	= /5(21)	+	/б(43)	- f7;
/8(171)	= /б(43)	+	Л(85)	= Fs-,
/э(341)	= Л(85)	+	/8(171)	= F9.
Alternatively, since
/fc(t) = fk-l(t) + fk-2 (2fc-x — t)
for 1 < t < 2fc-x, we can obtain
/9(171) = /8(171) + /7(85) = F9.
Junior Solutions
149
It turns out that 171 and 341 are the only weights which can
be balanced in 89 ways.
150
TOURNAMENT 18
SENIOR SOLUTIONS
Autumn 1996 (0 Level)
1. Without loss of generality, we can assume that the cube is in a
coordinate space so that its vertices are (0, 0, 0), (1,0, 0), (0,1,0),
(1,1,0), (0,0,1), (1, 0,1), (0,1,1), (1,1,1) and a, 6, c join the ver-
tices (1,0,0) and (1,0,1), (0,1,0) and (1,1,0), (0,0,1) and (.0,1,1)
respectively.
Then for any point (x,y,z) inside the cube, the squares of its dis-
tances from a, b and c are (x —1)2+?/2, (y — l)24-z2 and (z—l)2+x2
respectively. We seek points for which they are equal to one an-
other. We may assume that x is the largest among x, у and z.
Suppose x > у > z. Now
(?/-l)2+z2= (z — I)2-f~ x2
simplifies to
x2 + 2y = y2 + 2z.
Since x2 > y2 and 2y > 2z, we must have x = у = z.
Suppose x > z > y. Then
(я - I)2 +y2 = (z - l)2 + x2
simplifies to
z2 + 2x = y2 + 2z.
Since z2 > y2 and 2x > 2z, we must have x = у = z also. Con-
versely, if x = у = z, clearly (x,y,z) will be equidistant from a,
b and c. It follows that the desired locus is the diagonal joining
(0,0,0) and (1,1,1), the two vertices not incident with any of a, b
and c.
2. Suppose the dissection is possible. For each piece, colour the parts
of its perimeter which are convex circular arcs red and those which
are concave circular arcs blue. Let r and b denote the total lengths
of the red and blue parts of all the pieces. When the pieces are
assembled into a square, each red part must be matched up against
a blue part, and vice versa, so that r = b. When the pieces are
assembled into a circle, each blue part must be matched up against
a red part, while those red parts that form the circumference of the
circle are not matched up against blue parts. Hence r > b which
contradicts r = b. Thus the dissection is impossible.
Senior Solutions
151
3. Draw two parallel chords and construct their midpoints. Let I
be the line joining these points. Draw a chord of the parabola
perpendicular to £ and construct its midpoint. The line through
this point parallel to £ will be the ?/-axis, cutting the parabola at
the origin. The line through the origin perpendicular to £ will be
the x-axis.
To justify our construction, let the first chord join the points
and (^2,^2) while the second join the points	and
(Ж4, «4).
Their respective slopes are
22	22
XT — Xo	. xi — xj
-------= xi + X2 and —--------= X3 + X4.
— X2	X3 — X4
Since the chords are parallel, we have xi 4- X2 = #3 + x±. Hence
their midpoints have the same x-coordinate, namely, +^2) =
|(хз + X4), and £ is indeed parallel to the ?/-axis.
4. If each girl knows a different number of the boys, they must know
0,1,..., n boys respectively. Hence the total number of acquain-
tances is ^n(n + 1). If each boy knows the same number of girls,
then this total is divisible by n, which means that n +1 is divisible
by 2. It follows that if n is even, the situation is impossible.
Suppose n = 2k + 1 for some positive integer k. Divide the girls
into к + 1 pairs. For 0 < i < fc, let one of the girls in the г-th pair
know i boys, and the other know the remaining 2к + 1 — i boys.
Then each girl knows a different number of boys. On the other
hand, each boy knows exactly one girl from each of the к + 1 pairs.
Thus the situation is possible for any odd integer n > 1.
152
TOURNAMENT 18
Autumn 1996 (A Level)
1.	This is possible, as shown in the diagram below.
The desired planes are ACD - B, ACG - E, ADG - F, CDG - H,
BEF - А, ВЕН - C, BFH - D and EFH - G.
2.	(a) For n > 2, let
. _O 2 7
n ~3 2! 3!
n2 - 2
n!
Then
and
dn+i — d
(n + I)2 - 2
(n + 1)!
n
We prove by induction that
n T 2
This is certainly the case for n — 2. Suppose it holds for some
n > 2. Then
Ti T 2 (n T 1)2 — 2
n+1 n! (n +1)!
which simplifies to
(n T 1) T 2
(n + 1)! ‘
Since
2
0 < dn < -	—
(n- 1)!
for all ti > 2, the desired result follows.
Senior Solutions
153
(b) First of all we notice that
к? — a 1	(	3	(	1 a
k\	= (к -	3)! +	(Л — 2)!	+	(к - 1)!	“ k\
for к > 2. Therefore if we let a = 5, we obtain
(n — 2)! (n — 1)! n!
n2 4- 3n -T 5
n!
It is easily seen that
n2 + 3n + 5 < 4n(n — 1)
for any n > 2.
Hence
n2 + 3n T 5	4
n!	(n — 2)!
which means that a = 5, b = 9, c — 4 is an answer.
3.	Since Af is the midpoint of the side AB, the length of the per-
pendicular dropped from Af to the line FE is half the sum of the
lengths of the perpendiculars dropped from A and В to the line
FE. Hence 2|BFA'| = \EFA\ + \EFB\.
Similarly, we have 2\FAB'\ = |FAB| + \FAC|, 2\ABC'\ = |ABC| +
\ABD\, 2\BCD'\ = \BCD\ + |BCF|, 2\CDE'\ = \CDE\ + \CDF\
154
TOURNAMENT 18
and 2\DEF'\ = |PBF| + \DEA|. On the other hand,
\ABCDEF\ = \EFA\ 4- |DBA| + |ABP| + |BCD|
= \FAB\ + \EFB\-4- \BCE\ + \CDE\
= |ABC| + \FAC\ 4- \CDF| 4- \DEF\.
It follows that the area of the hexagon is two-thirds the sum of the
areas of the six given triangles.
4.	Let g(x) = f(J(x)) = x2 — 1996. A fixed point of g(x) is a solution
of the equation x = g(x). Now x2 — x — 1996 = 0 has two real
solutions. Denote them by a and b. Let f(a) — p. Then /(p) =
/(/(a)) = a since a is a fixed point of g(x). Now /(/(p)) = f(a) =
p, so that p is also a fixed point of g(x). It follows that either
f(a) — a and /(d) = 5, or /(a) = b and /(d) — a. Let
h(x) - р(р(ж)) = (ж2 - 1996)2 - 1996.
To find the fixed points h(x\ we solve the equation
ж4 - 3992ж2 - x 4- 3982020 = 0.
Since both fixed points of g{x) are also fixed points of h(x), we can
factor the quartic polynomial and obtain
(ж2 - x - 1996) (ж2 4- x - 1995) = 0.
Now ж2 4- x — 1995 = 0 also has two real solutions. Denote them
by c and d. Let g{c}' — q. Then g(q) = g(g(c)) = c since c is a
fixed point of h(x). Now g(g(q)) = g(c) — q, so that q is also a
fixed point of Д(ж). Since c is not a fixed point of #(ж), we must
have g(c) — d, and g(d) = c. Let /(c) = r and /(d) = s. Then
/(r) = g(c) = d and /(s) = g(d) = c. Hence
h(r) = /(/(/(/(r)))) = /(/(/(d))) = /(/(«)) = /(c) = r,
so that r is also a fixed point of h(x). Clearly, r is not a or b since
{/(a),/(d)} = {a,d}. If r is c or d, then c or d must be a fixed
point of g(x) which is a contradiction.
5.	(a) If either /13 = 0 or /24 = 0, the result is trivial. Hence we
may assume that both are positive. Consider an ordered pair
(P, Q) where P is a path from 1 to 3 and Q is a path from 2
to 4. It defines a unique ordered pair (Я, 5) of a path R from
Senior Solutions
155
1 to 4 and a path S from 2 to 3 as follows. Since P and Q
must intersect, let X be the last town or port on both.
Then R follows P up to X and then switches to Q, while S fol-
lows Q up to X and then switches to P. This correspondence
shows that /14/23 > /13/24-
(b) Denote the set of triples of paths counted in /14/23/35 by
U and the set of those in /15/24/36 by V. Classify those in
/16/25/34 into four subsets as follows. W consists of triples
in which the (l,6)-path intersects the (3,4)-path. For a triple
in which this is not the case, put it in X if the (2,5)-path
intersects the (l,6)-path before it intersects the (3,4)-path if
at all, in Y if the (2,5)-path intersects the (3,4)-path before
it intersects the (l,6)-path if at all, and in Z if the (2,5)-path
intersects neither the (l,6)-path nor the (3,4)-path.
For a triple of paths counted in /16/24/35, put it in A if the
(l,6)-path intersects the (2,4)-path, and in В otherwise. For
a triple in /15/26/34, put it in C if the (2,6)-path intersects
the (3,4)-path, and in D otherwise. Put all those in /14/25/36
in E. Consider a triple of paths in W. At the first town
where the (l,6)-path intersects the (3,4)-path, we can switch
them around thereafter and get a (l,4)-path and a (3,6)-path,
thereby generating a triple in E.
Since this process is reversible, we have a one-to-one corre-
spondence between W and E. Similarly, we can establish
such correspondences between U and A, V and С, X and D,
and Y and B. The desired inequality follows, and is strict if
Z is non-empty.
6. (a) We can win if we buy the following tickets:
(1 - 10), (1 - 5,11 - 15), (6 - 15), (16 - 25),
(16 - 20, 26 - 30), (21 - 30), (31 - 40), (41 - 50),
(51 - 60), (61 - 70), (71-80),
(81-90) and (91-100).
It takes 2 numbers to prevent a win by one of the first 3 tickets,
2 more to prevent the next 3, and another 7 to prevent the
last 7. Since the three groups of tickets have no numbers in
common, and only 10 numbers are drawn, we must have at
least one winning ticket.
156
TOURNAMENT 18
(b) Suppose only 12 tickets are bought. If one of the numbers
appears on at least 3 tickets, it may be drawn along with
one number from each of the remaining tickets, and we will
not have a winning one. So assume that each of the numbers
appears on at most 2 tickets. Then there are 10 x 12 — 100 = 20
numbers that appear on exactly two tickets.
Now consider two tickets with a common number. There are
at most nineteen numbers that appear on at least one of these
two tickets. Therefore there are another two tickets that have
a common number. Hence we can take a common number for
the first pair of tickets, a common number for the second pair
and one number for each of the remaining tickets, and we will
not have a winning ticket.
Senior Solutions
157
Spring 1997 0 Level)
1.	Let the original cube have edge of length m and the smaller cube
which is not a unit cube have edge of length n. Clearly, there is an
edge of the bigger cube which has no common points with the cube
with edge of length n. Hence this edge consists of edges of length
1. Therefore m is an integer which implies that n is an integer too.
Now we have
98 = m3 — n3 = (m2 + mn T n2)(m — n).
There are three cases. In the first case, m2 + mn + n2 = 98 and
m — n = 1. Then 3m2 — 3m = 97. This is impossible since 97
is not a multiple of 3. In the second case, m2 + mn + n2 = 49
and m — n = 2. Then 3m2 — 6m — 45, leading to m = 5 and
n = 3. In the third case, m2 + mn + n2 = 14 and m — n = 7. Then
3m2 — 21m = —35. This is impossible since 35 is not a multiple of
3. Hence the volume of the original cube is 125.
2.	Let p be any prime divisor of a. Then p divides ab. which in turn
divides a2 + b2. Hence p is also a prime divisor of b. Suppose pm
is the highest power of p which divides a, and pn is the highest
power of p which divides b. We may assume that m > n. Now ad
is divisible by but a2 + b2 is not divisible by p2n+1. Hence
m + n < 2n + 1 or m < n. so that m — n. Since p is an arbitrary
prime divisor of a and d, we have a = b.
3.	Draw the lines x = 2a and у = 2b. Together with the coordinate
axes, they divide the circle into nine parts.
The parts labeled with the same digit on the diagram are congruent.
Hence their areas are equal. Therefore the difference between S+
and S~ is the area of a rectangle 2a by 2b. Hence S+ — S~ = 4ab
if ab > 0 and S+ — S~ = —4ad if ab < 0.
158
TOURNAMENT 18
4.	Inscribe a cube inside the same sphere. We can position it so that
А, В, C and D are four of its vertices and no two of the vertices
А, В, C and D are the endpoints of an edge of the cube. Then C1
and D' are vertices of the cube also.
Since the triangles ABCr and ACD' lie on the faces ACfBDf and
ABfCDr which share the edge AD\ the angle between their planes
is 90°.
5.	The first player can force a win. Make the first n moves anywhere
on a line. For any pair of these n red points, there is one point
on each side of this line that the second player must colour green.
The number of such points is 2 ^owever’ the second player
can paint at most lOn of them green. Hence the second player can
no longer keep up once n(n — 1) > lOn, and the first player has a
sure win on the 12th move.
Senior Solutions
159
Spring 1997 (A Level)
1.	See solution to Problem 2 in Senior paper.
2.	Since BE and DE bisect /ABC and /ADC respectively, E is an
excentre of triangle BAD. Hence /DAC = /CAF where F is a
point on the extension of В A.
Since /DAC = /DAB as well, each is equal to 60° and we have
/ВАС = 120°.
3.	(a) Let «i < «2 < ... < «20 be the weights. Clearly an < 2n
for all n. If we take an ~ 2n for 1 < n < 8, an = 145 for
9 < n < 18 and an — 146 for 19 < n < 20, we can weigh any
object of integer weight m, 1 < m < 1997. Suppose «20 < 145.
Then
«9 + «10 + • • ’ + «20 < 1740
so that
«1 T- «2 + * * ‘ T «8 > 257.
This contradicts an < 2n for 1 < n < 8. Hence the minimal
value of the largest of the 20 weights is 146.
(b) First of all we note that if we have weights 1, 2, 4, 8, 16, 32,
64, 128, 4 x 145, 8 x 145^, we can weigh any object of integer
weight m, 1 < m < 1997.
Now assume that we have a different set of weights «1 < «2 <
 • • < «20 such that we can weigh any object of integer weight
m, 1 < m < 1997 and «20 < 145
160
TOURNAMENT 18
It is easily seen that if not all of a1} 0,2, ..., a? are integers,
then as < 127. Since
ai + Л2 + • • • + ay < 127,
we have
ai 4~ a2 4" * * ’ 4“ as < 254.
Hence ^20 > 145
Thus all ai, ^2, ..., ay are integers and ai4-a2 4~- • *+«7 = 127.
Hence а^ = 1, «2 = 2, as = 4, a^ = 8, a$ — 16, as = 32,
ay = 64 and as = 128.
Since ^20 < 1451, we have ag > 144. Therefore in order to
balance the weight of 145 x 3 4- 256, we have to use exactly
four weights from the set ag,... ,«20- Hence there exist four
weights, say a, b, c and d, such that a4-&4~c4-disan integer.
Since a2o < 145^,
a 4- b 4- c 4- d > 145 x 4.
Hence
a 4- b 4~ c 4- d > 145 x 4 4“ 1
which implies that «20 > 145Thus the minimal value of
largest of the 20 weights is 145^.
4.	We first establish some notations. Let G be the convex n-gon
A1A2  • • An. Let the boundary of F meet the extension of AnAi
at Bn and that of AiAn at Gn. For 1 < i < n — 1, let the boundary
of F meet the extension of	at Bi and that of Ai+1Ai at
Let Xi denote the region of F — G bound by A±Bn and AiBj, and
Yi that bound by AiGn and A1C1. For 2 < i < n, let Xi denote
the region of F — G bound by	and A^B*, and Yi that bound
by AiGi-i and AiGi.
Senior Solutions
161
Assume that we cannot find two support chords that have their
midpoints on the boundary of G. Without loss of generality, we
can assume that A±Bn < A±Cn. For every support chord of G and
two points P and Q on it, we say that P is on the left of Q if a bug
moving along the support chord from P to Q sees G on its right.
Now assume that for every support chord and each point of this
chord that lies on the boundary of G, the part of the chord that
lies on the left of this point is not shorter than that on its right.
Let the chord rotate about until it becomes В^С^. Then its
midpoint stays between Ai and the left endpoint of the chord
throughout the rotation. Moreover, A±B± < AiGi. We claim that
the area of Xi is less than that of Yi. This is obvious if AiBnBi
and A]GnGi are triangles. If the rotating chord passes over vertices
of F, we use the chords in those positions to partition X± and Y\
into triangles. Comparison of the areas of the corresponding pairs
of triangles yields the desired conclusion.
Similarly, we can prove that the area of Xi cannot be greater than
that of Yi for 2 < i < n. However, this is a contradiction since
X± U X2 U • • • U Xn = F - G = Yi U Y2 U • • • U Yn.
Thus we can find two support chords and two points on the bound-
ary of G such that the first point is on the right of the midpoint of
the first chord and the second point is on the left of the midpoint
of the second chord. Therefore there exist two support chords for
G such that their midpoints lie on the boundary of G.
5.	By the Arithmetic-Geometric Means Inequality,
a + b + c > 3^abc = 3 and ab 4- be 4~ ca > 3\^ab  be • ca = 3.
Hence
(<x -|- b 4- c)((z6 4~ be 4" ca — 2) > 3
which implies
2(a 4- b 4- c) < a6(a'4- 6) 4- bc(b 4~ c) 4- ca(c 4- a).
Therefore
1 1 1 x
1 4- a 4~ b 1 4~ b 4“ с 1 4“ c 4- a
2 4~ 2<z 4“ 26 4- 2c — (a 4~ 6) (b 4“ c)(c 4“ o')
(1 4~ a 4- 6)(1 4" 6 4- c)(l 4- c 4" &)
162
TOURNAMENT 18
2a 4- 26 4- 2c — a6(a 4- 6) — 6c(6 4- c) — ca(c 4* a)
(1 4~ cl 4~ 6)(1 4~ 6 4~ c)(l 4- c 4" cl)
0.
6. Clearly, the constant terms of both F(x) and G(x) are Is. Since
n > 1, there is an x term in F(x)G(x)y so that exactly one of F(x)
and G(z), say F(rr), has an x term. If (7 (ж) = 1, then
F(a;) = 1 + x + • • • + xn~L = (1 + x H-+ x^T^x)
with k — n and T(x) = 1. Hence we may assume that G(x) has
more than one term, and that the second lowest one is xk for some
k > 1.
This means that F(x) must contain
1 4- x 4----h xk~r
and that F(x)G(x) will contain
1 4- x 4----hrr2A:_1.
Hence neither F(x) nor G(x) contains any of the terms
fc+2 2fc—1
♦X/	• *X/	• a « • « «X/	•
We claim that for £ > 0, the coefficients of the terms
' £k £k+l £k+k-l
JU j	j • • • , JU
(i)	in F(x) are either all Os or all Is;
(ii)	in G (x) are all Os except that the coefficient of the xlk term
may be 1.
We shall prove these two assertions simultaneously by induction
on Л We have already seen that they hold for £ = 0 and £ = 1.
Suppose the claim has been verified up to £ = m — 1. Consider now
the coefficients of the terms
mk mfc+l	mk+k-1
JU « JU	• » • • * JU	•
If m > n, there are no such terms and the assertions hold trivially.
Hence we may assume that m < n, and consider three cases.
Senior Solutions
163
Case 1.
The xmk term is already present in F(x)G(x). By induction hy-
pothesis, G (ж) contains only terms of the form xbk so far. It follows
that xmk must be the product of an xak term in F(x) and an xbk
term in С(ж), where a 4- b — m. By induction hypothesis, F(x)
contains
xak + xak+l + . . . + xak+k-l
Hence F(x)G(x) contains
xmk _|_ xmk+1 -|_-I-
and neither F(x) nor G(x) can contain any of these terms.
Case 2.
The xmk term is not yet present in F(x)G(x) and it now appears
in F(x). By induction hypothesis, G(x) contains only terms of the
form xbk so far. For 0 < i < fc, the only way the хтк+г term can
be present in F(x)G(x) already is as a product of an хак+г term
in F(x) and an xbk term in С(ж), where a 4- b = m. By induction
hypothesis, F(x) also contains an xak term, and this contradicts
the absence of the term in F(x)G(x) before it is introduced in
F(x). Hence each хгпк+г must appear in F(x) or G(x). However,
if G(x) contains then F(x}G(x) contains
xk~ixrnk+i 4- xrnkxk — 2x^rn+1^k
which is a contradiction. It follows that F(x) contains
xmk 4- xmk+1 -j__4- xmk+k~l
and G (ж) does not contain any of these terms.
Case 3.
The xmk term is not yet present in F(x)G(x) and it now appears
in G(x). Then F(x)G(x) contains
7iii । „к—1\^,тк „mk .	। t mk^-k-1
4“ ж 4-* • * 4-ж )x =x 4- ж n 4“ • • • 4-ж ,
and neither F(x) nor G(x) can contain any of these terms.
This completes the induction argument. It follows from the first
assertion of the claim that
F(a:) = (1 + x + • • • + xk-r)T(x)
where each of the coefficient of Т(ж) is either 0 or 1.
164
TOURNAMENT 18
7. Strips parallel to one another may as well be combined, with no
loss in total width. Then no two strips are parallel to each other.
The slope of a strip is defined to be that of either of its two parallel
edges. We classify the strips into four types, those with slopes in
[1, oo), those in [0,1), those in [—1,0) and those in [—oo, —1), where
a vertical line is taken to have slope —oo.
By the Pigeonhole Principle, the strips of at least one type have
combined width of at least 25. By geometric symmetry, we may as-
sume that their slopes are in [0,1). Label these strips Si, S2,... ,Sn
in ascending order of their slopes.
By rotation if necessary, we may assume that Si is horizontal. Let
a vertical line £ cut its bottom edge at Bq and its top edge at Bp
For к > 1, after is in place, with its top edge cutting € at B^,
translate Sk+i so that is bottom edge passes through Bfc, and let
its top edge cut £ at В&+р
Finally, let the top edge of Sn cut the bottom edge of Si at A.
Then triangle ABoBn is completely covered by Si U S2 U • • • U Sn.
Since Bk-iBk is at least the width of S& for к > 1, BgBn > 25.
Since ZBnABo < 45° < £ABnBo, we also have ABq > BoBn > 25.
It follows that triangle ABoBn can easily cover a unit circle. By
translating the whole configuration, so can Si U S2 U • • • U Sn.
Remark.
The problem deals with a sufficient condition for a unit circle to
be covered by strips. That dealing with a necessary condition is
known as Tarski’s “plank problem”. The following references are
supplied by Murray Klamkin.
[1 ] Th. Bang, On covering by parallel-strips, Matematisk Tids-
skrift В (1950), 49-53.
[2 ] W. Fenchel, On Bang’s solution of the plank problem, Mati-
matisk Tidsskrift В (1951) 49-51.
[3 ] Th. Bang, A solution of the plank problem, Proc. Amer.
Math. Soc. 2 (1951) 990-993.
[4 ] M. Bognar, On W. Fenchel’s solution of the plank problem,
Acta Mathematica Acad. Sci. Hung. 12 (1961) 269-270.


OBITUARY
NIKOLAI BORISOVICH VASSIL1EV (1940-1998)
Nikolai Borisovich Vassiliev, Kolya to his numerous friends, died of a
brain tumor in a Moscow hospital on May 28, 1998. By profession,
Kolya was a research mathematician (he worked practically all his life in
LM. Gelfand’s famous biology and mathematics laboratory at Moscow
University), but he will be best remembered as one of the best olympiad
problem solvers and problem composers of all time.
As a problem solver, he was second to none in his generation. Even when
he was in his forties and fifties, the speed, depth and elegance of his so-
lutions placed him at least at an equal level with the best performers in
the next generations - Dima Fomin of Saint Petersburg, Sergei Konya-
gin and Sasha Razborov of Moscow, Maxim Kontsevich of Moscow and
Paris, Andy Liu of Edmonton. Yet, strangely enough, Kolya Vassiliev
had no official achievements in mathematics problem solving contests; in
fact, he never actually participated in any. His interest in problem solv-
ing (and indeed more generally in mathematics) arose rather late and, in
a sense, accidentally, when he was about to graduate from high school,
a specialized school for future musicians. Until then, his main interest
had been music, and his intention was to enter the Moscow Conserva-
tory in order to study the piano and/or the theory of music. However,
he had medical problems with the joints of his fingers, which hampered
the prospects of a career as a concert pianist. He began to lose interest
in the theory of music because of “the huge amount of boring details” it
involved, and so Kolya finally abandoned the idea of a career in music
just before graduation. He then began preparing for the entrance exams
to Moscow University, which included written and oral tests in math-
ematics, a subject that he had previously neglected. It was his good
fortune to be advised by an excellent math teacher, LKh. Sivashinski,
who discerned Kolya’s exceptional mathematical talent and convinced
him to apply for the Mechanics and Mathematics Faculty of Moscow
University, where his talent blossomed.
Kolya’s love of music was never suppressed by his mathematical activ-
ities: he was an excellent amateur pianist, an assiduous concert goer,
and, most important, the artistic and aesthetic aspect of his person-
ality permeated his work as a composer, compiler, and style editor of
mathematics olympiad problems. There is no doubt that Kvant maga-
zine and the Tournament of Towns were extremely fortunate to profit,
for decades, from the fact that their problem sections were headed by
a person combining the depth of a high class research mathematician
168
Obituary: NB Vassiliev (1940-1998)
with the brilliant aesthetic character of a composer of music. For Kolya
himself, the most rewarding period of his activity as a chooser and ed-
itor of problems was 1967-1979 (which may be called the golden era of
Russian olympiads), when he presided the Methodological Commission
of the All-Union Olympiad of the USSR, either de jure or de facto.
The choice of problems and of their final formulation, both in Kvant
and in the Tournament of Towns, was always the result of considerable
(sometimes heated) discussion. We feel that Nikolai Vassiliev’s credo
in these matters was best expressed in one of these discussions: when
one of us asked him why he was so vehemently against the inclusion of a
certain problem, Kolya answered: “How does a composer decide whether
to make a new melody available to the public or to throw it into the waste
basket? He assesses if the melody will be true gift, if it will give joy to
the listener. If not, it is best to forget about it. I choose mathematics
problems in the same way.”
Kolya Vassiliev was always a mild, soft-spoken, unassuming person, never
raising his voice in anger or irritation, never complaining about the vi-
cissitudes of the life of an underpaid scientist in Moscow. To be in his
company in or around the university, or to visit his large bedroom-living
room, crowded with overflowing bookshelves, two pianos and ancient fur-
niture, with its striking view of the Kremlin, was always a pleasure and
a meaningful intellectual experience.
On all important issues, he was a person who stood firmly for high ethical
principles, whether this was to his personal advantage or not. In his work
ethics concerning mathematics problems, he was inflexible, and would
not rest until the best problems were chosen and their best formulations
and solutions had been worked out. In this activity he in fact created
a specific style in contest problem formulation: the problems must be
natural and attractive, they should involve a minimum of professional
mathematical jargon and logical formalization, and yet be unambiguous
and rigorously stated. This style has now become the prevailing tradition
in many places, but we should not forget that Nikolai Vassiliev, more than
anyone else, was its creator.
Besides the style, there is also the substance, what a person leaves behind
after he is gone from this world. In that respect, Nikolai Vassiliev’s legacy
is exceptional: besides the numerous problems authored and solved per-
sonally, there are those that he selected and edited for Kvant magazine
(over a thousand!), for the Tournament of Towns, for the Moscow Math-
ematical Olympiad and for the All-Union Olympiad; he is the coauthor
of five olympiad problem books. Kolya was the person who convinced us
that the Tournament of Towns should become international and played
a leading role in implementing this idea, not an easy task when Soviet
Russia was still behind the iron curtain. He is also, in a sense, the main
Obituary: NB Vassiliev (1940-1998)
169
author of the subject matter of the three previous volumes in the Tour-
nament of Towns series, as well as of the present volume.
A.A. Egorov, N.N. Konstantinov, A.B. Sossinsky
Moscow
September 1998
Peter Taylor graduated with a PhD from
Adelaide University in 1972, and is now
Executive Director of the Australian
Mathematics Trust. He was Chairman of the
Problems Committee of the Australian
Mathematics Competition from 1979 to
1994. He has also been awarded the Paul
Erdos Award of the World Federation of
National Mathematics Competitions,
presented for his significant contribution to
the enrichment of mathematics learning at
a national level.
Andrei Storozhev is a Research Officer at
the Australian Mathematics Trust. He gained
his PhD at Moscow State University
specialising in combinatorial group theory.
He is a member of the Australian
Mathematical Olympiad Committee and
one of the editors of Mathematics Contests
- The Australian Scene journal.
Australian Mathematics Trust
Enrichment Series
ISBN 1 876420 03 0