к ·
41
i t
Я \( - )/q
(Σ4 )
(Σ Ο
-ι
j-i
ΑΜΤ Publishing
•

HUM GARY-ISRAEL
MATHEMATICS COMPETITION:
THE FIRST TWELVE YEARS
PROBLEMS, ANSWERS AND SOLUTIONS
AMT Publishing

Published by
AMT Publishing
Australian Mathematics Trust
University of Canberra ACT 2601
AUSTRALIA
Copyright ©2004 AMT Publishing
Telephone: +61 2 6201 5137
www.amt.edu.au
AMTT Limited ACM 083 950 341
National Library of Australia Card Number and ISSN
Australian Mathematics Trust Enrichment Series ISSN 1326-0170
Hungary-Israel Mathematics Competition: The First Twelve Years
ISBN 1 876420 15 4

The Australian Mathematics Trust
Enrichment Series
Editorial Committee
• Editor Peter J Taylor, Canberra Australia
• Assoc Editor Andrei Storozhev, 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
MlXOLAY K0NSTANT1N0V, 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 Australian Mathematics Competition Book 1 1978-1984
JD Edwards, DJ King a PJ O'Halloran
2 Mathematical Toolchest
AW Plank ft MH Williams
3 Tournament of Towns questions and solutions 1984-1989
PJ Taylor
4 Australian Mathematics Competition Book 2 1985-1991
PJ O'Halloran, G Pollard ft PJ Taylor
5 Problem Solving Via the AM С
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 Asian Pacific Mathematics Olympiads 1989-2000
HTausch ft С Bosch Giral
9 Methods Of Problem Solving Book 1
JB Tabov ft PJ Taylor
10 Challenge! 1991-1995
JB Henry, J Dowsey, AR Edwards, U Mottershead,
A Makos ft G Vardaro
11 USSR Mathematical Olympiads 1989-1992
AM Slinko
12 Australian Μ athematical Olympiads 1979-1995
Η Lausch ft PJ Taylor
13 Chinese Mathematics Competitions and Olympiads 1981-1993
ATiu

,14 Polish 8t Austrian Mathematical Olympiads 1981- 1995
ME Kuczma ft Ε Windischbacher
,15 TOURNAMENT OF TOWNS QUESTIONS AND SOLUTIONS 1993-1997
PJ Taylor ft AM Storozhev
,16 Australian Mathematics Competition Book 3 1992-1998
WJ Atkins, JE Munro ft PJ Taylor
,17 Seeking Solutions
J С Burns
,18 101 Problems in Algebra
Τ Andreescu ft Ζ Feng
,19 Methods of Problem Solving Book 2
JB Tabov ft PJ Taylor
,20 Hungary-Israel Mathematics Competition: The First Twelve Years
S Gueron

CONTENTS
DEDICATION
FOREWORD
PREFACE
ACKNOWLEDGEMENTS
1. PROBLEMS
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2. ANSWERS
3. HINTS
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
4. SOLUTIONS
1990
1991
1
3
5
7
11
11
12
13
14
15
16
17
18
19
20
21
22
23
25
25
26
27
28
29
30
31
32
33
35
36
37
39
39
44

5.
6.
7.
8.
9.
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
TEAM COMPETITIOM
1990
1991
1992
1993
1994
1995
1996
2000
2001
TEAM COMPETITIOM
1990
1991
1992
1993
1994
1995
1996
2000
2001
PROBLEMS
SOLUTIONS
CLASS1F1CAT10M OF PROBLEMS BY TOPIC
Individual Problems
Team Problems
LIST OF COMTESTAMTS
GLOSSARY
49
53
56
59
63
66
76
92
98
105
117
117
118
119
120
121
123
124
125
126
127
127
131
136
140
145
150
153
160
166
171
171
171
173
177

DEDICATION
I dedicate this book to the loving memory of Professor Joe Gillis (1911-
1993), who was the founder of the Israeli Mathematical Olympiads, a
great mathematician, and a dear friend.
Shay Gueron

FOREWORD
In my role of Executive Director of the Australian Mathematics Trust,
and currently as President of the World Federation of National
Mathematics Competitions I very much welcome the publication of this book.
The book meets an important need in making high quality problem
material available to students who are aspiring to compete at the national
and international level at Mathematics Olympiads. The material in this
book is very special. There are some beautiful problems here and they
should also serve to motivate and challenge the reader.
The book also makes a very strong statement about how mathematics
can cross barriers. When this event started the two countries involved did
not even have diplomatic relations. The founders of the event from both
Hungary and Israel should be applauded for their remarkable initiative.
I have personally worked on this book as a typesetter and proof-reader.
Shay Gueron supplied all of the material completely in TfjjX source code
and I reformatted it in the AMT Publishing style, proof-reading and
drawing the diagrams as I went.
I would like to thank my colleague Dr Andrei Storozhev for proof-reading
the book on behalf of the publisher and making many helpful suggestions
which improved the finished product.
Finally I would like to thank Shay Gueron, who has been very helpful to
work with on this project.
Peter Taylor
Canberra
01 June 2003

PREFACE
The History of the Competition
The Hungary-Israel Binational Mathematical Competition commenced
in 1990. In those days, official diplomatic relations between the two
countries were only their infancy. It was in the summer of 1988, during
the International Mathematical Olympiad (IMO) in Australia, where we,
the late Professor Joe Gillis and myself, met Janos Pataki and Jozsef Pe-
likan, the Hungarian IMO team leaders. Together, we amused ourselves
with the idea of initiating a binational mathematical competition
between the two countries. At that time it sounded like an imaginary plan,
but eventually, we made it come true.
The Hungary-Israel Binational Mathematical Competition is a
competition between teams of (four to six) students from each country. It is held
in the month of April each year, taking place in Israel in the even years,
and in Hungary in the odd years.
The competition is supported by the Israeli Ministry of Education, the
Israeli Ministry of Foreign Affairs, the Hungarian Mathematical Society
(Bolyai Janos Matematikai Tarsulat) the Hungarian Ministry of
Education, and the Hungarian Ministry of Foreign Affairs.
Aims and Format of the Competition
The aims of the Hungary-Israel Binational Mathematical Competition
include: discovering, encouraging and challenging mathematically gifted
students from the two countries, establishing friendly relations and
cooperation between students and teachers, creating an opportunity for
the exchange of information on school syllabi and practice, encouraging
mathematical involvement with problem solving and Olympiad type
activities, and serving as a good international experience for the students
that prepare for the coming IMO.
The Hungary-Israel Binational Mathematical Competition is a one week
event held in each year. The actual competition takes place during two or
three days. In the years 1990-1996, two one-day competitions were held:
an individual competition consisting of four problems, given in the first
day, and a team competition given in the second day. Starting in 1997,
the format was changed to an IMO style exam: two days of individual
competition with 3 problems and 4.5 hours working time in each. In the
year 2000, a team competition was added, as a third day, to the two
individual competition days.
The team competitions concentrate on one advanced topic that is
announced ahead of time, and some reference materials are decided by the

6
Preface
team leaders. The students learn the new topic and train for the
competition.
Apart from the actual days of the competition, the rest of the week is
devoted to marking the students' exams, mathematical activities, site
seeing and entertainment.
The Organization of the Book
This book summarizes the first twelve years, 1990-2001, of the Hungary-
Israel Binational Mathematical Competition. It includes the problems
and the complete solutions to the individual and team competition
problems, as well as final answers and hints to the individual competition
problems. Altogether, the book includes the 58 problems that appeared
in the twelve individual competitions, and the 44 problems that appeared
in the eight team competitions.
A preliminary Hebrew version of this book, written by me, was published
in 1996 in Israel.
Chapter 1 introduces the statements of the individual competition
problems, Chapter 2 provides the final answers (where such answers exist),
Chapter 3 offers hints for the solutions, and Chapter 4 provides the
complete solutions. Chapter 5 presents the problem statements of the team
competition, and the complete solutions appear in Chapter 6.
Some of the problems in the book are easy, and some are rather difficult.
However, no special or advanced knowledge, beyond that of the typical
IMO contestant's curriculum, is required in order to tackle the
individual competition problems and/or to read and understand the solutions.
For the convenience of the reader, we have added a Glossary section
explaining the terms and theorems which are not standard, and have been
used in the book. The team competition problems are typically more
advanced and require some reading on the related topic.
The book is directed to the wide audience of mathematics lovers, problem
solving enthusiasts, and students who wish to improve their
mathematical competitions skills. I sincerely hope that the book would be helpful
to all readers.
Shay Gueron
Haifa
01 June 2003

ACKNOWLEDGEMENTS
I am pleased to acknowledge the help of my friends and students who
went carefully over the text and made many helpful remarks, corrections,
and proposals.
Dr. Seannie Bar from the Academic College of Tel-Aviv Yafo.
Twice an IMO silver medalist, and a gold medalist in IMO 1988.
Seannie has been the Israeli Deputy Team Leader for the IMO since
1993, and helped me with the organisation of the Hungary-Israel
Binational Mathematical Competition in the past few years.
Eran Assaf (bronze medalist in IMO 2000, 2002, silver medalist in
IMO 2001), Mark Braverman (bronze medalist in IMO 1998, 1999,
and gold medalist in IMO 2000), Maxim Iorsh (bronze medalist in
IMO 1993, 1994, silver medalist in IMO 1995), Oran Lang (bronze
medalist in IMO 1998, 1999, gold medalist in IMO 2000, 2001),
Ran Tessler (bronze medalist in IMO 1999, silver medalist in IMO
2000, 2001, 2002).
Without their help - the number of mistakes in this book (which, I am
afraid, is still a positive integer) would have been larger.
In particular, it was a pleasure to work together in a team for preparing
the solutions of the team competitions.
I thank Prof. Noga Alon of Tel-Aviv University, who proposed the
solution to problem 5 of the 1994 team competition.
I would also like to acknowledge the help and comments of my dear
Hungarian friends Janos Pataki (the Hungarian team leader for this
competition in 1990, 1991, and from 2000 on) and Dr. Jozsef Pelikan (the
Hungarian IMO team leader and the team leader for the Binational
Competition in 1992-2000).
Shay Gueron
Haifa
01 June 2003

hat there exists a pair of distinct poi
it the inequality
1997
:fc)1997 = 1996 J] xk
fc=l
A ABC, AAB2C2 a
^■>7?(4^ + 6).
1997
S^'W"»
Jfe=l

1. PROBLEMS
1990
1. Prove that there exist no positive integers χ and у such that both
x2 + у + 2 and у2 + 4ж are perfect squares.
2. Let ABC be a triangle where LACВ = 90°. Let D be the midpoint
of ВС and let E: and F be points on AC such that CF = FE =
Ε A. The altitude from С to the hypotenuse AB is CG: and the
circumcentre of triangle AEG is ii. Prove that the triangles ABC
and HDF are similar.
3. Prove that
1989 1988 1987 2 1
~~2 3~ + ^ '■■" 1989 + 1990
_ 1 3 J5_ 1989
996 + 997 + 998 + '"+ 1990 '
4. A rectangular sheet of paper with integer length sides is given. The
sheet is marked with unit squares. Arrows are drawn at each lattice
point on the sheet in a way that each arrow is parallel to one of its
sides, and the arrows at the boundary of the paper do not point
outwards.
Prove that there exists at least one pair of neighboring lattice points
(horizontally, vertically or diagonally) such that the arrows drawn
at these points are in opposite directions.

12
1. Problems
1991
1. Let f(x) be a polynomial with integer coefficients, satisfying
/(0) = 11, f(Xl) = f(x2) = f(xs) = · · · = f(xn) = 2002,
for some distinct integers x±, x2:..., xn- Find the maximal value
of n.
2. The vertices of a square sheet of paper are A:B,C,D. The sheet
is folded in a way that the point D is mapped to the point D' on
the side ВС. Let A' be the image of A after the folding, and let Ε
be the intersection point of AB and A'D'. Let r be the inradius of
the triangle EBD'. Prove that r = A'E.
3. Let Η η be the set of all numbers of the form
2±y2± у2±...±л/2
where "root signs" appear η times.
(a) Prove that all the elements of Hn are real.
(b) Compute the product of the elements of Hn.
(c) The elements of Нц are arranged in a row, and are sorted by
size in an ascending order. Find the position in that row, of
the element of Нц that corresponds to the following
combination of ± signs:
4. Find all the real values of A for which the system of equations
x + y + z + v = 0, (1)
(xy + yz + zv) + \{xz + xv + yv) = 0, (2)
has a unique real solution.

1992
13
1992
1. Let с -φ 1 be a real positive number, and let η be a positive integer.
Prove that
cn + c-n _ 2
•nf <
c + с
2. Let 5 be a set of 1992 positive integers having the following
property: The list of the last digits of the elements of S includes all of
the digits from 0 to 9.
Prove that there exists a nonempty subset of S such that the sum
of its elements is divisible by 2000.
3. One hundred strictly increasing sequences of positive integers are
given:
A1 = {a[1\a{21\...,al1\...},
A - fJ2) J2) J2) \
Μ — \αγ ,α2 ,.. .,ak .. .J-,
л _ /J100) Jw°) J10°) \
For any positive integer η and integers r, s such that 1 < r, s < 100,
we define the following functions:
fr (n) - the number of elements of Ar that do not exceed n.
fr,s{n) - the number of elements of Ar Π As that do not exceed n.
For every η and r it is given that
fr(n) > -n
Prove that there exists a pair of distinct positive integers (r, 5),
such that the inequality
frAn) > 33
holds for at least five distinct integers η between 1 and 19920.
4. The five vertices of a given convex pentagon Ρ are lattice points.
Let Q denote the convex pentagon defined by the intersection
points of the five diagonals of P. Prove that there exists at least
one lattice point inside or on the boundary of Q.

14
1. Problems
1993
1. For any two integers χ and у the notation x.y represents a number
whose integral part is composed of the digits of χ and its fractional
part is compose of the digits of y. For example, if χ = 123 and
у = 456 then x.y = 123.456
Find all possible solutions of the equation
a и
— = b.a
b
where a and b are relatively prime positive integers.
2. Find all the polynomials f(x) with real coefficients, satisfying
f(x2-2x) = (f(x~2)f
for every real argument x.
3. Let Η be a semicircle with radius 1, and let A, B: C, D, Ε be five
points on its boundary, in this cyclic order. Prove that
AB2 + ВС2 + CD2 + DE2 + AB ■ ВС ■ CD + ВС ■ CD ■ DE < 4
4. A 3n χ 3n chessboard is given. Find the largest number of rooks
which can be placed on the chessboard in such a way that each
rook is taken" (threatened) by no more than one rook.

1994
15
1994
1. Let m and η be two distinct positive integers. Prove that there
exists a real number χ such that 1/3 < {xn} < 2/3 and 1/3 <
{xm} < 2/3.
Here, for any real number у, {y} denotes the fractional part of y.
For example {3.1415} = 0.1415
2. Let αχ,..., α*;, a^+i,..., an be η positive numbers (k < n).
Suppose that the values of α^+ι, a/c+2,.. ·, an are fixed. Choose the
values of αϊ, α2,..., α^ that minimize the sum
3. Three given circles have the same radius and pass through a
common point P. Their other points of pairwise intersections are
A: B: C. We define triangle AA'B'C, each of whose sides is
tangent to two of the three circles. The three circles are contained in
AA'B'C. Prove that the area of AA'B'C is at least nine times
the area of AABC.
4. An "n-m society" is a group of η girls and m boys. Prove that
there exist numbers no and mo such that every no — mo society
contains a subgroup of five boys and five girls with the following
property: either all of the boys know all of the girls or none of the
boys knows none of the girls.

16
1. Problems
1995
1. Let the sum of the first η primes be denoted by Sn. Prove that
for any positive integer n, there exists a perfect square between Sn
and Sn+i.
2. Let P, Pi, P2, P3, P4 be five distinct points on a circle. The distance
of Ρ from the line PiPk is denoted by dik- Prove that ^12^34 =
^13^24-
3. The polynomial f(x) = ax2+bx+c has real coefficients and satisfies
\f(x)\ < 1 for all χ G [0,1]. Find the maximal value of \a\ + \b\ + \c\.
4. Consider a convex polyhedron whose faces are triangles. Prove that
it is possible to colour its edges by either red or blue, in a way that
the following property is satisfied: one can travel from any vertex
to any other vertex while passing only along red edges, and can
also do this while passing only along blue edges.

1996
17
1996
1. Find all series of integers xi,X2,···, Ж1997 such that
1997 1997
X^*-1^*)1"^ 1996 J] Xk (1)
2. Let η > 2 be an integer. Suppose that n2 can be represented as the
difference of the cubes of two consecutive positive integers. Prove
that η is the sum of two squares. Prove also that such an η really
exists.
3. A given convex polyhedron has no vertex which is incident with
exactly three edges. Prove that the number of faces of the polyhedron
which are triangles is at least eight.
4. Let αϊ, α2, ·.., αη be arbitrary real numbers and let &i, 62, · · ·, bn
be arbitrary real numbers satisfying 1 > b\ > 62 > · · · > bn > 0.
Prove that there exists a positive integer к < η for which the
inequality \αφ\ + α2&2 + · · · + anbn\ < |«i + «2 + ··· + a,k\ holds.

18
1. Problems
1997
1. Is there an integer N such that
(>/Ϊ997 - V1996)1998 = y/N- y/N-1?
2. Find all the real numbers a that satisfy the following property: for
any positive integer η there exists an integer m such that
m 1
a < —
η on
3. Let ABC be an acute angled triangle whose circumcentre is O.
The three diameters of the circumcircle that pass through A, B,
and C, meet the opposite sides BC: AC and AB at the points Ai,
B\. Ci, respectively.
The circumradius of ABC is of length 2P, where Ρ is a prime
number. The lengths OAi, O-Bi, OCi are integers. What are the
lengths of the sides of the triangle?
4. What is the number of distinct sequences of length 1997 that can
be formed by using the letters А, В, С, where each letter appears
an odd number of times?
5. Let ABC be a given triangle. The three squares
ACCiA", ABBiA', BCDE
are constructed, outwards, on the sides of ABC. The centre of the
square BCDE is denoted by P. Prove that the three lines A'C,
A"B and PA pass through one point.'
6. Can a closed disk be decomposed into a union of two congruent
parts having no common points?

1998
19
1998
1. A player plays the following game: in each turn he flips a fair coin
and guesses the side on which it would fall. A successful guess
credits the player with one point. In any unsuccessful guess the
player loses all the points he has accumulated. The player starts
the game with 0 points. The game terminates when the player has
accumulated 2 points.
I. What is the probability pn that the game terminates after
exactly η turns?
II. What is the expected (average) number of turns until the game
terminates?
2. The circumcentre of an acute angled triangle ABC is O, and its
circumradius is R. The radii of the incircles of the triangles О ВС,
OCA, OAB are r±, ri, r%, respectively. Prove that
- + - + —> 4(4л/3 + 6).
r\ r2 r3 R
3. Let a, b, c, m, η be positive integers, and f(x) — ax2 + bx+c. Prove
that there exist η consecutive positive integers a±, a>2,.. ■, an such
that each one of the η integers f(a\), /(«2), · · ·, f{oLn) has at least
m different prime factors.
4. Find all the positive integers χ and у such that bx — 3y = 16.
5. Definition: A hexagon is called affinely regular if it is centrally
symmetric and the three pairs of its opposite sides are parallel to
the diagonal joining the two remaining vertices.
Let ABCDEF be a convex hexagon. Six equilateral triangles are
constructed, outwards, on its sides. Prove that the third vertices
of these triangles are vertices of a regular hexagon if and only if
the original hexagon ABCDEF is affinely regular.
6. Let η be a positive integer. A partition of η is a decomposition of η
into a sum of positive integers. Two partitions are not considered
to be different if they differ only in the order of the summands.
The set of all the partitions of η is denoted by Π. If α is a
partition of n, we denote the numbers of terms 1,2,... ,n in it by
αϊ (α), a2(a), ■.., an(a), respectively. Prove that
1αι(α)αι(α)! · 2α2(α)α2(α)! · · · nfl«Wfln(a)!

20
1. Problems
1999
1. Let f(x) be a polynomial whose degree is at least 2. Define the
sequence д{(х) by: gi(x) = f(x) and gn+i(x) = f(gn(x)) for η =
1, 2,.... Let rn be the average of the roots of gn{%)· It is given
that rig = 99. Find Г99.
2. A set of 2n + 1 lines in a plane is drawn. No two of them are
parallel, and no three pass through one point. Every three of these
lines form a non-right triangle. Determine the maximal number of
acute angled triangles, that can be formed.
3. Find all the functions / from the set of rational numbers to the set
of real numbers, such that for every rational ж, у
f(x + y) = f(x)f(y)-f(xy) + l.
4. Let с be a positive integer. Define the following sequence:
αϊ = с, αη+ί = can + y/(c2 - l)(a£ - 1), η = 1, 2,
Prove that all the terms an are positive integers.
5. The function
*, ч x2+y2 + z2
f(x, y, z) = ■ ■
χ + y + ζ
is defined for every x,y:z such that χ + у + ζ ^ 0. Find a point
(жо, 2/0, zo) such that
0 < xl + yl + zl < 1/1999
and
1.999</(z0,yo,zo)<2.
6. An exam consists of four multiple choice questions, where each
question has three choices. A certain group of examinees took the
exam. It turned out that for any subset of three of examinees,
there was at least one question to which their choices covered all
three possibilities. What is the maximal number of examinees in
this group?

2000
21
2000
1. Let S be the set of all partitions of 2000. For every partition ρ in
S we define the function
f(p) = (number of summands in p) + (maximal summand in p)
Compute the minimal value that f(p) attains over S.
Remark: A partition of a positive integer η is its representation as
a sum of positive integers. Two partitions differing from each other
only by order of the summands are not considered to be different.
2. Prove or disprove the following claim: For any positive integer
k, there exists a positive integer η > 1 such that the binomial
coefficient (™) is divisible by к for any 1 < i < η — 1.
3. Let ABC be a triangle which is not equilateral. Let Ai, B\ and C\
be the touching points of the incircle of AABC on the
corresponding sides, and Μ the orthocenter of triangle A\B\C\. Prove that
Μ is on the straight line through the incentre and circumcentre of
triangle ABC.
4. Let S = {1, 2,..., 2000}. Consider two sets A,B С S, such that
|A| · \B\ > 3999. Prove that (A - А) П (B - B) is nonempty.
The notation X—X stands here for: X—X = {s—t\s, iel,s^i}.
The notation \X\ stands for the number of elements in X.
5. d is a given integer. Let S be the set: S = {m2 + dn2 \ πι,η G Z}.
Suppose that p, q are two elements of 5, and that ρ is prime.
Suppose further that r = ^ is an integer. Prove that r also belongs
to S.
6. к and I are two given positive integers and a^·, 1 < i < к and
1 < j <l, are kl given positive numbers.
Prove that if q > ρ > 0 then
(Σ(Σ<·)ς/ρ)1/ς < (Σ(Σ<·)ρ/ς)1/ρ·

22
1. Problems
2001
1. Find positive integers x: у, ζ such that
χ > ζ > 1999 · 2000 · 2001 > у
satisfying
2000ж2 + у2 =z2.
2. A, B: С and D are points lying on the line I in that order. Find
the locus of points Ρ in the plane for which LAP В = ICPD.
3. Find all continuous functions / : R —> R satisfying the functional
equation
f{f(x)) = f(x) + x
for all real x.
4. Let P(x) = x3 — 3x + 1. Find the polynomial Q whose roots are
the fifth power of the roots of P.
5. A ABC is a given triangle. Bi:C± are the midpoints of AC,AB
respectively. I is the incentre of AABC. The lines B\I and C\I
meet AB and AC in C2 and B2 respectively.
Given that the areas of the triangles AABC and AAB2C2 are
equal, what is ABAC?
6. 32 positive integers, which sum up to 120 and none of which is
greater than.60 are given.
Prove that they can be divided into two distinct subsets that have
equal sum.

2. ANSWERS
1991
1. η = 4 3. (b) 2 (с) 1991 4. ^^ < A < ^Ь^
1993
1. a = 5, b = 2. 2. /(ж) = (ж + l)fc, for any positive integer к or
f(x) = 0 for all x. 4. 4n
1994
2. αϊ = α2 = ... = ak = Vab where
L 1 1
a = a\ Л V an: b = 1 1 .
a,\ an
4. for example щ = 9 and mo = 1 + 4 χ 29.
1995
3. 17
1996
1. Only the trivial solution x± = X2 = ... = Ж1997 = 0.
1997
1. Yes 2. The set of all integers. 3. a = b = c = 2Рл/3
4. (31997 - 3)/4. 6. No.
1998
1. I. pn = ^Fn-i, η = 2,3,..., where Fn is the n-th term of the
Fibonacci sequence (1, 1, 2, 3, 5, 8, ...). Π. χ = 6 4. χ = у = 2.
1999
2· (2Пз+1) + 6) (2η +1) 3. /(ж) = 1 or /(ж) = χ + 1.
5. For example (ΐ, ί2 - ΐ, 0) with ΐ = 1/10000. 6. 9
2000
1. 90. 2. The claim is false.
2001
1. (ж, у, ζ) = (900002 - 2000 + 2 · 90000,900002 - 2000 - 2 · 2000 ·
90000,2000+ 900002).
2. The locus is the segment ВС, the points in I outside AD, and the
perpendicular bisector of ВС if AB = CD or the circle of inversion that
maps А, В to D, C, if AB ^ CD.
3. f(x) = ^fix or f(x) = ±=fix. 4. Q(x) = x3 + 15ж2 - 198ж + 1.
5. LBAC = 60°.

3. HINTS
1990
1. Prove that 4ж — 2 < 2y < 4ж — 1, which implies that у = 2x — 1.
Since x2 + у + 2 is a perfect square, you can conclude that (2ж)2 <
fc2 < (2ж + l)2, which yields a contradiction.
2. Choose a coordinate system where С is the origin, AC is along
the y-axis, БС is along the ж-axis, and AC = 1. Express the
coordinates of the vertices A, B, C, D, F, G: Η and lengths of the
sides in terms of LCAB.
3. Prove first the identity
111 11 1 J_ _
2_3 + 4~'"+2n + n+1 + n + 2 + '"+2n ~
for example, by induction on n.
4. Consider closed arrow-paths, and rotate all the arrows in such path
by 90°.

26
3. Hints
1991
1. Define a new polynomial g (x) = f(x) — 2002. Use the factorization
of 1991 (= —g(0)) into two distinct prime factors.
2. Note that if the sides of a right angled triangle are a an b, the
hypotenuse is c, and r is the inradius, then r = |(a + b — c).
3. (a) Define a sequence of polynomials Pn by
Po=x-2, Pn = P*_i-2, η =1,2,... (1)
and deduce that Hn is the set of all the roots of Pn.
Use (1) to show that Pn(0) = 2 for η > 0.
Нц has 211 = 2048 elements. Suppose that χ G Яц is the
number that corresponds to the combination + + + + H h +
—I— of ± signs.
Since χ starts with "2 + ^J ", it follows that χ is larger than
all the elements of Нц that start with "2 — J ". Therefore,
χ belongs to the list of the 1024 largest elements of Нц-
4. The trivial solution (ж, у, ζ, ν) = (0,0,0,0) always exists. For other
solutions, try a solution of the form (1, P, — P, 1) for some P. Using
(2), derive a quadratic equation for P, and find the values of A for
which the system has real solutions of this type. This would give
you the range where there is no unique solution.
(b)
(c)

1992
27
1992
1. Write
cn + c-n_2= ^n -d-n)2, c + c-1 -2= (d-d'1)2,
where d = л/с, and use the Arithmetic Mean - Geometric Mean
inequality.
2. Choose ten elements αϊ, α2,. ·., αιο Ε 5 with different unit digits
and consider the set
A = {ai,a,2,.. .,aw,T- αί:... ,Τ - αι0}
Where Τ = α\ + α,2 ·. · + аю-
Show that there are 19 elements in A that have different residues
modulo 2000.
3. Check small values of n.
4. For a given pentagon, construct the smallest sub-pentagon which
yields a counterexample. Note that in every convex pentagon whose
vertices are lattice points, one of the midpoints of its sides or its
diagonals is also a lattice point.

28
3. Hints
1993
1. Suppose that 10n_1 < a < 10n for some n. You can express the
, · , . , ЮПЬ + a mi . , , a
decimal representation b.a as . This number equals -.
Conclude from this information that ab and a — b2 are relatively
prime.
2. Denoting у = χ — 1, you can write f(y2 — 1) = [f(y — l)]2. Show-
that if τ/ο — 1 is a root of /, then so is у ι — 1, where ?/i is a square
root of τ/ο ·
3. Prove the stronger inequality
AB2 + SC2 + CD2 + £>£2 + AB · ВС · CD + ВС · CD · DE < 4
by assuming that AE is a diameter, and by using the cosine law.
4. Divide the chessboard into η 3 χ 3 subboards with squares a^·,
1 < i,j < 3. In each such subboard put rooks in the squares
ац, ai2, a23, азз- Count the maximal number of rooks in two ways.

1994
29
1994
1. Define sequences Ii and Ji of intervals such that for any χ G Ц
1 r ι 2
-3<{n*}<-3
and similarly for Ji.
2. Apply the Cauchy-Schwartz inequality to the pairs
where
x = a\-\ h a/c,
1 1
у = — + ··· + — ,
a = йк+ι -\ l· an,
1 1
b = + ··· + — .
flfc+i a>n
3. Denote the centres of the circles by A", B", C", and their common
radius by R. The points А', В', С bisect B"C", C"A": and A"B",
respectively. Use the similarity relation
AABC ~ AA'B'C ~ AA"B"C"
and the inequality R > 2r (where r is the inradius of A'B'C) to
obtain
Aff ВС СА_
A'B' ~ B'C ~ ~σΑ> ~ 3'
4. Choose no = 9, ?πο > 4 · 29 and use the pigeonhole principle.

30
3. Hints
1995
1. Note that there is a square between any two integers a and b if
л/а — y/b > 1, i.e. a — b > 1 + 2\/b. If pn denotes the n-th prime,
it is sufficient to show that
Pn+i = Sn+i — Sn > 1 + 2 л/5.
2. Denote the radius of the circle by R. Use the formula
abc
S^abc - -^
for the area of a triangle A ABC whose sides are a,b,c and its
circumradius is R. Apply it to /\ΡΡχΡ2, ΑΡΡ3Ρ4, АРРгР3 and
APP2P4.
3. Substitute χ = 0, \ , 1 in the given inequality |/(ж)| < 1, and obtain
three inequalities involving a:b:c. Express a and b in terms of
A = a + 26 + 4c and Б = a + 6 + с Use triangle inequality to obtain
the upper limit of 17. To show that this maximal value is attained,
consider the polynomial f(x) = 8x2 — 8x + 1.
4. Choose any vertex С of the polyhedron. Connect it with its
neighboring vertices Ci,..., Cn. colour the sides as follows: CC\ blue,
CC2, CC3,..., CCn red, C1C2 red, C2C3, C3C4,..., Cn_iCn, CnCi
blue.

1996
31
1996
1. Note that if
(Ж1,Ж2,...,Ж1997)
is a solution, then so is
/Ж]. Ж2 Ж1997 \
V 2 ' 2 ''"' 2 У '
So, you can divide any solution by 2 until at least one of the a^s is
odd.
2. Denote the consecutive integers by b and 6+1, and obtain
3(26+l)2 = (2n + l)(2n-l)
Now, consider all possibilities for 2n + 1 and 2n — 1.
3. Denote the number of vertices, edges and faces by v, e, /,
respectively, the number of vertices of degree i by vi, the number of faces
with i edges by fi. Apply Euler's formula, namely
f + v-e = 2.
4. Use Abel's summation formula (summation by parts),
η η / 3 \
Σ aibi = Σ ( Σ ai ) (bi ~ Ъз+1)·
Apply the triangle inequality.

32
3. Hints
1997
1. Use the binomial expansion of
(s/x -+- 1 — \fx)
and of
(Vx + i + Vx)n ■
Note that
(Vx + 1 - л/ж) x (\/ж + 1 + л/ж) = Ι-
2. First show that if a is an integer the condition can be satisfied.
Then assume that a is not an integer and that the condition is
satisfied. Consider the two approximations rrik/2k and rrik+i/2k+1
for some positive integer k.
3. Denote AB = c, AC = 6, ВС = a and ΟΑγ = αϊ, ΟΒγ = Ьь
OC\ = c\. Prove the identity
sin a cos a + sin β cos β + sin 7 cos 7 = 2 sin a sin β sin 7
and deduce that
ОАг ОВг ОСх л
—- л л = ι.
АА1 ΒΒι CCi
Then, translate this equality into a quadratic equation in p.
4. Suppose that the (odd) number of As in the sequence is a. The
number a ranges between 1 and 1995* Once a is chosen, there are
1996 — a possibilities to choose the (odd) number b of Bs in the
sequence. The numbers a and b determine the number of Cs. Sum
up the appropriate possibilities and use the relations between the
binomial coefficients.
5. Rotate ΑΒΒχΑ' by 45° around B, and dilate by the factor of \/2.
6. Suppose that the disk С can be decomposed into the two congruent
parts PI and P2. The centre can be in only one of these parts.
Consider the congruence mapping that maps PI to P2 and consider
its inverse.

1998
33
1998
1. I. Write pn as
Pn = ψΜη
and prove that for η > 2 Mn = Fn-i, where Fn is the n-th term
of the Fibonacci sequence 1,1,2,3, 5, 8,
II. Use Binet's formula
to compute the average length of the game, which is defined by
oo
χ = Σ ηΡη
n=l
2. Prove that
1 1 1
—+ —+ —
П r2 r3
1112 2 2
R \coso; cos/3 cos7 sin2a sin2/3 sin27
and
q q /q
cos a + cos β + cos 7 < - , sin 2a + sin 2/3 + sin 27 < —-— .
Then apply the Сauchy-Schwartz inequality.
3. Prove by induction on m that if one of the numbers f(ai) has at
least m distinct prime factors, then the number f(Pj), where
Рз = аз + [/(αι)/(α2)... /(αη)]2,
has at least m + 1 prime factors.
4. Prove that χ and у must be even, i.e. χ = 2a and у = 2b where
a, 6, are natural numbers. Write bx — 3y in the form
bx-3y = (5a)2 - (3&)2 = (5a + 3b)(5a - 3b) = 16
and check all the possibilities for a and b.

34
3. Hints
5. Denote the centre of symmetry of the hexagon ACBDEF by O.
Use the fact that ВС \\ АО \\ OD and show that the quadrilateral
AOBC is a parallelogram. Show that the triangles OAB and OBC
are congruent.
oo
6. Consider the generating function TT e~.
n=l

1999
35
1999
1. Use Viete formulas.
2. Assume that all the lines pass through the origin (with no loss of
generality). Consider a pair of lines li:l2 forming the angles a and
180° — a between them. Assume that r < η — 1 of the given 2n — 1
lines are in the domain of the angle a and 2n — r — 1 of them are in
the domain of the angle 180° — a. One of the angles a and 180° — a
is obtuse.
3. Find /(0) and /(1) and express /(|) in terms of /(1).
4. Prove that an+i = 2can — an-i for every η > 2.
5. Consider a point Ρ of the form Ρ = (ί, t2 — t: 0) for some t.
6. Use the pigeonhole principle to show that the number of students
cannot exceed 9. To show the feasibility for 9 students, construct
an explicit example.

36
3. Hints
2000
1. Denote the number of summands in s by N(s), and the maximal
summand in s by M(s). Prove that M(s) x N(s) > 2000, and
conclude that f(s) > 89.
2. Take the case к = 4. Assume by contradiction that there is an
integer η such that (™) is divisible by 4 for 1 < i < η — 1, and
consider the sum of those binominal coefficients.
3. Let Α2:Β2:θ2 be the midpoints of the arcs BiC±: C±Ai, A\B\ of
the inscribed circle. Prove that A2B2\\AB: B2C2\\BC, C2A2\\CA.
Consider the homothety taking the inscribed circle into the circum-
circle.
4. Look at the function F:ixB^{2,3,..., 4000} defined by
F(a,b) = a + b.
5. Let ρ = χ2 + dy2, q = a2 + db2. Prove that p\(ax + by){ax — by),
and deduce that ρ divides one of ax + by, ax — by.
Take
ax± by
v=
Ρ
integer, and find an integer и such that
^=u2 + dv2.
Ρ
6. Prove the inequality by induction on k. Note that the case к = 2
is simply Minkowsky's inequality.

2001
37
2001
1. Use the identity n(m2-n + 2m)2 + (m2 —n — 2mn)2 = (n + l)(m2 +
n)2.
2. Let Ρ be a point on the locus, and consider the circles PAB, PCD.
Prove that they are invariant under the reflection with respect of
the perpendicular bisector (if AB = CD) or with the inversion
which maps A, D to D, C.
3. Prove that / is 1 — 1 and monotonic. Consider two cases: if / is
decreasing, prove that \f(x)\ < \x\- If / is increasing, prove that
irV)i < м-
4. Let α be a root of P. Then — 1 = a3 — 3a. Raise to the fifth power.
5. Use the theorem of Menelaus several times to find AB2:AC2-
6. Prove that for 3 < i < 30, a^ < i when a^ is the г-th term in the
sequence (by order of magnitude).

4. SOLUTIONS
1990
1. Note that x2 + у + 2 > χ2. Therefore, if x2 + у + 2 is a perfect
square, then
ж2 + у + 2 > (χ + Ι)2 = χ2 + 2ж + 1 => у > 2ж - 1.
Similarly,
у2 + 4ж > (у + I)2 = у2 + 2у + 1 => 2у < 4ж - 1.
In particular, 4ж — 2 < 2у < 4ж — 1 and therefore у = 2х — 1. Since
у2 + 4# is a perfect square, there exists an integer к such that
k2 = (2x - l)2 + 4ж = 4ж2 + 1.
The last equality implies that к2 < (2ж + 1)2 and к2 > (2ж)2, which
is a contradiction.
2. Consider a coordinate system where С is the origin, AC lies on the
y-axis, SC lies on the ж-axis and AC = 1. Denote LCAB = a.
The equation of the line AS is у = —(cot a)x + 1. The equation of
the line CG is у = (tancu)ar. Therefore, the coordinates of G are
(sin a cos a, sin2 a).
The point Η lies on the perpendicular bisector of AE. Therefore,
5
its y-coordinate is -. If хн is the ж-coordinate of Η, then
HA2 = x2H +
HG2 = {хн — sin a cos a) + ί - — sin2 a J .
Since HA = HG we have ж# = - cot a.
О
We can now compute the sides of AHDF. A straightforward
calculation yields
rr~ 4 cot2 a + 9 tan2 a + 13
HD2 = — ,
36

40
4. Solutions
2= 4cot2a + 9
36
and
2= 9tan2Q + 4
36
The sides of AABC are AB2 = 1+tan2 а, ВС2 = tan2 a, AC2 = 1.
Now,
(HF\2 _ 4cot2a + 9 _ 2 _ /ACT "
\FDJ 9tan2a + 4 \BC
and consequently
HF _ AC
F~D ~ ВС
Further, we also have
HF2 + FD2 = 4cot2Q + 9tan2Q + 13 = HD2
36
By the inverse Pythagorean theorem, this implies that AHDF is
a right angled triangle. Since both AABC and AHDF are right
angled triangles and the ratios of their sides are equal, it follows
that they are similar.
3. We first prove, the following general statement:
1111 1 h 1 1 -, μ
5n = --- + --- + ...+ —+ —— + —— + ·.. + —= 1. (1)
2343 2n n+1 n + 2 2n
The proof goes by induction. Verification for η = 1 is trivial. Now,
assume that Sk = 1 for some к. For Sk+i we have:
о 1 111 1
-bfc+l = -bfc — 7^—— + ———- — -——- + +
2fc+12fc + 2 fc + 1 2&+1 2fc + 2
= «St + + — = Si- = 1.
к 2к + 2 2к + 2 к + 1 к
This completes the proof of (1).
We now return to the required equality. Its left hand side is

1989 1988 1987 1
L = — —+ — +
3 4 1990
/1989 Λ /1988 Λ / 1 Λ 1
/111 1 λ
= 1991 2-3 + 4-- + Ϊ990 Ь1'
and its right hand side is
_ 1 _3_ _3_ 1989
~ 996 + 997 + 998 + " ' + 1990
a-2) + (9l7-2, + ,--2,+
/1989 _ λ
V1990 J
+ -^— - 2 + 2(1990 - 996 + 1) =
/111 1
= 1990 - 1991 [ —- + —- + —- + · · · +
V996 997 998 1990
Therefore, using (1) we have
R-L = 1991 - 1991 ( \ - - + \
V2 3 4
111 1
1990 996 997 1990
which completes the proof.
Alternative solution
1989 1988 1
L = — — + ..· +
1990
/1989 Λ /1988 Λ /1 Λ -,
,111 1
1991 - - - + - - ... +
2 3 4 1990

42
4. Solutions
= 1991(2G+i+--+ϊέο)
= ΐ99ΐ((ι+5+5+··+ά)
-β+ΐ+-·+ϊέο))-1
= 1991(1_(_L + J_ + ... + J_Y)_1
V V996 997 1990;)
/11 1 λ
= 1990 - 1991 + + ... + .
V996 997 1990;
Finally, L is exactly R from the first solution.
4. Let us assume that there exists no pair of neighboring points whose
arrows point in opposite directions ("conflict"), and start our
solution with a few definitions.
A "subdomain" as a connected region of the sheet whose boundary
is composed of only line segments which are parallel to one of its
sides, and connect two neighboring lattice points.
We call every subdomain whose arrows do not conflict, a "good
domain". Thus, our assumption implies that every subdomain is
good. Finally, we call every good domain whose boundary arrows
point inwards, an "excellent domain".
We now choose any lattice point x\ of the sheet. We construct
the orbit of lattice points Ж1,Ж2,жз,... by going from one point
Xk to the next point Xk+i in the direction of the arrow at Xk- We
continue the process until the first time that orbit crosses itself (i.e.,
the first time we return to a point that is already on our orbit).
Since the total number of lattice points on the sheet is finite, our
process ends within a finite number of steps. We end up having a
closed orbit which we denote by Li, which encloses a subdomain
which we denote by Αγ. Clearly, A\ is a good domain. With no
loss of generality, we may assume that L\ goes clockwise, and the
domain A\ is found to its right.

1990
43
We now rotate all the arrows on the sheet clockwise by 90°. After
this rotation, all of the arrows along L\ point inwards, and it follows
that A\ is now an excellent domain.
In the second step, we choose a lattice point X2 that is found in
the domain A\ (if there exists such), repeat the above process and
obtain a new excellent domain A2 which is strictly included in A\
(because the new closed orbit cannot reach Li, the boundary of
the excellent subdomain A\).
We continue this process as long as there are still inner points in
the current excellent subdomain. Finally, we end up with an
excellent rectangular subdomain, say Ar: whose "width" is one square.
The subdomain Ar is encircled by a closed orbit Lr of arrows that
point in the directions of one of its sides. Obviously, along Lr
there exist two neighboring squares with arrows at opposite
directions. This contradicts our starting assumption, and the desired
statement follows.

44
4. Solutions
1991
1. We define g(x) = f(x) - 2002. If f(xi) = 2002 then x{ is a root of
g (x). Consequently, we can write
η
9{x) = Y[(x-Xi)q(x) (2)
i=l
for some polynomial q{x) with integer coefficients, where η is the
required maximal possible number of a^s.
Substituting χ = 0 in (2) we obtain
η
0(0) = -1991 = -11 x 181 = Y[(-Xi)q(0).
i=l
Since 11, and 181 are primes, it follows that —1991 can be written as
the product of at most 4 different factors, namely —1 χ 1 χ 11 χ 181,
and we therefore have η < 4.
It remains to provide an example where η = 4. This occurs for
example with
g{x) = {x- l){x + l){x + И)(ж + 181), q(x) = 1,
that is,
f(x) = (x- l)(x + l)(x + 11)(ж + 181) + 2002
One can now easily verify that indeed /(0) = 11 and /(1) =
/(-1) = /(-11) = /(-181) = 2002, as required.

1991
45
2. Denote the length of the side of the square by a.
D x L С
The distance of D' from AD is a. Therefore, the distance of D
from ED' is also a. It follows that D is the centre of the excircle
of the triangle AEBD'. Consequently, as the lengths of the two
tangents to a given circle, extended from a given point, are equal,
it follows that the perimeter of AEBD' is 2CD = 2a Finally, in a
right angle triangle AEBD' we have
r = -(BE + BD' -ED'),
that is,
r = -{BE+BD'+ED' -2ED') = \{2a-2ED') = a-ED' = A'E.
as required.
3. We prove part (a) by induction. For η = 1 the statement is trivial.
Assume now that the elements of Hn_i are real and belong to the
interval (0,4). Now, from the definition of Hn, it follows that if
χ G Ηn then (χ — 2)2 e Ηη-\. Using the induction hypothesis, we
conclude that the elements of Hn are also real and are found in the
interval (0,4).

46
4. Solutions
To prove part (b) we note that the elements of Hn are the roots of
the polynomial Pn, where the sequence Pn is defined by
P0=x-2, Pn = P*_1-2, η =1,2,...
Therefore, if we assume by induction that Pn_i(0) = 2 for some
η > 1 we immediately have that Pn(0) = 2 as well. Using Viete's
formulas, it follows that the product of the roots of Pn, which is
also the product of the elements of Hn, is 2.
For part (c), we note that Нц has 211 = 2048 elements. Let
χ G Нц denote the number that corresponds to the combination
+ + + + + - + + - + - of ± signs.
Since χ starts with "2 + ^J ", it follows that χ is larger than all the
elements of Нц that start with "2 — ^J ". Therefore, χ belongs
to the list of the 1024 largest elements of Нц. Further, the first
five + signs appearing in χ imply that χ is among the first 64
elements of Ни · Since these four + signs are followed by a — sign,
it follows that χ is between the 33rd and 64th largest elements of
Ни- Finally, it is easy to conclude that χ stands in the 1991s*
position in the ascending row of the elements of Нц-
Alternative solution:
2 - \ 2 + en\2 + 6n_iA/. · · + 6iл/2
= 2'
2 + бп\/2 + бп_1\/... + б1\/2
4- 2 + 6η\/2+6η_1λ/··· + ειλ/2
= 2-6η\/2 + 6η-ιλ/···+ειν/2·

1991
47
Hence
Д (2 + en+1 γ/2 + епл/7Г.)
ei,e2,...,en,en+ie{ — 1Д}
Д (2-6η^2 + 6η_1λ/ΓΤ)
ei,e2,...,enG{-l,l}
Therefore,
Π (2 + εη^2 + 6η_1ν/ΤΤ).
ei,e2,...,enG{-l,l}
Д ж=Дж = ...= Дж = 2.
хенп+1 хенп хен0
4. We first note that the trivial solution x = y = z = v = 0 always
exists. To eliminate cases where there is evidently no unique
solution, we look for the cases where there exists an additional solution
of the form (x:y:z,v) = (1,P, —P, —1), for some P. Substituting
the first equation into the second, we obtain
P2 + 2(A-1)P + A = 0.
This quadratic has real roots if and only if (A — l)2 — A > 0, that
. ^ З + л/5 ^ З-л/5
is, for A > —-— or A < —-—.
We conclude that for any real A such that A 0 [—-—, —-—],
the system does not have a unique solution.
We now guess, and try to prove the following statement: for all
values of A such that
^^<A<i±^ (3)
2 - - 2 y J
the system has only one solution, which is the trivial one.
To prove the statement, note that
(2)
(1) => χ = -{y + ζ + ν) => у2 + yv + Xyz + X(z + v)2 - zv = 0
which after rearrangement, reads

48
4. Solutions
у2 + (υ + \z)y + \{ζ + ν)2 - ζν = 0.
This equation has a real solution if and only if its discriminant is
nonnegative, that is,
(ν + λζ)2 -±(\{z + v)2 -zv) > 0
=> (4A - l)v2 + A(4 - \)z2 + 2(-3A + 2)vz < 0. (4)
In particular, it follows from (3) that 4A — 1 < 0. Therefore, if
ζ = 0, the inequality (4) can hold only if ν = 0 as well. In this case
the equations of the original system imply that у = 0 and χ = 0,
and we therefore return to the case of a unique (trivial) solution.
On the other hand, if ζ Φ 0, we can regard the left hand side of
the inequality (4) as quadratic in the variable v, with a negative
leading coefficient. This quadratic can attain a nonpositive value
only if
4(-3A + 2)2-4A(4A-l)(4-A) = 16(A3 - 2A2 - 2A + 1)
= 16(A + 1)(A2-3A + 1)
> 0.
This contradicts (1) and the desired conclusion follows immediately.

1992
49
1992
1. Denote d = л/с. We have
cn + c-n _2= (rfn -d~n)2,
c+c-1 -2 = (d-d-1)2.
The required inequality is equivalent to
dn - d~n
d-d~l
> n.
Now we have
dn-d~n ιΛ_ηά2η-1
= a
d-d'1 d2-\
= d1-n(l + d2+d4 + ... + d2n-2)
> d1-nn^/d2+^+-+(2n-2)
= n.
with which we are done.
2. We choose ten numbers αχ, а2, · · ·, α ίο from 5, having distinct last
digits.
Denote Τ = a\ + a,2 + · · · + αιο· We define the following set of
twenty numbers
A = {αι,α2,. ..,αιο,Τ- αϊ, Τ — α2,... ,Τ — αί0}
and show that its elements have at least 19 distinct residues modulo
2000. We consider the following cases:
a. If αϊ = dj (mod 2000), for some distinct indices i and j,
we obtain a contradiction to the assumption that оц ф uj
(mod 10).
b. Similarly, if Τ — сц = Τ — uj (mod 2000), for some distinct
indices г and j we obtain a contradiction.
с Suppose that Τ — ai = a,j (mod 2000). It then follows that
Τ — cii — dj, which is the sum of eight numbers from 5, is
divisible by 2000 and our problem is solved. Thus, we assume
that this option does not hold.

50
4. Solutions
d. Assume that
T-ai = ai (mod 2000),
i.e.
Τ = 2ai (mod 2000)
for some index i. This can occur only for one index г,
because if Τ ξ 2a,j (mod 2000) for i ^ j then сц — aj = 0
(mod 1000), in contradiction with our assumption on the last
digits of the chosen numbers.
It follows that we can choose 19 numbers from А, ск1? ск2,..., a±g
having 19 distinct residues modulo 2000.
We now arrange the elements of 5 in a way that the first ten are
αϊ, α2,..., αιο, and denote the sum of the first i elements in this
sorted set by Si.
If there exist two elements in 5ц, 5i2,.. ·, S1992 having the same
residue modulo 2000, then the difference between the largest and
the smallest one is a sum of elements from S and it is divisible by
2000, so the problem is solved.
Recall that each one from the 19 numbers αϊ, 0:2,..., a±g is a sum of
elements αϊ, α;..., аю, therefore for the same reason it follows that
ak ψ Si (2000) for each 1 < к < 19 and 1 < I < 1992. Altogether
we have 19 + 1982 = 2001 distinct residues modulo 2000, which is
a contradiction, and the required statement is therefore proved.
3. For each 1 < r < 100 we have
/r(l) > \ => a[r) = 1.
Therefore, a2 = 2 or a2 = 3 for each 1 < r < 100. Consequently,
(r) (s)
there exist distinct 1 < r, s < 100, for which a\ = a\' and thus
/«(!) = !> ^, /„(2) = lor2>~^,
/rs(3) = 2>^, /rs(4) = 2>^i, /rs(5) = 2>^.
4. For every pentagon Ρ we denote the pentagon formed by
intersection points of its five diagonals by Q(P). We also denote the "star"
defined by the diagonals of the original pentagon by R(P). Clearly,
we have R(P) Э Q(P).

1992
51
Assume that there exists a convex pentagon P0 for which Q(Po)
contains no lattice point. If the pentagon Po or its boundary
contain five points which define a pentagon Pi for which Q(Pi) also
contains no lattice point, we replace Po by P±.
Since the number of lattice points of Po is finite, we can repeat this
process until we end up with a pentagon Ρ for which Q(P) contains
no lattice point, and such that Ρ contains no sub-pentagon having
this property.
We now observe that in every convex pentagon whose vertices are
lattice points, one of the midpoints of its sides or diagonals is a
lattice point. This follows easily by considering the parity of the
coordinates of the vertices.
If R(P) or on its boundary contains a lattice point we consider a
pentagon P' defined by replacing the corresponding vertex (say A)
by a lattice point in the star (A') (see figure).
Since Q(P') С Q(P), we obtain a convex pentagon P' contained
in Ρ and Q(P') contains no lattice point. This contradicts the
definition of P.
Since Ρ contains at least one lattice point (a midpoint of a side or
of a diagonal), and this point is not inside R(P) or on its boundary,
it follows that this point is necessarily the midpoint of a side in P.
Now we can consider the (convex) pentagon P" whose vertices are
lattice points, which is obtained by replacing В by A",
Since Q(P") С R(P) (by convexity), it follows that Q(P") contains
no lattice point and this contradicts the definition of P.

Ϊ2
4. Solutions
These contradictions result from assuming the existence of the
pentagon Pq, and the statement is therefore proved.

1993
53
1993
1. Assuming that 10n λ < a < 10n for some positive integer η we
obtain
a 7 a 10n6 + a ab __
- = b.a О - = —— <^> — = 10n.
b b 10n a-b2
We now prove that ab and a — b2 are relatively prime. If we assume
that they have a common prime factor p, it follows also that a3 =
a2 (a — b2) — ab- ab and b3 = ab — b(a — b2) have the same common
prime factor p: and this contradicts the assumption that a and b
are relatively prime.
Therefore, it follows that a — b2 = 1 and, consequently, that ab =
10n. Since a and b are relatively prime and a = 1 + b2 > 6, we
conclude that b = 2n, a = 5n. Therefore
a = 1 + b2 => 22n + 1 = 5n => 4n + 1 = 5n => 4n + 1 = (4 + l)n
This is possible only if η = 1. In this case we have b = 2, a = 5.
Consequently, | = 2.5 is the only solution.
2. We denote ж - 1 = у, and obtain /(y2 - 1) = [/(г/ - l)]2. Now,
assume that yo is a number, not necessarily real, such that yo — 1
is a root of /.
We denote by у ι one of the complex square roots of ?/o, that is,
y\ = τ/ο- It follows that
[/(У1 - I)]2 = ЛИ - 1) = /Ы - 1) = 0,
which implies that Jy~Q — 1 is also a root of /. Similarly, we conclude
that ■sjs/yo— 1 is a root of /. It is now clear that for every positive
integer n, 2Уу~о — 1 is also a root of /.
Since the number of roots of / is finite, it follows that yo = 0, or
yo = 1. Therefore, / has at most two roots, namely (—1) and 0.
This implies that
f(x) = C(x + l)kxm, h,meN
for some constants C. Applying this to.the identity given in the
statement of the problem, we have m = 0 and then С = 0 or С = 1.
Consequently, the only two possibilities are f(x) = (x+l)k, к e JV,
or f(x) = 0.
It is now easy to verify directly that these are indeed valid solutions.

54
4. Solutions
3. We may assume that A and Ε are the ends of the diameter of
the semicircle. If this is not the case, we can map A and Ε to be
the ends of the diameter, and the lengths of AB and DE increase.
Thus, the left hand side of the desired inequality increases, and the
inequality becomes even stronger.
Applying the cosine law three times, we conclude that the required
inequality
AB2 + ВС2 + CD2 + DE2 + AB · ВС · CD + ВС · CD ■ DE < 4
implies that
AB-BC-CD+BC-CD- DE
< -2AB · ВС · cos I ABC - 2DE · CD ■ cos LCDE.
To prove the last inequality, it is sufficient to show that
AB-BC-CD < -2AB ■ ВС · cos I ABC,
and ВС-CD-DE < -2CD -DE- cos L CDE.
By symmetry, it is sufficient to prove only one of the last two
inequalities, say
CD < -2 cos Ζ ABC. (1)
Since
Ж_СЕ=1Ж-СЕ = АС = Ш,_1АВС
and
CD
CD = 2sin-—

1993
55
the inequality (1) can be written as
• CD CE
sin — < sin — . (2)
Since
0 < CD < CE < 180°,
It follows that
n CD CE
0< — < — <90°
Finally, since the sine function is increasing on the interval [0, 90°],
the inequality (2) follows, and this completes the proof.
We divide the board S into n2 sub-squares of size 3x3. We place
four rooks in all of the squares that intersect the main diagonal, in
the following way: if the nine subsquares of the square are denoted
by ay, 1 < i < 3, the four rooks are placed at 011,012,023,033.
With this construction we have placed on the board An rooks that
satisfy the requirements of the problem,
We now prove that no more than An rooks may be placed on the
board.
We divide the rooks into three types: rooks which take no other
rook, those taking other rooks horizontally, and those taking other
rooks vertically.
Assume that there are к rooks of the first kind, I rooks of the second
kind, and m rooks of the third kind. In any good arrangement the
к rooks of the first kind "occupy" к rows and к columns, I rooks of
the second kind occupy | rows, and I columns, and m rooks of the
third kind occupy m columns and Щ rows. Altogether, the number
of occupied rows and columns is
3 3
2k + -Z + -m.
We now recall that there exist 6n rows and columns, and therefore,
conclude that
3 3 3
6n > 2k + -I + -m > -(k + l+m).
Finally, this leads to к + I + m < An.

56
4. Solutions
1994
1. We assume that η > m. Consider the left condition (which refers
to ή). The x-s which satisfy it lie in the "good" interval of the form
к Ik 2
η 3n ' η 3n
(k is an integer) whose length is ^.
These are separated by open "bad" intervals of the form
1
3n ' η 3n
(k is an integer) of length ^ where the condition does not hold. We
call them η-good and η-bad intervals. Similarly, there are ra-good
and га-bad intervals.
We now assume that no χ satisfies
1/3 < {xn} < 2/3
and
1/3 < {xm} < 2/3.
Then every га-good interval is contained in one of the η-bad
intervals. Since an η-bad interval is an open interval of length ^,
whereas an га-good interval is a closed interval of length 3^, we
conclude that
J_ A
Зга 3n
and consequently that η < 2m.
Now since η < 2ra we see that
2
Зп Зга'
which means that η-good interval
1 2_
3n 3n
has common points with га-good interval
Зга' Зга

1994
57
Hence for any
we have
and
2 1
3n Зга
1/3 < {xn} < 2/3
1/3 < {xm} < 2/3.
Remark: The statement is not true if the condition 1/3 < {xn} <
2/3 and 1/3 < {xm} < 2/3 is replaced by 1/3 < {xn} < 2/3 and
1/3 < {xm} < 2/3. A counterexample is for η = 2, m = 1.
2. Define
1 1
x = a1-\ ha/c, y = 1 1 ,
1 !
a = a/c+i Η h an, о = \ \
We note that
Using the Cauchy-Schwartz inequality twice we obtain
(x + a)(y + b)> (y/xy + Vab)2 > (k + Vab)2.
The minimum of (x + a) (y + b) is obtained by taking
a\ = ai = ... = dk = vab.
Denote the centres of the three circles by A", B", C". Ρ is the
circumcentre of the triangle A" B"C". Since the circles have the
same radii, it follows that the segment joining the midpoint of PB
and the midpoint of PC joins also the midpoint of A"C" and the
midpoint of A"B". This segment is therefore equal (and parallel)
to \BC and to \B"C".
An analogous result is obtained for the other two sides, and it
follows that the triangles ABC and A"B"C" are congruent. The
sides of triangle A'B'C are parallel to those of AA"B"C" and
they are therefore similar to AABC.

58
4. Solutions
Moreover, the centre of the incircle of AA"B"C" is also the
centre of the incircle of AA'B'C', and therefore the similarity ratio
between these triangles is (R + r) : r where r is the inradius of
AA"B"C" and R is the circumradius which is also the circumra-
diusof AA"B"C".
Using the well known inequality between the inradius and the
circumradius of a triangle, we have R > 2r. Therefore, the ratio r at
least 3 and therefore the ratio of the areas is at least 9.
4. Take no = 9, mo > 4 · 29. Assume that an mo-no-society is given
and let В be the set of 9 girls. For each of the mo boys consider
the set of girls that he knows. Since there are only 29 distinct sets
of girls and more than 4 · 29 boys, there exists a set A of 5 boys
who know exactly the same set С of girls.
If С contains 5 or more girls, we are done.
If С contains less than 5 girls, then the complementary set contains
at least 5 girls that no boy from A knows and we are done again.

1995
59
1995
1. We first note that if sja — Vb > 1, that is, a — b > 1 + %Vb, then
there is a square between the integers a and b.
We now denote the n-th prime by pn. It is now enough to show
that
Pn+i = Sn+i — Sn > 1 + 2у Sn.
For η < 4, we have
Si = 2, 52 = 5, S3 = 10, 54 = 17, 55 = 28.
and it is easy to verify the statement directly. Suppose now that
η > 5, and write Pn = 2k - 1, i.e., fc = (l/2)(Pn + 1). Then,
Sn = 2 + 3 + 5 + 7 +11 + ··· + Ρη
< 1 + 3 + 5 + 7 + 9 + ··· + (Pn- 2) +Pn
= ^2,
so
2v^ - 1< 2k - 1 = Pn.
We now have 1 + 2y/Sn~ < Pn + 2 < Pn+i and we are done.
2. For any triangle ABC, we shall denote its area by Sabc· With no
loss of generality, we assume that the radius of the circle is R = 1.
Using the fact that the area Τ of a triangle whose sides are a, 6, с
and circumradius R is Τ = abc/^R, we have
2SPPlp2 = d12 ■ РгР2 = ipPi · PP2 ■ P1P2,
and consequently,
di2 = \pPi PP2.
Similarly, we obtain

60
4. Solutions
^34 = ^РРзРРь
dia = \pPiPPs,
and d24 = 2PP2 Pp4-
and the result follows.
Alternative solution:
The two angles LP\P2P, /-Ρ1Ρ3Ρ (see the figure) are equal as they
lie on the same arc.
This implies the similarity
ΔΡΤ1Ρ2 ~ &PT2P3, ΔΡΤ4Ρ3 ~ ΔΡΤ3Ρ2
where Ti, T2, T3, T4 are the feet of the perpendiculars from Ρ onto
P2Pi, P1P3, P2P4, P3P4, respectively. We now have
d12 = PTi = PP2
d13 PT2 PP3
d24 = PT3 = PP2
dM ~ РП РР3
and therefore d\2d?,b = d\?,d2±.

1995
61
Note here that this proof is not yet complete, as it depends on
the cyclic order of the points P, Pls P2, P3, P4 as it appears in the
figure. For example, LPiP2P and ZP1P3P are not equal if P3 lies
between Ρ and Pi on the arc opposite to the one in the figure. In
this case 1РгР2Р + ZP1P3P = 180°. To complete the proof, we
simply note that if we replace Pi by P3 and replace di2 with dis
appropriately, then the claim of the problem remains unchanged.
3. We check the values of f(x) at 0, |, 1. This gives
|c| < 1, |a + 2b + 4c|<4, \a + b + c\<l.
We denote
A = a + 26 + 4c, В = a + b + c.
This implies
a = -A + 2B + c, 6 = A - В - 3c.
It follows that
\a\ < \A\ + 2\B\ + 2|c| <4 + 2 + 2 = 8
and
|6| < |A| + \B\ + 3|c| < 4 + 1 + 3 = 8
so
И + |Ь| + |с| < 8 + 8 + 1 = 17.
This yields an upper bound for \a\ + |6| + |c|.
Finally, the example f(x) = 8x2 — 8x + 1 shows that the value 17
can indeed be attained, and the result follows.
4. Consider a convex triangular polyhedron with η > 4 vertices. We
choose an arbitrary vertex C. Suppose that r > 3 edges emanate
from С Due to the polyhedral structure, there exists a proper
labeling of these neighboring vertices, say, CCi, CC25 ■ · · ■> CCr in
a way that CC±: C1C2, C2C3, ..., Cr_iCr, CrCi are edges. We
colour CC\ in blue, CC2, CC3,..., CCr in red, C1C2 in red, and
C2C3, C3C4, ·.., Crd in blue.
We now proceed by rounds: we choose any triangular face F which
has either one or two coloured edges. We consider the following
two cases:

62
4. Solutions
(a) If F has only one coloured edge, we colour the remaining two
edges with two opposite colours: one in red and one in blue.
Note that before this colouring, F had precisely one vertex
which was yet unreachable by coloured paths. We call it a
"new vertex".
(b) If F has two coloured edges, we colour the third edge with
any colour. Note that all of the vertices of F were already
reachable by coloured paths even before the colouring of this
third edge.
From our colouring it follows that in case (a) we can reach the
new vertex by both red and blue paths. In case (b) no new vertex
is reached. At the end of this round, the vertices that belong to
completely coloured faces can be reached from С by both red and
blue paths.
We continue with these rounds inductively: at each step we seek a
new face with either one or two coloured edges and repeat (a) or (b),
accordingly. This procedure preserves the good colouring property
of the subset of vertices that belong to completely coloured faces.
We conclude after all edges have been coloured. This must occur
within a finite number of steps. Otherwise, we would have two
disjoint subsets of faces: one which is completely coloured and
the other which is completely uncoloured. This contradicts the
polyhedral structure. At that point we are done.

1996
63
1996
1. The only solution is the trivial one, namely (0, 0,..., 0).
Let m = 1997. If
\X± , 3?2, · · · , X-m)
solves (1) then so does
— yX± , Χ21 · · ■ ι Xm ) ·
Therefore, we assume that one of the terms Xk is odd. Let the
first odd Xk be xq+i where q G 0,1, 2,... ,ra — 1, which implies
that Xk = 2uk for some integer Uk for any к < q. Now, it follows
that the left hand side of (1) equals 2q χ an odd number, and the
right hand side of (1) equals 2q χ (an even number) and this is a
contradiction.
2. If 6 is a positive integer then
(6 + l)3 - b3 = 3b2 + 36 + 1 = n2,
that is
1262 + 126 + 3 = 4n2 - 1,
or
3(26 + l)2 = (2n + l)(2n-l).
Since 2n +1 and 2n — 1 are relatively prime, there are two cases to
check:
A) 2n - 1 = 3c2, 2n + 1 = d2. This yields d2 - 3c2 = 2, which is
impossible if we consider modulo 3.
B) 2n - 1 = d2: 2n + 1 = 3c2. Thus d is odd. Then
d = 2s + l,
i.e.
2n = d2 + 1 = 4s2 + 45 + 2 = 2 ((s + l)2 + s2) ,
or
n= (s + 1)2 +s2:
and we are done.
To find an example, we use the first equation. This gives

64
4. Solutions
The first η > 2 for which the discriminant is a square is η = 13,
giving 6=7. Indeed,
83 - 73 = 512 - 343 = 132
and
13 = 22+32.
Remark: Using Pell's equations with the discriminant 12n2 — 3 we
can get all the solutions. The next solution is η = 181, noting
1053 - 1043 = 1812, where 181 = 92 + 102.
3. Denote the number of vertices, edges and faces by v, e, /,
respectively, the number of vertices of degree i by vi, the number of faces
with г edges by fa. We have:
ν = (vs = 0) + V4 + V5 + vq + ...
/ = /3+/4 + /5 + /6 + ...
2e = (3v3 = 0) + 4v4 + 5v5 + 6v6 + ...
2e = З/3+4/4+5/5+6/6 + ...
Now by Euler's formula,
4v + 4/ = 4e + 8 = 2e + 2e + 8,
so
4(V4 + V5 + Vq + . . .) + 4(/3 + U + /5 + · · ·)
= (4i;4 + 5^5 + · · ·) + (З/з + 4/4 + 5/5 + ...)+ 8,
i.e.
/3 = 8 + (v5 + 2v6 + - · ·) + (/5 + 2/e + .··)> 8
4. We denote S = a±bi + ... + anbn and write S as:
S = ai(bi - b2) + (ai + a2)(b2 - b3)
+(αι +a2 +a3)(63 - b4)
... + (ai + a2 + · · · + On-i)(bn-i - bn)
+(ai + ... +an)6n.

1996
65
Let Ai = |αι +α2 + · · · +α^| and suppose that Ak is maximal among
the Αφ. Then,
η η
|5| < Y^Aiih - bi+1) < AkJ2(bi ~ bi+i) = Akh < Ak
1 1
(by definition, we assume bn+i = 0). This completes the proof.

66
4. Solutions
1997
1. The answer is positive in the following general context. Suppose
that ж, η are positive integers and η is even. Then there exists a
positive integer N such that
(y/x + 1 - y/x)n = y/N- y/N-1.
Proof: Note that
(Vx + i -Vx)n
n/2 / Ν
ι—η \ '
eV+1>+^· (1)
\kι fZ\n—k
k=0
n/2
\kx 2
\ '/k: I 4
k=0
Vx + 1
7=— X
v k=0
Similarly,
^ (л/ж + 1 + y/x)n
n/2 / Ν
= Σ ;>+^-
/c=0 V У
+ ^F*ft)-»'-, w
fc=0
We denote the sum
n/2
k=0 v 7
by 5i and the sum

1997
67
y/x + l
η/2-1
Σ
k=0
П
2k+ 1
(х + 1)кх^
by 52. Multiplying (1) by (2), we end up with
1 = (y/x + 1 + Vx) x (y/x + l ~ Vx)
= (51-52)x(51+52)
= sl-sl
Note that 5i is an integer and therefore N = Sf is also an integer.
Consequently, we get
(VxTT- V^)n = Si-s2 = Vn-Vn^i.
as required.
2. The set of numbers a that satisfy the required condition is the set
of all integers.
Suppose that a is an integer. Then, for each η we may choose
m = an, and the condition is satisfied.
Conversely, suppose that the condition holds for some a. Let mu
be the corresponding numerators for η = 2k, к = 0,1, —
If
then
mk mk+1
ГПк . ГПк+1
~2~к~ ι 2k+1 '
2mk - гпк+ι
2k 2k+1
2k+1
>
2k+1 '
Therefore, using the triangle inequality,
2fc+i
<
<
<
mk гпк+ι
2k 2k+1
mk
2k
1
a
+
+
a
mk+1
2k+1
3 · 2k 3 · 2k+1
1
2/c+i'

68
4. Solutions
and this yields a contradiction. It follows that m,k/2k = mk+i/2k+1
for all k, and thus all the approximations of the form mk/2k to a
are equal to an integer tuq. But then
\a — rao
mk
2k
1
<
3-2fc
for every k. Consequently a —mo = 0 and a is therefore an integer.
3. Denote AB = c, AC = b: ВС = a and ΟΑλ = a1: ΟΒλ = Ьь
OCi =ci.
We start with the following statement.
Statement:
ОМ ОВг OCL =
ААг ВВг ССг w
Proof: Denote a = LB AC, β = IABC, 7 = LBCA. Denote also
δ = 90° + 7 - β. We note that
LOBC = 90° - a.
Then by the sine law, applied to AOA±B: we have
Ο Αχ _ OAx _ R
sin(90° — a) cos a sin δ
and in AAAiB we have
AAi с 2i?sin7
Hence,
sin β sin 5 sin δ
Ο Αι cos α
AA\ 2 sin/3 sin 7
Similarly, we have
OBi cos/3 OCi cos 7
β.Ε?ι 2 sin α sin 7' CC\ 2 sin α sin β
Addition with common denominator 2 sin a sin β sin 7 yields
QAi OBx OCx
AAX + SSi + CCX
sin α cos α + sin β cos β + sin 7 cos 7
2 sin α sin /3 sin 7

1997
69
It now remains to show that
sin a cos a + sin β cos β + sin 7 cos 7 = 2 sin a sin β sin 7. (2)
This latter equality follows from considering areas. We denote the
area of AXYZ by SXYZ. Then
Sab с = 8p2 sin α sin /5 sin 7.
The angles of AABC are arcs on the circumcircle, and therefore
LBOC = 2a, LCOA = 2/3, ZAOS = 27.
Now,
Sboc = 2p2 sin 2a = 4p2 sin a cos a,
and similarly,
Scoa = 4p2 sin /3 cos /3, Saob = 4p2 sin 7 cos 7.
From the equality Sabc = Sboc + Scoa + Saob it follows that
8p2 sin α sin /3 sin 7 = 4p2 (sin α cos α + sin β cos /3 + sin 7 cos 7)
and (2) is obtained through division by Ap2.
When (1) is written in terms of αϊ, bi, ci,p, we obtain
αϊ Ь\ ci _
2p + αϊ 2p + bi 2p + ci
This yields
4p3 - p(aibi + biCi + ciai) = aibiCi. (3)
Prom the assumptions, it follows that p|ai&iCi. Since ρ is prime, it
follows that it divides at least one of αϊ, Ь\ or c\. We assume, with
no loss of generality, that p\a\. Since the diameter is the longest
chord in a circle, we have αϊ < 2p, and therefore αϊ = p. Equation
(3) becomes
4p2-p(6i+ci) = 26ici. (4)

70
4. Solutions
Now, p\2biCi. И ρ > 2, it follows that, for instance, p\bi, and again,
since 6i < 2p: we obtain ρ = b±. This lead to ρ = c\ and to the
conclusion that the triangle is equilateral.
If ρ = 2 it follows from (4) that
(bi + l)(ci+l) = 9,
i.e., bi = ci = 2. Now it also follows that a± = 2 and the triangle
is equilateral.
Finally, the only solution is an equilateral triangle with a = b =
с = 2Рл/3.
4. Solution 1
We start constructing a sequence by first choosing a occurrences
of A for some odd a. Since В and С must appear at least once,
we have 1 < a < 1995. The number of such choices is ( ). For
any choice of A's we can choose b occurrences of В for some odd
b where 1 < b < 1996 - a. We have (199^~α) choices. Choosing
a and b already determines the sequence. Therefore, the required
number of sequences is
1995 /-,™„\ 1996-a /л „„„
1997 — a
s= Σ (Ш7)х Έ (
Since the sum
. a J 2-—' V &
a=l,a odd 6=1,6 odd
JV
Σ (? 4-
We have
г=1,г odd
1995
N
i,2
-is er>
α=1,α odd ч
1997-α
We now use the expansions
a+z)w = Σ ("У"
and (1-s)" = Σ (^)f-1)
г=1 ^ ^
N-i N-i

1997
71
and write
N
i=l,i odd
In our case, with N = 1997 and χ = 2 we finally have
S=i(i(31997-l)-l) = j(31997-3).
Solution 2
For every odd η > 3 we denote the number of sequences of length
n, composed of the letters A, jE?, С and such that each letter occurs
an odd number of times, by xn. We use yn to denote the number of
sequences of length η composed of the letters which can be A, B: С
such that the number of occurences of А, В, С is odd, even, even,
respectively. Similarly, we use zn to denote the number of sequences
of length η with even, odd, even occurences of A, B: C, respectively.
Finally, let wn denote the number of such with even, even, odd,
occurences of А, В, С, respectively.
By symmetry we have yn = zn = wn. Since η is odd η the
sequences counted by xn, yn, zn, and wn cover all possible sequences
of length η that are composed of the letters A, B: C. We therefore
conclude that xn + 2>yn = 3n.
For η = 3 it is easy to see that xn = 6 and yn = zn = wn = 7 (zero
number of occurences is counted as even).
We now examine xn+2 · Sequences of length η + 2 can be obtained
from a sequence of the type xn by adding AA: BB or CC. They
can be obtained from sequence of the type yn by adding AB or
В A, from zn by adding AC or С A, and from wn by adding ВС от
СВ. We therefore have
Xn+2 = ЗЖП + 6yn
or
Xn+2 = xn + 2 · 3 .
To solve the recurrence relation, we seek a solution of the form
xn = a · 3n + β. Tis leads to
Xn = \{T-Z).

72
4. Solutions
The required answer is obtained by substituting η = 1997 in this
formula.
Solution 3
We use generating functions. Suppose that the sequence is
composed of a As, b Bs, and с Cs where a, 6, с are odd. The number
of possibilities for constructing such a sequence is
1997!
a! 6! c!
where a + b + c= 1997. Therefore, we are looking for the sum
^ 1997!
a+b+c=1997, a,b,c odd
To that end, we note that
00 к ι °° к /
fc=0 fc=0, /c odd
We now use the generating function
№ = i(e*-e-*)xi(e*-e-*)xi(e*-e-*)
= I (e3x - 3ex + 3e~x - e~*x)
8
8 l^ i! ^ j! ^ /! ^ fc!
The coefficient of ж1997 in the latter expansion is
1 '->1997
4 χ 1997!
On the other hand,
(3iyy'-3).
OO h OO r
rf*Vb rf**J /Ύ*'-
/w= Σ ^гх Σ ¥χ Σ сГ
α=0, α odd 6=0, Ь odd /c=0, c odd

1997
73
Therefore, the coefficient of ж1997 in this expansion is
ул 1997!
a+b+c=1997, a,b,c odd
Finally, it follows that
a! 6! c!
Σ
1997! l(3iew_3)_
a! 6! c! 4
a+b+c=1997, a,b,c odd
We consider the squares ABB\A' and BCD Ε and apply the
following transformation: rotation around В by 45° and shrinking
by the factor y/2. The point A' is mapped to A and the point С
is mapped to Ρ (see figure). The segment А'С is mapped to the
segment AP.
It follows that the angle between these two segments is 45°.
Denote the intersection point of these segments by 0\. The angles
LCO\P and LCBP are equal (both equal 45°), and the
quadrilateral BO\CP is therefore cyclic. Consequently, the circumcircle of
ABC Ρ intersects the line AP at 0\.
Consider now the intersection point O2 of AP and В A". By the
same considerations, the circle circumscribing ABCP intersects
the line AP at O2· Consequently the points 0\ and O2 coincide,
i.e. the lines AP, A'C and A"B are concurrent.
6. Solution 1
The answer is negative. Suppose that the disk С can be
decomposed into the two congruent parts Pi and P2. Let / be the
congruence mapping that maps Pi to P2 and let g be its inverse. Denote
the image of the whole disk С under / by C\ (which is a disk), and

74
4. Solutions
the image of С under g by C2. The three disks C, C\ and Ci are
congruent and the union of C\ and C2 covers С It is easy to see
now that the two image disks C\ and C2 must each cover C. If this
is the case, then the three disks must coincide. Since / and g are
congruences they must keep the centre of С fixed. Since Pi and P2
are disjoint, this yields a contradiction.
Solution 2
Suppose that we divide the disk into two disjoint congruent parts A
and B. This implies that there exists some isometry transformation
Μ which maps A onto B. We now consider some properties of
isometries: if an isometry in a plane preserves direction then it is a
pure translation or a pure rotation. If it reverses direction, then it
is a combination of reflection and translation. We investigate and
obtain a contradiction in all possibilities.
Case (a). M is a translation and Μ (A) = B. Let I be a line tangent
to a circle whose direction is parallel to the direction of translation
and let К its tangency point to the circle.
•ж
There are two possibilities: К belongs to Л or К belongs to B. If
К belongs to Л then M{K) £ B. But M{K) is totally outside the
circle. If К belongs to B, then М~г(К) G A and again, М~г{К)
is outside the circle. The contradiction proves that Μ is not a
translation.
Case (b). Μ is a rotation around the point O. If О is not the
centre of the circle, consider the point К at the largest distance
from O. As in case (a), M{K) and Μ~λ(Κ) do not belong to the
circle and we thus arrive at a contradiction.

1997
75
If M is a rotation around the centre of the circle O, then the centre
of the circle is a fixed point of M, i.e. if О G Л then О = Μ (Ο) G В,
in contradiction to A and В being disjoint. Conversely, if О G В
then Ο = Μ~λ(0) G A, again a contradiction.
Case (c). Μ is a reflection with respect to a line I. Since all the
points of I are fixed points of M, and by considerations mentioned
in case (b) there may be no fixed point inside the circle, the line
I does not intersect the circle. But then Μ maps the circle into a
circle which is disjoint to it, in contradiction with Μ (A) = B.
Case (d). Μ is a combination^ of reflection with respect to a line
I followed by a translation. If the direction of the translation is
perpendicular to I, the Μ can be described as a reflection with
respect to a line V parallel to I and we are back in case (c).
Generally, the translation can be decomposed into two components: one
perpendicular to I and the other parallel to I. Therefore Μ can
be described as a combination of reflection with respect to a line
V (parallel to Ϊ) followed by a translation at a direction parallel to
V. Consider now the point К of the circle whose distance from V
is maximal (for this consideration it does not matter whether the
line V intersects the circle or not). The points M{K) and M~l{K)
do not belong to the circle, and thus we arrive at a contradiction
as in cases (a) and (b).

76
4. Solutions
1998
1. I. We denote a success by 1, failure by 0, and the probability that
the game ends exactly after η turns by pn. Every sequence of η
turns (coin flips) consists of η steps, each bears the probability -
to be a 1 or a 0. We therefore have
Pn = ^Mn
where Mn is the number of η digits binary sequences that end with
two consecutive Is and contains no prior two consecutive Is. Any
such "legal" sequence belongs to one of the following types
(a) It begins with 0, and followed by η — 1 digits, where the last
two digits are 11
(b) It begins with 1, followed by η — 2 digits where the last two
digits are 11.
Consequently, for any η > 5 we can write the following recurrence
relation:
Mn = Mn_i+Mn_2.
It is easy to verify that Mi = 1 (the sequence is 11), M3 = 1 (the
sequence is Oil), and M4 = 2 (the two possible sequences are 1011
and 0011).
Let Fn denote the n-th term of the Fibonacci sequence F\ = 1,
F2 = 1, Fn+2 = Fn+i + Fn for η > 1. It follows that
Pn=— -Fn-i, η = 2,3,....
II. We denote the average (expected) number of coin flips till the
game terminates by x. We first prove that χ is finite, a fact which
is not apriori obvious. To that end, we use Binet's formula
Now, the average length of a game is, by definition,

1998
77
n—l „, / ,_\ η—1
~ ~ n /ΐ + λ/5\ 1 ~ /1 + л/5
2n \ 2 / 2 ^ \ 4
n=l n=l \ / n=l \
The ratio, rn, of two consecutive terms in the latter series is
4 ) 1 + л/5
(η-1)(ίψ)
n-1
n-1
It is easy to see that rn < 1 for η > 7. Consequently, our series is
dominated by a convergent geometric series, and is therefore also
convergent.
Knowing that χ is finite, we can write equations that involve χ as
a variable. We consider the following three cases:
(a) the game starts with one 0 (i.e. failure),
(b) the game starts with 10,
(c) the game starts with 11 (and ends).
The respective average game lengths in these three cases are:
-(ж + 1), -(ж+ 2) and 2=2'4'
Therefore, we can write
X= 2 + 2(ж + 1) + 4(ж + 2)
and the solution is χ = 6.
Alternative solution for II: We use the identity
oo 1
n=l
We write

78
4. Solutions
., r, OO OO
1 3 т—^ П тг-^ П
- о + я+2^^—2 + 2^*™-3
2η -t—' 2Τ
η=4 η=4
_ 7 1 γ> 71 + 1 1γ^
η + 2
■Γη-1
8 2 ^ 2η 4^2
η=3 η=3
Now, applying (1) we have 5 = 2 and therefore
3 3
Х=Г+2
which implies χ = 6.
2. Solution 1
Denote LCAB = a, Ζ ABC = /3, Z5CA = 7. These correspond
to arcs of the circumcircle, which correspond to the central angles
LBOC = 2a, LAOC = 2/3, LBOA = 2Ί.
Denoting the area of any triangle AXYZ by Sxyz, we conclude
that the areas of the triangles ABOC, ACOA, AAOB are,
respectively,
111
Sboc = ^r2 sin 2a: scoa = 2 r2 sin 2A 5aob = -R2 sin 27.
On the other hand, the area of each of these triangles equals to the
radius of the incircle times half the perimeter. Therefore,
Sboc = -R2 sin 2a
r-±(2R + BC)
7^-(2R + 2Rsma)
= r\R{\ + sin a).

79
which implies that
1 1 + sin α 1 + sin α 1/1 2
= 2-——- = — = - +
r\ R sin 2a R sin α cos α R Vcosa sin 2a
Similarly, we obtain
1 1/1 2 \ 1 _ 1^ / 1 _2
Г2 R \cos/3 sin2/3/ ' гз -R \c0s7 sin27
By summing up the last three equalities we get
111
— + — + —
Г\ Г2 Г3
1/1 1 1
+ » +
R \cosa cos/3 cos7
2 2 2 λ
+ sin2a + sin 2/3 + sin277 ' ^ ^
We now recall the following well known inequalities that hold for
any triangle (for a proof, see below):
3
cos α + cos β + cos 7 < - (2)
Зл/3
and sin 2a + sin 2/3 + sin 27 < ——-. (3)
Applying the Cauchy-Schwartz inequality to the two triples
1 1 1
(\/cos~a, \/cos /3, -γ/cos 7),
л/cosa ' -v/cos/3 ' y/cos^y
and using (2) gives
9 < (cos α + cos /3 + cos 7) ( 1 Η ) ,
\cosa cos ρ cos7y
which implies
ill 9 9
+ + > > —г = 6. (4)
cos a cos/3 cos 7 cos a + cos/3 + cos 7 3/2

80
4. Solutions
By applying the Cauchy- Schwartz inequality to the triples
(Vsin2a, л/sin 2/3, \/sin27),
Vsin 2a Vsin 2/3 Vsin 27
and using (3), it follows that
x,l 1 1
9 < (sin 2a + sin 2/3 + sin 2η) . + . +
sin 2α sin 2/3 sin 27/ '
i.e.
Ill 9
sin 2a sin 2/3 sin 27 sin 2a + sin 2/3 + sin 27
9
~ Зл/3/2
= 2л/3. (5)
Finally, using (4) and (5), with (1) we get
П Г2 Г3 it
which is the required inequality.
It now remains to prove the two standard inequalities (2) and (3).
The inequality (2) is obtained by
cos α + cos /3 + cos 7 = cos α + cos /3 — cos(a + /3)
a + /3 а —в ( ?α + β . 2 a +/3
= 2 cos —-— cos — cos — sin
2 2 V 2 2
a + /3 α — β , _ οα+ β
= 2 cos ——- cos ——^ + 1-2 cos2 ——^
Δ Δ Δ
a + в 9 a + /3
< 2cos—^-+ 1 - 2cos2 —-A
Δ Δ

1998
81
The maximum of the quadratic polynomial 2x +1 — 2x2 is obtained
for χ = -, and its value is -. Thus, substituting χ = cos we
2 2 2
derive (2).
A straightforward method for proving (2) is to apply Jensen's
inequality to the convex function — cos(rr), and the result follows
immediately.
To prove (3) we note that
sin 2a + sin 2β + sin 2j = 2 sin(o; + β) cos(a — β) + 2 sin 7 cos 7
< 2 sin (a + β) + 2 sin 7 cos 7
= 2 (sin 7 + sin 7 cos 7).
Seeking the local maximum of the function
Τ [η) = 2(sin 7 + sin 7 cos 7)
7Γ
in 0 < 7 < — by differentiation, we get
2(cos7 + cos2 7 — sin2 7) = 2(cos7 + cos27)
= 4 cos — cos —
Δ Δ
= О
°·2
IS
(the derivative must vanish at the local maximum, since it is easy
to verify that the maximum is not attained at the endpoints of
the interval). The only solution of the latter equation in
7 = 60°. Therefore, the required maximum is
Зл/3
2(sin 60° + sin 60° cos 60°) = -~,
which completes the proof.
Solution 2
Let О be the circumcentre of A ABC. Denote the distances of О
from the sides α = BC,b = С А, с = AB (of A ABC) by da, db: dC:

82
4. Solutions
respectively. Denote the areas of AOBC, AOCA and OAB by t±:
i2, h, respectively and denote the area of A ABC by t.
Clearly, we have
1 _2R + a _ R a _R a _ R 1
r\ 2ti t\ 2ti t\ ad a ti dA'
and similarly
J_ _ Я J_. 1 _ R J_
r2 t2 dB ' гз *з dc
Therefore,
1 1 1 /1 1 1 λ / 1 1 1
ri r2 r3 \ii i2 <з/ V^a as dc
Using the Cauchy-Schwartz inequality we have
and obtain
(x + y + z)[- + - + -)>9
\x у ζ '
111 9
+ ^ + — >
t\ ti ^з ti +t2 + ts
л 111. 9
and — + —- + — >
dA dB dc dA+de + dc
Now by using the inequality R > 2r and the equality
dA + dB + dc = R + r (6)
(see explanation below), it follows that
111 96
3- + 3- + Т- ^ 7; ^ 7ϊ·
CtA «В «с it + Г R
Finally, we conclude that

1998
83
Since
4
we obtain
1 4
>
t ~ 3V3R2'
and therefore
1 1 1 36Д 6 _ 4\/3 + 6
η + ^ + ^з ~ Зл/3^2 #~ Я
It now remains to prove (6). To that end, we recall that if r is the
inradius of A ABC and S is its area, then S = rp: where
a + b + с
Ρ =
is half the perimeter of A ABC.
Thus, we have
ρ = _R(sin a + sin β + sin 7)
= i?(sin a + sin β + sin(o; + β))
= 2R sin —-— cos — h cos
2 V 2 2
. D . 180° -7 ^ /5 .0 α β 7
= 4it sin cos — cos — = 4-K cos — cos — cos —
Zi L· £1 L· L· Δι
and
ал + ав + dc — R = i?(cosa+cos/3+ C0S7 — 1)
= R [cos a + cos β — (cos(a + β) + 1)]
0 + /3 / α-/3 α+β
= 2-K cos —-— cos — cos
2 V 2 2
,D 180°-7 . α . /3
= 4л cos sin — sin —
α β . 7
= 4:R sin — sin — sin —.
2 2 2

84
4. Solutions
Therefore,
(dA +dB +dc - R)p
1fiD2 · a ■ β · 7 " β Ι
= 1QR sin — sin — sin — cos — cos — cos —
2 2 2 2 2 2
1i;D2 · " a . β β . 7 7
= loit sin — cos — · sin — cos — · sin — cos —
2 2 2 2 2 2
and finally,
= 2R2 sin a sin β sin 7
= S.
dA + dB + dB — R = — = — = r,
Ρ Ρ
which implies (6).
3. We prove the statement by induction on m.
For m = 1 the statement is obvious.
Now choose η consecutive natural numbers cki, «2,..., скп such that
each of the numbers /(αϊ), /(«2), · · ·, f{oLn) has at least m distinct
prime factors.
Denote
A=[f(a1)f(a2)...f(an)]2
and define
Pj = A + cxj, 1 < j < n.
Note that the numbers β^ are also η consecutive natural numbers.
Now,
/(&) = a(A + aj)2 + b(A + aj) + с
= aa2 + bctj + с + A(aA + 2aa3- + b)
= Да,·) + иЫ)2иЫ)2 ■ ■ ■ (f(an))2(aA + 2aaj + 6)
= /К)[1 + (/Ы)2(/Ы)2]

1998
85
...(/(α,·_0)2/Κ)№,+ι))2
...(f(an))2(aA + 2aaj +b)]
= f(aj)[l+Bf(aj)]
for some integer B. Since 1+Bf(a>j) and f(atj) are relatively prime,
it follows that f(Pj) has at least one more prime factor than f(a-j)
has. This completes the proof.
4. Solution 1
Assume that χ and у are positive integer solutions of the equation
Ъх - 3V = 16.
It follows that
bx = 16 (mod 3).
Consequently, 2ζξ1 (mod 3). This is possible only if χ is even,
i.e., χ = 2a for some integer a.
Now,
5* - ЗУ = 16 => 1 - (-If = 0 (mod 4)
and this is possible only if у is even, i.e., у = 2b for some integer b.
We can now conclude that
5* - 3y = 16 => 52a - 326 = 16 => (5a)2 - (36)2 = 42. (1)
Using (1), it follows that
(5α + 36)(5α-36) = 16.
The only possibilities for factoring 16 are:
Г 5" + 3b = 16 Г 5a + 36 = 8
\ 5a - 36 = 1 \ 5a - 36 = 2
From I it follows that 2 · 5a = 17, which is impossible.
Option II yields 2 · 5a = 10, i.e., a = 1 and therefore 6=1.
The only solution of the given equation is thus χ = у = 2.

86
4. Solutions
Solution 2
From (1) it follows that 5a, 3b, 4 is a Pythagorean triple. It therefore
has the representation
5a = m2 + η2, 36 = m2 - n2, 4 = 2ran,
for some integers ra, n. From 36 = m2 — n2 it follows that m2 > n2
i.e., m> n. The equality 2mn = 4 can hold only for m = 2, η = 1.
Therefore,
5a = m2 + n2 = 5, 36 = m2 - n2 = 3 =^>
a = b=l=>x = 2a = 2, у = 26 = 2,
and the only solution is ж = ?/ = 2.
5. We denote
ZAOS = a, ZSOC = /3, ICOD = 7.
Since Б С || АО \\ OD (where О is the centre of symmetry of the
hexagon ACBDEF, and АО = OD, BO = OE, CO = OF), it
follows that
LOBC = a, LBCO = 7
and that the quadrilateral AOBC is a parallelogram. Therefore,
LOAB = LBCO = 7
which implies the congruence of the triangles OAB and О ВС.
Similarly, the triangles OBC and OCD are congruent. The other
three triangles that have a common vertex O, namely AODE,
AOEF, AOFA, have sides that are parallel to those of the
triangles AOAB, AOBC and AOCD. By symmetry, they are of the
same corresponding sides. It follows that all the triangles whose
vertices are О plus two other consecutive vertices of the hexagon are
congruent. By the construction of the triangles AFAFi, AEFEi,
ADED1: ACDC1: ABCB1: ААВАЪ we have
LOBBx =α + 60°, Ζ OB Ax =/3 + 60°,
and

1998
87
ΔΑ1ΒΒ1 = 360° - LOBΑλ - LOBBx
= 180° +a + β + Ί -(/3 + 60°) -{a + 60°)
= 7 + 60°.
In AA1BB1 and ΑΟΑΑλ we have
OA = BC = BBu AA1=A1B,
and
LAxAO = LAXBBX = 7 + 60°.
Therefore, these two triangles are congruent, and Ο Αχ = ΑχΒχ.
Similarly, the triangles AA\BB± and AOCB\ are also congruent
and thus OB\ = AiB±. This implies that the triangle ΑΑιΟΒι
is equilateral. If we pass over all the triangles having the
common vertex О plus two other consecutive vertices of the hexagon
AiBiCiDiEiFi, we conclude that they are all equilateral.
Therefore, the hexagon A1B1C1D1E1F1 is regular.
We have so far proved that if ABCDEF is an affmely regular
hexagon, then A-]_BiC\D\E\Fi is a regular hexagon.
We now prove the opposite direction, namely, that if
AiBiCiDi^i-Fi
is a regular hexagon with centre O, then the triangles
АОАгВъ АОВгСъ ..., ΔΟΉΑι
are equilateral and congruent. To that end, note that
LAxBxO = LBxCxO = ... = LFxAxO = 60°.
Also,
LBBXC = 60° = LBBxO + LOBxC = 60° - ΙΑλΒλΒ + LOBxC
Therefore, LOBxC = ΑλΒλΒ. Since OBx = АгВи BXC = ВВЪ
and it follows that AOB\C and ΑΑχΒχΒ are congruent, which
implies that ОС = A\B = AB. Similarly, we obtain that О А =
BC: and thus О ABC is a parallelogram. Consequently,

88
4. Solutions
OC = AB = OF, ОС || AB || OF || BE.
The analogous conclusion applies to the other sides and diagonals
of ABCBEF, and this proves that ABCBEF is affinely regular.
6. Solution 1
Let S be the set of all arrangements of the numbers 1, 2,..., те in
a row. The number of elements of S is те!.
We now define the function f:S —> Π in the following way: for
any given arrangement s there is a unique partition into blocks
such that in each block the leftmost number is the largest, and
those leftmost elements form a descending sequence. Finally, we
define f(s) as the partition of те whose summands are the number
of elements of the blocks in this partition.
To illustrate, we give an example. Suppose that те = 6 and s is the
arrangement 3,1, 5, 2, 4, 6. The blocks will be {3,1}, {5, 2, 4}, {6}.
Therefore, in this case f(s) is the partition 6 = 2 + 3 + 1.
Now, for any given partition a G Π we compute the number of
elements in f~1(a). In other words, we compute the number of
arrangements s G S for which f(s) = a. The number of ways for
distributing the те positions in the arrangement into sets of the sizes
that occur in a = αχ (α), a2(a),..., αη(α), is
^ ) (!!)«!(«)(2!)a2(a)... (η!)α4«)αι(α)!α2(α)! · · · an(a)! '
After determining the positions distribution, the leftmost number
in each block is uniquely determined. For the other positions in a
block of size г we can arbitrarily arrange the other г — 1 numbers.
The order of the blocks is also determined by the order of the
leftmost elements. Consequently, the number of arrangements in
/-» is
Ρ (α) · (0!)αι^(ΐ!)α2^ · ((η- 1)!)а-И
те!
_ 1αι(α)αι(ο:)! ■ 2а2^а2(а)\ · · · па"(а)ап(а)\'
Summing up this expression over all the partitions a G П, counts
actually the number of arrangements of the те elements, and we
conclude that

1998
89
те!
)αι(α)! · 2α2(Ω)α2(α)! · · · ηα^α)αη(α)\
= η\
«en
Dividing by те! gives the required result.
Solution 2
This solution uses generating functions.
We expand the infinite product
oo
n=l
into a power series in x. This yields
n=l \n=l
oo r
For 0 < χ < 1, the series V^— is bounded by the geometric
n=l
series /~^n, and it is therefore convergent. The series is obviously
n=l
also convergent for —1 < χ < 0. The explicit sum of this series
is obtained by interchanging the order of summation and term by
term integration of У^жп:
n=l
Σ£ = Σ/^1*=/Σ'η-1<«=/ϊ#ϊ = -1»(ΐ-*)·
n=l n=lq q n=l £
From (2) we have
/ω = ΠeV = J™,ΠeV = Ji«Lexp Σ
iV—>oo -1--1- iV—>oo \ -'-—' те
n=l n=l \n=l
From the continuity of the function e* we have

90
4. Solutions
f(x) = lim exp V
N—>oo * ■ώ—'
/ oo
= exp Ι Σ
N r
Xr
N—уоо \ *-^ П
n=l
oo r
X7
П
.71=1
= e
1
ln(l-a;)
1-х
oo
= Σ>η· (3)
n=0
On the other hand, by expanding every term in the product (1) in
a power series we obtain
xTl v^ 1 /жпХ
k\ \ η
k=0
and therefore
/(Ж) 7 Ση αι! Σ) α2! 2«* " ' Σ αηι ηα„ "" · (4)
αι=0 α2=0 αη=0
By comparing the coefficients of xn m (4) with the corresponding
coefficients in (3) we end up with
У —
= 1 where
— ±αιαι! ·2α2α2!···ηα-αη! _ /5ч
Π = {αϊ, α2,..., αη | αϊ + 2α2 Η Υ ηαη = η}
To justify (5), it remains to show that the series obtained from the
expansion (4) is convergent in the domain \x\ < 1. To show that,
we denote
N w ται °° ι r2a2 °° 1 ~Na
/sW = rie^E£_E_L|_...E
αϊ! ^ ^2! 2a2 ^ aN\ Na"
n=l ai=0 u2=0 a^f=0

1998
91
In this product the sum of the coefficients up to те = N is
^ ^ 1αία1\·2α2α2\···ηα^αη\'
The coefficients c'n of xn in the expansion of fw (x) are all positive
and satisfy
dn = Cn, те = 0, l,...,iV,
c'n <cn, n> N.
Also, /ν(χ) can be written as
/ oo
/ν(χ) = 9N(x)f(x), 9n(x) = exp ( - ^
\ m=N+l
(6)
m
X
m
Consequently, for η < N, the coefficients c'n of xn are obtained by
applying Leibnitz's differentiation rule:
Kn),
c'n = ^(0)
= ^[^/](n)(0)
1
те!
^/(η)(θ) + Σ^(ο)/Μ)(ο)
fc=l
All the derivatives of gN(x) up to order N vanish at χ = 0.
Therefore for те < Ν,
^ = ^)^ = >)(°) = ^(τ^
(η)
= 1.
ζ=0
From (6), it follows that we can change the order of summation in
the series expansion of /л/-(ж), and therefore (5) is justified.

92
4. Solutions
1999
1. Let I > 2 be the degree of f(x) and ki — the degree of gi{x).
Statement: ki = ll for г = 1,2,...
Proof: The proof is by induction. For г = 1 the statement is
obvious.
Assume that ki = ll and write
f(x) = aix1 + a2xl~l -\ l· αι+ι
and gi(x) = hxki + b2xki~l Η hbfci+i.
Now
gi+i(x) = cuihx^+b2xki~1+ --- + bki+1)1
+a2(b1xki + b2xki~l + ··■ + bfci+i)i_1
+ ··· + αί+ι. (1)
Clear the leading term is of power kil, i.e. lt+1 as required.
In the polynomial gi{x) denote by an the coefficient of the highest
power of χ and by a2i the coefficient of the next lower power. Then
by Viete formula the sum of the roots of gi(x) is —a2i/an, therefore
—а2г/ац
Given an, a2i, we show that the next two equalities hold:
fli,i+r= $α\ί·, «2,i+i = slau a2i,
where s is the coefficient of xl in f(x).
Proof: If
f(x) = sxl + a2xl~l -\ h αι+ι
then by (1) with a\s = s it follows that the coefficient of the highest
power is obtained only from the first term, namely
«1,г+1 = sa\i-
Since I > 2, the highest power of all the terms in the sum (1) is
/*(/ - 1) = ki(l -1)<к{1-1 = li+1 - 1,
therefore the coefficient of xl _1 in the polynomial gi+\{x) is the
coefficient of xl ~l in the first term of the sum (1), namely
«2,i+l = s^a\i a2i->

1999
93
which proves the statement.
Now, given τι = }l—-, it follows that
r
-a2,i+i/ai,i+i _ slau a2i/'salu _ -a2i/au
therefore
Г ■ ι ι = ■—' ■ ■—■ = — — — = Г ■
^99 = ?"98 = · · · = П9 = 99.
2. The problem deals with angles between lines, and the discussed
properties are invariant under translations of the lines. Therefore,
with no loss of generality, we assume hereafter that all the lines
pass through the origin.
Consider a pair of lines l\, l2 forming between them angles a and
180° — a. Assume that r < η — 1 of the given 2n — 1 lines are
in the domain of the angle a and 2n — r — 1 of them are in the
domain of the angle 180° — a. One of the angles a and 180° — a
is obtuse. Therefore the number of triangles whose obtuse angle
is between h and l2 is either r or 2n — r — 1, and this number is
at least r. Counting all the possibilities of pairs of lines such that
there are r other line "between" them, we see that there are 2n + 1
possibilities. Therefore the number of obtuse angled triangles is at
least
-nV- n(n-l)(2n+l)
r—\
Hence the number of acute angled triangles is at most
'2n+l\ n(n-l)(2n+l) _ n(n+l)(2n+l)
3 у 2 6
Finally, to show that this bound is strict, it is to be proved that
n(n+l)(2n+l)
6
acute angled triangles can be obtained.
It is easy to see that if the angles between them are all equal (and
equal to J^ry), then iV triangles are actually obtained.
3. Put χ = у = 0 and obtain
/(0) = ДО)2 - /(0) + 1 => (/(0) - l)2 = 0 => /(0) = 1.

94
4. Solutions
Now put у = —χ and obtain,
l = f(x)f(-x) - f(-x2) + l =* f(x)f(-x) = f(-x2),
and in the last equation, putting χ = 1, we obtain
/(-1)(/(1)-1) = 0,
i.e. /(1) = 1 or /(-1) = 0.
Now, if /(1) = 1, putting in the last equation у = 1 we obtain
fix + 1) = /(l)/(s) - fix) + 1 = fix) ~ fix) + 1,
i.e. f(x) = 1 for every x. Such a function satisfies in fact the
requirement of the problem, since 1 = 1 — 1 + 1.
Assume now /(—1) = 0. Putting у = — 1 in the first equation, we
obtain
f(x-l) = -f{-x) + l,
i.e.
f(x-l) + f(-x) = -l Vs, (1)
In addition, putting у = 1, we obtain
f(x + l) = (f(l)-l)f(x) + l. (2)
Put χ = —1 in (1) and χ = — 2 in (2) and obtain
/(1) + /(-2) = 1, 0 = /(-2)(/(l) - 1) + 1.
The second equation yields /(—2)/(l) + l — /(—2) =0 and since
1 - /(-2) = /(1), it follows that /(1)(2 - /(1)) = 0, i.e. /(1) = 0
or /(1) = 2.
Assume /(1) = 0. Then by (1), f(x + l) = —f(x) + l, and replacing
χ + 1 by x, we obtain f(x + 2) = —f(x + 1) + 1 = f(x), i.e.
f(x + 2) = f(x) for every x. But putting у = 2 in the first equation
it follows that
/(s + 2) = /(2)/(a0-/(2a0 + l,
and by /(2) = /(0) = 1 it follows
f(x) = fix) - fi2x) + 1 =* fi2x) = 1.
Hence fix) = 1 for every x, contrary to /(1) = 0, and therefore
/(1) = 2. In such a case (1) becomes fix + 1) = fix) + 1 and by
induction we find that f(n) = η + 1 and

1999
95
f(x + n) = f(x)+n (3)
for each integer η and any x.
Now we prove that
\n / η
for any integers πι, η and this will imply that f(x) = x+1 for every
rational x.
τη
Putting χ = —, τ/ = η in the first equation yields
η
/(=+„)=/(η)/(=)-/(m) + l.
By(3)
V η / V η
and since f(n) = η + 1,
ra\
-/© - ^(π) + '(ϊ)-ί1+") + 1
=Φ· η/ Ι — I = n + m
„ /ra\ n + m m
=* f { — ) = —— = 1 + -
\n J
η η
Hence f(x)=x + l. It remains to show that this function satisfies
the conditions of the problem. In fact,
f(x + y)=x + y + l,
leading to
f(x + y) = f(x)f(y)-f(xy) + l
= (x + l)(y+l)-(xy + l) + l
= x + y + 1,
therefore there are two solutions, f(x) = 1 and f(x) = χ + 1.
4. We prove that an+\ = 2can — an-\ for every η > 2.
Proof: By definition,
an = can-i + у (с2 - 1)(а2г_1 - 1).

96
4. Solutions
Transferring from one side to another and squaring we obtain
(an - can_i)2 = a2 - 2canan_i + c^n-i
2 2 2 2 , ι
= с an_! - с - an_! + 1
which by cancelling by (?a^_x and adding c2a^ at both sides yields
(?o?n - a2 - c2 + 1 = c2a2 - 2canan_i + a2_l5
i.e.
(c2 - l)(a2 - 1) = (can - a^)2.
Now can — an_i > 0 since с > 0 and by definition an > ап-ъ
therefore
V^c2 - l)(al - 1) = can - αη-λ
and adding can to each side yields
an+i = can + ^/(c2 - 1)(α£ - 1) = 2can - a„_i.
We shall prove by induction that an Ε Ν for each n.
First
αϊ = с G iV, a2 = с2 + л/(с2 - l)(c2 - 1) = 2c2 - 1 G N.
Now if an G iV and αη+ι G iV, then also
an+2 = 2can+i - an £ N.
5. Take a point Ρ = (t, t2 — t, 0) for some t. It is easy to see that
f(t, t2 - t, 0) = (i4 + 2i2 - 2ί2)/ί2 = 2 + t2 - It.
We restrict our discussion to t such that 0 < t < 2 so that
t2 -2t< 0.
It is necessary to solve the inequality t2 — 2t+0.001 > 0, and smaller
values of t are in the interval
0 < t < 1 - 3/lOOVlllO.

1999
97
t = 1/10000 = 0.0001 is of course in this interval, since
3333
100
> Vino.
Now for t = 1/10000 we obtain clearly
xl + Vl + 4 = (ί4 + 2ί2 - 2ί3) <
2000
Note that by the choice Ρ = (t, t2 — t, 0) for some t and computation
of f(P) at such a point we conclude existence of an appropriate
point, but our problem was to find such a point. Also note that 2
is not a limit of f(x,y,z) at (0,0,0) since / has no limit at this
point.
We show first that the number of students cannot exceed 9.
Suppose negatively that there are more than nine students in the set.
Consider their answers to question 1. Note that there are only
three possibilities. Hence, by the Pigeon Hole principle, we obtain
that there is a set of at least seven students whose answers are from
a subset of two choices only.
We choose now such a 7-tuple of students and consider their
answers to question 2. There are among them a subset of (at least) five
students whose answers are from a subset of two choices only. In
this 5-tuple there is a subset of (at least) four students which chose
from two choices only for question 3. Therefore it follows that for
satisfying the conditions of the problem these four students have
to give different answers to question 4. This is impossible, since
there are only three choices.
Consequently the number of students does not exceed 9. To finish
the solution, we show that there exists a set of nine students with
three choices a, b, с for question 1, 2, 3, 4 such that the condition
of the problem is satisfied. One possibility is:
Student
Question 1
Question 2
Question 3
Question 4
1
a
a
a
a
2
a
b
b
с
3
a
с
с
b
4
b
a
b
b
5
b
b
с
a
6
b
с
a
с
7
с
a
с
с
8
с
b
а
b
9
с
с
b
а

98
4. Solutions
2000
1. Denote the number of summands in s by N(s), and the maximal
summand in s by M{s). Then clearly
f(s) = N(s) + M(s) > 2^N(s) χ M(s) > 2(у/ЖЮ) > 89. (1)
Explanation: The first inequality is the G-E inequality. To obtain
the second inequality, note that by replacing each summand in a
partition of 2000 with M{s) we obtain a larger sum (unless all the
elements are equal). The new sum is N(s) χ M{s).
Since f{s) = N(s) + M{s) is an integer, it follows by (1) that
N(s) + M{s) > 90.
The minimal value 90 is attained for the partition
s0 = 45 + 45 +...+ 45+20
44 times
or for the partition
s0 = 40 + 40 + ... + 40.
4 ν '
50 times
Clearly, N(s0) = 45, M(s0) = 45 and therefore f(s0) = 90.
Consequently, the required answer is 90.
2. First solution:
The statements false. To prove this, take к = 4 and assume by
contradiction that there exists a positive integer η for which (™) is
divisible by 4 for every 1 < г < η — l.'Then,
n-l у \
Σ I )=*»-2
г=1 ч 7
is divisible by 4. This is false for every η > 1, and thus we arrive
at a contradiction.
Second solution:
We prove that the set of positive integers к for which the claim
holds is exactly the set of primes. Clearly, if к is a prime, then we
can take η = к. For every 1 < г < к — 1, the numerator of
fc!
i\(k-i)\

2000
99
is divisible by k, while its denominator is not divisible by k. Since
к is prime, it follows that (J is divisible by k.
Suppose now that к is not a prime. Then consider two cases:
First case: к = pr, where ρ is a prime and r > 1.
We find a value of i for which the statement does not hold.
Suppose that there is a positive integer η such that for all 1 < i <
n—1, (?) is divisible by pr. Obviously, η is divisible by pr, and we
write η = ραβ for some β with gcd(P,p) = 1.
Take i=pa-\ Then,
n\ " TT PPa ~ 3
When j = 0 we have
г j ■*- ■*- pa l — j
pa~l-3
When j is coprime with p, both the above numerator and the
denominator are coprime with p.
In all other cases, we write j = δρΊ for some δ coprime with ρ and
7 < a - 2. Thus,
βρα - j βρα - δρΐ ρΐ(βρα-"< - δ)
pa-l _ j pa-1 _ <5p7 p-y(pa--y-l _ β) '
Now, since a —7 —1 > l,we have βρ°ί~Ί — δ andpa_7_1 — δ coprime
with p. In this case, the power of ρ in the above numerator and
the denominator is 7, and the power of ρ in the above product of
fractions, which is an integer, is 1. This contradicts the assumption
that pr I n.
Second case: к is divisible by at least two distinct primes p, q.
Assume by contradiction that there is a positive integer η as
required. Then η is divisible by pq and we can write η = ραβ where
gcd(p, β) = 1 and β > 1 (since q divides β). Take г = pa. Then,
When j
= 0,
ЛЛ _PW βρα - j
W Д Pa~3
βρ«-3_β
pa

100
4. Solutions
is со-prime with p. In all other cases, both the numerator and the
denominator of
βρα~3
pa -j
are either co-prime with ρ or are divisible by the same power of p:
and therefore the product of those fractions is not divisible by p.
But ρ divides fc, and hence (™) is not divisible by k: contrary to
our assumption.
Finally, the only positive integers к for which the claim holds are
the primes.
3. First solution:
Let ABC be the triangle, I be its incentre, О be its circumcentre.
The triangle itself is not equilateral to make the line IO well
defined. Let J be the external centre similarity of the two circles and
enlarge the incircle into the circumcircle from J.
Under this mapping I —> O, A\ —> A2, B\ —> B2 and C\ —> C2.
Since OA2 is parallel to IA\, Α2 is the midpoint of the arc ВС and
similarly B2 and C2 are the midpoints of the corresponding arcs
С A and AB. Hence AA2, BB2 and CC2 are bisecting the angles
А, В and С and thus these lines meet at I.
Now AA2 and C2B2 are perpendicular — this follows from the fact
that the sum of the arcs AB2 and A2C2 is the semiperimeter of
the circumcircle — so AA2 is the altitude of the triangle A2B2C2.
Similarly, BB2,and CC2 are also altitudes so I is the orthocentre
of the triangle A2B2C2. Hence I is the image of the orthocentre
Μ of triangle A1B1C1 under the above enlargement. Thus JI is
passing through Μ and О and we are done.
Second solution:
Denote by J, О the incentre and circumcentre of triangle ABC.
Inverse the figure with respect to the incircle.
Under this inversion, the midpoints of A\Bi: Bid: C\A\ are
mapped to C, A, B: and thus the nine-points circle of triangle
A1B1C1 is mapped to the circumcircle of triangle ABC. Denote
the centre of the nine-points circle of the triangle A1B1C1 by T.
Then J, Ο, Τ lie on a straight line (although О is not necessarily
the image of Τ under the inversion). But the line passing through
J, Τ is the Euler line of the triangle A\BiCi: and therefore it passes
through its orthocentre M. Hence J, Μ, Ο are collinear.

2000
101
4. Look at the function F: Α χ Β -»■ {2, 3,..., 4000} defined by
F(a,b) = a + b.
We deal with two cases:
1. F is onto. Then both A and В contain 1 and 2000. Therefore,
1999 = 2000 - 1 belongs to (A-A)U(B-B).
2. F is not onto. Since |A| χ |jE?| > 3999, it follows by the pigeonhole
principle that F cannot be one-to-one (by definition F may have at
most 3999 possible values and F does not assume all of them). So,
we must have αϊ, αϊ in A and 61,62 in В such that αϊ +6ι = 0,2 + 62.
From this we get αϊ — 02 = 62 — 61, and since αϊ — α2 G A — A and
62 — 61 G В — В, it follows that A — AnB — В is nonempty, which
completes the proof.
5. It is easy to verify that the product of two numbers of the form
m2 + dn2 can also be written as follows:
(x2 + dy2)(u2 + dv2) = (xu ± dyv)2 + d{xv =F yu)2, (1)
i.e. also in the form m2 + dn2.
Now let q = (a2 + d62) and ρ = χ2 + dy2 be the corresponding
representations of q and p. Write q = rp. We are going to show
that there exist integers u, ν such that α and 6 can be written either
as
or
a = xu + dyv
b = xv — yu
a = xu — dyv
b = xv + yu
(2)
(3)
Elimination of ν from the system (2) yields
ay + bx
and from the system (3)
ν =
ν =
x2 + dy2
ay — bx
x2 + dy2'
Thus ν is an integer if and only if either x2 + dy2\ay + bx or x2 +
dy2\ay — bx.

102
4. Solutions
Since χ2 + dy2 is prime, it is enough to show that
Let
Then
x2 + dy2\[ay + bx)(ay — bx).
Τ = (ay + bx)(ay — bx).
(4)
T=(a2 + db2)y2 - (x2 + dy2)b2.
Since x2+dy2\a2+db2, the product Τ is indeed divisible by x2+dy2.
Thus in one of the systems (2), (3) ν is a whole number. Each of
these systems implies that и is rational. On the other hand
2 , 2 a2 + db2
и +dv = -= — = r
xz + dyy
is an integer, and if ν is an integer, it follows that и is also an
integer and we have finished.
6. First solution:
Define
bj =Σα
i=l
Denote the left hand side of the required inequality by L and its
right hand side by R. Then
к / I
j=l j=l \г=1 / г=1 V j=l
(q-p)/p p
з αϋ
Using Holder's inequality it follows that
к
г=1
к
= Σ
ι
(У^ (ь(.9-р)/р W(9-p) ) (я~р)/я (V^ (αρ. )«/Ρ)Ρ/ί
г=1
г
г
j=i
(Σ&"/ρ)(ς"ρ)/ς(Σ4)ρΑ
J = l
j=i
E(E4)p/i
*=1 J=l
= Lq-pRp.

2000
103
The inequality L < R follows by dividing the last inequality by
Lq~p and taking the p-th root.
Holder's inequality states:
Let p: q positive numbers such that ρ > 1 and
ρ q
Then, for every two sequences αϊ, α2:..., an and b\, &2, · · ·, bn of
nonnegative real numbers,
η /η \1/P/n \ 1/4
k=l \k=l J \k=\ J
Second solution:
Denote r = -,Ъц = α^·. Then r > 1, and the given inequality is
equivalent to the following inequality:
' /л \ΤΫ л/'
Σ Σ4 ^Σ Σ4,
Kj=l \г=1 / у г=1 \j=l
We shall prove this inequality by induction on k. For к = 1, we
have equality. For fc = 2, the inequality becomes Minkowsky's
inequality.
Suppose that fc > 3 the inequality holds for к — 1. Then by the
induction assumption for к — 1 we have
I I
к ( I \ r ( I /k-1 \T\ r ( I
ΣΣ% ΗΣΣ4 + Σ4*
Using the induction assumption for к = 2 (or Minkowsky's
inequality) with
k-\
hj = 2_^ by, b2j = bkj,
г=1
we have
l /k-\ \r\ r I I \ r I I / к
ij
Σ Σ4 + Σ^ >ΣΣ'
j=l \i=l J J \j = \ J \j = \ \i=\

104
4. Solutions
And we are done.
Minkowsky's inequality states:
For any a,i: hi > 0, г = 1,2,..., η and ρ > 1,
A A A
/ η \ ρ /та \ ρ /та \ ρ
(for ρ < 1 reverse the direction of the inequality). Equality holds
if and only if bk = Xctk for some A and for all к.

2001
105
2001
1. First Solution:
We shall use the identity
n{m2 + 2m - n)2 + (m2 - 2mn + ri)2 = (n + l)(m2 + ri)2.
Which can be easily proven. Setting η = 2000, га = 90000 will give
χ = m2 + 2m — η > m2 + n = z,
ζ = m2 +n
= (45 · 2000)2 + 2000
> 20002·2025
> 1999 · 2000 · 2001,
and
у = m2 — 2mn + η
= (45 · 2000)2 - 2 · 45 · 2000 + 2000
< 20003 - 2000
= 1999-2000-2001.
And thus the triple ж, ?/, ζ satisfies the condition of the problem.
One can ask how to come up with such an identity. One way is to
note that the equation
nx2 +y2 = {n + l)2
is equivalent to
n(x -y)(x + y) = (n+ l)(z - y)(z + y).
We can set
χ = у + 2n{m + 1), ζ = у + 2т(п + 1)
and the equation becomes
Anm(n + l){y + mn + m) = 4n(m + l)(n + l)(y + mn + n).
Extracting у we get
?/ = m2 — 2mn + n,

106
4. Solutions
and thus
χ = m2 + 2ra — η, ζ = m2 + n.
Second Solution:
Here we offer a more constructive method for a solution. We shall
look for a solution with у = 1. Consider the Pell equation
X2 - 2000 · 2001Z2 = -2000
It has a basic solution (2000,1). The unit Pell equation
X2 - 2000 · 2001Z2 = 1
has a solution (4001,2). Therefore, by Pell's theorem, we have an
infinite family of solutions, namely
Xn + Zn\/2000 · 2001
= (2000 + V2000 · 2001)(4001 + 2V2000 · 2001)n.
Now it is simply a matter of computation of the first three solutions.
We arrive at the following results:
(Χι,Ζι) = (2000-8003,8001),
(X2,Z2) = (2000[8003· 4001+ 4002-8001],
4000-8003 + 4001-8001),
(X3, Z3) = (2000[8003 · 40012 + 2 · 4001 · 4002 · 8001
+4000 · 4002 · 8003], 4001 · 4000 · 8003
+8001 · 40012 +4000 · 4001 · 8003
It turns out that
+4000-4002-8001).
{x^z) = i2ok^Z3)
satisfies the conditions of the problem. It is clear that χ > ζ since
2000ж2 - 2001-г2 = -1.
Further,
у = 1 < 1999-2000-2001.
Finally,
ζ > 4001 · 4000 · 8003 > 1999 · 2000 · 2001.
And we are finished.

2001
107
2. First Solution:
Let Ρ be a point on the locus.
If Ρ G I, then Ρ lies either inside ВС, and then
LAPB = LCPD = 180°
or outside AD, and then
LAPB = LCPD = 0°.
Assume from now on that Ρ does not lie on I. Let с be the circle
such that the inversion with respect to it maps А, В to D, С. It is
well known that there exists a single circle with this property. The
centre of с lies on the line I. This centre could be at the point of
infinity and in this case с is a line. The latter case occurs if and
only if AB = CD.
Denote by ci,C2 the circumcircles of APAB, APCD respectively.
Let P' be the invariant point of Ρ under the inversion with respect
to с Then AP'CD ~ APBA and therefore
LCPD = LAPB = LCP'D
so P' lies on c^. Hence the inversion with respect to с maps c\ to
C2, and hence they intersect on c. We conclude that Ρ lies on c.
Conversely, suppose that Ρ lies on С. Then APAB ~ APDC and
therefore LAPB = LCPD, so Ρ lies on the locus. We conclude
that the locus is the circle c, the segment ВС and the outside of
the segment AD.
Second Solution:
The case where Ρ lies on I is treated the same as in the last solution,
and we shall ignore this case from now on.
Let Ρ Μ be the bisector of LB PC, with Μ on I. Then Ρ Μ is the
bisector of LAPD as well. Denote the area of the triangle AXYZ
by Saxyz- Then
AB Saabp
CD Sacdp
The function
PA-PB- sin LAPB
PC-PD- sin LCPD
f(M\ _ MA-MB
MA-MB
MC-MD
is continuous and monotonic on the segment ВС.

108
4. Solutions
Since f(B) = 0, f(C) = oo then there exists a unique point Μ such
that
/(M) = i|,
so the bisector of LBPC meets ВС at a unique point M. Then
Ρ lies on the circle of Apollonius of B: С with respect to this M,
which could also be a line if AB = CD (and then Μ is the midpoint
oiBC).
If Ρ lies on the circle of Apollonius of the point Μ satisfying
/<"> = £§■
then by the formulas for the areas of the triangles AABP, AC DP
we have LAP В = LCPD.
Third Solution:
We shall use analytic geometry. Fix a coordinate system where I
is the ж-axis, the point (0,0) being the point О lying inside ВС
for which О A · OB = ОС · OD and fix the unit length to be this
product. Let
A=(a,0), B = (i,0), C = (c,0), D = (-c,0).
Then a < J <0 <c< J, which implies a<—1<0<с<1.
Let Ρ be a point on the locus, and let та,ть, тс, rrid be the slopes
of PA,PB,PC,PD respectively. Then Ρ is on the locus if and
only if
ma -mb mc — md
1 + тать 1.+ mcmd
Let Ρ = (x,y). The latter equation becomes
У У У
1 χ — с 1
- χ
а _ с
У2 У2
1 + ^ τ- 1 +
1 1
(х - а)(х ) (х — с)(х )
Now we want to divide by у both sides of the equation. This can
only be done in case у ^ 0, i.e. Ρ does not lie on I. The case where
Ρ lies on I is treated as in the first solution. Dividing by у and
rearranging both sides, we get
(x-a)(x- \) + У2 {x-c)(x-\)+y2'

2001
109
Multiplying by the common denominator and rearranging, we have
(a---c+-)(x2+y2 + l)-2(---)x = 0.
\ a cj \c a/
Suppose ac = — 1, so ^ — a = \ — c, or AB = CD, then the equation
becomes
(a2 - c2)x = 0
a2 ^ c2 for otherwise a2 = c2 = 1 so the locus is the line χ = 0.
Now suppose ac^f — 1. Then we can divide by (a — ^ — с + ^):
^ a + cV m2 >2-D(i-°2)
V ac+l,) +?/ " (oc+1)2 '
This is an equation of a circle. The radius is clearly positive since
α < -1,0 < с < 1.
It remains to check that if Ρ satisfies the equation we have found,
then it lies on the locus. But this is simply a matter of reversing
the steps, and then we are finished.
3. We begin with a few properties of /:
f(x) = f(y) implies
/(*) + χ = f(f(x)) = f(f(y)) = f(y) + у
and therefore χ = у. Hence / is 1 — 1. We deduce that / is
monotonic.
Let a = /(0). Then f(a) = a and thus
/(α) = /(/(α)) = /(α) + α
so a = 0.
By induction, one can prove that
f^n\x)=Fn-1x + Fnf(x)
where Fn is the Fibonacci sequence defined by Fo = 0, F\ = 1, and
Fn+2 = Fn+i + Fn.
Consider now two cases:
Case 1: f is decreasing. Since /(0) = 0, χ < 0 implies f(x) > 0
and hence
0>f(f(x)) = f(x)+x.

110
4. Solutions
ж > 0 implies /(ж) < 0 and
0<f(f(x)) = f(x)+x.
Both cases lead to \f(x)\ < |ж|, so
1/(та)И1 <L
|ж|
Then for ж φ 0,
/(ж) ^I_J_ /W n
+ ρ — ρ ' ^n—>oo ".
And therefore
/(ж) = lim —χ = —-—χ.
П—УОО Fn 2
Case 2: f is increasing. Then the sign of /(ж) is the same as the
sign χ (since /(0) = 0) and therefore
\f(f(x))\ = \f(x)\ + \x\>\x\.
Hence the / is onto, and since we have already shown that / is
1 — 1 then / is bijective. Let g = f~l. Then g is continuous and
satisfies
g(g(x)) + g(x) = χ·
By induction,
(-l)n+1g^(x) = Fng(x) - Fn-lX.
The sign of g(x) is also the same as the sign of ж, and hence
Μ = \g(x)\ + \g(g(x))\
which leads to
\g(x)\ < \x\.
Therefore
\p(n)(x)\
\9{n\x)\ г
\x\
and thus for ж φ 0,
g(x)__Fn-1= )n+1 _ J_ _ g(n\x)
Χ -ί1η "η. Χ

2001
111
Therefore
/ л т Fn-\ 2
g(x) = lim —-—χ = —
and
l + y/5
/0е) = —2—Ж'
4. First Solution:
Let α be a root of P. Then —1 = a3 — 3a. Raised by the fifth
power, this yields
-1 = α5(α2-3)5
= a5(a10 - 35 - 15α2(α2 - 3)(α4 - 3α2 + 9)).
Since α3 — 3α = — 1
-1 = α5(α10-35 + 15(α5-3(α3-3α))
= α5(α10-35 + 15(α5 + 3)).
Let b = α5. Then
Ь3 + 15Ь2-1986+1 = 0
So Q(rr) = χ3 + 15ж2 - 198ж + 1.
Second Solution:
Let α, b and с the roots of P. By the Vieta formulas,
a + b + c = 0,
ab + bc + ca = —3,
and abc = —1.
We want to find the coefficients of Q, given by
Q(x) = x3 - (a5 + b5 + с5)ж2 + (a565 + b5c5 + с5а5)ж - a5b5c5.
The last coefficient obviously equals —1. For the other two, we
shall use Newton's formulas for sn = an + bn + cn, namely
So = 3, Si = 0 and s2 = 6
and for η > 3,
5n = 3sn_2 — 5n-3·
Calculating, we have
53 = —3, 54 = 18 and 55 = —15.

112
4. Solutions
Then the coefficient of ж2 is 15.
The last term is a bit harder. We can use the identity
a5b5 + b5c5 + c5a5 = -{s\ - s10).
And now we are left with the task of finding Sw. One can verify
that
s6 = 57, s7 = -63, s8 = 186, ею = 621.
And therefore
a5b5 + b5c5 + c5a5 = ^(s25 - s10) = -198.
So
Q(x) =x3 + 15ж2 - 198ж + 1.
5. Let α, b and с denote the lengths of the sides of AABC. The given
equality of the areas of AABC and AAB2C2 implies
bc = AB2 -AC2.
Then either
AB2 > 6, AC2 < с or AB2 < 6, AC2 > с
Without loss of generality, we shall assume that the former holds.
It follows that b > a > c.
Let D, Ε and F be the intersection points of the line ВС with
AI, Bil and C\l respectively. Then F lies in the interior of the
segment SC, while Ε lies on its exterior.
Α Βλ С В2

2001
113
A well known result in triangles states that
BD = aC
CD =
b + c
ab
b + c
Λ ΑΙ b + c
and — = .
ID a
By Menelaus' theorem applied on the triangle AADB and the line
CiIF,
BF CiB IA b + c
Therefore
and we get
and
FD CiA ID
BD _ b + c-a
F~D ~ a
^^ a c
FD =
FC = CD-FD =
(b + c)(b + c-a)
a(b— a)
b + с— а
Applying the theorem of Menelaus on the triangle AABC with the
line B2FC\ yields
B2C FC b-a
B2A FB
Simplifying, we get
π „ be
B2A =
a + c—b
In the same manner we see that
OA = bC
a + b — с
We recall the equality AB2 · AC2 = be, which becomes now
h2r2
7 CO 27227
be = г^т — rr => a =b +c -be.
(a + (b - c))(a - (b - c))
By the cosine law, this implies /.ВАС = 60°.

114
4. Solutions
6. We shall generalize the result of the problem in the following
manner:
Let fcbea positive integer, 5 = 12k, m = 3k + 2. If
«i < «2 < · · · < flm < 6k
are positive integers which sum up to 5, then there exists a subset
which sums to 5/2 = 6k.
Recall that a sequence is called universal if every positive integer
between 1 and the sum of the sequence can be expressed as a sum
of some terms from the sequence. One can show by induction that
if the sequence χ ι < x^ < ... < xn satisfies
i-l
Xj < 1 + У^ Xj
3=1
then it is universal. In particular, if Xi < i then it is universal.
We begin the proof by showing that in general, if S < Am—6 (which
holds in our case, since S = Am — 8) then for every 3 < г < m — 2,
αϊ < i. Indeed, for every г,
г—1 m
S = 2_] aj + /~2 aj ^ (*— i) + i771 +1— 0аг·
Hence
5+1 — г 5 — 771
ai < = Ц .
m+1 — i m + 1 — i
We shall show that
5 — 771
: <г,
771+ 1 - г
and the claim will follow. The last inequality is equivalent to
г2-(т+1)г+(5-т) < 0.
Since for г = 3, i = m — 2 the expression on the left is negative
(recall that 5 < Am — 6) then for г between those values, щ < i.
If the sequence щ is universal from the beginning, i.e щ < г for
every 1 < г < m — 2. If
m-2
Σ «i > 5/2
г=1

2001
115
then since the sequence is universal, there exists a subset of the
sequence which sums to 5/2. Otherwise, am_i + am > 5/2 so
5/4 < am < 5/2, and since clearly
m-2
Σ аг > S/4: = m - 2
then 5/2 can be expressed as the sum of am and a subset of
αϊ, a2 ■ ■ ■ am-2.
Therefore we shall assume that the first two terms of the sequence
do not join into a universal sequence. It follows that αϊ + α2 > 4,
and аз > 2. Consider two cases:
Case 1: аз = 2. Then αϊ = α2 = аз = 2. Let 2d be the number of
odd terms of the sequence (it is even, since the sum is even). Then
2d < 771—3. We shall compose a new sequence &i < ^2 < · · · < bm-d
whose terms are half the even terms of a^ or the average of two odd
terms. Then b\ = &2 = Ьз = 1,
m—d
and since am+am_i < 5/2 (for otherwise there should have been an
element a^ smaller than 2), bm-d < 5/4. Since 5/2 < 4(ra — d) — 6
we can apply the first claim and get that the sequence fy is universal
from the beginning and hence 5/4 can be expressed as a sum of
terms from this sequence. Therefore 5/2 can be expressed as a sum
of terms from the sequence a^.
Case 2: аз = 3. We can refine the inequality for a^ from the
beginning of the proof:
г—1 m
5 = ai + a2 + ^ a^ + ^ a-,· > 4 + 3(г - 3) + (m + 1 - г)а{.
j=3 j=i
Therefore
5 + 5 — Зг т — 6
a; < — r = 3 + — ;.
771 + 1 — г 771+1 — г
For г < 6, the last expression is less than 4 and therefore аз = 04 =
«5 = «6 = 3. For i < 2k + 4, it follows that a^ < 6 and hence the
elements аз, a^ ... a2k+A are equal to either 3, 4 or 5. Let t be the
number of elements from the last sequence that are equal to 3, and
let s = 2k +.2 — t be the number of elements that are equal to 4
or 5. Then t > 4 and if t > 2k we are through. We can assume
therefore that t < 2k or s > 3.

116
4. Solutions
For the rest of the proof, we need only those 2k + 2 elements. Let
3/i be the largest multiple of 3 that can be expressed as the sum of
the s 4s and 5s. By induction on s, starting from s = 3 it follows
that h > s — 1, and that either 9,12,or 15 is the least multiple of 3
that can be expressed in this way. If h < 2k: so 3h < 5/2 then we
can add multiples of 3 until we reach 5/2 (since
3h + 3t > 3(5 + t) - 3 = 5/2 + 3).
Otherwise, remove the multiples of 3 from the sum of the 4s and
5s until we decrease under 5/2. Since the least possible multiple of
3 we can remove is always at most 15, then at the end we reach at
least 5/2 — 12. Add the necessary number of 3s (recall that t > 4)
and we are done.

5. TEAM COMPETITION PROBLEMS
1990
1. Let α be a positive rational number. Show that there exists an open
interval / which contains a and for any rational β G /, β ^ α, the
denominator of β is greater than that of a (the fractions should be
considered in their simplest form).
2. For any rational a denote by Ia the maximal interval with the
above property.
19
Find L· if a = —.
90
3. Let a and b be real numbers for which 0<a<b<a + l. Prove
that there exists such a rational number a, for which a < a < b
and a, b Q Ia, i.e., for any rational β for which a < β < b and
β 7^ α, the denominator of β is greater than the denominator of a.
4. For any positive real pair (a; b) denote the above a by α(α; b). Find
the values of
/ 70 27\
aVm;68y'
a (ν/Ϊ99?];\/Ϊ99Ϊ).
Devise an algorithm as quick as possible to calculate the value of
a.

118
5. Team Competition Problems
1991
1. Let f(x) = x2 + ax + 6, where a, b are integers. Prove that if f(x)
is a square number for infinitely many integer values of χ then f(x)
is the square of some integer polynomial.
2. Show that there exists an integer polynomial f(x) = ax2 + bx + c,
which is not a perfect square and f(x) is a square number for
infinitely many integer values of x.
3. Show that if N > 0 is an arbitrary integer then there exists an
integer polynomial f(x) = x2 + ax + 6, which is not a perfect
square and f(x) is a square number for at least N integer values
of x.
4. If f(x) = x2 + ax + b is an integer polynomial which is not a perfect
square and / assumes a square value for JV consecutive integer
values of ж, then / is called an iV-square polynomial. Denote the
discriminant a2 — 46 of f(x) by D(f).
(a) Prove that if / is an iV-square polynomial (N > 2) then 64 |
D(f).
(b) The square values of an iV-square polynomial are alternately
even and odd.
5. (a) Construct a 3-square polynomial,
(b) Construct a 4-square polynomial.

1992
119
1992
Preface
Consider the following two sequences:
1. The Fibonacci sequence is defined as
F0 = 0, Fi = l, Fn = Fn-1+Fn-2 (те > 2).
2. The definition of the Lucas-numbers is:
L0 = 2, Li = 1, Ln = Ln_i+Ln_2 (те > 2).
It is well known, that for any те > 0,
Fn = jS- and Ln = an+0n,
V5
where
1 + V5 , a 1-V5
a=—-— and β=—-—.
You can use the results stated above, however, any other property of
these sequences which you want to use should be proved.
The problems
1. Prove that 1 + L2J = 0 (mod 2j+1) (j > 0)
2. Prove that ^
<*Fk + -
= F2n+i (n > 1).
fc=l L ^
3. A natural number is called r-Fibonacci, if it can be written as the
sum of r — not necessarily distinct — Fibonacci numbers (r > 1).
Prove that there are infinitely many numbers which are not r-
Fibonacci for any r (1 < r < 5).
4. Prove that
Fn · Fn-i · Fn · Ln · Ln-i ■ Ln+i (те > 2)
is not a perfect square.
5. Prove that
Ln+1 + (-l)n+1 (те>1)
can be written as the product of three (not necessarily distinct)
Fibonacci numbers.
6. The coordinates of the vertices of a rectangle are all Fibonacci
numbers. It is also given that there are no vertices of this rectangle
on the coordinate axes. Prove that the sides of this rectangle are
either parallel to the axes or they make a 45° angle with them.

120
5. Team Competition Problems
1993
1. Let к > 1 such that for every x:y G G
(ху)г = xlyl holds for г = к — 1, к and к + 1.
Prove that G is Abelian.
2. Let η > 1 such that the mapping ж —> xn, χ G G is an isomorphism
of G onto itself. Show that an~1 G G for every α G G.
3. Prove that every element of Sn can be expressed as the product of
two cycles.
4. Let Η < G, a,b e G. Prove that \aH П iib| is either zero or a
divisor of \H\.
5. Let |#| = 3 (Я < G). What can be said about \NG(H) : CG(#)|?
6. Let a:b £ G. Assume that
ab2 = 63a, ba2 = a3b.
Prove that a = b = 1.
7. Let |G'| = 2. Prove that |G : G'\ is even.
GLOSSARY of Notations
G: a finite group
G'\ the commutator subgroup of G
Η < G: Η is a subgroup of G
Ng(H): the normalizer of Η in G.
\G : H\: the index of the subgroup Η in G.
Cq (H): the centralizer of Η in G.
\X\: the cardinality of the subset X С G.
Sn: the symmetric group of degree n.
Z(G): the centre of G.

1994
121
1994
1. Let G(V, Ε) be an undirected graph, V is the set of vertices, Ε is
the set of edges. Let w : Ε —> R be a function assigning a real
number called its weight to each edge. The max-weight of a
nonempty set of edges is the maximum of the weights of the edges
contained in the set. Suppose that G is connected and denote \E\
by m. Find a spanning tree in 0(m) steps whose max-weight is
minimal (in one step two real numbers can be compared and the
. corresponding pointer administration can also be performed).
2. G(V: E) is a connected undirected graph, w : Ε —> R is a weighing
function and е(ж, у) is a given edge of G. Decide in 0(m) steps
(m = \E\) if there exists a minimal spanning tree — whose weight
is minimal — containing e.
Remark: Graphs are always given by the corresponding adjacency
list, i.e. for every vertex we are given the list of its neighbours.
3. Given a G(V, E) directed graph, one of its vertices s is fixed as the
"source", a function w : Ε —> R assigning a positive weight for
every edge and another function d : Ε —> R. Someone claims that
d(x) is the minimum of the weights of the directed paths s —> χ for
every vertex χ G V.
Decide in 0(n + m) steps if she is right (n = \V\, m = \E\; in one
step you can perform an arithmetic operation or the comparison of
two real numbers with the corresponding pointer administration).
4. An undirected graph is fc-regular if the degree of every edge is k.
(a) Show that the set of edges of any 3-regular graph G(V, E) can
be split into two subsets E\, £2 such that the degree of any
point is at most 2 in both of the graphs (V, E{) and (V, E2).
(b) Find such a division ΕΊ, £2 in O(ra) steps (m = \E\).
(c) A colouring of the edges of a graph is "good" if the colour
of the edges having a common vertex is different. Find an
algorithm in O(ra) steps which well-colours the edges of a 3-
regular graph with 4 colours.
O. X\, Ж2, · · · , Xn Ε {+1,-1} are unknown numbers. We have to find
the value of Y\xi, i.e. the parity of the number of —1 elements of
the above list.
We can ask "linear" questions. A linear question is an ordered
list αϊ, α2,..., αη, b of η + 1 real numbers. The answer for such a

122
5. Team Competition Problems
question is YES if
a\X\ + a2X2 Η l· an> b
and NO otherwise.
Prove that if we have a strategy yielding the value of Y\xi
using at most к linear questions (independently of the values of
Χι, X2, · · ·, xn), then к > log2 n.
Remark: Our strategy is deterministic: each question is a function
of the previous replies.

1995
123
1995
1. Consider the family of curves whose equation is χ4 — χ2 = a, where
a is an arbitrary positive number. Cut these curves with a line I,
which is parallel to the y-axis. Draw the tangent to each curve at
the point of intersection.
(a) Prove that these tangent lines are passing through a common
point Pi.
(b) Find the locus of the points Pi as the line I assumes every
position parallel to the y-axis.
2. Ρ is a point on the curve ж2/3 + у2/3 = 1 (ж, у > 0) and the tangent
to the curve at Ρ cuts the y-axis at the point Q. R is a point on this
tangent such that its first coordinate is not negative and QR = 6,
where b is a given positive number. What is the locus of the points
R as Ρ is moving along the curve?
3. Consider the curve С in the space with parametric equation
{M2,i3 \teR}.
Find the points P(a: 6, c) such that projecting С from Ρ to the
x, y-plane the resulting cubic curve has a singularity, with
(a) a cusp,
(b) distinct tangent directions (the curve cuts itself).

124
5. Team Competition Problems
1996
1. The graph G has 20 vertices, it is triangle-free and the degree of
each vertex is a multiple of 4. What is the maximum number of
edges in G?
2. G is a graph of η vertices (n > 1). Suppose that the degree of
each vertex is at least (n — l)/2. Prove that there exists a set S
of vertices such that the size of S is less than 1 + log2 η and each
vertex outside S is connected to at least one vertex in S by an edge.
3. For which values of к does every connected fc-regular bipartite
graph contain a Hamiltonian circuit?
4. s and t are distinct vertices of a directed graph. Assume that the
in-degree of each vertex is equal to its out-degree and, furthermore,
for each subset S of the vertices containing t but not s, the number
of edges entering S is at least k. Prove that there exist 2k edge-
disjoint paths connecting s and t such that half of them are from
s to t while the other half are from t to s.
5. Which one has the biggest number of edges among those graphs of
1000 vertices which do not contain a path of length 100?
6. Denote the maximum number of edges in those connected graphs
which have к vertices and do not contain a path of length 100 by
Prove that there exist constants C\, c^ such that
49fc - ci < f(k) < 49fc - c2.
Find as good estimates for the two constants c\ and c2 for
i) every value of k;
ii) к sufficiently large.

2000
125
2000
1. Let AABC be a given triangle. Pi is a point inside AABC.
(a) Prove that the lines obtained by reflecting P\A: P\B, P-^C
through the angle bisectors of /.A, LB, LC, respectively, meet
at a common point P2.
(b) Let A\, B\, C\ be the feet of the perpendiculars from Pi on
ВС, С A and AB, respectively. Let A2, Д2, C2 be the feet of
the perpendiculars from P2 on ВС, С A and AB, respectively.
Prove that these six points A\, B\, C\, A2, B2, C2 lie on a
circle.
(c) Prove that the circle of part (b) touches the nine point circle
(Feuerbach's circle) of AABC if and only if Pi, Pi and the
centre of the circumcircle of AABC are collinear.
2. An ant is walking inside the region bounded by the curve whose
equation is
x2 + y2 + xy = 6.
Its path is formed by straight segments parallel to the coordinate
axes. The ant starts at an arbitrary point on the curve and takes
off inside the region. When reaching the boundary, it turns by 90°
and continues its walk inside the region. When arriving at a point
on the boundary which it has already visited, or where it cannot
continue its walk according to the given rule, the ant stops. Prove
that, sooner or later, and regardless of the starting point, the ant
will stop.
3. (a) In the plane, we are given the circle С (without its centre)
and the point P. Is it possible to construct, with a ruler only,
the line through Ρ and the centre of the circle?
(b) In the plane, we are given two circles C\ and C2 (without their
centres). Construct, with a ruler only, the line through their
centres when:
i. the two circles intersect.
ii. the two circles touch each other, and their point of
contact, T, is marked.
iii. * We do not know how to solve this problem if the two
circles have no common point. It might even be the case
that this construction cannot be done at all with a ruler
only. Can you do better?
Note: Part (iii) does not belong to the official team
contest. However, any progress will be appreciated.

126
5. Team Competition Problems
2001
In the following questions, Gn is a simple undirected graph with η
vertices, Kn is the complete graph with η vertices, Kn^m is the complete
bipartite graph with m vertices on one party and η vertices on the other
party, and Cn is a circle with η vertices. e(Gn) is the number of edges
in the graph Gn.
1. The edges of Kn: η > 3 are coloured with η colours, and every
colour appears at least once. Prove that one can find a triangle
whose sides are coloured with 3 different colours.
2. η > 5 is given. If e(Gn) > ^ + 2, prove that there exist two
triangles which has exactly one common vertex.
3. e(Gn) > ^ + f · Prove that Gn contains C4.
Пу/п
4. (a) Gn does not contain К2,з. Prove that e(Gn) < -^=- +n.
(b) Given η > 16 distinct points Pi, P2,..., Pn in the plane, prove
that at most Пл/п of the segments PiPj has unit length.
5. (a) Let ρ be a prime. Consider the set {(ж, y)\0 < ж, у < ρ — 1} of
vertices, such that (ж, у), (ж', у') are connected if xx'+yy' = 1
(mod p). Prove that this graph does not contain C4.
(b) Prove that for infinitely many values of n, there exists a graph
Gn that does not contain C4 and e(Gn) > ^ψ^ — п.

6. TEAM COMPETITION SOLUTIONS
1990
τη
1. Let a = — with gcd(m.n) = 1.
η
Denote by S the set of rationale with denominator not greater
than n. The set S is well-ordered, and hence there exist rationale
/3,7 G S such that β is the maximal element in S smaller than a,
and 7 is the minimal element in S greater than a. Then in the
interval I = (/3,7) there are no rationale with denominator less
than or equal to n, except a.
2. Let Sn be set the of rationale with denominator less than or equal
to n. As we stated, Sn is well-ordered for every n. The Farey
sequence
шу ι
V / m=l
is defined to be the elements in Sn with this order. Clearly, if
a = F^k\ then
Ia = (F<ik-1\F<ik+V).
We shall now prove the following property of the Farey sequence:
If
F{rn) = a F(rn+i) = £
6' n d
with
gcd(a,6) = gcd(c, d) = 1
be— ad > 1.
We shall now prove that if a, b natural numbers with gcd(a, b) = 1
then there exist natural numbers c, d such that d < 6, gcd(c, d) = 1
and be— ad = 1, which will complete the proof.
To that end, consider the set {ax\l < χ < b}. If for 1 < d < 6,
ad= 1 (mod 6) then we are through. Otherwise, since there are b
different residues modulo 6, it follows from the pigeonhole principle
that for 1 < Χι < x2 < b,
ax\ = ax2 (mod b).
then be
Proof:
: — ad
= 1.
Since Fim)
a
<
С
~d~~
„(m+l)
bc-
then
ad >

128
6. Team Competition Solutions
Then b\a(x2 — Xi), and since gcd(a, 6) = 1, ЦХ2 — Х1, but b > X2 — X\
and we arrive at a contradiction.
α с
It remains to find rationale β = -, η = - such that 196 — 90a = 1,
90c - 19d = 1 and 6, d < 90.
4
196 = 90a + 1 => 1 - 5a = 0 (mod 19)=>a = 4=>/3= —
15
90c = 196 + 1 => 1 + 5c ξ 0 (mod 19) => с = 15 => 7 = —
Therefore
3. It is a well-known fact that between any two real numbers lies a
rational number.
и
Let α < ε < 6, ε = —. By the minimum principle, there exists a
ν
rational a G (a, 6) such that the denominator of a is minimal.
τ
We shall now prove that a is unique. Let a = -, and assume that
■s
r± 1
0= — G(a,b).
Then since
(r ± 1)5 — Sr = ±5 φ 1,
it follows that a, /3 aren't consecutive in Fs, so there exists 7 G (a, 6)
such that 7 is between a and /3 in Fs, and thus the denominator of
7 is less then s: contradicting the minimality of s.
Therefore, a is unique.
4. Of course, there is the algorithm of finding the consecutive elements
in the Farey sequence, as we used in the previous problem. We
shall use now a different method, consisting of the properties of
continued fractions.
For the first case, note that
_ J0_ 1 27 _ 1
α"Ϊ77_^ Ϊ ' 68~
2 + = "u 2 +
1 + — 1 + r
8+-

1990
129
Now
and
1 _ 17 _70_ 1 _ 2 27
2+ \ ~^<ΐ^' 7^37" 8 > β»
2 17
19
48
17
' 43 "
43 + 5
1
43-48'
48'
2
5 ~
19
' 48 ~
1
5-48
5 43 5-43
Therefore |, || are consecutive elements in F43. Hence the number
with the least denominator between them is
17 + 2 19
Since
Then ||, || and | are consecutive elements in F48. This leads us
to the conclusion that || is the number with the least denominator
in the interval (||, |) and thus
/_70_ 27\ _ 19
α V177' 68У ~ 48'
For the second case, note that the representations of V1990 and
л/1991 as continued fractions are

130
6. Team Competition Solutions
Let
5
i = 44 +
1 +
χ = 44 Η = 44 +
1 + -^
1 + ^
1
1+ϊ
1 3
and у = 44 Η ζ = 44 + -.
1
1 + ϊ
We have χ < \/Ϊ990 < л/1991 < у , and у — χ = ^ and hence χ, у
are consecutive elements in Fg. Therefore
3 3+5 8 , 5
-, = —, and -
5' 5 + 8 13' 8
are consecutive in F13 because
_8__ 3 _ J_
13 ~ 5 ~ 65
and
5 8 _ 1
8 ~ 13 ~~ 104'
Finally, we get
л/1990; уДш\ = 44 + -^.

1991
131
1991
1. Assume that the integer polynomial
f(x) = x2 + ax + 6
is a square number for infinitely many values of x. If
x2 + ax + 6 = y2
then the discriminant
a2 - 46 + V
must be a perfect square, say
z2 = a2 -4Ъ + Ц)2.
There are therefore infinitely many values of у and ζ such that
z2 - (2y)2 = a2 - 46.
Clearly, the values of z2 and y2 increase beyond all bounds, and so
do the values of г, у.
Assume by contradiction that
a2 - 46 = η φ 0.
Then
(z-2y)(z + 2y)=n:
but ζ + 2y increases beyond all bounds, while ζ — 2y is at least 1,
contradicting η is finite.
Therefore, a2 = 46, and there exists an integer с such that a = 2c
and 6 = c2. Thus
f(x) = x2 + 2cx + c2 = (x + c)2.
2. Let
/(ж) = 2ж2 + Зж + 1,
for all integers ?/, ζ such that
22 - 8y2 = 1.
Then if ζ = 3 (mod 4), we have
.fz-3\ n z2-6z+9 0 z-3 , z2-l 2

132
6. Team Competition Solutions
and if ζ = 1 (mod 4) then similar calculation yields
It is left to prove that there are indeed infinitely many solutions to
the equation z2 — 8y2 = 1 in integers.
This equation is a particular case of a more general case of Pell's
equation. A first solution is provided by 32 — 8 · l2 = 1, and every
other solution is given by
x + yy/8 = (3 + V8)n.
Obviously, there are infinitely many solutions and thus f(x) is a
perfect square for infinitely many values of x.
3. For every TV, consider the polynomial
f{x) = x2 + {2N + 4) + (2^+1 + 4).
If τ/, ζ are integers such that
z2 - 4y2 = 22N = a2 - 46
and ζ is even, then
We shall prove- that there are 27V — 1 different solutions to the
equation
ζ2-4ν2 = 2Ψ,
yielding 27V — 1 values of χ for which f(x) is a perfect square.
For every к -ф ±1, then the system of equations
( z-2y= 2k
{ z + 2y= 22N~k
has the solution
(y, z) = (2n-k~2 - 2k~2, 2k~x + 2п~к~1) ,
with ζ even.
Since there are 27V — 1 different options for fc, it follows that here
are 27V — 1 solutions to that equation, thus 27V — 1 values of χ such
that f{x) is a perfect square.

1991
133
4. Let us prove part (b) first. Denote the smallest χ for which f(x) is a
perfect square by x0, let у о = >Jf(xo) and let zq be the discriminant
For every 0 < к < TV, we have /(жо + &) = y\, and thus
^ = 2(x0 + fc) + а = z0 + 2k.
We have
£>(/) = *o - (%o)2 = (*o + 2)2 - (2У1)2 = (z0 + 4)2 - (2y2)2,
implying
2£>(/) = 2(z0 + 2)2 - 2(2y2) = zl + (зд + 4)2 - (2y0)2 - {2y2f.
Therefore
yl+y22 = 2yl + 2.
Checking residues modulo 4, we find that the values of 2/o, 2/i, 2/2
can be odd, even, odd or even, odd, even respectively. Obviously,
this relation holds for every yk, yk+i, Ук+2 when 0 < к < N — 2.
Therefore, the values of
У к = Vf(xk)
are alternately odd and even.
For part (a), note that zq + 1 = y2 — y\. Since the parity of yo, y\
is different, zq is even. Let us check residues modulo 8:
20ξ0 (mod 8) : y\ - yg = 1 (mod 8)
=>· yo = 0 (mod 4)
=> £>(/) = z2 - (2y0)2 = 0 (mod 64)
z0 = 2 (mod 8) : y\ - yg = 3 (mod 8)
=>· yi ξ 2 (mod 4)
=> £>(/) = (г0 + 2 + 2yi)(z0 + 2 - 2yi)
ξ 0 (mod 64)
ζ0ξ4 (mod 8) : у\-у\ = Ъ (mod 8)
=> y0 ξ 2 (mod 4)
=*£>(/) = (*o + 2y0)(*o-2y0)
ξ 0 (mod 64)
^o ξ 6 (mod 8) : y2 - yg = 7 (mod 8)
=>· yi ξ 0 (mod 4)
=^(/) = (*о + 2)2-(2у0)2
ξ 0 (mod 64)
Our claim is proved.

134
6. Team Competition Solutions
5. (a) We need to find three integers yo, Уъ У2 such that
2y?+2 = y02+y22
but yi — yo -φ 1, for otherwise D{f) = 0, implying / is a square
polynomial.
Hence we have to solve the Pell equation
y2-2y2 = 2-y2.
Putting yo = 1, we have to solve the unit equation
u2 - 2v2 = 1.
The fundamental solution of this equation is (3,2), and all
other solutions are given by
u + vV2= (3 + 2л/2)п.
Taking η = 2, we have
У2+У1\/2=17 + 12л/2,
implying у 2 = 17, у ι = 12. Then
zQ = 122 - 1 - 1 = 142
and thus D(f) = 20160. Therefore we can choose a = b = 144,
and thus
f(x) = x2 + 144ж + 144
receives square values for χ = —1,-,0,1.
(b) We shall show a different method of finding an TV-polynomial.
Suppose that D = pq with
Vk < y/p- y/q < Vk + 1.
Then
p + q-1 = (Vp-Vq)2+2^/pq
< k + 2y/D
< (Vp- Vq)2 + zVpq
= p + q.
Hence
\2VD + k]=p + q,

1991
135
and it follows that
\2VD + k]2-4,D=(p-q)2.
Note now that if D is given then there can be only one pair
(p, q) such that
Vk < y/p-y/q< Vk + 1
for a given k, since if (p, q) are a pair satisfying this inequality,
then pq and ρ + q are determined uniquely.
We can now present a way of finding an TV-polynomial. We
need to find an integer D for which there are N pairs pi, qi
such that D = piqi and
о < Vpi - Vol < >/iv.
If we have found such D, then the polynomial f(x) = x2 — 4£)
is a perfect square for
x=\2VD + f\, i = 0,l,...N-l.
In order to find a 4-polynomial, we have to find D such that
D = pq and
o< Vp-Vq< 2
holds for four different pairs p, q. One solution is D = 15120
with the pairs (126,120), (135,112), (140,108), (144,105).
Then
Г2У15120] = 246
and
f(x) = x2 - 4L> = x2 - 60480
is a perfect square for χ = 246 , 247, 248 and 249.

136
6. Team Competition Solutions
1992
1. We shall use induction on j. The case j = 0 is trivial. Assume that
the claim holds for j, that is, L2o + 1 = ra · 2J+1. Then
L2j+i = α2 + /Г
= (a2J+p2J)-2(apf
= (m · 2j+1 - 1) - 2
= 2j+2(m2-2j -m)-l
= -1 (mod 2j+2).
Which is what we wished to prove.
2. We will prove that for every k,
akFk + 2
= F2k·
This is equivalent to
,2k n2k
к ok
aAK _ βΖ* аь _ β
2k n2k
<
a +2<
aZk - β
~~7ί
+ 1.
л/5 " л/5
Simplifying, we get the inequalities
_^*<^_(_1)*<л/5_02*.
We will prove the left inequality first. Since β < 1 it follows that
^1 >!>(-!)* >(-!)*-/?
\fc o2k
For the second inequality, if к > 3, then
^-^ + (-1)'>^-1>/35>/?2*,
and it is left only to verify the inequality to к = 0,1, 2.
This yields
Σ
fc=0
akFk + -
= ^, F2k — F\ + ^ ^2fc = -P;
2n+l·
fc=0
k=l

1992
137
3. First, any number which is r-Fibonacci, where 1 < r < 5 is 5-
Fibonacci as well, since we can add Fo = 0 to the sum. Also,
if
η = Fkl + Fk2 + Fk3 + Fki + Fkb
is the representation of η as 5-Fibonacci number, we will assume
that \ki — kj\ φ 1.
Our claim is that for к > 6, i^fc+i — 1 is not 5-Fibonacci. Assume
by contradiction that
F2k+1 -l = Fkl+ Fk2 + Fk3 + FkA + Fkb
with ki + 1 < ki+ι. Then
Fkl + F/C2 + Fk3 + -^4 + Fk5
< -^2fc + -^2fc-2 + F2k-4 + -^2fc-6 + F2k-8
2k
< Σ^
= F2k+i —
ΙΑ contradiction.
4. We note the following identities:
FnLn = -±=(an - βη)(αη + βη)
= F2n
Fn_!Ln+1 = -L(a«-i-^-i)(an+1+)9n+1)
= -^(^-^-(а/ЗГ-1^2-^2))
Fn+1Ln_! = -^ (α«+ΐ-^+ΐ)(α™-ι+^-ΐ)
= ^g (<*2n - /32n + (α/?)""1 (α2 - β2))

138
6. Team Competition Solutions
= F2n + (-l)n-\
Therefore,
Fn-iFnFn+iLn-iLnLn+i = F2n(F2n — 1)
Suppose that F2n(F2n — 1) is a perfect square. Since
gcd(F2n,F22n-l) = l
it follows that both of them must be perfect squares, but since
F2n > 1, F2n — 1 cannot be a perfect square.
5. For every n, we claim that
L2n+i + (—l)n = F$ · Fn · Fn+i.
The proof is very easy:
F5-Fn-Fn+1 - 5·—^ -^
= a2n+1 + /32n+1 - (a + /3)(a/3)n
= L2n+1 + (-1Γ+1.
6. Denote the rectangle by ABCD with
A=(Fai,i^2) S = (JP6l,Fbl)C=(JPCl,JPC2) D=(Fdl,Fd2)
Since ABCD is a rectangle, it follows that
^01 + ^d = Fbl + Fdl and Fa2 + FC2 = Fb2 + Fd2.
If, for example Fai = Fbl then FCl = Fdl and since ABCD is a
rectangle, we get Fa2 = Fb2 and ,РС2 = Fd2 and thus the sides of
ABCD are parallel to the coordinate axes.
Therefore, assume that Fai Φ Fbl and Fai -φ Fdl. With no loss
of generality we can assume that Fdl > Fai, Fbl, FCl. Clearly, the
inequality must be sharp, for otherwise we would get that Fdl is
equal to FCl or Fai. Suppose that Fai φ FCl. Then since Fbl φ Ο,
it follows that
Fai + FCl < Fdl_i + Fdl_2 < Fdl + Fbl,
contradicting that ABCD is a rectangle. Therefore, Fai = FCl.

1992
139
In a similar manner, from the equality
Fa2 + FC2 = Fb2 + Fd2,
we must have Fd2 = Fb2 (since Fa2 -φ FC2), and therefore the
diagonals of the rectangle ABCD are parallel to the coordinate
axes, and thus ABCD is a square whose sides make 45° angles
with the coordinate axes.

140
6. Team Competition Solutions
1993
1. We will use the following identity: for every x,y G G and for every
i > 1,
(xy)i = x-(yx)i-1-y.
Let x,y G G. It is given that
{xy)k+1=xk+1yk+\
and using our identity we get
(yx)k = xkyk = (xy)k.
Similarly, we have
(ys)*"1 = {xyf-1.
But
(xy)k = (xy) ■ {ху)к~г
and
(yx)k = (yx) ■ (yx)k~l,
which leads to the conclusion that xy = у χ for every x, у G G,
which is what we wished to prove.
2. Denote by φ the mapping χ —> xn. Since φ is an isomorphism,
then for every x, у G G we have
у(я) · </?Ы = <р(ху),
that is,
Ж™^ = (Xy)n.
Let an_1 G G, and let b be an arbitrary element in G. The mapping
φ is on G, and hence there exists с Ε G such that b = cn. It follows
that
α71-1^ = α~λ ■ (an ■ cn)
= a'1 ■ (ac)n
= α~λ ■ (a ■ {caf-1 ■ c)
= (ca)n ■ a'1
= οηαη-λ
= ban~\
and therefore an_1 G Z(G) for every a EG.

1993 141
3. We shall prove the claim by using induction on n. Clearly, the
claim holds for η = 1,2,3,4,5. Assume that for every σ G 5n-i>
we can write σ as a product of two cycles. Let σ G Sn with η > 6.
Consider three cases:
Case 1: σ leaves one element in the set {1, 2,.. .n} in its place.
Then there exist σ' G 5n-i such that σ = σ', and thus by our
induction hypothesis, σ is the product of two cycles.
Case 2: σ is a product of m cycles with size 2, where η = 2m, and
without loss of generality we can assume
σ= (1 2)(3 4)---(2m-l 2m).
Then
σ = (2m - 1 2m - 3 ... 5 3 1)(1 2 3 4 5 6 ... 2m)
Case 3: σ effects every element in {1,.. .n} and contains at least
one cycle with length I > 3. Assume that
σ= (1 2 ...1-11)-τ,
where r and the cycle are distinct (r is not necessarily a cycle) and
let
σ= (1 2 ...I-l)-т.
By our induction, σ is the product of two cycles, say σ = ψ ■ φ.
Since σ(1 — 1) = 1, the cycle ψ takes φ (I — 1) to ^(1). We define a
new cycle φ:
( tp{k) к^ф{1-1\1
Ф{к) = Ι ι к = ф(1-1) .
1 ^(1) к = 1
It is easy to verify that φ is indeed a cycle, and that σ = ψ ■ ф.
4. Assume that
\аНПНЪ\ ^0,
then there exists an element of aH: say a, which can be written as
a = hb where he H. Denote by К the set Η Π b~1Hb.
We shall prove that
|ϋί| = |α# П#Ь|.
Indeed, let к G K, so that k £ Η and fc = b~1h'b, where /ι' G i7.
Then afc G aii, and

142
6. Team Competition Solutions
On the other hand, let χ G aHDHb, so there exist hi, h2 Ε Η such
that
χ = ahi = h2b.
This implies that
hi = a~1h2b = b-1h~1h2b G b^Hb.
We will now need to show that \K\ divides \H\.
To that end, recall that for every b G G, b~1Hb is a subgroup of G.
The intersection of two subgroups is a subgroup as well, so К < G.
But К С Η and therefore К < Η. By Lagrange's theorem, its
order divides \H\.
5. The problem is solved easily using the "TV/С theorem", which
states that there exists a homomorphism
φ : NG{H)-+Aut(H\
where Aut(H) is the group of the automorphisms of H, such that
Κεν{ψ) = Cg{H)· In other words, there exists a subgroup К of Η
for which
NG(H)/CG(H) 9έ К.
Since \H\ = 3, then
Aut(H) =S2 = Z2.
Using the N/Otheorem, we deduce that \Nq{H) : Cg(H)] divides
2, and therefore
[NG(H) : CG(H)} = 1 or 2.
We shall now prove the N/C theorem. Define φ in the following
manner: for every g G Ng(H),
^{g)){h)=ghg-\
Since g G Ng(H), this mapping is defined for every h G i7, and
it is now easy to verify that the mapping h —> ghg"1 is indeed an
automorphism. The unit element in Aut(H) is the identity function
of H: which leads to
Κβτ{ψ) = {9\ψ{9) = idH} = -Ы УЛ G Я, ^(Г1 = Л} = Сс(Я).
And our claim is proved.

1993
143
6. Let us write the given equations in the form
ab2a~l = b3 ba2b~1 = a3
Denote by o(x) the order of χ for every χ G G. From the equations
above, we have o(b2) = o(b3). It follows that
o(b2) = o(b) = m.
The relation
gcd(k:o(x))
implies that gcd(2,m) = 1, and therefore there exists integers r,p
such that 2r + mp =1. In a similar manner, we conclude that there
exists integers s, t such that 2s + nt = 1, where η = o(a).
The condition аЬ2а~х = b3 implies that b3r = α№τα~λ = aba-1.
Similarly, a3s = bab'1. But b3r = b2r ■ br = br+1, and the first
condition becomes
br = aba~lb~l = a ■ {bab'1)'1 = a ■ a~3s = a ■ a'3'1 = a~s.
It follows that b = b2r = a~2s = α-1, and now it is easy to conclude
that a = b = 1.
7. Let G' =< a >, that is, G' contains the unit element and a.
We will start by showing that a G Z(G). Indeed, for every χ G
G, axa~lx~l G G' which means that either axa~1x~1 = 1 or
αχα~~λχ~ι = a. The latter option implies that a = 1, which is
impossible, and thus ax = xa for every χ G G.
For every д G G denote by
G ■ д = {y\3x g G, хдх~х = у}.
Suppose у G G ■ g. Then either у = g: or there exists χ G G such
that xg -φ gx, and xgx~l = y. We conclude that
a = xgx^g-1 = yg~l
and thus у = ag. Therefore, G ■ g = {g} if g G Z(G) and gG'
otherwise.
Obviously, Z{G) -φ G because otherwise G is Abelian, and G' =
{1}. Let g <£ Z{G). It is well known that \G ■ g\ = \G\/\Zg\: the
notation Zg standing for {x\xg = gx]. Since G ■ g = gG': we end

144
6. Team Competition Solutions
up with |G| = 2\Zg\. Suppose χ G Zg. Then xg = gx: and since
a £ Z(G),
(ax)g = a{xg) = (xg)a = g{xa) = g(ax)
So that αχ Ε Zg. We conclude that Zg contains a natural number
of cosets of G', and therefore \Zg\ is even. Finally, |G| is divisible
by 4 and \G : G'\ = h\G\ is even.

1994
145
1994
1. We demonstrate an algorithm A which will be used for the solution:
(a) Find the median h of the set of all weights.
(b) Check, using the BFS algorithm if the graph
d = (V, {e G E\w(e) < h})
is connected.
(c) If the answer to 2 is NO, then let V' be the set of connection
compounds of G\, and E' be the set of edges connecting
between those compounds, and return the result of A applied on
the graph (V',E').
(d) If the answer to 2 is YES, then check if the graph
G2 = (V, {e e E\w(e) < h})
is connected using the BFS algorithm.
(e) If the answer to 4 is NO, then return h.
(f) If the answer to 4 is YES, then return the result of A applied
on (?2·
The required algorithm is the following:
(a) Apply A on the graph, and let w\ be the number it returns.
(b) Find a spanning tree to the graph
(V, {e <= E\w(e) < ιυλ}).
This tree is the required spanning tree of the graph.
Correctness of the algorithm: Each time A is applied, either it stops
or it runs on a graph with number of edges at least twice as small.
Therefore A must stop, and return a number w\. We shall prove
that this number is the minimal weight w for which the graph with
edges whose weight is at most w is connected. It is easy to see
that if this number is the median h, then the algorithm returns the
correct answer. But since this number is not changed each time
that we create a new graph in our algorithm, it follows that A
indeed returns the required number. Hence follows the correctness
of the whole algorithm.
Complexity: We shall prove by induction on m that the complexity
of the algorithm is indeed 0(m). The case m = 1 is trivial. Suppose

146
6. Team Competition Solutions
that the complexity of the algorithm on a graph with less than m
edges is 0(|£Ί). Let с be a constant such that the algorithm takes
at most c\E\ steps, and we can assume that c\E\ is always greater
than twice the number of steps it takes to do stages 1, 2, 3, 4, 5,6
in A, without recursive calls. This is possible, for all the stages in
A take 0(\E\) steps. Then for m > \E\ < 2m:
If the algorithm stops at stage 5 of the first call, then obviously we
are through. Otherwise, in the next call the algorithm is applied
on a graph with less than half the number of edges, and thus the
total number of steps is at most
\E\
(The number of steps to do 1, 2, 3, 4, 5,6) + c-—
\E\ \E\
< cV+cV
= c\E\.
And we are done.
2. The algorithm:
(a) Turn G into G' = (V, {/ G E\w(f) < w(e)}).
(b) Check if there is a path in G' between χ and y.
(c) If the answer to 2 is YES, then return NO.
(d) Else, return YES.
Correctness of the algorithm: We shall prove that there is a
spanning tree in the graph containing e if and only if the algorithm
returns YES.
If there is such a spanning tree, then it is impossible that there is a
circuit in the graph in which e is the heaviest edge. For otherwise,
remove e from the alleged spanning tree and add one of the edges
in the circuit so that this tree will be connected. We get a lighter
spanning tree, which contradicts the minimality of the spanning
tree.
If the algorithm returns YES, then there is no spanning tree with
all its weights smaller than w(e). Apply the Kruncal algorithm to
find a spanning tree, with e being the first edge in the list of edges
with weight w(e). Then we would get a minimal spanning tree,
necessarily containing e.
Complexity: The complexity of the algorithm is clearly 0(|-£?!).

1994
147
3. The algorithm:
(a) Check, using BFS algorithm, for which vertices χ it is possible
to reach χ from s.
(b) Check that χ cannot be reached from s if and only if d(x) = oo.
(c) If 2 does not hold, return NO and stop.
(d) Check if d(s) = 0. If no, return NO and stop.
(e) For each у ф s with d(y) φ oo:
i. Check for every vertex ζ —> у if d{z) +w(e) > d(y). If no,
return NO and stop,
ii. Check if there is a vertex ζ —>· у with d(z) + w(e) = d(y).
If no, return NO and stop.
(f) If you have reached so far, return YES and stop.
Correctness of the algorithm: Assume that d is indeed the function
assigning the weight of the path from s to χ for every vertex χ G V.
It is very easy to see that all the tests in stages 2,4, 5 indeed hold
for d and thus the algorithm will return YES.
Assume that the algorithm returns YES. The test in stage 2 implies
that d is correct for all the vertices which cannot be reached from
s. The test at stage 4 implies that d is correct to s.
Define a function f : V —> R which gives for every vertex χ G V
the minimal weights of the paths from s to x. We need to show
that f{y) = d{y) for all у that can be reached from s.
First, we show that f > d. Assume by contradiction that this is
not the case, and let у be the vertex for which f(y) < d{y) and
f(y) is minimal. Then у φ s. There is a path from s to у with
weight f(y). Let ζ be the preceding vertex to у in that path, and
e be the edge (z,y). Then
f(z) + w(e) = f(y).
By the minimality of y, it follows that f(z) = d{z). But then
d(y)>f(y) = d(z)+w(e):
which contradicts 5.1.
Next, we show that f < d. Assume by contradiction that there is
a vertex у for which f(y) < d{y). Let у be the vertex with the

148
6. Team Competition Solutions
minimal d(y) that satisfy this. Then у -ф s. From 5.2, it follows
that there is a vertex ζ —>· у such that
d(z)+w(e) = d(y).
Then ζ can be reached from s, and d(z) < d(y). It follows that
d(z) = f(z), but then, from the definition of /,
f(y)<f(z)+w(e) = d(y):
a contradiction.
Therefore / < d for all the vertices y.
Finally, we have proved that f = d.
Complexity: Stages 1, 2 can be done in 0(n) steps. Stages 3, 4,6 are
of complexity O(l). In stage 5, we check each edge in the graph
at most twice, and hence it requires 0(m) steps. Therefore the
complexity of the whole algorithm is 0(m + n).
4. (a) Add a vertex to G and connect it to all the other vertices.
The new graph is connected and the degrees of all vertices are
even (since the degree of every vertex in the old graph is 4,
and the degree of the new vertex is equal to the number of the
vertices in the old graph, which is even). Hence, it contains
an Euler circuit.
Walk on this circuit and colour its edges alternately in two
colours. Then remove the new vertex, and let E\ be the set of
the remaining edges coloured in the first colour, and E^ the
set of the remaining edges coloured in the second colour. It
is clear that for each vertex, there are at most two edges in
the same colour connecting it, and therefore we obtained the
required result.
(b) It is clear that the last algorithm can be applied in 0(m)
steps.
(c) First, colour the vertices of G in four colours 0,1, 2, 3 using
the greedy algorithm - for each vertex, colour it such that its
colour will be different from the colour of all its neighbors.
This can clearly be done in 0{n) steps, where η = |V|, and
since 3n = 2m, 0{n) = 0(m).
Next colour the edges of G the following way: let c(v)
denote the colour of a vertex ν G V. For each edge е(ж, у),
colour e in c(x) + c(y) mod 4. One can easily show, that if

1994
149
βι (ж, у ι), е2(х: у 2) are edges having a common vertex x: then
since c{y\) ^ с(т/2), it follows that
c(x) + c(yi) φ c(x) + с(уг) mod 4.
Therefore our colouring is good.
5. (This solution is due to Prof. Noga Alon of Tel-Aviv University)
We shall prove by induction on к that if η > 2k~~l then it requires
at least к questions to determine the product of X\,... xn.
For к = 1 the claim holds, for if η > 1 then it takes at least one
question to determine the sign of χ ι.
Assume that the induction claim holds for k, and let η >2k.
Suppose that the first question is whether
η
У^ diXi > C.
i=\
If
[η/2] η
- Σ Ы + Σ Ια*Ι -с
г=1 г=[п/2] + 1
then the answer to that question is positive for every sequence
Oi,rE2,...:E[n/2],sign a[n/2]+i,...sign an).
Hence determining the product of the original sequence using linear
questions is equivalent to finding that product for the sequence
(^1,^2,... ,X[n/2])· By our induction hypothesis, it will take at
least к more questions, making it a total of к + 1 questions.
On the other hand, if
[η/2] η
- ^2 \di\ + ^2 \di\ < С
г=1 г=[п/2] + 1
then the answer to the question will be negative for every sequence
(-sign αϊ,..., -sign a[n/2], X\, x2, ■ ■ ■, xn-[n/2])
and since n— [n/2] > 2fc_1, it follows from the induction hypothesis
that we need at least к more questions.

150
6. Team Competition Solutions
1995
1. (a) We choose some olq > 0 and a real number c. Let Ρ be the
intersection point of the curve x4 — x2y = α$ with the line
χ = c. Then the y- coordinate of Ρ satisfies
2 ao
The derivative of the curve is
4ж3 - 2xy - x2y' = 0 => у' = 4ж - 2
The tangent to the curve at Ρ is therefore
χ — с с
Simplifying, we get
У= 2c + 0 ,
с / c^
3 / ,,2
At the point x = Щ the value of у is ?/ = 2c2, and therefore
all of the tangent lines pass through the point P\ = (γ, 2c2).
(b) The coordinates of Pi are Pi = (xi,yi) = (^,2c2), and it
follows that
yi = 2c2 = 2(-x)2 = -x2.
yi v3 ) 3
Thus the Locus of the points Pi is the parabola у = |ж2.
2. Let Ρ = (xo:y0) with
xl +y* =1.
Denote и = -ξ/χ~ο, ν = .ξ/y^, so that и2 + υ2 = 1. We are now to
find the tangent to the curve at P.
ζ ζ -, 2Д 1 /N Λ , ν
жз +уз = l=> (_ + _.y') = o=>y' = .
3 и ν и
The tangent equation is therefore
uy + vx = uv.
The point Q of intersection between the tangent and the y-oxis is
(0, v). To find R: we solve the two equations
uy + vx = uv
x2 + {y - v)2 = b2

1995
151
The positive solution is R = (\u\b, ν — vb). The coordinates of R
sa.t.isfv t.Vm miiatinn
satisfy the equation
У2
+ ,. „„ =1-
b2 (1-b)2
So R lies on the right half of this ellipse.
To end the proof, we need to show that for every point R' on the
indicated ellipse, there exists a point P' on the curve such that
P'R' is tangent to the curve and the distance between R' to the
intersection between P'R' and the y-axis is b. Let R' = (x\:yi).
The corresponding point P' will be
It is easy to verify that P' is indeed on the curve, and that P'R' is
tangent to the curve. The equation of P'R' is
£i(l -b)y + y1bx = x1y1.
Then
and
3. For every Ρ = (α, 6, с), we will check if the projection of С from Ρ
on the ж, у plane gives a curve with a cusp or a node.
A node will occur if one of the lines through Ρ cuts two points on
C, and hence there exist two points (ί, ί2,ί3), (s,s2:s3) G С such
that
t — S _(!) t — S _(2) £ — S
α — s b — sz c— s
Equality (1) implies
b- s2 = (t + s)(a- s)
and hence
b — as
t= .
a — s
3 ·

152
6. Team Competition Solutions
From equality (2) we deduce
s2(a2 -b) + s{c - ab) + (b2 - ac) = 0.
The existence of a point Ρ with a note is equivalent to the existence
of a solution to the equation, i.e that the discriminant Δ of the
equation is nonnegative.
Δ = (с - ab)2 - 4(α2 - b)(b2 - ас) > 0.
If Δ > 0, then we have a node. If Δ = 0, then we have an extremum
node, which is a cusp.

1996
153
1996
1. The maximal number of edges is 96. An example of such a graph
is the bipartite graph 8 χ 12. We shall prove that there can be no
more then 96 edges in G.
Obviously, if the degree of each vertex of G is lesser than 12, then
it can be at most 8, and the total number of edges is at most
\ χ 8 χ 20 = 80.
Suppose that there exists a vertex υ such that the degree of ν is
greater than 12. Then the degree of ν is 16, and let A be the
set of vertices that are connected to v. No two vertices of A are
connected, and thus the degree of each vertex in A is at most 4.
The maximal degree of every vertex in G is at most 16, so that the
degree of the three remaining vertices is lesser than or equal to 16.
The total number of edges in G is therefore
1 1
- У2 аеФ) < о (16 х 4 + 4 χ 16) = 64.
Assume that the degree of each vertex in G is not greater than
12. Let ν be a vertex with degree 12. Denote by A the set of
those vertices of G which are connected to ν and by В the set
of the vertices outside of A. As before, no two vertices in A are
connected, so their degree can be no more than 8. The degree of
each vertex of G can be at most 12, and thus the degree of each
vertex in В can be at most 12.
This brings the total number of edges in G to
1 1
- ^ ае&х ^ о (12 x 8 + 8 χ 12) = 96.
xEG
The maximal number of edges in G can therefore be 96.
2. Consider the following algorithm to find such a subset S of G.
Set г = 1 and let B0 = G: щ = п.
For every i, denote by Bi the subset of Bi-\ of vertices not
connected to Vi, and щ = \Bi\.
We shall prove that there exists a sequence of vertices v±:V2 ■ ■ -Vk
such that щ< ψ.

154
6. Team Competition Solutions
Our set S will be the set of vertices {i>i, V2, ■ ■ ■ Vk} and since
к < 1 + log2 n,
this would yield the desired result.
For every г, consider two cases:
Case 1:
There exist a vertex χ in S^-i such that χ is connected to at least
ni~2~ vertices in S^-i· Then set Vi = x, and then
thus
η
- 2г
Case 2:
If each vertex in S^-i is connected to less then Пг~21 ~ vertices in
Bi-i, then each vertex is connected to at least n~rbi-1— vertices
in Ai_i, the complementary set to i?i_i. The total number of
edges in the bipartite graph between Ai-\ and S^-i is therefore
n{-i(n-wi-i)^ an(j ^ ^e pjgeoimoie principle there exists a vertex
α 6 Аг-ι such that α is connected to at least
rti-i(n-nt-i) rtt-i
2(те - 7ii_i - 1) ~ 2
Obviously, α ^ гл,- for every j < г, since every vertex in S^-i is also
in Sj. Set Vi = a, and we have
. Гсг-ι
П^ —'
which implies
η
г - 2г
Since the number of vertices in G is finite, the algorithm must end
at some stage, say after к steps. Then 2k < n, or к < 1 + log2 n,
and we have reached a set 5 as requested.
3. We shall prove that there is a Hamilton circuit in every connected
fc-regular bipartite graph if and only if к = 2.
For к = 2, every such graph is necessarily a circuit, and hence it
contains a Hamilton circuit.

1996
155
Assume that к Φ 2. Consider the following fc-regular graph:
A complete к bipartite graph is a graph with 2k vertices, each
party contains к vertices and each vertex is connected to all of
the vertices in the other party. Take three such graphs K±: K2: Кз
together. Choose к pairs (αΐ,&ΐ)ΐ=ι such that ai is connected to
bi: ai φ dj and hi φ bj for i φ j: and for each j = 1, 2, 3 there
is at least one pair (α^.,δ^.) G Kj. Remove the edges (ai,bi), and
let Ki:K2:Ks be the complete graphs after the removal of those
edges. Now add two more vertices a, b. For i = 1, 2,... k, connect
a to bi and b to ai. Consider the graph G that was obtained. Then
G is connected, and it is fc-regular.
Assume by contradiction that there is a Hamilton circuit in G.
Then this circuit passes through a and b. Remove a and b from
G. The Hamilton circuit will be separated into two connecting
compounds, but this is impossible since if we remove a, b from G we
would get at least three connecting compounds Κι, К2:Кз. This
contradicts the assumption, and hence there is no Hamilton circuit
inG.
4. Note that the given condition is equivalent to that from every
subset Τ of vertices containing s but not t and there are at least k
edges exiting T. Also note that if there are m edges entering some
set X of vertices, then since the in-degree of each vertex is equal to
its out-degree, there are m edges leaving X. s and t are therefore
symmetric, so we can prove only one direction, that there are k
path-disjoint paths from s to t.
We shall prove the claim using induction on n, the number of
vertices in the graph. Obviously, η > k + 1. The case η = k + 1
is trivial, and assume that the claim holds for every graph with
m < η vertices. There are at least k edges coming from s, to at
least k different vertices. Denote by Τ the subset of those vertices
and s. We will now prove that there are at least k path-disjoint
paths from s leaving T. Assume by contradiction that this is not
the case. There are at least k edges leaving T, so at least two of
them must leave the same vertex a G T, with α φ s. Consider the
set of vertices T\{a}. There are at most k — 2 edges leaving Τ
plus one more leaving s towards a, making it at most k — 1 edges
leaving T\{a}, a contradiction.
Let us consider now the graph consisting of all the vertices of the
original graph except for those in T, and Τ as a vertex. In this new
graph, the in-degree of each vertex is equal to its out-degree, and for
every set of vertices containing Τ there are at least k different edges

156
6. Team Competition Solutions
leaving it. By induction, there are к path-disjoint paths leaving Τ
to i, and since the к paths leaving Τ are also path-disjoint, this
means that the claim holds in the original graph. Therefore, the
claim holds for every number η of vertices in the graph.
5. We will prove by induction that all those graphs with η vertices
that do not contain a path with length 100 have no more than 49. bn
edges, and that equality happens only in the graph consisting of
unconnected i^ioo graphs.
The claim obviously holds for η < 100. Assume that it holds for
all к < η, and let G be a graph with η vertices that do not contain
a path with length 100. If there is a vertex in G whose degree is
not greater than 49, then remove this vertex and proceed by
applying the induction assumption on the remaining graph. Therefore,
suppose that the degree of every vertex in G is greater than 49.
Consider the maximal path χι, x2,... xm in G, with m < 100. All
the neighbors of x± and xm are among those vertices in the path,
because otherwise we would get a contradiction to the maximality
of m. Since Xi,xm has more than 50 neighbors, it follows from the
pigeonhole principle that there exist 1 < i < m so that
%ί j ·Ετη are
neighbors and Xi,Xi+i are neighbors. Then
•£l j «£2} · · · Xii Xmi %m—li · · · %i+l > %1
is a circuit. If there exists a vertex у connected to one of the
vertices in the" circuit, then there is a path with length m + 1,
contradicting the maximality of m. Therefore in this connection
compound the only vertices are the ones in the circuit. Therefore
in this compound there is at most
(?T) < 49.5m
edges. For the rest of the graph we apply the induction hypothesis,
and find that it has at most 49.5(n — m) edges. Hence G has at
most 49.bn edges.
Equality happens only if m = 100 and this connection compound
is a complete graph. By induction, the rest of the graph must also
consist of if loo connecting compounds.
In particular, if η = 1000 then the graph with he most edges consist
of 10 unconnected i^ioo graphs.

1996
157
6. We start by finding a lower bound to f(k). To that end, we have
to find an example for a connected graph with к vertices that does
not contain a path with length 100. Consider the regular bipartite
graph with 49 vertices on one party and к — 49 vertices on the
other. It is clear that this graph is connected, and since each path
of length m contains at least [m/2] vertices from the first party,
there is no path of length 100 in the graph. In this graph there are
49(fc - 49) = 49fc - 2401
edges.
We now note that we can add to this graph all of the edges
connecting each two vertices from the first party, and the longest path
in the graph will still be less than 100 in length. The number of
edges in this graph is
Щк - 49) + ( 9 J = 49fc - 1225
and hence c\ = 1225.
We now turn to the task of finding an upper bound to f(k).
Definition: A graph G is said to be k-connected if for. every к —
1 vertices in G, the graph received by removing those vertices is
connected, or equivalently, G cannot be partitioned into 2 subgraphs
G\,Gi such that
\V(G1)nV(G2)\<k-l
and if ν is a vertex not in V{G\) Π У(б?2) then ν is not connected
to the vertices in the other subgraph.
Lemma 1: G is a simple, 2-connected graph with η vertices. If
the degree of each vertex is at least k, then G contains either an
Hamiltonian circuit or a circuit with at least 2k vertices.
Proof: Let Ρ = (x0, x±:... xm) be the longest path in the graph.
Clearly, all of the neighbors of Xo,xm are in P. Consider three
cases:
Case I: There does not exist l<i<j<m—1 such that Xj
is connected to connected to xm. Let i be the maximal
index such that Xi is connected to Xq, and let j be the minimal
index for which Xj is connected to xm. Then j > i and all vertices
Xi+i,Xi+2 ■ ■ ■ xj-i are not connected to either xm or x0.

158
6. Team Competition Solutions
Consider the sets A\ = {^1,^2,.. -Xi],Ai = {xj,Xj+i, ■ ■ .xm-i}.
The neighbors of xq are all Αχ while all the neighbors of
in A2, and since the degree of each vertex in G is at least k, it
follows that |Ai|,|A2| > k. Now in a 2-connected graph, every
two vertices are connected by some simple circuit, and therefore
there exist two disjoint paths Ρι,Ρζ connecting A\ and A2, say
-Pi = (xP, ■ ■ -Xq),P2 = (xt, ■ ■ -xs) with p,t < i and s,q > j, with
xp,Xt connected to Xq and Xt,xs connected to xm. Then we can
find a circuit passing through the neighbors of Xq , xm and through
-Ръ-р2> which implies that its size is greater than 2k.
Case 2: There exists an index 0 < i < m — 1 such that Xi is
connected to xm and Xi+i is connected to Xq. Assume that there
is a vertex ν in G such that ν ^ P. Then since G is connected, ν
is connected to Xq and hence is connected to some vertex Xj in P.
Without loss of generality, we can assume j < i. But then
yV, . . . , Xj, 3Jj_|_i, . . . Xi, Xmi Xm—lt · · · Xi+1 j XO: Xl · · · ·> Xj—l)
is a path with length m + 1, contradicting the maximality of P. It
follows that the circuit
, Ж1, . . . Xi , Xrni Xm—11 · · · Хг+1 э Xo)
is Hamiltonian.
Case 3: There exist two vertices Xi,Xj in Ρ such that i < j, Xi is
connected to жт, Xj is connected to Xq and the difference j — г > 2
is minimal. Then the vertices Жг+ι,.. .Xj-i are not connected to
either x0 or xm: because of the minimality oij — i. Since the degree
of Xo,xm is at least к, it follows that ϊ,τη — j > к — 1 and thus the
circuit
, X\, . . . , Xi, Xmi Xm—1 > · ■ ■ Xj ·> Xo)
is with length greater than or equal to 2k.
Lemma 2: If G is a graph with η vertices and over ^ ' edges,
then G has a circuit with size at least к + 1.
Proof: Clearly, we must have к > n. The claim will be proved by
induction on n. The claim holds for η = к + 1, because a graph
,2
with к + 1 vertices and Щ^ edges, contains a Hamiltonian circuit.
Assume that the claim holds for all m < n, and let G be a graph
with η vertices and over ^ ' edges. If there is a vertex in G
with degree not greater than |, remove it and we get a graph with
(Xq
(xo

1996
159
η — 1 vertices and more than -^—- edges, and by our induction
assumption, G has a circuit with size к + 1.
Suppose that all the degrees in G are at least Щ^. If G is not 2-
connected, it follows that we can divide G into two graphs G±, G2
such that
\V(G1)nV(G2)\<l
in the way described above. By the pigeonhole principle, one of
G±,G2 must satisfy the condition of the lemma, or otherwise.we
would have
\E(G)\ = \E{G1)\ + \E{G2)\
< l(W(G1)\ + \V(G2)\)
fc(n-l)
- 2 '
a contradiction.
We can now turn to finding an upper bound for f(k). We claim
that
f(k) < 49fc-49.
Proof: The proof follows easily from the last lemma. If G has
more than 49fc — 49 edges, then from the previous lemma, it has
a circuit of length 100. Since G is connected, it follows that this
circuit is connected to at least one more vertex, and therefore it
contains a path of length 100.

160
6. Team Competition Solutions
2000
1. (a) We use the following lemma: if Μ is a point on the side XY
of triangle XYZ, then
XM _ XZ sin IX Ζ Μ
УМ ~ Υ Ζ sin LYZM
For if h is the altitude from Ζ to XY, then
area(AXZM) _ h-XM _ XZ ■ ZM ■ sin IXZM
area(AYZM) ~ h-YM ~ Υ Ζ ■ ZM ■ sin LYZM '
Let ΑΡι, Β Pi, С Pi meet the opposite sides at Di,Ei,Fi,
respectively, and let their reflections meet the opposite sides at
D2,E2,F2, respectively. Then by the lemma,
BD2 CE2 AF2
CD2 ' AE2 ' BF2
sin LBAD2 sin LCBE2 sin Ζ ACF2
sin 1СAD2 ' smLABE2 ' sin LBCF2
sin LCADy sin LABEi sin LBCFi
sin LBADi ' sin LCBEX ' sin LACFi
CDi AEi BFi
BDi ' CEi ' AFi'
and the result follows immediately from the Ceva's theorem.
(b) The quadrilaterals PiAiCBi and P2A2CB2 are cyclic, and
hence
LAiBiC = LAiPiC
= 90 - LPiCAi
= 90 - LP2CBi
= LB2P2C
= LB2A2C.
Thus the quadrilateral ΑιΑ2Β2Βι is cyclic. ΡιΒιΒ2Ρ2 is a
right-angle trapezoid, and hence the perpendicular bisector of
BiB2 meets PiP2 at M, the midpoint of PiP2. Similarly, the

2000
161
perpendicular bisector of A\ A2 passes through M, and
therefore Μ is the centre of the circle circumscribing ΑιΑ2Β2Βι.
Similarly, the quadrilaterals B1B2C2C1 and C1C2A1A2 are
cyclic, and the centre of the circumscribing circles is M. Hence
A1A2B2B1C1C2 is inscribed in a circle with centre M.
(c) We shall prove the following claim, from which the problem
is easily solved:
If Pi lie on a fixed line passing through the circumcentre of the
A ABC, then the circle A\BiC\ passes through a fixed point
on the nine points circle of AABC.
Proof: Let Ma, Mb and Mc be the midpoints of the sides
ВС, С A and AB respectively. Denote by С, A' and B' the
intersection points of MaMb, MbMc and McMa with ΑλΒλ,
B\C\ and C\A\ respectively. We intend to prove that the
three lines A\A', B\B' and C\C meet at a point L which lies
on the intersection of the nine points circle and of the circle
AXBXCX.
Consider the circumcircle АМьМс. Let La be its second
intersection point with the line P\0 (O being the circumcentre
of AABC). Then lALaO = 90°. Hence the points La, Βλ, d
lie on the circle with AP\ as diameter. Let A[ be the
reflection of A\ with respect to МьМс. Then A[ lies on the line
passing through A and parallel to ВС, and also on the line
A1P1. Hence LAA\PY = 90°, so that A[ also lies on the circle
with AP\ as diameter.

162 6. Team Competition Solutions
A'
We shall now prove that A',La,A\ are collinear. Since La
lies on the circles АМьМс and ABiC\, it follows from the
theorem of Simson that the feet of the perpendiculars from La
to АМь, AMC, ΑιΒι and МаМъ are collinear. Hence La lies
on the circumcircle of Α' Β ι Мъ by the converse of this theorem.
Thus the angles LA'LaB\, 1А'МъВ\ are either equal or their
sum is equal to 180°. We shall consider the first case, and
the proof to the latter case is similar, with the appropriate
modifications.
Since Α, Ρ, Β\ , C\, La and A[ are concyclic, it follows that
LBYLaA\ = LBYAA\
= 180° - ίΑ\ΡΒλ
= 180°- АА'МьВ^
Furthermore,
LA'LaBl = 180° - LBxLaA\.
Therefore A', La and A[ are collinear. Let L be the reflection
of La with respect of МьМс. Then L lies on A\A' and also
on the nine points circle (since reflection through МьМс maps
the circle АМъМс to the nine points circle). Also,

2000
163
Hence L is the intersection of the nine points circle and the
circle AiBiCi. Thus if Pi moves along a fixed line through
O, then the point La, and therefore L, remains fixed.
2. First Solution:
Assume that the ant moves in a direction parallel to the ж-axis,
and starts from the point (a, b) on the given curve. It meets the
curve at the (c, b), where we have
Г a2 + ab + b2 = 6
\ c2 + cb + b2 = 6 '
Subtracting the first equation from the second, we get
(a - c)(a + b + c) = 0,
which implies с = —a — b. Similarly, if the ant moves in a direction
parallel to the y-axis, it meets the curve at (a, —a — b).
Let Ρ = (a, b) be the starting point of the ant, and assume that the
ant starts walking in a direction parallel to the ж-axis (the second
case is analogous). If at some stage during the walk, the ant cannot
move any longer, it stops. Otherwise, its walk is composed of the
following points on the curve:
(a, b) —> (—a — b,b) —> (—a — b,a) —> (b, a) —> (6, — a — b)
—> (a, —a — &)—>· (a, b).
Therefore, the ant returns to the starting point of the walk after
at most six steps.
Second Solution:
Rotate the curve by 45°, by multiplying (x,y) with the matrix
Til -ι ι J'
The equation of the image of the curve under the rotation is
3x2 + y2 = 12.
Hence the curve is an ellipse. The new directions of the paths of
the ant are inclined by ±45° with respect to the ж-axis.
Apply an affine transformation, sending у into -уцУ- The curve is
mapped to the curve
x2 + y2 = 4

164
6. Team Competition Solutions
which is a circle with radius 2. The directions of the paths of the
ant are now inclined by ±30° with respect to the ж-axis.
Denote the centre of the circle by O. Assume that the ant starts
moving while creating an angle of 30° with respect to the ж-axis
from Ρ to Pi and from Pi to P2. Then
ZPP1P2 = 120° => lPOP2 = 120°
Hence, moving twice, the ant rotates around О by 120°. Therfore,
after at most six moves, the ant will return to the starting point.
3. (a) The answer is NO. Assume by contradiction that this
construction can be made using a ruler only. Then the
construction is made using a sequence of straight lines and their point
of intersection.
Perform a projective transformation on the figure, taking С
to another circle С. The lines and their points of intersection
are kept under the transformation, and thus they yield the
point which is the map of the centre of C. On the other hand,
those lines compose a construction which gives the centre of
С. But the centre of С is not mapped to the centre of C",
and thus we arrive at a contradiction.
(b) i. Denote by Ρ and Q the intersection points of C\ and C2-
We shall describe a construction which leads to finding
both centres 0\ and 02 of C\, C2, and all that remains is
to construct О1О2.
Choose a point A inside C\. Construct AP, AQ and let
В, С be their second intersection with C\, and D, Ε their
second intersection with C2. Then
LADE = LAQP = LACB
Thus, DE\\BC. Construct DQ,EP and let F,G be their
second intersection with C\. Then,
LGFQ = LEPQ = IEDQ
Hence, DE\\FG, and it follows that FG\\BC.
Since B, C, F and G lie on C\, then BCGF is an
isosceles trapezoid. Construct Η and J, which are the point of
intersection of BF and CG, and of BG and CF,
respectively. Then Η В = НС, IB = 1С which implies that HI
is the perpendicular bisector of В С, so it passes through
Oi.

2000
165
Choose another point A' inside C\. The same
construction will yield another line through Ο ι, and then we can
construct 0\. Similarly, we can construct O2, and then
we can construct О1О2.
ii. Construct two lines through T. Those lines meet C\ at
A, B and C2 at C,D. We shall prove that AB\\CD. Let
P, Q be points on the common tangent from different sides
ofT. Then
LABT = IATQ = ICTP = LCDT
Hence AB\\BC. Construct AD,ВС and their point of
intersection S. Then S is the external centre of similarity
of C\ and Ci, and hence ST is the line of the centres of
C\,C2-

166 6. Team Competition Solutions
2001
1. We shall use induction on n. The case η = 3 is trivial. Assume
that the claim holds for η — 1, and consider Kn. Let α be a vertex
in Kn, and consider
If it is coloured with at least η — 1 colours, then by the induction
hypothesis we are done. Otherwise, it is coloured with at most
η — 2 colours, say 1,2,... η — 2. The colours η — 1, η must appear
in Кn and hence there exist two vertices Ъ,сф a such that the edge
(a, b) is coloured with colour η — 1 and the edge (a,c) is coloured
with n.
But (6, c) is not coloured with either n—l or η and therefore a,6,с
is a triangle whose sides are coloured with three different colours.
2. We shall use induction on n. For η = 5,
25
e(G5)>- + 2
implies
e(G„) > 9,
so at most one pair of vertices in G5 is not connected. Let a,b,c,d,e
be the vertices and suppose that a, b are not connected. Then
{a,e,c} and {b,,d,c} are two triangles with one common vertex.
Assume that the claim holds for n—l, and consider Gn with
n2
e(Gn)>T+2.
If the degree of some vertex in Gn is lesser than ^, then we can
remove it and the number of edges in the new graph is at least
η2 η η (η— Ι)2
and we can apply the induction hypothesis. Therefore we can
assume that the degree of every vertex is at least ^.
Since the sum of the degrees in Gn is
n2 n2
2 2

2001
167
then there exists at least one vertex a who has degree greater than
η
2 -
Then
Τί
deg(a) > I-J + 1.
Let v\,... vr be the vertices connected to a, with
r>L|j+i
and let u\,..., us be the remaining vertices, with
s = η - r - 1 < [-] - 2.
Now η > 6 and hence r > 4. For every 1 < i < r, the degree of Vi
is at least ^ and hence it is connected to at least one of the other
vertex Vj.
Suppose that v\ is connected to V2· If г>з is connected to a vertex
Vj with j -φ 1,2 then the triangles {a,v\,V2} and {a,V3,Vj} have
one common vertex. Hence we can assume г>з is connected to v\.
For 4 < i < r, if Vi is connected to a vertex Vj with j -φ 1 we are
finished, and hence we can assume that V\ is connected to all of
the vertices г>2, г>з,... vr and that no other pair Vi, Vj is connected.
It follows that each vertex Vi for i -φ 2 is connected to all of the
vertices и j, 1 < j < s and that
Consider the sets A = {v2,v$ .. .vr} and В = {a,Vi,u\ .. .us},
with |A| = [f J and \B\ = [|]. For every χ G A,y G В the pair
ж, ?/ is connected. In addition, a, v\ are connected and no pair from
A is connected. Since
n2
e(Gn)>-+2
then at least one more pair in В must be connected, and therefore
there exist two triangles with exactly one common vertex.
3. Assume by contradiction that the claim does not hold, so Gn does
not contain C4. Let e = e(Gn) and denote by d\,d2 .. .dn be the
degrees of the vertices in Gn. Then
η

168
6. Team Competition Solutions
Let m be the number of triples (a,b,c) of vertices in Gn with a
connected to both b, с (where (a,b,c) and (a,c,b) are considered
identical). Since for every pair b, с there can be at most one vertex
a that is connected to both 6, с (for otherwise Gn contains С4) and
thus m < (2)· On the other hand, every vertex α is a member
of ( 2 ) triples (a,b,c), and hence by the quadratic-arithmetic
means inequality,
n(n-!)^ ^di(di-l) , x V^2 ^ ,22
——^m = L· 2 = -e+222di--e+ne-
i=\ i=\
Rearranging, we obtain 4e2 — 2ne — n2(n — 1) < 0. Hence
2n+v/4n2 + 16n2(n-l)
6 - 8 < 4 + ~2~"
A contradiction,
(a) We shall obtain a stronger result, namely that
e(G„)<-^ + I.
Let d\,d2,.. -dn, m and e be as in the previous problem. In
this case, m < 2(™) since every pair 6,с can have at most two
common neighbours. Then
n{n-l)>m = ±d^^ = -e+\±dl>-e+2-
2^ г ~ η
г=1
and hence
2e2-ne + n2(n-l) < 0.
Therefore
η + \/n2 + 8n2(n — 1) η ПлУп
e < Y Ά " " < Τ + -7^·
4 4 ^2
(b) Here also we shall prove a stronger result: the claim holds for
every value of n.
Consider the graph Gn which has the points Pi, P2,... Pn as
vertices and every two points Pi, Pj are connected if and only
if PiPj has unit length.
If P, Q are two points in the plain then there are exactly two
points in the plane that have unit distance from both Ρ and

2001
169
Q. Therefore, the graph Gn does not contain Ksi2 and hence
by (a),
e{Gn) < - + -¥=- < nv^
The last inequality holds for every η > 2. If η = 1 there is
nothing to prove.
Comment: In fact, there is a stronger bound for e(Gn), which
is in 0(η-ξ/η).
5. In the following problem, equality means equality in the field of
residues modulo the prime p.
(a) Assume by contradiction that (xi>2/i), (2^2,2/2), (хз,Уз) and
(^4,2/4) form a C4. Then
Ж1Ж2 + Ш2/2 = 1
Ж2Ж3 + ?/2?/3 = 1
Ж3Ж4 + 2/32/4 = 1
x±x\ +УаУ\ = 1.
Subtracting the first two equations and the last two equations
yields
x2(xi - хз) = ~У2{У\ ~ Уз)
2/4(2/1 - Уз) = -Ха{х\ ~ хз)·
Multiplying both equations, we obtain
(xi ~ Хз){У\ ~ Уз){х2Уа ~ У2Х4) = 0.
Similarly,
(ж2 - Х4)(У2 ~ Уа){х\Уз ~ У\Хз) = 0.
If, for example x\ = Ж3 then 2/12/2 = 1—Ж1Ж2 = 1—Ж3Ж2 = У2У3
and hence either у ι = 2/з, which is impossible since (x\ ,2/1)7^
(%з,Уз) by assumption, or y2 = 0. Similarly, 2/4 = 0. But
then Ж2Ж1 = 1 = Ж1Ж4 and thus X2 = X4, a contradiction.
We conclude that no two elements from the pairs {х\,хз},
{x2,X4J, {ш,г/з} and {2/2,2/4} are equal.
Therefore Ж12/3 = £32/1 and Ж22/4 = Ж42/2· Using the first two
equations, we obtain
ХЗ = Ж1Ж2Ж3 + У1У2ХЗ = Ж1Ж2Ж3 + X\ 2/22/3 = X\-
And thus we arrive at a contradiction.

170
6. Team Competition Solutions
(b) We shall prove a stronger result, that there exist infinitely
many values of η such that there exist a graph Gn that does
not contain С4 and
e(Gn) > — + — ·
Consider the graph from part (a). The number of vertices in
this graph is clearly η = p2.
We shall investigate the degree of each vertex. Let ν = (χ, у)
be a vertex in G. If χ = 0, у = 0 then ν has degree 0.
Otherwise, if χ φ 0 then for every ?/ there exists a unique
ж' = х~1(1-уу')
such that (x',y') is connected to v. The case where у ^ 0
is similar, and in both cases the degree of ν is p. Hence, the
total number of edges in the graph plus the number of loops
in the graph is equal to \p{p2 — 1)· The number of loops in
the graph can be at most 2p, since for every x, there exists at
most two values of у such that 1 — x2 = y2. Hence G has at
most
lob 1 ,— 0 .—

7. CLASSIFICATION OF
PROBLEMS BY TOPIC
Individual Problems
Plane Geometry
90/2, 91/2, 93/3, 94/3, 95/2, 97/3, 97/5, 98/5, 00/3, 01/2, 01/5.
Functions
91/1, 93/2, 95/3, 99/1, 99/3, 99/5, 01/3, 01/4.
Sequences
90/3, 91/3, 92/3, 93/2.
Trigonometry
98/2.
Number Theory
90/1, 93/1, 95/1, 96/1, 96/2, 97/1, 98/3, 98/4, 99/4, 00/2, 00/5,
01/1.
Equations and Inequalities
91/4, 92/1, 94/2, 96/4, 97/2, 00/6.
Combinatorics
92/2, 94/4, 95/4, 96/3, 97/4, 97/6, 98/1, 98/6, 99/2, 99/6, 00/1,
00/4.
Miscellaneous
90/4, 92/4, 93/4, 94/1, 01/6.
Team Problems
The topics of the team competition problems
1990 Continued fractions.
1991 Polynomials.
1992 Sequences.
1993 Groups.
1994 Algorithms in graph theory.

172
7. Classification of Problems by Topic
1995 Algebraic curves.
1996 Graph theory.
2000 Geometry (transformations, constructions).
2001 Extremal graph theory.

8. LIST OF CONTESTANTS
1990
1991
1992
1993
1994
Hungarian Contestants
Balogh Jozsef
Matolcsi Mate
Kondacs Attila
Czirok Andras
Hungarian Contestants
Boncz Andras
Harcos Gergely
Turanyi Zoltan
Ujvary- Menyhart Zoltan
Hungarian Contestants
Ujvary-Menyhart Zoltan
Almos Attila
Futo Gabor
Szendroi Balazs
Hungarian Contestants
Katz Sandor
Futo Gabor
Csornyei Marianna
Kalman Tamas
Hungarian Contestants
Csornyei Marianna
Futo Gabor
Koblinger Egmont
Parniczky Benedek
Israeli Contestants
Alon Gil
Lapid Erez
Ladkany Sephi
Meiraz Guy
Israeli Contestants
Alon Gil
Braverman Alexander
Gemintern Alexander
Ladkany Sephi
Israeli Contestants
Angel Omer
Mangovy Dan
Pinhasy Rom
Vanunu Avishay
Israeli Contestants
Angel Omer
Borde Yuri
Nehushtan Oren
Vanunu Avishay
Israeli Contestants
Iorsh Maxim
Shkolnikov Hagay
Yager David
Zilberman Lior

174
8. List of Contestants
1995
1996
1997
1998
1999
2000
Hungarian Contestants
Szadeczky-Kardoss Szabolcs
Koblinger Egmont
Valko Benedek
Burcsi Peter
Hungarian Contestants
Burcsi Peter
Gyarmati Katalin
Ba'ra'sz Miha'ly
Groller kos
Hungarian Contestants
Br aim Gab or
Pap Gyula
Frenkel Peter
Lippner Gabor
Toth dm
Hungarian Contestants
Lippner Gabor
Lukacs Laszlo
Zubcsek Peter-Pal
Berczi Gergely
Hungarian Contestants
Gyenes Zoltan
Kiss Gergely
Terpai Tamas
Zabradi Gergely
Hungarian Contestants
Csikvari Peter
Gyenes Zoltan
Vizer Mate
Zabradi Gergely
Israeli Contestants
Iorsh Maxim
Buhovsky Lev
Radzivilovsky Lev
ZukOr
Israeli Contestants
Buhovsky Lev
Carmiel Yishay
Desiatnikov Eli
Radzivilovsky Lev
Israeli Contestants
Carmiel Yishay
Dovgard Roman
Heller Yuval
Yuval Tom
Israeli Contestants
Dovgard Roman
Keller Natan
Puder Doron
Simkin Michael
Israeli Contestants
Braverman Mark
Lang Oran
Tessler Ran
Yuval Amitay
Israeli Contestants
Antin Alexey
Braverman Mark
Lang Oran
Tessler Ran

8. List of Contestants
175
2001
Hungarian Contestants
Csikvari Peter
Csoka Endre
Harangi Viktor
Horvath Illes
Voros Laszlo
Vizer Tibor
Israeli Contestants
Antin Alexey
Assaf Eran
Lang Oran
Shafrir Doron
Shein Aviv
Tessler Ran

9. GLOSSARY
In this chapter we cite several well known facts that were used in the
book, and which may be nonstandard in regular high school curriculum.
The triangle inequality
For any two real numbers a, b,
\a + b\ < \a\ + \b\.
This inequality holds also for complex numbers. In such cases,
when ζ = χ + iy, \z\ can be interpreted as the distance of the point
(x, у) from the origin.
The Cauchy-Schwartz inequality
For any two sequences of real numbers
аьа2,...,ап and 61,62, - - ·, Ьта
of η the following inequality holds
y^^ajbj
<
i=\
\ЪаЬ\
Σ»ι
i=\
Equality holds if there exists a real number A such that a^ = Xbi
for all 1 < i < n.
Pell's equation
The diophantine equation
x2 - dy2 = 1
where the given integer d is not a perfect square.
If (xo,yo) is the smallest solution where xo, and y0 are positive,
then all solutions can be expressed by
χ + yy/d = ±(x0 + y0Vd)n, nGN.

178
9. Glossary
Fibonacci sequence
The sequence Fn defined by the recurrence relation
Fn = -Fn-l + Fn-2
for η > 2 with Fq = Fi = 1 is called Fibonacci sequence.
Fn can be expressed explicitly by means of (Binet's formula)
Pythagorean triples
Three positive integers x,y,z satisfying x2 + y2 = z2 are called a
Pythagorean triple. The name stems from Pythagoras' Theorem
satisfied by the sides x,y,z of a right angled triangle.
Any Pythagorean triple x, y, ζ for which x, y, ζ are relatively prime,
can be expressed by χ = m2 — n2, у = 2mn (or χ = 2mn, у =
m2 — n2) and ζ = m2 + n2, for some relatively prime positive
integers m, n.
The Sine Law
If AABC is a triangle whose sides are a, 6, с and the corresponding
angles are α, β, 7, then
h
= 2R,
sin a sin β sin 7
where R is the circumradius of AABC.
The Cosine Law
If AABC is a triangle whose sides are a, b, с and the corresponding
angles are α, β, 7, then
a2 = b2 H- c2 — 26c cos a,
62 = c2 H- a2 — 2cacos/3,
c2 = a2 Ч-62 -2abcos7.
The inradius of a right angled triangle
Let a, b be the sides of a right angled triangle, с its hypotenuse and
r its inradius. Then
r = -(a + b-c).

9. Glossary
179
The relation between the inradius and the circumradius
in a triangle
Let R and r be respectively, the circumradius and the inradius of
AABC. Then R > 2r and equality holds only for an equilateral
triangle.
The product law for chords in a circle
Let PQ and RS be two chords in a circle C, and let Τ be their
intersection point. Then
PT-QT = RT- ST = k.
If Τ is outside the circle C, and TU touches С at the point U, then
к = TU2.
The area of a triangle
Let ABC be a triangle with
sides a = ВС, b = С А, с = AB,
angles a = IB AC, β = LABC, 7 = LCAB.
Let the inradius and the circumradius be r and R, respectively.
Then the area S of AABC is given by
S = -be sin a
2
= -acsin/3
= -absin7
= 2R2 sin a sin β sin 7
= -r(a + b + c)
abc
4R

180
9. Glossary
A property of the common divisor
If с is a common divisor of the integers a and b, then for every pair
πι, η of integers, с divides ma + nb.
Divisibility of polynomials
Let f(x) be a polynomial of degree n.
If /(a) = 0, then f(x) = (x — a)g{x) where g(x) is a polynomial
whose degree is η — 1.
Viete formulae
Let
n-l
f(x) = xn + Σ αίχί
i=0
be a polynomial of degree η and let r\,..., rn be its roots, i.e.
η
1(х) = Ц(х-п)
г=1
Then
η
an-i = -^Vi, ап-2 = ^2,пг^ ..
г=1 *.д
The Pigeonhole principle
Suppose that the η sets 5i,... ,Sn contain m elements, and suppose
that m > kn for some positive integer k. Then, at least one of the
sets Si contains more than к elements.
The Arithmetic Mean - Geometric Mean (AM - GM)
inequality
Let d\, a2,..., an be some η real positive numbers. Then
«i + «2 + l· an ^ ,
> ναια2 · · · αη·
η
and equality is attained if and only if a\ = u2 = · · · = an.
The fundamental theorem of the algebra
A polynomial of degree η has exactly η complex roots (not
necessarily distinct).
αο = (-1)ηΠ'
i=\

9. Glossary
181
Local minimum and local maximum of a function
Let f(x) be a differentiable function in the interval I = (a,b).
Then, at each point с Ε I where f(x) assumes a local minimum or
a local maximum, we have /'(c) = 0.
Abel's summation formula (summation by parts)
Let di and bi, i = 1, 2,..., η be two sequences of numbers. Then
та та / j \
where bn+i = 0.
Jensen's inequality
Definitions: Let / be a real function defined on the interval I. The
function / is called convex on the interval I if /(Arc + (1 — X)y) <
Xf(x) + (1 — X)f(y) for any x,y £ I and any 0 < A < 1.
If / is twice differentiable, and f"{x) > 0 for all χ G I then / is
convex on I (note: this is a sufficient but not necessary condition).
Jensen's inequality: Let / be convex on the interval I. Suppose that
X\, X2, ■ ■ ■, xn are η points in I and Ai, Аг,..., An are η nonnegative
numbers satisfying Ai + Аг + ·.. + An = 1. Then
/та \ та
/ Ete <ΣΑ^)·
\г=1 / г=1
Euler's formula
Let G be a planar graph (or a polyhedron). Let the number of its
faces be /, the number of its edges be e, and the number of its
vertices be v. Then,
f+v=e+2

tfi Р\(я-р)/я
1
Professor Shay
Gueron got his
PhD. in applied
mathematics from
the Technion
l.l.T.in 1991, and
is now a faculty
member of the
department of
mathematics at
the University of Haifa, Israel. His research
is in applied mathematics: mathematical
biology, and computations.
Prof. Gueron is also interested in problem
solving and mathematical competitions.
He founded and runs a national project
for mathematics competitions in Israel.
Together with the late Professor Joe Gillis,
and with Mr. Janos Patake of Hungary, he
founded the Israel-Hungary mathematical
competition in 1990, and has since been
association with it.
Prof. Gueron has been the Israeli Team
Leader for the International Mathematical
Olympiad since 1994.
The Australian Mathematics Trust
Enrichment Series
ISBN 1876420154
9 781876 420154