POLISH AND AUSTRIAN
MATHEMATICAL OLYMPIADS
1981-1995
ME KUCZMA a E W1ND1SCHBACHER
a.
c\
\2
l-OAi-OAj + (OAi)
V
u
(p
pzvz
an Australian Mathematics Trust publication
u
)
azuz

POLISH AMD AUSTRIAN
MATHEMATICAL OLYMPIADS
1981-1995
-Selected Problems with
TVIlJLTlTn^JSOLlJTlOlNIS
• OX, ■ OA*j + (OAif
(P
9 9
ME KUCZMA 8t E WINDISCUBACHER
-JSj
?/,
o
J
9

Published by
Australian Mathematics Trust
Australian Mathematics Trust
University of Canberra ACT 2601
AUSTRALIA
Copyright ® 1998 Australian Mathematics Trust
Telephone: +61 2 6201 5137
AA/1T0S Pty Ltd ACN 058 370 559
National Library of Australia Card Number and ISSN
Australian Mathematics Trust Enrichment Series ISSN 1326-0170
Polish and Austrian Mathematical Olympiads 1981-1995
ISBN 1 876420 02 2

The Australian Mathematics Trust
Enrichment Series
Editorial Committee
• Chairman Graham H Pollard, Canberra Australia
• Editor Peter J Taylor, Canberra Australia
Warren J Atkins, Canberra Australia
Ed J Barbeau, Toronto Canada
George Berzsenyi, Terra Haute USA
Ron Dunkley, "Waterloo Canada
Walter E IVIientka, Lincoln USA
NlKOLAY K0NSTANT1N0V, MOSCOW RUSSIA
Andy Liu, Edmonton Canada
Jordan B Tabov, Sofia Bulgaria
John Webb, Cape Town South Africa
The books in this series are selected for the motivating, interesting
and stimulating sets of quality problems, with a lucid expository style
in their solutions. Typically, the problems have occurred in either
national or international contests at the secondary school level.
They are intended to be sufficiently detailed at an elementary level
for the mathematically inclined or interested to understand but, at
the same time, be interesting and sometimes challenging to the
undergraduate and the more advanced mathematician. It is believed
that these mathematics competition problems are a positive
influence on the learning and enrichment of mathematics.

The Australian Mathematics Trust
Enrichment Series
Books in the Series
1 All the Best from the Australian Mathematics Competition
JD Edwards, DJ King ft PJ O'Halloran
2 Mathematical Toolchest
AW Plank ft NH 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 AMC
W Atkins
6 Tournament of Towns questions and solutions 1980-1984
PJ Taylor
7 Tournament of Towns questions and solutions 1989-1993
PJ Taylor
8 The Asian Pacific Mathematics Olympiad
H Lausch
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 IMakos ft G Vardaro
11 USSR Mathematical Olympiads 1989-1992
AM Slinko
12 Australian Mathematical Olympiads 1979-1995
H Lausch ft PJ Taylor
13 Chinese Mathematics Competitions and Olympiads 1981-1993
A Liu
14 Polish and Austrian Mathematical Olympiads 1981-1995
ME Kuczma ft E Windischbacher

FOREWORD
The traditions of National Mathematical Olympiads in many European
countries dates back to about 1950 (in some cases further back). These
Olympiads are used, inter alia, to select national teams to participate in
the International Mathematical Olympiad.
The traditions of the Polish and Austrian Mathematical Olympiads are
particularly strong, and to a certain extent they are linked, since together
they developed the Austrian-Polish Mathematical Olympiad, one of the
world's strongest regional events.
As the reader will determine, the problems in this book are quite
exquisite, having been hand-picked from the problems of many years. They are
also noted for having multiple independent solutions, making the
mathematics so much richer. There can be little more satisfying than finding
a different, independent solution to a known one. Being mathematics, of
course, the result is always the same after having taken a quite different
route.
The authors of this book have many decades of experience at this level.
Of the two, I have only had the pleasure of personally knowing Dr
Kuczma. Dr Kuczma has one of the world's highest reputations in
problem creation. Indeed, he has had no less than four of his problems posed
in International Mathematical Olympiads. Further, he has had many
more reach the final preselection stage. He is also equally renowned as
a problem solver. From mutual acquaintances and examination of the
work in this book, Erich Windischbacher is held in no less regard.
The Australian Mathematics Trust aims to set a high standard of
material and exposition in this Enrichment Series. The contents of this series
involve pedagogical material in problem solving and instructive problems
which have not appeared before in English. We are confident that this
book achieves the high standards to which we have aimed.
Peter Taylor
Executive Director
Australian Mathematics Trust
Canberra
4 August 1998

PREFACE
Mathematics Olympiads have a long tradition in Poland as well as in
Austria, and they have many features in common in both these countries.
Academic supervision comes from the Mathematical Societies and from
university centres. Financial support is provided, in the greatest part, by
the Ministries of Education (the exact official name of that institution,
in each country, has changed several times during the past decades).
The effective running of the competitions relies on people (high school
teachers and university teachers) whose enthusiasm and devotedness is
practically the sole motive for their activities.
The organizational format is much the same in the two countries.
Contestants are high school students, most of them attending the last or
the last but one grade. College students are not allowed to participate.
The final round of the Austrian MO and of the Polish MO is a two day
written exam, with three problems to be solved each day — just like the
IMO. As regards earlier stages, there are some differences; but, anyhow,
each elimination round consists of problem solving. All the problems
posed at our olympiads are essay type; all steps of the reasoning have
to be explained and justified by the solver — short answer questions or
multiple choice questions are not used.
In the late seventies, a bilateral agreement on cultural exchange was
concluded between the Polish and the Austrian Ministers of Education.
This resulted, in particular, in frequent visits of scientists and teachers,
from one country to the other, and has led to exchange of experience —
for instance, in the organization of math olympiads (remember that, in
those years, Austria and Poland pertained to distinct political zon§s of
Europe). It is also in that time that the Austrian-Polish Mathematics
Competition was launched.1
The authors of the present book are just two of those "enthusiasts of the
Olympic idea in mathematics", for many years involved in the running of
the national mathematics olympiads in Poland and in Austria. It is quite
a time ago that we first met. Soon the idea occurred to us to present, in
book form, a selection of our countries' olympiad problems.
As a guideline for the selection, we have decided to take the diversity of
methods of solution. Accordingly, each problem in this book is presented
1A compilation of all the problems posed at the first sixteen rounds of that
competition, with complete solutions, has appeared in book form: ME Kuczma, Problems.
144 problems of the Austrian-Polish Mathematics Competition 1978-93, published
1994 by: The Academic Distribution Center, 1216 Walker Rd., Freeland, Maryland
21053, USA.

viii
Preface
with at least two solutions, and sometimes more than two; this feature of
the book we consider important enough to be reflected in the sub-title.
It is obvious that various ways of approach to any problem provide a
better understanding of its nature, reveal several aspects of the relevant
topics and teach various techniques.
Now, it can always be questioned whether a different solution is a really
different one. In some rare cases, it can be justly considered as such.
In many cases, it cannot — and this is evident at first glance. And in
most other cases — also not; the "second" method can use other
symbols, language, terminology, it may look quite unlike the "first" one, and
still be, in fact, the same. For instance: is the Law of Cosines
anything else than operating with vectors and their inner products? Is the
examination of divisibility of polynomials via manipulation in real
domain anything essentially different from complex roots and factorization
technique? Combinatorial arguments, when disguised in the language
of polynomials (in fact, the generating functions of the quantities
under consideration), do they really differ from the analogous arguments
presented in pure form, without disguise?
This list can be continued, of course. Viewed from a certain level of
professionalism, all or almost all approaches to a particular olympiad-
style problem are just like dressing the same idea in a robe of one or
another colour. What can be, however, immediately recognized by a
mathematician, need by no means be evident to a young student who
just makes the first steps in off-curricular areas of mathematics.
Indeed, we think that — besides getting acquainted with various tools
and tricks supplied by various methods — the reader's own discovery
of the intrinsic uniformity hidden behind apparently distinct ways of
approach is the true profit she or he can have from studying those solutions,
and is the best we can offer her or him.
Most of our solutions have been elaborated in detail. The intention was
to make them accessible to a rather wide audience; some readers will
find them unnecessarily lengthy, perhaps. We are sure that the readers'
invention will often go further; no doubt, they will find yet other ways
of resolving this or that problem, possibly more elegant or more general
than the presented ones. So much the better! Satisfaction from a good
job done is the solver's true reward.
(Another kind of satisfaction comes from detecting the authors' errors
and mistakes; these are also very instructive!)
There is one more thing we must mention here. There should be no
surprise if a problem turns out to be identical or very closely related to a
question that had appeared at some other competition or in the problem
section of some journal. It is no secret that problems "circulate" and

Preface
ix
are being "borrowed" from one competition to another. There is also
nothing paradoxical in the fact that very similar ideas occur to people
who independently devise olympiad stuff, in distant parts of the globe.
Although we have tried to avoid the use of problems of which we knew
to have been used elsewhere, we can by no means be sure...
We are presenting 64 problems (a beautifully round number) from the
two national olympiads, half from the Austrian, half from the Polish.2
They are arranged more or less thematically; the rough rules are easy to
spot. Such rules can never be quite univalent; a problem may be difficult
to classify; it can pertain to more than one thematic area, sometimes
depending on the solution method.
The arrangement has nothing to do with the level of difficulty; quite
challenging problems often follow or are followed by trivially simple ones.
The reader should not know "what to expect next".
We will be happy to receive any feedback from the readers: comments,
communication about mistakes, any suggestions. We wish all the readers
joy, fun and pleasure in tackling the problems.
Martin E Kuczma Erich Windischbacher
Institute of Mathematics Bundesrealgymnasium
University of Warsaw Keplerstrafie 1
ul. Banacha 2 A-8020 Graz
PL-02-097 Warsaw Austria
Poland
2Problems from the Austrian MO: 1, 4, 5, 7, 9-12, 16-19, 23, 28-30, 32-35, 37,
38, 43, 52, 53, 55-61.
Problems from the Polish MO: 2, 3, 6, 8, 13-15, 20-22, 24-27, 31, 36, 39-42, 44-51,
54, 62-64.

ACKNOWLEDGEMENTS
We are happy to see our book appearing as an AMT publication.
Our sincere thanks go to Professor Peter Taylor, the executive director
of the AMT, for his invitation to publish this book in the AMT
Enrichment Series and for his help in typesetting/formatting; and to Dr Andrei
Storozhev for producing the diagrams.
MEK & EW
May, 1998

CONTENTS
FOREWORD
PREFACE
ACKNOWLEDGEMENTS
PROBLEMS
Arithmetic and Combinatorics
Algebra
Geometry
SOLUTIONS
Arithmetic and Combinatorics
Algebra
Geometry
V
vii
xi
3
6
11
15
57
117

< a
>^
a
n
an-l + 1
h
1
• # • • m I t& a

Problems: Arithmetic and Combinatorics
1. Show that 2^3") + 1 is not divisible by 17, for any integer n > 0.
2. Let a, b, c be positive integers with the properties: a3 is divisible
by b, b3 is divisible by c, c3 is divisible by a. Show that (a+fe+c)13
is divisible by abc.
Ln/3J / n \
3. For every integer n > 2 show that the number V^ (—l)fcl J is
divisible by 3. fc=o ^ '
(The symbol [x\ denotes the Greatest Integer Function.)
4. Calculate the sum of all divisors of the form 2X • 3y (with x, y > 0)
of the number N = 1988 - 1.
5. Show that there do not exist four successive integers whose product
is 1993 less than a perfect square.
6. Show that there are infinitely many positive integers n such that
each one of the three numbers n — 1, n, n + 1 can be represented
as the sum of two perfect squares.
7. Show that the following system of simultaneous equations has no
solution in integers:
x — Zxy -\- 3y — z = 31
-x2 + Qyz + 2z2 = 44
x2 + xy + 8z2 = 100.
8. Solve the following equation in integers x, y:
x2(y-l)+y2(x-l) = l.
9. If a;, y, z are integers, at least one of which is 1990, show that
x2 + y4 + z6 > xy2 + y2z3 + xz3.

4
Problems
10. Consider the sequence xo = 0, x\ = 1,
xn+2 — 3xn+i £Xn
for n = 1, 2, 3, Define yn = x\ + 2n+2. Show that yn is the
square of an odd integer, for every non-negative integer n.
11. The sequence (an) is defined recursively by
a-n-i + *
ao = 1, ai = 2, an = for n = 2,3,4,....
Show that each an is an integer.
12. Find all functions / mapping non-negative integers into
non-negative integers and such that /(/(n)) + f(n) = 2n + 6 for every integer
n > 0.
13. Show that [nV3\ is a power of 2 for infinitely many natural
numbers n.
(The symbol [^J denotes the Greatest Integer Function.)
14. Four numbers are randomly chosen from the set {1,2,..., 3n} (n
is a fixed integer greater than 1). Compute the probability that
the sum of those four numbers is divisible by 3.
15. For what natural numbers n is it possible to tile the n x n-chess-
board with 2x2 and 3 x 3-squares?
16. A triangular prism is a pentahedron whose two parallel faces ("top
base" and "bottom base") are congruent triangles and the
remaining three faces are parallelograms. We are given four non-coplanar
points in space. How many distinct triangular prisms having the
four given points as vertices are there?
17. Consider the infinite chessboard with squares coloured white and
black, in the usual manner. Suppose S is a set of 1976 squares such
that every two squares in S can be connected by a path consisting
of consecutively adjacent squares. (Two squares are adjacent if
they have a common edge.) Show that there are at least 494 white
squares in S. Moreover, show that 494 is the exact bound.

Arithmetic and Combinatorics
5
18. Consider an alphabet consisting of three symbols a, b, c. How many
n-character words with the following properties (1) and (2) can be
composed?
(1) the word should begin and end with an a;
(2) neighbouring positions must be occupied by different symbols.
19. Nine trucks follow one another, in a line, on a highway. At the
end of a day's ride it turned out that each driver disliked the style
of the driving of the one in front of him. They wish to rearrange
themselves so that, next day, no truck would follow the same truck
that it followed on the first day. How many such rearrangements
are possible?
20. We are considering paths (Po, A, • • •, Pn) of length n over lattice
points in the plane (i.e., points (x,y) with integer coordinates); for
each i, the points Pi-\ and Pi are assumed to be adjacent on the
lattice grid. Let F(n) be the number of those paths that begin in
Po = (0,0) and end in a point Pn lying on the line y = 0. Prove
that F(n) = (2^).

Problems: Algebra
21. Determine all real polynomials P(x) of degree not exceeding 5, such
that P(x) + 1 is divisible by (x — l)3 and P(x) — 1 is divisible by
(x + 1)3.
22. Prove that the polynomial xn + 4 factors into the product of two
polynomials of lower degrees with integer coefficients if and only if
n is divisible by 4.
23. Find all natural numbers n for which the polynomial
Pn(x) = x2n + (x + l)2n + 1
is divisible by the trinomial T(x) = x2 + x + 1.
24. For every positive integer k show that the polynomial
Pfc(x) = (x4 - 1) (x3 - x2 + x - l)k + (x + ljx4*-1
is divisible by the binomial x5 + 1.
25. Find all pairs of real numbers a, b such that the polynomials
P(x) = x4+ 2ax2' + 4bx + a2 and Q(x) = x3 + ax + b
have two distinct common real roots.
26. Let a, x, y, z be real numbers such that
cos x + cos y + cos z sin x + sin y + sin z
cos(x + y + z) sin(x + y + z)
Prove the equality: cos{y + z) + cos(z + x) + cos(x +y) = a.
27. If a, b, c are pairwise distinct real numbers, show that the value of
the expression
a — b b — c c — a
1 + ab 1 + be 1 + ca
is never equal to zero.

Algebra
7
28. Solve the system of equations:
x + y + xy = 19, y + z + yz = 11, z + x + zx = 14.
29. Solve the system of equations
xi(xi - 1) = x2 — 1
x2{x2 - 1) = x3 - 1
Xn\Xn 1) — X\ 1
in real numbers x\,..., xn.
30. Solve the system of equations
o o ^^U * / 2
x +y -\ = 1, y/x+y — x -y
x + y
in real numbers x, y.
31. Solve the system of equations
x2 + y2 + z2 = 2, x + y + z = 2 + xyz
in real numbers x, y, z.
32. Let n > 3 be a fixed integer and let a, b, c be fixed real numbers
with a + b + c = 0. Find all n-tuples (xi,..., xn) of real numbers
satisfying the system of simultaneous inequalities
axi-i + bxi + cxi+i > 0 for i = 1,..., n,
where by definition xq — xn, xn+i = x\.
33. Let a, b, c be the sides of a triangle. Show that
a b c
+ + < 2.
b + c c + a a + b
34. Let a, b, c, d be positive real numbers with abed = 1. Show that
a2 +b2 +c2 + d2 + ab + ac + ad + bc + bd + cd> 10.

8
Problems
35. Let a, b be non-negative real numbers with a2 + b2 = 4. Show that
ab
<>/2-l
a + b + 2
and determine when equality holds.
36. The real numbers a^, bi, Ci, di are such that 0 < Cj < a^ < &j < di
and a* -t- &j = a + di for i = 1, 2,..., n. Prove the inequality
n n n n
Y[cn+Y[t>i < Y[ci+Y[di
i=l i=l i=l i=l
37. Prove the following inequality for all integers n > 1:
•l + (n + l)"+1\w-\ /1+n'
n + 2 / ln+1
38. Let n > 9 be an integer. Which one of the numbers (\/n)
and (yjn + 1) is greater?
/n+T
39. Prove the inequality
"In
n
%i<4n for n = 1,2,3,
40. Prove that the inequality
^ VZ-' m + n/ ~~
holds for any real numbers a\, a,2, • ., ar. Find conditions for
equality.
41. For a fixed integer n > 1 find the least value of the sum
,x2,xl, ,<
xi + —+ — + ■■■-{ ,
2 3 n
given that x±,..., xn are positive numbers satisfying
1 1 1
1 1 H = n.
xi x2 xn

Algebra
9
42. On a given segment AD, find points B and C so as to maximize
the product of the lengths of the six segments AB, AC, AD, BC,
BD, CD.
43. Find all functions /:R —> R satisfying the equation
x2f(x)+f(l-x) = 2x-x4 for xeR.
44. Let A and B be real numbers different from zero. Prove that the
function f(x) = A sinx + B sin(-\/2 • x) is not periodic.
45. Find all monotonic functions /: R —> R satisfying the equation
/(4x) - /(3a;) = 2x for x eR.
46. A sequence ao, a\, a^,... of real numbers different from zero is
generated according to the rule: an+\ = (a^ — l)/(2an). Show that
it contains infinitely many positive terms and infinitely many
negative terms.
47. Four sequences of real numbers
ao,ai,a,2,..., &o, &i, &2> • • • > c0, c\, C2, ■ ■ ■, ^0,^1,^2,...
satisfy the simultaneous recursions
Un+l — an + bn, bn+i = bn + cn, cn+i = cn -f- dn, <2n+i = dn + an
for n = 0,1,2, Suppose there exist integers k, r > 1 such that
afc+r = afc, &fc+r = &fc, cfc+r = cfc, rffc+r = dk-
Piove that ai = &i = ci = di = 0.
48. The sequences xo,xi,xq,, ■ ■ ■ and yo,yi,y2, ■ ■ ■ are defined by:
^o = 2/o = 1,
*n + 2 yjj + 2 , n , 0
^n+i = TT ' S/n+i = "i; tor n = 0,1,2,
Show that j/n = a;2n-i for every integer n > 0.

10
Problems
49. Two sequences of integers 0,1,0,2,0,3,... and &i,&2>&3>--- are
defined uniquely by the equality (2 + y/3 ) = an + bnV3. Compute
lim (an/bn).
n—>oo '
50. The sequence (xn) is defined by
1 2n-3
xi = -, xn = — xn_i for n = 2,3,4,... .
Prove the inequality
xi + x2 + • •" + xn < 1 f°r n = 1,2,3,... .
51. A sequence of real numbers 00,01,02,- ■. satisfies the recurrence
Wn\ — ttn-i + Q-n+i for n = 1,2,3,.... Show that an+g = an for
all n.

Problems: Geometry
52. Construct a right triangle ABC with a given hypotenuse c such
that two of its medians are perpendicular.
53. Let ABC be a triangle, AC ^ BC. Assume that the internal
bisector of angle ACB bisects also the angle formed by the altitude
and the median emanating from vertex C. Show that ABC is a
right triangle.
54. If ABCDEF is a convex hexagon with AB = BC, CD = DE,
EF = FA, prove that the altitudes (produced) of triangles BCD,
DEF, FAB, emanating from vertices C, E, A, concur.
55. Let ABCDEF be a regular hexagon with M and N points on
diagonals CA and CE (respectively) such that AM = CN. If M,
N and B are collinear, prove that AM — AB.
56. Let ABC be an acute triangle with altitudes BD and CE. Points
F and G are the feet of perpendiculars BF and CG to line DE.
Prove that EF = DG.
57. Consider the right triangle ABC with LC = 90°. Let Ai and Bi
be two points on line AB (produced beyond A and B) such that
AA\ = AB = BB\ and let N be the foot of the perpendicular from
Ai to line B\C. Show that the rectangle with sides B\C and CN
has area twice as large as the square with side AB.
58. Let ABCDE be a convex pentagon inscribed in a circle. The
distances from A to lines BC, CD, DE, and BE are a, b, c, and d,
respectively. Express d in terms of a, b, c.
59. Let ABC be an isosceles triangle with base AB. Let U be its
circumcentre and M be the centre of the excircle tangent to side
AB and to sides CA and CB produced. Show that
2-CU < CM < A-CU.

12
Problems
60. The diagonals AC and BD of a convex quadrilateral ABCD
intersect in E. Let Fi, F2 and F be the areas of triangles ABE, CDE
and quadrilateral ABCD, respectively. Show that
\[F~\ + \[f~2 < v^F •
When does equality hold?
61. Let P1P2 be a fixed chord (not a diameter) of a circle A;. The
tangents to k at Pi and P2 intersect at Ao. Let P be a variable
point on the minor arc P\P2- The tangent to A; at P intersects lines
AqP\ and A0-P2 at A\ and A2, respectively. Determine the position
of P for which the area of triangle A0A1A2 is a maximum.
62. Let P be a point inside a parallelepiped whose edges have lengths
a, b and c. Show that there is a vertex whose distance from P does
not exceed |\/a2 + b2 + c2.
63. Do there exist two cubes such that each face of one of them meets
each face of the other one (possibly at an edge or a corner)?
64. Let A\, A2, A3, A\ be points on the sphere circumscribed about
the regular tetrahedron with edge 1 such that AiAj < 1 for i ^ j.
Prove that these four points lie on one side of a certain great circle
of the sphere.

-■.::■ ■-'■'■■^
m
■**a \
■ ■**'
2 a
a
cot —-
(3 7
tctll — ~r t£in —

Solutions: Arithmetic and Combinatorics
Problem 1
Show that 2(3") + 1 is not divisible by 17, for any integer n > 0.
Problem 1, Solution 1
Assume, to the contrary, that 23 + 1 is divisible by 17 for a certain
n > 1 (we write just ab<: for a^c)). Let r be the remainder left by 23"
in division by 17. Thus
r3 = (23""1)3 = 23" = -1 (mod 17),
by our assumption. This implies
0sr3 + l = (r + l)(r2-r + l) (mod 17).
Direct examination of all possible remainders shows that the second
factor (r2 — r + 1) is never 0 (mod 17); and since 17 is a prime, the-first
factor must be 0 (mod 17), i.e., we have r = — 1 (mod 17). So we have
shown that
23" = -1 (mod 17) forces 23n_1 = -1 (mod 17).
Descending, we conclude inductively that
23fc = -1 (mod 17)
for k = n,n — 1, n — 2,..., 1,0. This, however, is a contradiction because
23° = 2 ^ -1 (mod 17).
Problem 1, Solution 2
Fix an n > 1. The exponent 3n is a number of the form 4k + 1 or 4k + 3.
If 3n = 4k + 1, then
23" = 24fc+1 = 16fc • 2 = 2(-l)fc (mod 17),
and if 3n = 4k + 3, then
23" =24fc+3 = 16fc-8 = 8(-l)fc (mod 17).
Note, however, that
2(-l)* + l=(-J !°tk°dd' 8(-l)* + l = {
y [ 3 forfc even, ' I
— 1 for k odd, Q( ^^ , 1 _ / — 7 for k odd,
9 for k even.

16
Solutions
So 23 +1 is never congruent to 0 (mod 17).
Problem 2
Let a, b, c be positive integers with the properties: a3 is divisible by
b, b3 is divisible by c, c3 is divisible by a. Show that (a -f- b + c)13 is
divisible by abc.
Problem 2, Solution 1
The 13-fold product (a + b + c)13, when multiplied out, splits into 313
summands of the form
a bmcn; k, m, n > 0 integers, k -+- m +n = 13. (1)
It will be enough to show that each of them is divisible by abc. This is
evident when the exponents k, m, n are all positive. So it remains to
consider the case where one of them is zero. Let e.g. n = 0. The product
(1) then becomes
akbm; k, m > 0 integers, k + m = 13. (2)
The conditions of the problem imply that a9 is divisible by c and b9 is
divisible by a. Any number of the form (2) can now be represented as the
product of four factors (separated by multiplication dots in the listing
below) :
if k = 13 , m = 0
if 10 < k < 12, 1 < m < 3
if l<fc<9,4<ra<12
if k = 0 , m = 13
in each case the first factor is divisible by a, the second by b, the third
by c (and the fourth is an integer), and so the product abc is a factor of
akbm. That does the job.
Problem 2, Solution 2
Let p be any prime divisor of the product abc. Write
a = pau, b = pPy, c = p^w\ (3)
where a,fi,j > 0 and u,v,w > 1 are integers non-divisible by p.
Since a3 is divisible by b, the exponents a and f3 satisfy 3a > /3. Likewise,
3/3 > 7 and 37 > a; and hence 9a > 7, 9/3 > a, 97 > /3.
Let r = min(a:,/3,7). We obtain
akbm= a -b ■a9iak-10bm-1);
akbm= a -b ■b3iak-1brn-4)-
akbm = b9-b -b3-l:
a+P + j<r + 3r + 9r= 13r.
(4)

Arithmetic and Combinatorics
17
The numbers a, b, c are divisible by pr. Thus (a + b + c)13 is divisible
by P13r, hence by pa+0+T? m view 0f inequality (4). On the other hand,
according to (3), a + P + 7 is the exact power in which p enters the prime
factorization of abc. Since p was an arbitrarily chosen prime factor of abc,
we conclude that (a + b + c)13 is divisible by abc.
Problem 3
|n/3J
For every integer n > 2 show that the number \^ (~1) ( ) *s
divisible by 3. fc=o \3k'
(The symbol [a;J denotes the Greatest Integer Function.)
Problem 3, Solution 1
For any fixed non-negative integer n, the fundamental Binomial Identity
is valid for every integer j, if we agree that
(1)
= 0 for j < 0 and for j >
(2)
Consider the following three sums:
An = £(-1)
k
Cr
= D-D
k( n
3k
k( n
3fc-l
3k~2
(3)
Summation limits have not been indicated; we may assume that k ranges
from —00 to 00. That will cause no ambiguity because there are only
finitely many non-zero terms in each of these sums. E.g., in An
summation actually spreads from k = 0 to k = [n/3\. Thus An is exactly the
number defined in the problem statement. We will show that
An = Bn = Cn = 0 (mod 3) for n > 3.
(4)
(It is only required to show that An = 0 (mod 3); however, it proves
practical to handle the assertion in this more general version.)
Using equation (1) we derive the following recursion formulas:
Ln+l
= £<-
ra + 1
3A;

18
Solutions
n
k3fc-l
k x ' k x
= An + Bn, (5)
n 4- r
5«+i = E(-X)fc
3fc-l
k x ' k x
= 5n + Cn, (6)
n
3k-2
and
C.
n+l
'n + 1
k3fc-2
n
3fc-3
= b-d*(;
- b-^(3;_2)-E(-i)'(3")
— Cn — An. (7)
And since A3 = 1 — 1 = 0, #3 = —3, C3 — —3, obvious induction
justifies the claimed relations (4).
Remark
It is not hard to derive from (5), (6), (7) the recurrence equation of the
second order for the Ans:
An+2 = 3(An+i - An) for n > 1 (8)
(with the initial data A\ — A2 = 1); we invite the reader to do that.
Readers familiar with linear recurrences may like to work out an explicit
formula (on the basis of the system (5), (6), (7) or of the single equation
(8); compare Problem 10, Solution 3). We now show how to find that
formula by a different method.
Problem 3, Solution 2
Notation (3) together with the convention (2) is preserved from Solution
1. For any complex number z we have by the Binomial Theorem
(1 +Z)n = J2 ("V = Mz)+9n(z)+hn(z), (9)

Arithmetic and Combinatorics
19
where
'-M-SCfe
+ K«-»y]'v
»»w = E((6/_1) + L"+2
+ i....bsU6j'-1,
and hnW = £(( » +[6.;U3)z,-2
In particular, if a; is any cubic root of —1 (i.e., a complex number
satisfying uj3 = —1), then we have for any integer j:
^
a;6'"1
W«"2
=
=
=
1,
u'1 = -u\
-2
u> — —uj:
hence (compare (3)),
and likewise
gn(ui) = Bnuj-1 = -Bnuj2, hn(uj) = Cnuj~2 — -Cnuj.
Equality (9) thus implies
(1 + u)n = An- Bnu2 - Cnu for w3 = -1. (10)
Setting w = -1 we hence obtain
Bn = An + Cn for n= 1,2,3,... . (11)
Now consider the complex number
a = I + ±y/Zi = cos(tt/3) + i sin(7r/3),
also satisfying a3 = —1, and moreover, a2 = a — 1. For a; = a equalities
(10) and (11) yield
(1 + a)n = An- Bn(a - 1) - Cna = §An - (§An + Cn)>/3*. (12)
On the complex plane, the numbers 0, 1 and a represent the vertices of
an equilateral triangle, which is completed to a parallelogram (rhombus)

20
Solutions
by the vertex 1 + a. Thus 1 + a — v/3(cos(7r/6) + i sin(7r/6)), and by de
Moivre's Theorem
(1 + a)n = 3n/2 (cos(n7r/6) + i sin(n7r/6)). (13)
Comparing the real parts of (12) and (13),
An = 2-3n/2_1cos(n7r/6);
this is the explicit formula we have promised. If [n/2\ = q, we can
rewrite it as
where
__ J 2cos(n7r/6) for n = 2q,
n ~ \ 2^008(71.^/6) for n = 2q + l.
For each n, Kn is an integer; in particular, K% = 0. Hence A3 = 0; and
for n > 4 we have q > 2, so An = 3q~1Kn is divisible by 3.
Problem 4
Calculate the sum of all divisors of the form 2X ■ 3y (with x, y > 0) of the
number N = 1988 - 1.
Problem 4, Solution 1
The only trouble is to determine the highest powers of 2 and 3 that divide
N. This can be done using the Binomial Theorem:
1988 = (20 - l)88
= 1 - 88 • 20 + (terms divisible by 26)
(we used the fact that (828) = \ • 88 • 87 = 22 • 3 • 11 • 29); and
1988 = (18 +1)88
■ (oVG8)1-©1^©1^-©-88
= 1 + 88 • 18 + (terms divisible by 34).
Since 88 • 20 = 25 • 5 • 11 and 88 • 18 = 32 • 24 • 11, these representations
show that N = 1988 - 1 is divisible by 25, but not by 26, and is divisible
by 32, but not by 33.

Arithmetic and Combinatorics
21
Consequently, the sum we are about to evaluate equals
]T 2X ■ 3y
(x,y): x,y>0
2x-3!/ dividing AT
J2 2X • 3y
x€{l,2,3,4,5}
y€{i,2}
5 2
= E2IE3y
x=l y=l
= (2 + 4 + 8 + 16 + 32)(3 + 9)
= 744.
Problem 4, Solution 2
Let us inspect the powers of 19 modulo 26 and modulo 33:
192 = 361 = -23, 194 = (-23)2 = 529 = 17 (mod 64),
and
198 = 172 = 289 = 33 (mod 64); (1)
while
192 = 361 = 10 (mod 27). (2)
The well-known theorem of Euler (sometimes referred to as generalized
Fermat's Theorem) asserts that if a, n are relatively prime natural
numbers, then a^n) = 1 (mod n), where
(j)(n) = Y[pfi~1(pi - 1) for n = JJp?* (Pi distinct primes).
In particular, 0(64) = 32 and 0(27) = 18. Thus
1932 = 1 (mod 64) and 1918 = 1 (mod 27).
Raising the first of these relations to third power and the second one to
fifth power, we get
1996 = 1 (mod 64) and 1990 = 1 (mod 27);
or — which is exactly the same —
198 • 1988 = 1 (mod 64) and 192 • 1988 = 1 (mod 27).

22
Solutions
Consequently, in view of (1) and (2),
1988 # 1 (mod 64) and 1988 # 1 (mod 27) (3)
(if 1988 were 1 (mod 64), the product 198 • 1988 would be 33 rather than
1 (mod 64); and the second relation of (3) is justified similarly).
On the other hand, equation (1) shows that 198 = 1 (mod 32). Besides,
19 = 1 (mod 9). If we raise the first relation to power 11 and the second
to power 88, we obtain
1988 = 1 (mod 32) and 1988 = 1 (mod 9). (4)
Statements (3) and (4), combined, show that N is divisible by 32 and by
9, but not by 64 or 27. The concluding calculation is done as in Solution
1.
Problem 4, Solution 3
The argument of Solution 2 can be carried out without resorting to Eu-
ler's Theorem and Euler's Function, in a fashion less sophisticated and
more straightforward. Namely, upon arriving at formulas (1) and (2), we
continue as follows. Since
332 = (32 + l)2 = 322 + 2 • 32 + 1 = 1 (mod 64),
we obtain from (1)
1988 = (198)ii = 33ii = (332)5 . 33 = 33 (mod 64).
And since by (2)
193 = 192- 19 = 10-19= 190= 1 (mod 27),
we conclude that
1988 = (193)29 • 19 = 19 (mod 27).
Claims (3) hence result. The remaining portion of the preceding solution
has to be repeated without any changes, yielding the outcome: S = 744.
Problem 5
Show that there do not exist four successive integers whose product is
1993 less than a perfect square.
Problem 5, Solution 1
Assume that the equation
x(x + l)(x + 2){x + 3) + W93 = y2 (1)

Arithmetic and Combinatorics 23
is fulfilled for some integers x and y. Examine equation (1) modulo 5.
Either the product x(x + l)(x + 2)(x + 3) is divisible by 5 or its four
factors leave remainders 1, 2, 3, and 4, in which case the product equals
4 (mod 5).
Anyhow, the expression on the left of (1) is either 3 or 2 (mod 5), and
this is obviously a contradiction because a perfect square y2 can only be
0, 1, or 4 (mod 5).
Problem 5, Solution 2
Assume equation (1) and transform the product under examination as
follows:
x(x+3)-(x + l)(x + 2) = (x2+3x)(x2+3x + 2) = (z- l)(z + l) = z2- 1,
where we have denoted by z the expression x2 + 3x + 1; this quadratic
trinomial has the minimum value (over the reals) equal to —5/4, and
hence z > — 1. Equation (1) now takes the form z2 + 1992 = y2, i.e.,
(y - z)(y + z) = im. (2)
We see from (2) that z cannot be —1; hence z > 0. We may also assume
(see (1)) that y > 0. So the second factor in equation (2) is non-negative;
consequently, both factors must be positive, the second one greater than
the first. Both factors are integers of the same parity; their product
is even, so they both are even. In view of the prime decomposition
1992 = 23 • 3 • 83, the prime factor 83 must enter y + z and we conclude
that the pair (y — z, y + z) must be one of the following:
(2, 996), (4, 498), (6, 332), (12, 166).
Accordingly, z equals 497, 247, 163, or 77, which means that the product
(x + l)(x + 2) equals 498, 248, 164, or 78. However, it is easily verified
that no one of these four numbers is equal to the product of two successive
integers. Contradiction ends the proof.
Problem 6
Show that there are infinitely many positive integers n such that each
one of the three numbers n — 1, n, n + 1 can be represented as the sum
of two perfect squares.
Problem 6, Solution 1
Define nk = (2k2 + l)2 for k = 0,1,2,... .
Then the sequence ni,722,723,... is strictly increasing and each of its
terms is equal to the sum of two squares:
nk - 1 = (2k2)2 + (2k)2, nk = (2k2 + l)2 + 02,
nfc + l = (2fc2 + l)2 + l2.

24
Solutions
Problem 6, Solution 2
Now let nk = 2m| + 1, where mk = k(k + 1). It is enough to notice that
nfe-l = m|+m|, nk = (fc2 + 2k)2 + (fc2 - l)2,
nfc + l = (mfc + l)2 + (mfc-l)2.
Problem 6, Solution 3
Define the sequences a\, a,2, a^,... and b\, &2, H, ■ ■ ■ recursively by
a0 = 4, b0 — 3, afc+i = 2afc&fc, &fc+i = 2&fc - 1
and notice the equality a| + 2 = 2b\ (easy proof by induction). Hence,
if we set nk = a2 + 1, we are done because
nfc-l = a| + 02, nk = a2k + l2, nk + 1 = b\ + b\.
Problem 7
Show that the following system of simultaneous equations has no solution
in integers:
x — 3xy + 3y — z = 31
-x2 + 6yz + 2^2 = 44
x2 + xy + 8z2 = 100.
Problem 7, Solution 1
Since the terms x2 and z2 appear in all the three equations, it is tempting
to apply the method of elimination so as to get rid of them. If we multiply
the first equation by a, the second by 6, and the third by c, and add the
resulting equations, we obtain an equation in which the coefficients of
x2 and z2 are a — b + c and —a + 2b + 8c, respectively. Setting these
expressions to be zero, we find that e.g. a = 10, b = 9 and c = — 1 do the
job, producing the equation
10 • (-3xy + 3y2) + 9 • 6yz ~ xy = 10 • 31 + 9 • 44 - 100,
i.e.,
y(-31x + 30y + 54*) = 606.
This yields the possible values of |y|: 1, 2, 3, 6, 101, 202, 303, 606.
In a similar manner we can eliminate the terms x2 and xy, multiplying
the first, the second and the third equation of the system by suitable
factors a, b, c; now we need that a — b + c and — 3a + c (the coefficients

Arithmetic and Combinatorics
25
of x2 and xy in the resulting equation) should be zero. When we take
a = 1, b = 4, c = 3, we obtain
(3y2 - z2) + 4(6yz + 2z2) + 3 • 8z2 = 31 + 4 • 44 + 3 • 100,
i.e.,
31z2 + 24yz + (3y2 - 507) = 0.
Viewing this as a quadratic equation with the unknown z, we compute
its discriminant:
D = (24y)2 - 4 • 31 • (3y2 - 507) = 4{5ly2 + 15717);
then the roots zlt z2 are: (-12?/ ± y/D/4)/31. Thus 51y2 + 15717 ought
to be a square number in order that z\, z2 be integers. Yet, for the
previously found values of \y\ this expression takes values 15768, 15921,
16176, 17553, 535968, 2096721, 4697976, 18744753, no one of which is a
perfect square. So the system has no integer solutions.
Problem 7, Solution 2
An astonishingly simple proof results from examination of the two outer
equations modulo 5 (the middle equation is not needed!). Multiplying
the first equation by 8 and adding the third equation we get
9a;2 - 23xy + 2Ay2 = 348,
which is
-x2 + 2xy - y2 = 3, i.e., (x - y)2 = 2 (mod 5).
Yet the square of an integer can only be 0, 1 or 4 (mod 5); the claim
follows.
Problem 8
Solve the following equation in integers x, y:
x2(y-l)+y2(x-l) = l.
Problem 8, Solution 1
Set x = u + 1, y = v + 1', the equation becomes
(u + l)2v + (v + l)2u = 1;
equivalent ly:
u v + 2uv + v + uv -\-2uv-\-u = 1;
uv(u-\-v)-\- 4uv + (u + v) = 1;
uv(u+v +4) + (u + v +4) = 5;
(u+v +4)(uv + l) = 5.

26
Solutions
One of the factors must be equal to 5 or —5 and the other to 1 or —1
(respectively). This means that the sum u + v and the product uv have
to satisfy one of the four equation systems:
u + v = 1 u + v = —9
uv = 0 uv = —2
u + v = —3 u +1? = —5
uv = 4 uv = —6
Accordingly, the numbers it and v have to be the roots of one of the four
quadratic trinomials:
t2 - t; t2 + 9t - 2 ; t2 + 3t + 4; t2 + 5i - 6
The two trinomials in the middle (the second and the third) have no
integer roots. The first one has roots 0, 1, and the last one has roots —6,
1. Thus (u,v) must be one of these two pairs, up to permutation. Hence
the final outcome: {x, y) = (u + 1, v + 1) must be one of the pairs: (1,2),
(-5,2), (2,1), (2,-5).
Problem 8, Solution 2
The symmetric shape of the equation suggests introducing the
fundamental symmetric forms s — x + y and q = xy. The equation, rewritten
as xy(x + y) = x2 + y2 + 1, takes the form
sq = s2-2q + l; (1)
i.e., (s + 2)q = s2 + 1. The factor (s + 2) cannot be zero, and division
is admissible:
s2 + 1 94. 5 m
q = , 0 = s-2 + —— . (2)
s + 2 s + 2
If this has to be an integer, the denominator s + 2 must be a divisor of
5, which means that s must be one of the numbers —7, —3, — 1, 3. For
each of these values of s, the corresponding value of q is computed from
(2) and we arrive at the four possible systems of equations for s = x + y,
q = xy:
x+y = —7 x + y = —3
xy — —10 xy = —10
x +y = — 1 .T+y = 3
xy — 2 xy = 2
(3)
(they correspond, in a certain order, to the four systems obtained in
Solution 1). The numbers x and y must be the roots of the respective

Arithmetic and Combinatorics
27
quadratic trinomial
t2 + It - 10 ; t2 + St - 10 ; t2 + t + 2 ; t2 - St + 2 .
Of these, only the second and the fourth have integer roots; these are,
respectively,. —5, 2 and 1, 2. So (x, y) is one of the pairs (—5,2), (2, —5),
(1,2), (2,1).
Problem 8, Solution 3
Use the symmetric forms s = x +y, q = xy. The resulting relation (1)
can be viewed as a quadratic equation with the unknown s and parameter
s2 - qs + (1 - 2q) = 0.
Its discriminant equals D = q2 + 4(2g — 1) = {q + 4)2 — 20 and produces
the roots
8i=\{q + VD), s2=\{q-yfi5). (4)
One of these roots has to be equal to x + y, an integer. Therefore D
must be the square of an integer: D = d2; d > 0. Then
20 = (q + 4)2 - D = {q + 4 + d)(q + 4 - d),
with both factors of same parity, the first factor greater than the second.
There are only two factorizations of 20 that suit the need: 20 = 10 • 2
and 20 = (—2) • (—10), giving rise to the equation systems
g + 4 + d=10 , q + 4 + d=-2
and
q + 4-d = 2 g + 4-d=-10,
with solutions q = 2, d = 4 in the first .case and q = —10, d — 4 in the
second. Recall that d = y/~D. Thus, in view of (4), the possible values of
s are: 3, —1 (if q — 2) and —3, —7 (if q = —10). So we have obtained the
systems of equations (3) from Solution 2. Repeating its final passage we
determine the four integer pairs (x,y) that make up the solution of the
given equation.
Problem 8, Solution 4
The technique of inspecting the discriminant can be employed in a yet
more straightforward manner, without introducing the forms s and q.
Suppose a pair (x,y) is a solution. At least one of the integers x, y is
greater than 1; otherwise the left-side expression would be nonpositive.
In view of symmetry we may assume x > 1. Let us look at the given
equation as a quadratic one with respect to variable y,
{x-l)y2+x2y-{x2 + l) = 0, (5)

28
Solutions
with discriminant
D = x4 + 4(x - l){x2 + 1) = x4 + 4x3 - Ax2 + 4x - 4, (6)
which must be a perfect square in order that equation (5) has an integer
root y.
Suppose x > 2. Then the following inequalities hold:
D - {x2 + 2x - 4)2 = 20(x-l)>0,
D - {x2 + 2x - 2)2 = -4(x-l)(x-2) < 0,
showing that D is strictly comprised between the squares of two skip-
consecutive integers x2 + 2x — 4 and x2 + 2x — 2. Therefore D has to be
the square of x2 + 2x — 3. This, however, cannot be the case, since this
last number is of different parity than D (see (6)).
The only possibility that remains is that x — 2. Equation (5) then
becomes y2 + Ay — 5 = 0; equivalently, (y — 1) (y + 5) = 0, and we get y = 1
or y = —5. So (2,1) and (2,-5) are all pairs of integers (x,-y) with
x > 1, satisfying the equation. Symmetry yields two other pairs (1,2)
and (—5,2); and there are no more — as the argument shows.
Problem 8, Solution 5
Assume that the integers x, y satisfy the equation. Its left side is the
sum of two addends, one of which must be > 1 and the other one < 0.
Let e.g. y2{x - 1) > 1, x2{y - 1) < 0. Then x > 2, y / 0, y < 1.
If y = 1, then of course x = 2 (just look at the equation).
Assume y < 0 for the sequel (remember that y = 0 has been excluded).
Again let x + y = s and rewrite the equation in the form
x2(s -x-l) + (s- x)2{x - 1) = 1.
Expanding and regrouping,
sx2 - x3 - x2 + x3 - 2sx2 + s2x - x2 + 2sx - s2 = 1;
x(s+2)(s -x) = s2 + 1.
The factor s — x — y is negative; x is positive. Hence s + 2 must be
negative, and so s < —3, whence s2 > 9.
Rewrite the last equation as f{x) = 0, where by definition
f(x) =[-(s+ 2))x2 + [s(s+ 2)]x - [s2 + 1].
Notice that the coefficients (in square brackets) are positive. Thus, in
view of x > 2, we get
f(x) > /(2) = -4(s + 2) + 2s(s + 2) - (s2 + 1) = s2 - 9 > 0. (7)

Arithmetic and Combinatorics
29
Equality f{x) — 0 implies that both inequalities in (7) must turn into
equalities. Now, f(x) = /(2) means that x = 2, while s2 = 9 means that
s = —3. Hence y = s — x = —5. Recalling the case of y = 1 (mentioned
at the beginning), we obtain the two solving pairs (x,y) with y < 1:
(2,1) and (2, —5). Interchanging the roles of x and y we get the other
two pairs: (1,2) and (—5, 2); and these four pairs constitute the complete
solution.
Problem 9
If x, y, z are integers, at least one of which is 1990, show that
2 , 4 , 6 ^ 2 , 2 3, 3
x +y + z > xy +y z +xz .
Problem 9, Solution 1
This is in fact the Cauchy-Schwarz inequality for the triple of numbers
x, y2, z3; it can be settled (in the weak form) as follows, using the
arithmetic mean-geometric mean inequality for pairs of numbers:
2, 4, 6 x2+j/4 x2 + z6 y4 + z6
x +y + z° = 1 1
> ^x2y4 + Vx2z6 + y/y4z6
= \x\y2 + \x\\z\3+y2\z\3
> xy + y z + xz
(because \x\ > x and \z\ > z).
Equality would require that x2 = y4 = z6 and either y = 0, xz > 0, or
y ^ 0, x, z > 0. In the first case we get x = y — z = 0, in contradiction
to the "1990" condition.
Regarding the second case, we now have z3 = y2 = x > 0. Since x, y,
z have to be integers, z3 = y2 forces that z is itself a perfect square:
z = u2, with u being a positive integer. Thus y = ±u3, x = u6. By
assumption, one of the numbers x = u6, y = ±u3, z = u2 has to be
1990. And since 1990 is neither a square or cube or sixth power, equality
cannot occur and the given inequality holds (in the strict form).
Problem 9, Solution 2
The proof can be also derived from the following transformations:
/2,4,6\ /2,23, 3\
{x +y +z )-{xy +y z + xz )
6 - (y2 + x)z3 + (y4 - xy2 + x2)
■Z-(z3+y*)x + (ze-y2z3 + y4)
,2.3/9 \2
2 . 5; ^ on2 (1)
^-\^+x)Y + \{y2-x)
(x-l{z3+y2))2 + l(Z3-y2y.

30
Solutions
These expressions are non-negative. Now, x, y, z are integers, one of
them being equal to 1990. If x = 1990, then y2 / x. If y = 1990 or
z = 1990, then z3 ^ y2. In each case one of the terms {y2 — x)2 and
{z3 — y2)2 is strictly positive, and so is the difference expressed by
formulas (1).
Problem 10
Consider the sequence xo = 0, x± = I,
xn+2 = 3zn+i — 2xn for n = l,2, 3,
Define yn = x\ + 2n+2. Show that yn is the square of an odd integer, for
every non-negative integer n.
Problem 10, Solution 1
The initial 0, 1, 3, 7, 15, 31, ..., so it is natural to guess that
xn = 2n - 1. (1)
We prove this by induction. For n = 0 and n = 1, (1) holds. Assume
that (1) holds for some two successive integers n and n + 1. Then
Xn+2 — 3zn+i — 2xn = 3(2n+ — 1) — 2(2n — 1)
= 3 . 2n+1 - 2n+1 - 1 = 2n+2 - 1,
proving (1) for n + 2. Hence, formula (1) is true for all integers n > 0.
From (1) we get
yn = 4 + 2n+2 = (2n - l)2 + 2n+2
= 22n - 2 ■ 2n + 1 + 4 • 2n
= 22n + 2 • 2n + 1 = (2n + l)2,
showing that yn is the square of an odd integer, as asserted.
Problem 10, Solution 2
The recursion formula for zn+2 can be rewritten as
xn+2 - xn+i = 2zn+i - 2xn for n = 0,1,2,... .
Thus, setting xn+\ — xn = tn we have tn+\ = 2tn for n — 0,1,2,...; and
since to = 1, we infer tfe = 2fe, i.e.,
xfc+i - :rfe = 2 (2)
for A; = 0,1, 2,... . Fix an integer n > 1. Summing the equalities (2) over
A; = 0,1,2,..., n — 1 we obtain
(xi - xq) + (x2 - xi) + ■ ■ • + (xn - xn-i) = 2° + 21 + • • • + 2
n-l

Arithmetic and Combinatorics
31
or, which is the same (in view of xq = 0),
Xn = Z I.
So we have formula (1) of Solution 1 (without guessing), and it remains
just to repeat the last paragraph of that solution.
Problem 10, Solution 3
We are dealing with the homogeneous linear recursive equation of the
second order
xn+2 — 3zn+i + 2xn = 0 for n = 0,1,2,... .
The well-known method of handling such recursions is to solve the
characteristic equation, which in this case is
q2 - 3q + 2 = 0, (3)
and to postulate xn — Aan + B(3n, where a and (3 are the roots of that
equation (provided they are distinct). Now, equation (3) has roots a = 2
and /3 = 1, yielding xn = A ■ 2n + B. From the initial data xq = 0, x\ = 1
we get
A+B = 0, 2A + B = l.
Thus A = 1 and B = — 1, i.e., xn = 2n — 1. As in the first solution, we
hence obtain yn = (2n + l)2.
Problem 10, Solution 4
If one prefers (unwisely enough) to work out a recursive formula for the
yns, that is also possible. Squaring the equation that defines zn+2 we
obtain
whence by setting x\ = yn — 2n+2 and denoting xnxn+\ by zn:
yn+2 - 2n+4 = 9(yn+i - 2n+3) + 4(yn - 2n+2) - 12zn.
This simplifies to
12*n = -yn+2 + 9yn+i + Ayn - 18 • 2n+2. (4)
Consider zn+\:
Zn+l — Sn+iXn+2
= xn+i(3a;n+i — 2xn)
== ^xn+l ~ ^xnxn+l
= Z(yn+1-2n+3)-2zn.

32
Solutions
Multiply this by 12 and insert expression (4) (and the analogous
expression for 12zn+i):
-yn+3 + 9yn+2 + 4yn+i - 18 • 2n+3
= 36(yn+1 - 2"+3) - 2(-yn+2 + 9yn+1 + Ayn - 18 • 2n+2).
The powers of 2 cancel out and we are left with
2/n+3 - 7yn+2 + 14yn+i - 8y„ = 0.
Apply the method described in Solution 3. The characteristic equation
is
q3 - 7q2 + Uq - 8 = 0.
Its coefficients sum up to 0, hence one of the roots is 1 and the
equation factors into (q — l)(q2 — 6q + 8) = 0. The roots of the quadratic
factor are found e.g. from the Viete's Formulas; they are 2 and 4. So we
postulate
Vn = A ■ 4n + B ■ 2n + C. (5)
The initial terms xq = 0, x\ = 1, x2 = 3 yield the initial terms of the
sequence (yn)'- yo = 4, y\ — 9, y2 = 25. Setting these in (5) we obtain
the system of linear equations for the constants A, B, C:
A + B + C = 4, AA+2B + C = 9, 16 A + 4B + C = 25,
with the unique solution A — 1, B — 2, C = 1. Therefore
yn = 4n + 2-2n + l= (2n + l)2.
Problem 11
The sequence (an) is denned recursively by
2 , i
ao = 1, a\ = 2, an = for n = 2, 3, 4,... .
On-2
Show that each an is an integer.
Problem 11, Solution 1
We proceed by induction. The first three terms ao = 1, a\ = 2 and a2 = 5
are integers. Fix n > 3 and assume that the afes are integers for all k < n;
we will show that an+\ is an integer also. According to the defining
formula, an-\ = (aj_2 + l)/o„_3; thus
an_2 + 1 = «n-l«n-3-

Arithmetic and Combinatorics
33
The numbers an-i> «n-2) &n~3 are integers, by the inductive assumption.
The last formula shows that an_i and an_2 are coprime. Now,
\ «n-2 /
a4n-i + 2aLi + 1 + «n-2
_ oj-i+ 2a^_!+ an-iQn-3
2 '
an-2
and hence
K +1)
All the afcS occurring in this equality are whole numbers. So the
product (a\ + l)aj_2 is divisible by o„_i. And since an_2 and an—\ are
coprime numbers, an_i has to be a divisor of a\ + 1. Consequently,
an+\ = (a^ + l)/an_! is an integer. This completes the inductive step.
Problem 11, Solution 2
According to the definition,
2 , i
an_1 + 1 = an_2an-
Replacing n by n + 1 we obtain
an + i — an-\a>n+i-
Subtracting the first equation from the second one,
2 2
an ~ an-l — an-lan+l ~ «n-2«n!
so an(an + an_2) = an_i(an+i +an_i), i.e.,
an + «n-2 _ Qn+1 + Qn-1
an—1 an
This shows that the sequence ((an+i + an_i)/an) is constant. It begins
with (<22 + ao)/ai = (5 + l)/2 = 3, and hence (an+i + an_i)/an = 3 for
all n; equivalently,
an+i = San — an-i for n = l,2,3,... .
Since ao = 1 and ai = 2, this forces that all the ans are integers.

34
Solutions
Problem 11, Solution 3
A few initial terms of the given sequence are: ao = 1, a\ — 2, 122 = 5,
a3 = 13, a4 = 34, as = 89; the even-indexed Fibonacci numbers are
immediately recognized. The Fibonacci sequence, denned by the
recursion
F0=l, Fi = l, Fn = Fn_!+Fn_2 for n = 2,3,4,..., (1)
begins with
(F0, Fi, F2, F3, F4, F5, F6, F7, Fs, ■ ■ •) = (1,1, 2, 3, 5,8,13, 21,34,...),
so it is natural to guess that
an = F2n for n = 0,1,2,3,... . (2)
Since (2) holds for n = 0 and n = 1, it will be enough to prove that
the sequence (F2n) fulfills the same recursion formula that defines the
sequence (an):
^2» = -J£=^ for n = 2,3,4,...;
^2(n-2)
equivalent ly,
F2nF2n-4 - Fln-2 = 1 for n = 2,3,4,.... (3)
The Fibonacci numbers are expressed by the well-known equality
an+l _ pn+1 1 + VE 1-y/E
Fn — 7= where a — — , B — — .
V5 2 ' ^ 2
(Readers not familiar with this expression may like to derive it from
the recursion (1), employing the techniques described in the solution to
Problem 10, this book.) Notice that a + B - I, a - B = a/5, <xB = -1.
Thus
F2nF2n-4 ~ ^2n-2
a2n+l _ g2n+l Q2n-3 _ g2n-3 /a2n-l _ o2n-l\2
y/E y/E \ \/5
tAn~2 - (aB)2n-3(a4 + B4) + BAn~2
5
a4n-2-2(aB)2n-1 + B4n-2

Arithmetic and Combinatorics
35
aA+{34 2
5 5
a4 - 2(aP)2 + /34
5
5 ~ '
equality (3) results, proving our claim (2). It just remains to use the fact
that the Fibonacci numbers are integers.
Problem 12
Find all functions / mapping non-negative integers into non-negative
integers and such that /(/(n)) + f(n) = 2n + 6 for every integer n > 0.
Problem 12, Solution 1
Suppose / satisfies the given equation
/(/(n)) + /(n) = 2n + 6 for n = 0,l,2,.... (1)
Assuming f(n) = f(m) for some n,m > 0 we get /(/(n)) = /(/(m)),
whence by (1) n = m. Thus / is injective. Denote:
/(0) = o, f(a) = 6, /(6) = c, f(c) = d, f(d) = e. (2)
Setting in (1) n = 0, a, b, c we obtain, respectively,
b + a = 6, c + 6 = 2a + 6, d + c = 2b + 6, e + d = 2c + 6. (3)
If a were zero, all the numbers in (2) would be zero, in contradiction
to b + a = 6. So a =£ 0, and by injectivity /(a) / /(0), i.e., b =fi a. Since
a + 6 = 6, we see that a/3.
Subtract the first equation of (3) from the second, the second from the
third, and the third from the fourth:
c - a = 2a, d - b = 2b - 2a, e- c = 2c-2b. (4)
By the first equation of (3), b — 6 — a. Relations (4) hence imply:
c = 3a, d = 36 - 2a = 18 - 5a, e = 3c - 26 = 11a - 12. (5)
All the values taken by / are non-negative integers; in particular, d > 0
and e > 0. This in view of (5) shows that jf < a < ^. Since 3 has been
excluded as a possible value of a, we infer a = 2.

36
Solutions
Thus 6 = 4, and from equations (4) (or (5)) we compute: c = 6, d = 8,
e = 10. The obvious guess is
/(2A;) = 2A;+2 for k = 0,1,2,... . (6)
This holds for small values of k. Assuming (6) holds for a certain k, we
get from equation (1)
/(2fc + 2) = /(/(2fc)) = 2(2fc) + 6 - f(2k) = 2{k + 1) + 2,
showing that (6) holds with A; + 1 in place of A;. So, equality (6) is settled
by induction.
Now, let /(l) = q. By equation (1),
f{q) +Q = 8. (7)
So q < 8. The numbers 2, 4, 6, 8 are values of / at 0, 2, 4, 6, respectively
(see (6)). Injectivity forces that q = f(l) must be one of the numbers:
0, 1, 3, 5, 7. We will show that 0, 1, 5, and 7 can be easily eliminated.
If q = /(l) = 0 then, by (7) and (6), /(0) = f(q) = 8 = /(6), violating
injectivity.
If Q — /(I) — 15 contradiction with equation (7) is evident.
If q = /(l) = 5 then, by (7), /(5) = 3. Setting in equation (1), first,
n — 5, and then n = 3, we obtain
/(3) + /(5) = 16 and /(/(3))+ /(3) = 12;
hence /(3) = 16 - /(5) = 13 and /(/(3)) = 12 - /(3) = -1, a
contradiction again.
If q = /(l) = 7 then, by (7), /(7) = 1. Equation (1) with n = 7 yields
/(/(7)) + /(7) = 20,
i-e., /(/(7)) = 19, in contradiction to /(/(7)) = /(l) = 7.
We are left with the only possible value /(l) = 3. Induction very similar
to the proof of formula (6) shows that
f(2k + l) = 2k + 3 for k = 0,1,2,... . (8)
Equalities (6) and (8) jointly result in
/(n) = n + 2 for n = 0,1,2,... .
and it is readily verified that this function indeed satisfies the given
equation (1).

Arithmetic and Combinatorics
37
Problem 12, Solution 2
Choose and fix an integer n > 0. Consider the following sequence of
non-negative integers:
a0 = n, a1 = f(n), a2 = f(f(n)), ..., ak = fk(n), ..., (9)
superscript denoting iteration. In equation (1) set fk(n) in place of n;
the result is
ak+2 + afe+i = 2afe + 6. (10)
Subtracting 2a,k+i from both sides we get
afc+2 - ofc+i = 2(afc - ak+i) + 6;
that is,
rfe+i + 2rfe - 6 = 0,
where r-fc = afe+i — afe. Write r/- = xk + 2; the equation becomes
xk+\ +2xfe = 0.
All these relations hold for A; = 0,1, 2, The last equation obviously
implies the explicit formula x^ — (—2)fezo- Consequently
rfe = 2 + (-2)fea;o for fc = 0,l,2,... .
By telescoping, we obtain for every integer m > 1:
771 — 1
dm = ao + 7 ,(afc+i — afc)
fe=0
m—1
= a0 + ^ rfc
fc=0
771—1
= a0 + 2m+ ^(-2)fex0
fe=0
1 _ (_2)m
= a0 + 2m + v -x0. (11)
o
Recall that all OttjS are supposed to be non-negative. The exponential
growth of |(—2)mzo| can be in no way matched by the linear term 2m,
unless xq — 0. (To be more precise: if xq > 0 then the expression obtained
in (11) is negative for large even m; and if xq < 0 then it is negative for
large odd m.)
Therefore xq must be 0, whence vq = 2; i.e., a\ — ao = 2. This in view
of definition (9) means that /(n) — n = 2.

38 Solutions
We have begun by choosing an integer n > 0 arbitrarily. The conclusion
is that
f(n) = n + 2 for n = 0,1,2,... .
Problem 12, Solution 3
This is just a variation of Solution 2. Introduce the sequence of iterates
(9) and write equation (10). Note that (10) is an inhomogeneous linear
recursion of the second order, with a constant free term.
The method of solving such equations is algorithmic. One postulates a
solution of the form a'k = Ck (ignoring the initial data). In the case of
equation (10) this yields C = 2; thus the sequence (2k) is a particular
solution of (10).
If (ofc) is the sequence (9) we are looking for, then the difference
Cfe = afe — 2k
satisfies the homogeneous equation corresponding to (10):
cfe+2 + cfe+i - 2cfe = 0. (12)
This is solved by the standard method (see Problem 10, for example):
the characteristic equation A2 + A — 2 = 0 has roots 1 and —2, and so
cfe = A(—2)k + B is the general solution of (12). This implies
afe = A(-2)k + B + 2k, (13)
with unknown constants A and B; the explicit evaluation of those
constants has been carried out in the previous solution, formula (11), in
terms of the data ao and xq = ro — 2 = a\ — ao — 2. But we do not need
to know their values! Just note that if A / 0 then the term 2k is
negligible alongside with A(—2)k, and so ak is negative for A; sufficiently large,
even or odd according as A < 0 or A > 0. And since it is required that
«fc = fk(n) > 0 for all k, we conclude that A — 0. So ak — 2k + B for
A; = 0,1, 2,... . Hence by definition (9)
f{n) - n = ax - a0 = (2k + 2 + B) - (2k + B) = 2,
and we arrive at the same result as in the two former solutions.
Problem 12, Solution 4
The ideas of the Solution 1 and Solutions 2/3 can be neatly combined
to produce a fourth one. Consider the sequence of iterates (9) and their
recursion equation (10):
afe+2 = 2ak - afe+1 + 6. (14)

Arithmetic and Combinatorics
39
Using this recursion we compute:
a3 =
(24 =
«5 =
a& -
a7 =
- 3ai — 2ao,
= 6ao — 5ai + 18,
= llai — 10ao — 12,
= 22a0 - 21oi + 54,
- 43ai - 42a0 - 72,
(15)
In the Solutions 2 and 3, the sequence (ofc) was generated by an arbitrary
initial term ao = n. Now let us take n = 0 and n = 1, and denote the
resulting sequences (ofc) by (pfc) and (gfc):
Pfc = /fe(0), 9fc = /fe(l) for k = 0,1,2,...
(thus po = 0, go = 1)- Equalities (15) yield, in particular,
P5 = llpi - 12,
p6 = 54-21pi,
g6 = 76 - 21gi,
97 = 43gi - 114.
These numbers have to be non-negative. So we get the two-sided
estimates:
12 54 114 76
11 -^ 21' 43 ~ y 21
Each one of these intervals contains only one integer, and hence p\ = 2,
qi = 3. Formulas (15) applied to (ofc) = (pk) and (ofc) = (qk) now
produce
Po — 0, pi = 2, P2 = 4, P3 = 6 (and so on)
and
90 = 1, 9i = 3, 92 = 5, 93 = 7 (and so on).
The general rules p^ = 2A; and g^ = 2k + 1 are easily guessed and equally
easily proved by induction, based on the recursion formula (14). Restate
them more explicitly as:
/fe(0) = 2A;, /fe(l) = 2A; + l for k = 0,1,2,... .
This means that the function / acts as follows:
0 i—»■ 2 i—»■ 4 i—>• 6 i—>■ - - - , X i—»■ 3 i—>5i—> 7 >-*••• .
In other words, / is the function: f(n) — n + 2.

40
Solutions
Problem 13
Show that Lnv3j is a power of 2 for infinitely many natural numbers n.
(The symbol [x\ denotes the Greatest Integer Function.)
Introductory Remark
There is nothing peculiar about the number v3. In fact, it can be
replaced by any other number a with 1 < a < 2. We present three
solutions to the problem involving the sequence [na\, with an arbitrarily
fixed a E (1,2), plus a fourth solution in which a is additionally assumed
to be irrational.
So, let us fix an a with 1 < a < 2. Call an integer n nice if [na\ is a
power of 2. We wish to show that there are infinitely many nice ns.
Problem 13, Solution 1
Assume this is not the case. Take an integer k with 2k > na for all
nice n. Let q be the (unique) integer such that qa < 2 < (g + l)a. Set
r — 2k — qa; thus 0 < r < a.
There is a (unique) integer j > 0 for which
(a/2) < 2jr < a.
Since (by assumption) a < 2, the number a/2 exceeds a — 1, and we
obtain
a-l< 2jr = 2j(2k -qa) < a;
equivalent ly,
{2jq + l)a - 1 < 2j+k < {2jq + l)a.
Denoting 2Jg + 1 by m we thus have [maJ = 2J+fc, and hence m is nice.
Note, however, that m satisfies the inequality
ma = (2jq + l)a > (g + l)a > 2k,
which is impossible, according to the definition of k. Contradiction ends
the proof.
Problem 13, Solution 2
Clearly, 1 is nice (so the set of nice numbers is non-empty). Choose
any nice number n. The product na represents as na = 2k + r, k > 0 an
integer, r E [0,1). Consider three cases.
Case 1. 0 < r < 1/2. Then [2naJ = 2fe+1, hence 2n is nice.
Case 2. a/2 < r < 1. (This case cannot occur for n = 1; indeed, if
n = 1, then A; = 0 and r — a — 1 < a/2.) Now we have
(2n-l)a = 2fc+1 + (2r-a),

Arithmetic and Combinatorics
41
with 2r - a € [0,1). Hence, [(2n - l)oJ = 2fe+1 and so 2n - 1 is nice.
(Note that 2n - 1 > n.)
Case 3. 1/2 < r < a/2. Define
1 o-l/ 1\ „ „ rt
*'=2 + -2-(1-ai) for ^ = 0-1-2--;
this is an increasing sequence, starting from xq = 1/2 and converging to
a/2. So there exists a (unique) integer j > 1 such that a^-i < r < Xj.
Since r = na — 2 , we obtain the inequalities
1 a- 1 / 1 \ rtfc 1 a - 1 /.. 1 \
-2 + -r(l-^)ina-2 <2 + ^(1-2i)-
equivalent to
2fe+j+i + 2 - a < (2i+1n - 2J' + l)a < 2fc+J+1 + 1.
Denote the number in parentheses by m. We see that \ma\ = 2fc+J'+1,
and hence m is nice. Evidently, m > n because \na\ = 2 .
In each of the three cases we have found a nice number m greater than
n. It follows that there are infinitely many nice numbers.
Problem 13, Solution 3
Consider the binary representation of 1/a:
i = (0.cic2c3...)2 with cfee{0,l}for A: = 1,2,3,... . (1)
a
This representation is not unique if 1/a is a dyadic fraction (e.g., 3/4
can be written either as (0.11)2 or as (0.101111.. .)2 )• In such a case,
choose the infinite expansion. Thus, in the sequel we are only considering
representations (1) with infinitely many CfeS equal to 1.
Choose an index A; for which ck+i — 1. According to (1),
2 • - = (ciC2 • • • cfc)2 + (O.Cfe+iCfe+2 .. .)2 = mjfe + rfc;
a
mk an integer, rfc e Q, l].
Recalling that 1 < a < 2, we get
(2fe + l)-- = mfe+(Vfc + -Y with rfc + - 6(1,2).
a \ a/ a
Hence
2fc • - < mk + 1< (2fe + 1) • i ,
a a

42
Solutions
showing that [(rrik + l)aj = 2k. So mfc + 1 is a nice number.
To distinct A;s with c^+i = 1 there correspond distinct mfeS (because
mfe = (cic2 • • • cfe)2 )• And since Cfc+i equals 1 for infinitely many A;s,
this proves that there are infinitely many nice numbers.
Problem 13, Solution 4
Here we assume that a E (1,2) is an irrational number.
Let b E (2, oo) be the number determined from the equation
1 1
- + - = 1. (2)
a o
The reasoning will be based on the well-known theorem which says that
if a, b are any positive irrational numbers satisfying equation (2) then
the sets
A = { [na\ : n E N } and B = { [nb\ : n E N }
constitute a partition of the set N of positive integers; this means that
they are disjoint and their union exhausts all of N. (Reference: D. J.
Newman, A Problem Seminar, New York-Heidelberg-Berlin, 1982; Problem
46, p. 8; Solution, p. 68.)
We will prove that
2 E A for infinitely many A;s;
this is equivalent to the assertion of the problem. And since N=AUB
is a partition, it suffices to show that
if 2k E B then 2k+j E A for a certain j > 0.
Thus assume 2fe E B. So 2fe = [nb\ for some n E N:
nb = 2k + r, r E (0,1) irrational.
There exists a (unique) exponent j > 1 such that 2Jr 6 (1,2). We claim
that 2k+j E A. Suppose not; then 2k+j E B, i.e., 2k+j = [mb\ for some
m E N:
mb = 2k+j +s, s E (0,1) irrational.
Hence
(2jn - m)b = (2j+k + 2jr) - (2k+j + s) = 2jr - s.
The number on the right side belongs to the interval (0,2); that on the
left is a multiple of b > 2. This is obviously a contradiction. Thus,
indeed, 2k+:> E A; the proof is complete.

Arithmetic and Combinatorics
43
Remark
There exists numbers a > 2, arbitrarily close to 2, such that the set of
integers "nice with respect to a" is finite.
Take for instance a number whose reciprocal has the binary
representation
- = (0.0 11... 11 00 ... 00 1 00... 00 1 00... 00 1 )2
771 ?7li 7712 7713
where m > 1 and m-i > m for each i.
Consider the product u — 2k • (l/o), where A; is an integer greater than
m. The first binary digit of u after the point is either a zero or a one
followed by a block of mi zeros (for some i). In either case, the "fractional
part" of u satisfies the estimate
u - \u\ < (0.1 00. . . 00 1)2 = - + —tt < r + 77-7^ •
77li— 1
Note also that
1 111
- < (0.0 11 ... 11 01)2 = - - 7T—7 + —-To •
a v N v ' ' 2 2m+1 2m+3
771
Hence u — \u\ + (l/o) < 1, and consequently \u + (l/a)J = ['"J- As u
is not an integer, this equality shows that there are no integers in the
interval [u, u + (1/a)}. In other words, there is no integer n satisfying
the inequalities 2fe < na < 2k + 1.
This shows that no power 2fe, with any exponent A; > m, is equal to the
integer part of any product na. Clearly, a is close to 2 if m is large
enough. The block lengths mi, m,2, ms,... may form a periodic sequence
or not; accordingly, a can be made rational or irrational, as we please.
Problem 14
Four numbers are randomly chosen from the set {1,2,..., 3n} (n is a
fixed integer greater than 1). Compute the probability that the sum of
those four numbers is divisible by 3.
Problem 14, Solution 1
The sum of four integers is divisible by 3 if and only, if their remainders
modulo 3 constitute one of the following patterns:
(0,0,0,0), (0,1,1,1), (0,2,2,2), (0,0,1,2), (1,1,2,2)
— up to permutation (in each quadruple). Enumerate these patterns 1
through 5, in the order as they are listed above. Suppose there are Ni

44
Solutions
four-element subsets of {1,2,..., 3n} corresponding to the i-th. pattern
(for i = 1,2,3,4,5).
Each residue class (0, 1 or 2 (mod 3)) is represented by n numbers in
{1,2, ...,3n}. Therefore
*-C> *="-(")G> *-G)G)' "-&
The probability p we are about to evaluate is equal to the fraction
N/D with numerator N = N\ + N2 + N3 + N4 + N5 and
denominator D = ( 2~) » the number of all four-element subsets in the set under
consideration. It is a matter of a simple calculation to get the outcome
p = N/D = 1/3.
Problem 14, Solution 2
Let T be the family of all four-element subsets of {1,2,..., 3n}. For each
C € T denote by r(C) the remainder the sum of elements of C leaves in
division by 3. Clearly, T — Tq U T\ U JF2, where
Fi = {C eF\ r(C) = i} for i = 0,l,2.
The probability sought equals
P |^o| + |^l| + |J2|*
the symbol \Fi\ denoting the cardinality of family T%, i.e., the number of
sets in that family.
Define the operation c h-> c', acting in {1,2,..., 3n}, by
/_fc + l ifc< 3n,
11 if c = 3n
— the cyclic shift (mod 3n). To each set C 6 J- assign the set
C = {c'\ ce C}.
Since C consists of four numbers, it follows that
r(C) = 0 if and only if r(C;) = 1,
r{C) = 1 if and only if r{C') = 2,
r(C) = 2 if and only if r{C') = 0.
Thus the assignment C h-> C' maps .Fo onto Fi, T\ onto F2) and J^
onto Tq\ hence the three families are equipotent (consist of equally many
members): \Tq\ — \T\\ = JJ^Ij and so p = 1/3.

Arithmetic and Combinatorics
45
Remark
Suppose we choose a /--element set C from
{l,2,...,3n} (k fixed, 1 < k < 3n).
Are all values of r{C) equally probable, as in the case of k = 4?
The method of the second solution yields an affirmative answer to this
question, provided that k is not divisible by 3; indeed, r(C') = r{C) + k
(mod 3); the assignment C >-> C' maps T§ onto T\ or onto T% (etc.),
according as A; = 1 or 2 (mod 3). The argument, however, breaks down
when A; is divisible by 3. For instance, the probability that the sum of 3
numbers randomly drawn from {1,2,..., 9} is divisible by 3, equals 5/14
rather than 1/3.
Problem 15
For what natural numbers n is it possible to tile the n x n-chessboard
with 2x2 and 3 x 3-squares?
Problem 15, Solution 1
If n is even, the tiling is trivially possible. Thus let n be odd and suppose
the chessboard has been tiled as described. In each 3 x 3-tile, colour blue
the three cells (unit squares) adjacent to its left edge, colour red the three
cells adjacent to its right edge, and colour green the three cells in the
middle; the 2 x 2-tiles remain uncoloured.
Enumerate the columns (vertical lines) of the board 1 through n.
Suppose there are bi blue cells, gi green cells, ri red cells and ui uncoloured
cells in the i-th column. Clearly, Ui is even, and the sum bi + gi + Ti + ui
is equal to n2, an odd number. Therefore
bi+gi + ri=l (mod 2) for i = l,...,n. (1)
The right neighbour of a blue cell is a green cell; the right neighbour of
a green cell is a red one. Thus bi = gi+i = r^ and we restate relations
(1) as
ri+2 + ri+i + ri = 1 (mod 2) for i=l, ...,n —2; (2)
or — which is the same —
ri+s + ri+2 + r^i = 1 (mod 2) for i = 0,..., n - 3. (3)
Subtract (2) from (3) to obtain
r;+3 - ri = 0 (mod 2) for i = 1,..., n — 3. (4)

46
Solutions
In the two leftmost columns of the board there are no red cells; so
ri — r2 — 0, and relations (4) imply
Ti = 0 (mod 2) for i non-divisible by 3. (5)
In the rightmost column there are no blue or green cells; so bn = gn = 0,
whence by (1): rn = 1 (mod 2). This in view of conditions (5) shows
that n must be divisible by 3.
In conclusion, if the board can be tiled as required, then n is divisible by
2 or 3. The converse implication is obvious.
Problem 15, Solution 2
A colouring argument can be used in a yet smarter manner. As in
Solution 1, assume n is odd. Colour all the columns of the board black
and white alternately, in a "zebra" fashion. For n odd, the two outer
columns are coloured alike — say, black; so there are n black cells more
than white ones.
Suppose the tiling is possible. Each 2 x 2-tile covers two white cells and
two black cells. Each 3 x 3-tile covers three white cells and six black
cells, or conversely. The difference between the number of black cells
and the number of white cells covered by a single tile equals 3, —3 or
0. The total difference between the numbers of black and white cells
(in the whole board) equals n. Thus n is the sum of some threes, some
minus-threes, and some zeros — hence, it is a number divisible by 3.
Conclusion as in Solution 1: a tiling in question is possible if and only if
n is divisible by 2 or by 3.
Remark
The easy "if" part results from "uniform" tilings, using tiles of only one
of the two kinds. It is however worth noticing that if n > 6 is divisible
by 3 or 2, then one can tile the n x n-board actually using at least one
tile of either kind (the reader may try to show that).
Problem 16
A triangular prism is a pentahedron whose two parallel faces ("top base"
and "bottom base") are congruent triangles and the remaining three faces
are parallelograms. We are given four non-coplanar points in space. How
many distinct triangular prisms having the four given points as vertices
are there?
Problem 16, Solution 1
The four points can be distributed between the two bases of a prism in
two fashions: 3 + 1 or 2 + 2.
First case (3 + 1): Choose three points out of four (this can be done in 4
ways); they span a triangle, which we take for the base of a prism. Link

Arithmetic and Combinatorics
47
the fourth point with one of the vertices of that base (3 possibilities);
the connecting segment will be a side edge of the prism, which is thereby
fully determined.
Second case (2 + 2): Split the given set of four points into two pairs
(there are 3 ways to do that); label the points in one pair A, B and
those in the other C, D. The points A, B are supposed to lie in one
base of the prism under construction, and C, D in the other. Take one
of the segments AC, AD, BC, CD to be a side edge of the prism (4
possibilities); again, the prism is determined.
Thus we can construct 4 • 3 = 12 prisms of the first type and 3 • 4 = 12
prisms of the second type, and this gives 24 as the final outcome.
Problem 16, Solution 2
Imagine an arbitrary triangular prism. Any quadruple of its vertices
necessarily contains at least one pair of points belonging one to the bottom
base, the other one to the top base, and connected by a side edge of the
prism. Hence, if the four given points are to be vertices of a triangular
prism, two of them (call them P, Q) must be the endpoints of a side
edge. The other two points [R and S) cannot be joined by an edge, since
they are not coplanar with P and Q.
There are (2) = 6 ways to choose the pair P, Q. This done, we can attach
each of R, S to either P or Q. The resulting pairs of segments will be
edges of the prism:
PR, PS or QR, QS or PR, QS or PS, QR.
This defines four possible cases. We claim that in each case the prism is
uniquely determined.
In each one of the first two cases, we have already one base triangle (and
the side edge PQ); translate that triangle by the corresponding vector
{PQ or QP) to get the other base.
Consider the third case, with PQ, PR, QS being edges of the prism.
Complete the parallelograms PQR'R and PQSS' (note that R' ^ S and
S' ^ R); the points R' and S' are the remaining two vertices of the prism.
The fourth case is analogous.
We see that, on the total, there exist 6 • 4 = 24 triangular prisms with
four vertices in the given points.
Problem 17
Consider the infinite chessboard with squares coloured white and black,
in the usual manner. Suppose S is a set of 1976 squares such that every
two squares in S can be connected by a path consisting of consecutively
adjacent squares. (Two squares are adjacent if they have a common

48
Solutions
edge.) Show that there are at least 494 white squares in S. Moreover,
show that 494 is the exact bound.
Problem 17, Solution 1
If every two squares in a certain set can be linked (within that set) by
a path consisting of consecutively adjacent squares, we will say that the
set is connected.
We are going to prove a fact slightly more general than requested:
For any positive integer n, the number of white squares in every
connected set of n squares is not smaller than (n — l)/4.
This is trivially true for n = 1,2. Fix an integer n > 2 and assume
inductively that the claim holds for all positive integers smaller than n.
Take any connected set S composed of n squares.
Define the distance between two squares as the minimum number of
edges one has to cross while going from one square to the other, along an
admissible path (within S). Choose and fix a pair of squares A, B € S
whose distance is a maximum; denote their distance by m. (Since n > 2,
m > 1.) Thus there exists a path CqC\ ... Cm-iCm, composed of squares
Ci G S, with Co = A, Cm = B. Remove from S square Cm_i together
with those squares adjacent to Cm_i whose distance from A is exactly
m. Denote by S' the set that remains.
Note that square Cm_2 has not been removed (its distance from A is
m — 2 and not m). So we have removed at most four squares, and hence
|$'| = n' > n - 4.
One of the squares Cm_i and Cm is white, and these two squares have
been moved from <S; so there is at least one white square in the set S \ Sf.
We now show that S' is connected. Choose a square D G <S'. There exists
a path EoEi... Ek-iEk in the set S, with Eq — A, Ek — D; of course,
k < m (by the maximality of m).
Squares Eo,Ei,..., Ek-2 obviously belong to Sf (the distance from A to
each of them is less than m — 1, so they have not been removed from
S in the formation of S'); the question is whether Ek-i also belongs
to S'. Suppose not. The only removed square distant from A by less
than m is Cm_i. Hence Ek-i — Cm-i and k = m. But then the square
D = Ek, adjacent to Ek-i, i.e., to Cm_i, has distance m from A; and
this means that this square should have been removed — contrary to its
choice (D G Sf).
So every square D G <S' can be linked with A within Sf. The
connectedness of S' follows and the induction hypothesis applies: there are at
least {n' — l)/4 white squares in S'. And since S\S' contains at least
one white square, we conclude that the number of white squares in S is

Arithmetic and Combinatorics
49
not less than (n' - l)/4 + 1 > (n - 4 - l)/4 + 1 = (n - l)/4. This is
precisely the induction claim.
The theorem formulated at the beginning is now proved. For n = 1976
it implies the required bound 494. To see that 494 is optimal, consider a
horizontal 3 x 988 rectangle, with white squares removed from the upper
row and from the lower row (but not from the middle one). This is a
connected set of 1976 squares, out of which exactly 494 are white.
Problem 17, Solution 2
We will apply another inductive reasoning to prove the fact stated at
the beginning of Solution 1: if a connected set of n squares has w white
squares, then w > (n — l)/4.
Assume this is true for all positive integers smaller than a fixed integer
n > 1. Let S be a connected set of n squares.
Choose a white square W e S. From any other square in S a path
(contained in S) leads to W, and this path necessarily passes through
one of the four squares adjacent to W. Consequently, every square in
S \ {W} is accessible from one of those four squares via a route omitting
W; i.e., a route contained in S \ {W}. Thus the set S \ {W} is the union
of at most four connected sets. Label these sets <Si,..., Si (1 < / < 4).
Suppose Si consists of ni squares, W{ of them being white. According
to the inductive assumption, wi > {rn — l)/4 for i = 1,... ,1. Therefore,
denoting by w the number of white squares in S, we obtain
i
w = 1 + / ^wj
En,- 1
i=l
1 l
completing the induction step.
The claim is proved. For an argument that for n = 1976 the bound
w > \(n — l)/4] = 494 is sharp, see the last paragraph of Solution 1.

50
Solutions
Problem 18
Consider an alphabet consisting of three symbols a, 6, c. How many
n-character words with the following properties (1) and (2) can be
composed?
(1) the word should begin and end with an a;
(2) neighbouring positions must be occupied by different symbols.
Problem 18, Solution 1
Consider words of length n that begin with an a and satisfy condition (2).
Denote by an, bn, cn the numbers of such words ending in a, b, c,
respectively. Attaching an a to a word of length n whose last character is b or
c we obtain an admissible word of length n + 1. Hence an+\ = bn + cn.
Likewise, bn+i = an + cn and cn+i = an + bn- Since the roles of symbols
b and c are symmetric, we infer bn = cn, and so
«n+i = 2&n, bn+\ = an + bn.
Consequently
an+2 — «n+i = 2(bn+i — bn) = 2an,
i.e.
an+2 = an+l + 2an. (3)
The initial ans are: a\ = 1, ai = 0; a few subsequent terms are computed
using (3):
(ai, a2, a3, a4, a5, a6, a7, a8, a9,...) = (1, 0, 2, 2, 6,10, 22, 42, 86,...).
A "roughly geometric" sequence? Consider (|an):
(..., f a4, §a5, §a6, §a7, f a8, §a9, ...) = (..., 3, 9,15, 33, 63,129,.. .).
The pattern becomes plain: |aTC = 2n-2 + (—l)n_1; i.e.,
aB=§(2»-2 + (-l)»-1). (4)
Once guessed, this equality is easily proved by induction. For n = 1
and n — 2 formula (4) gives the correct values, and the inductive step
((n, n+1) —> (n+2)) follows immediately from equality (3):
an+2 = §(2"-1 + (-1)") + 2 • §(2-2 + (-l)"-1) = §(2" + (-ir+1).
Note that an is the number we had to calculate. Its value is given by
formula (4).

Arithmetic and Combinatorics
51
Remark
The explicit formula (4) could be derived from (3) without guessing,
by the usual method of solving linear recursions (compare Problem 10,
Solution 3, for instance).
Problem 18, Solution 2
Assume n > 3. Imagine a row of n empty cells. They have to be filled-in
with symbols a, b, c, observing conditions (1) and (2). In the two outer
cells, as must be placed; this is prescribed. Assume that character a
occurs A; times inside the row. (Consider k to be fixed, for the while.) There
remain n — 2 — k cells to be filled with other symbols. The occurrences
of a split those cells into A; + 1 blocks of positive lengths /?i,... ,/?fe+i
(positive, because the as never occur on neighbouring positions).
There are {n~k~ ) ways to represent the number n — 2 — k as a sum
of k + 1 positive integers n — 2 — k = /3i + ■ ■ ■ + fik+i (because the sums
/?i, /?i+/?25 /5i+/?2+i53, ..., /5iH h/?fe can constitute an arbitrary
subset of {1,... ,n—3—k}). Every such representation determines the
positions of a. Each of the k + 1 blocks must be filled with bs and cs
alternately, and that can be done in two ways. Summarizing, there are
an words satisfying conditions (1) and (2), where
- = £CT>*+1;
(5)
applying the usual convention that (^) = 0 whenever k < 0 ov k > m
(cf. the solution to Problem 3), we may assume that A; in the sum in
formula (5) ranges over the set of all integers.
To bring this sum to a closed form, note that
Ei (n — 2 — k\ (n — 3 — A; \ \
fe
= E
fe
= E
n — 3 — k
k-1
n-A-l
fe+1
1+2
= 2E("T >,+1
= 2an_i (for n > 4),

52
Solutions
and we arrive at the recurrence formula (3) of Solution 1. For n = 3, 4
the expression (5) yields a3 = a^ = 2. The explicit formula (4) is deduced
in a standard way; see Solution 1.
Problem 19
Nine trucks follow one another, in a line, on a highway. At the end of a
day's ride it turned out that each driver disliked the style of the driving
of the one in front of him. They wish to rearrange themselves so that,
next day, no truck would follow the same truck that it followed on the
first day. How many such rearrangements are possible?
Problem 19, Solution 1
Translated into mathematical terms, the problem is to calculate the
number of permutations of the set {1,2,..., 9} in which no one of the
successions 12, 23, 34, 45, 56, 67, 78, 89 appears. Let F(n) be the
number of permutations of {1,2,..., n} with the analogous property (call
them feasible). We are going to derive a recurrence formula. Clearly,
F(l) = F(2) = 1.
A permutation of
{1,2,... ,n,n+l}
arises from a permutation tv of
{l,2,.,.,n}
by inserting the element "n+1" to one of n+1 positions (n—1 sockets
between successive entries, plus two outer positions, one at the beginning
and one at the end). The arising permutation will be feasible if either
■k is a feasible permutation and the element "n+1" is placed on any
position except the one immediately after the "n" or -k is a non-feasible
permutation, feasibility violated by a single forbidden pair A;, k+1 in
direct succession, and the element "n+1" is placed just so as to disconnect
that pair.
In the first case there are n possibilities of inserting the element "n+1"
into one of F(n) feasible permutations -k of {1,2,..., n}. This yields the
first summand in the recurrence formula (1) (below). In the second case
the address of "n+1" is determined (between "fc" and "fc+1"), while A;
can be any number out ofl,2,...,n—1; the permutation -k with the only
non-separated pair k, k+1 can be identified with a feasible permutation
of an (n— l)-element set, since we can regard the "brick" (A;, k+1) as a
single entity. This yields the second summand in the formula we arrive
at:
F(n + 1) = nF(n) + (n-l)F(n-l). (1)
Using this formula and knowing the initial data F(l) = F(2) = 1 we
easily compute F(9) = 148329.

Arithmetic and Combinatorics
53
Problem 19, Solution 2
For i = 1,2,... ,n, let Vi be the set of those permutations of the set
{1,2,... ,n} in which the element "i" appears immediately after "i—1".
Note that 17^1 = (n — 1)! (the number of arrangements of the elements
1,2,..., i—1, i+1,..., n ; the position of V is determined).
If K is a subset of {2,..., n} with \K\ = k, then
\f]Vi\ = (n-k)\ (2)
i€K
(such is the number of permutations of {1,2,..., n} \ K; any such
permutation uniquely generates a permutation that belongs to (j Vi —
i€K
the elements of K have to be inserted, from smallest to greatest, to the
appropriate places, fully determined).
A permutation is feasible if and only if it does not belong to any Vi-
Thus
n
F{n) = n\- \\JVi\.
i=2
By the Inclusion-Exclusion Principle, and in view of equality (2),
n n n
\\jVi\ = ^i^i-Ei^n^i+---+(-i)n-i|n^|
i=2 i=2 i<j i=2
= S-i)*+i e |nH
fe=l KC{2,....,n} i€K
\K\=k
n-l
fe=l
n-l
k+1n-k
= (n-l)!^(-l)
fe=i
Consequently,
F(n) = n!-(n-l)!^Vl)fc+l!^ = (--l)!E(-l)^"fc
fc=l fc=0
For n = 9 this quantity evaluates to 148329. This is the number sought.

54
Solutions
Problem 20
We are considering paths (Pq, Pi, ..., Pn) of length n over lattice points
in the plane (i.e., points (x,y) with integer coordinates); for each i, the
points Pi-i and Pi are assumed to be adjacent on the lattice grid. Let
F(n) be the number of those paths that begin in Pq — (0,0) and end in
a point Pn lying on the line y = 0. Prove that F(n) = (2^).
Problem 20, Solution 1
For any integer A;, denote by f(n,k) the number of paths of length n
(short, n-paths) beginning in (0,0) and ending in a point on line y = k.
Thus F(n) — f(n, 0). Every (n — l)-path ending either on line y = A; — 1
or on line y = k + 1 can be uniquely extended to an n-path ending on
line y = k. An (n — l)-path ending on line y = k admits exactly two such
extensions. Hence follows the recursion formula
f(n, k) = f(n - l,k - 1) +2f(n - l,k) + f(n -l,k + 1). (1)
There exists only one feasible path of length 0 (both its endpoints
coinciding with the origin). So
/(0,fe) =
1 for Jfc = 0,
0 for k + 0.
(2)
Formulas (2) and (1) generate the table of values of f(n,k):
Jfc = ...-4 -3 -2 -1 0 1 2 3 4
000010000
000121000
001464100
0 1 6 15 20 15 6 1 0
Even-numbered rows of Pascal's triangle are readily recognized. Hence
we guess that f(n,k) = g(n,k), where
g(n,k)= [n~+k) ^ n, |fc| = 0,1, 2,
(3)
To prove this guess, it will be enough to show that the numbers g(n, k)
obey the same recursion relation as the f(n,k)s.
With the convention that (fy — 0 when r is smaller than 0 or greater
than q, the fundamental Binomial Identity g) = (J~^) + (q~l) holds,
without any restriction, for every natural q and every integer r (compare

Arithmetic and Combinatorics
55
Problem 3, Solution 1). Using this identity, we calculate
V ; \n + kj \n + k-lj \n + k
In - 2 \ / 2n - 2 \ fin-2
n + k -2) \n + k-lj \n + k
= g(n-l,k-l) + 2g(n - 1, k) + <?(n - 1, fc + 1); (4)
and moreover,
The recursion formulas (1) and (4) for / and g are the same, and so are
the initial values (2) and (5). So the guess (3) was correct. Hence, in
particular,
F(n) = /(ra,0) = g(n,0) = ( U J for n = 0,1,2,....
Problem 20, Solution 2
An n-path (Po, Pi,..., Pn) beginning in Pq = (0,0) can be encoded by
a (2n)-string of zeros and ones (ci,c2,... ,C2n-i,c2n), according to the
following rules:
if Pj-iPj = [1,0], then c2j-i — 1, c2j = 0
if Pj-iPj = [0,1], then c2j-i = 1, c2j = 1
if Pj-iPj = [—1, 0], then c2j-i — 0, c2j = 1
if Pj-iPj — [0, —1], then c2j-i = 0, C2j = 0.
To put this in words: each couple of successive symbols (c2j-i,c2j)
represents one step on the path; a step east is rendered by the coupling
(10); a step north - by (11); a step west — by (01); a step south — by
(00). And conversely, every such (2n)-string represents a feasible path.
To distinct paths there correspond distinct codes; the coding is bijective.
Suppose a path consists of u steps north, v steps south, and (jointly)
n — u — v steps east or west. Then the endpoint Pn lies on line y = A;
if and only if u — v = k ("horizontal" steps are irrelevant). The number
of "ones" in the code of such a path equals 2u + (n — u — v), i.e., n + k.
Consequently, the paths ending on line y = 0 are encoded by binary (2n)-
strings with exactly n "ones". As there are exactly (^) such steps, the
result follows.

56
Solutions
Problem 20, Solution 3
As in Solution 2, we regard a path as consisting of steps north, south,
east and west. A path ends on the line y — 0 if and only if there are
equally as many steps north and south.
Now, look at the polynomial (x2 + 2x + l)n, written in the form
(x2 + x + x + 1) (x2 + x + x + 1) • • • 02 + x + x + 1) (6)
(product of n factors). Multiplying out, we obtain the sum of terms
xr with exponents r = 0,1,... ,2n. Each of these terms results by an
independent choice of one of the four entries from each factor (the x2,
the "first" x, the "second" x, the 1).
Every such selection induces a feasible path. Namely, let us agree that:
if the term selected then the j-tla. step
from the j-th. factor is: is performed:
x2 north,
first x west,
second x east,
1 south.
Paths ending on the line y = 0 correspond to those selections in which
x2 is used as many times as 1. The product of the selected terms equals
xn in that case; in any other case it is different from xn. Hence, the
number of paths ending on line y = 0 is equal to the coefficient of xn in
the polynomial (6). It remains just to notice that
(*»+2,+i)" = (*+i)a» = £;(2;y.
r=0 \ r /
Accordingly, the coefficient of xn equals (2^). Thus F(n) = (2^).

Solutions: Algebra
Problem 21
Determine all real polynomials P(x) of degree not exceeding 5, such that
P(x) + 1 is divisible by (x - l)3 and P(x) - 1 is divisible by (x + l)3.
Problem 21, Solution 1
Let P(x) be as required; then
P(x) + l=(x- l)3Q(x), P(x) -l=(x + l)3R(x),
with Q(x) and R(x) real polynomials of degree 2 (at most). In each of
them the leading coefficient is the same as in P(x) (zero not excluded),
and thus Q(x) = ax2 + bx + c, R(x) = ax2 + px + q. The postulated
identities result in P(x) + 1 = (x3 — 3x2 + 3x — l)(ax2 + bx + c), i.e.,
P(x) + l = ax5 + (b-3a)x4 + (c-Sb+3a)x3 + (-3c+3b-a)x2 + (Sc-b)x-c
and, analogously,
P(x)-1 = ax5 + (p+3a)x4 + (q+3p+3a)x3 + (3q+3p+a)x2 + (3q+p)x+q.
Hence, comparing the coefficients,
b — 3a = p + 3a,
c — 3b + 3a = q + 3p + 3a,
— 3c + 36 — a = 3o + 3p + a,
3c — b = 3o +p,
-c = g + 2.
Luckily enough, this system of five equations with five unknowns is quite
easy to solve and yields
o=-|, & = -§, c=-l, p=§, q = -1.
Thus P(x) is given by any one of the following two equalities:
P(x) = ^-^(.p.^.!).^
P(x) = (x + l)3(-lx2 + lx-l) + l.
Each of them produces the final formula P(x) = — |x5 + ^a;3 — ^x,
defining the unique polynomial with properties as needed.

58
Solutions
Problem 21, Solution 2
The reasoning will be based on the well-known fact of algebra: a
polynomial F(x) is divisible by (x — xo)k if and only if its derivative F'(x) is
divisible by (x — xo)k~l, and moreover F(xo) = 0.
Let P(x) be any polynomial of degree at most 5. Then each one of the
statements 1-4 (below) is equivalent to the subsequent one (we write
G(x)\H(x) when G(x) divides H(x)):
Statement 1.
(x- l)3 | P(x) + 1 and (x + l)3 | P(x) - 1.
This is just the condition of the problem.
Statement 2.
(x - l)2 | P'{x)- (x + l)2 | P'(x); P(l) + 1 = 0 = P(-l) - 1.
Statements 1 and 2 are equivalent in view of the theorem formulated at
the beginning, applied to F\(x) = P(x) + 1 and 1*2(x) = P(x) — 1.
Statement 3.
(x2-l)2\P'(x)- P(l) = -1; P(-l) = l.
Statements 2 and 3 are equivalent because (x — l)2 and (x + l)2 are
coprime polynomials, and hence P'{x) is divisible by both of them if and
only if it is divisible by their product.
Statement 4-
P'(x) = Ax4-2Ax2 + A- P(l) = -1; P(-l) = 1.
(The degree of P(X) does not exceed 5.)
Statement 5.
P(x) = \Axb - lAx3 + Ax + C; P(l) = -1; P(-l) = 1.
The equivalence between statements 4 and 5 follows from the deriva-
tive/antiderivative algorithm.
Now, if P(x) satisfies the conditions of Statement 5, then by setting x = 1
and x = — 1 we obtain C + j$A — — 1, and C — j^A = 1, whence C = 0,
A — — y , and so
Pyx) = — gS + -g-x g-x.
Conversely, if P(x) is given by this formula, then the conditions of
statement 5 are satisfied. And since statement 5 is equivalent to statement 1,
we infer that the polynomial P(x) = — |x5 + ^§x3 — ^-x is the unique
solution to the problem.
Problem 22
Prove that the polynomial xn + 4 factors into the product of two
polynomials of lower degrees with integer coefficients if and only if n is divisible
by 4.

Algebra
59
Problem 22, Solution 1
Assume xn + 4 = F(x)G(x),
F(x) = ao + a\x -\ + akx , G(x) = bo + b\x -\ + brnxm\
a{, bj integers; 0 < fc < n, 0 < m < n, k +m = n.
Then ao&o = 4, akbm = 1, and hence ak — bm = ±1. It is convenient to
set cii — 0 for i > k and bj = 0 for j > m. Let a be the least index for
which aa is odd and let /3 be the least index for which bp is odd. Since
o-k — ^m — =tl, we have a < k and (3 < m. In the product F(x)G(x), the
coefficient of xa+@ equals
aa+pbo + aa+/3_i&i -\ + aab/3 -{ h aiba+p-i + ao&a+/3- (1)
In this expression all summands except aabp are even numbers (because
a{S are even for i < a and bjS are even for j < /5). So the coefficient (1)
of xa+/3 in F(x)G(x) = xn + 4 is odd, which means that a + /? = n,
and consequently a = k, (3 = m. Thus, according to the definition of a
and /5,
ao, a\,..., afc_i , 6o, 6i,..., 6m_i are even numbers. (2)
Since ao&o — 4, we get ao — bo — ±2.
We claim that k — m. Assume the contrary: let k < m, say. Write the
product of F(x) and G(x) in the form
F(x)G(x) = P(x)+Q(x)+xn, (3)
where
P(x) = (a0 + alX-{ h afc_ia;fe~1) (b0 + bxx -\ +&m_izm~1),
Q(x) = [akb0xk + akb\xk+l -\ h afc6m_ia;TC-1)
+ (bma0xrn + bmaixm+1 + ■■■ + bmdk^x71-1).
In view of property (2), all coefficients of P(x) are divisible by 4, while
the coefficient of xk in Q(x) equals ±2 (as a^ = ±1, 6q = ±2). Thus the
coefficient of xk in the polynomial (3) is an even integer, non-divisible by
4; and this is a plain contradiction with the equation F(x)G(x) = xn + 4.
This settles the claimed equality k = m. Consequently n = 2k, and
therefore
F{x)G(x) = x2k + 4> 0. (4)
It follows that F(x) and G(x) are real polynomials without real roots,
hence of an even degree. So k is an even number, i.e., n is divisible by 4.

60
Solutions
And conversely, if n = 4/, I e N, then
xn + 4 = (x2< + 2x< + 2) (x21 - 2xl + 2)
is the desired factorization.
Problem 22, Solution 2
The equation xn = -4 has n distinct complex roots zi,...,zn, each of
an absolute value of 41/n. If xn + 4 factors into a product F(x)G(x),
then each of zi,...,zn must be a root of either F(x) or G(x). Assume
z\,...,zk are roots of F(x) and z\,..., ^n_fc are roots of G(x); then
F(x) = A(x - z\) ■ ■ ■ (x - zk), G(x) = B{x - zk+1) ■ ■ ■ {x - zn),
with non-zero constants A and B, satisfying AB = 1. The factors F(x)
and G(x) are assumed to have positive degrees and integer coefficients.
So 0 < A; <n and A = B = ±1. The free terms of F(x) and G(x), equal
respectively to (—l)kAzi ■ ■ ■ zk and (—l)n~kAzk+i ■ ■ • zn, should also be
whole numbers. Their absolute values 4fe/n and ^n~k^n are comprised
strictly between 1 and 4 (as 0 < A; < n), and their product is equal to 4.
Hence, each of them equals 2, which means that A; = n/2, and we arrive
at the inequality (4) of Solution 1. Conclusion as before.
Problem 23
Find all natural numbers n for which the polynomial
Pn(x) = x2n + (x + l)2n + 1
is divisible by the trinomial T(x) = x2 + x + 1.
Problem 23, Solution 1
Note that T(x — 1) = x2 — x + 1, and so
x6 - 1 = (x - l)(x2 + x + l)(x + l)(x2 - x + 1) = (x2 - l)T(x)T(x - 1).
Replacing x by x + 1,
(x + l)6 - 1 = (x2 + 2x)T(x + l)T(x).
Therefore the difference
Pn+3(x) ~ Pn(x) = X2n+6 + (x + l)2n+6-X2n-(x + l)2n
= x2n(x6 - 1) + (x + l)2n((x + l)6 - 1)
is divisible by T(x), for every integer n > 0. Since
P0(x) = 3, P1(x) = 2T(x), P2(x) = 2T{x)2,

Algebra
61
obvious induction shows that Pn(x) is divisible by T(x) if and only if n
is non-divisible by 3.
Problem 23, Solution 2
A polynomial P(x) is divisible by T(x) if and only if the two complex
roots of T(x),
a = —^ + ^v/3i and /? = — \ — \y/%i,
are also roots of P(x). These numbers satisfy the equalities:
c*2 = /?, (32 = a, c*3 = /?3 = l, (a + l)2 = a, (/? + l)2 = /?.
Consequently, each of the two numbers
Pn(a)=(a2)n + ((a + l)2)TC+ 1
and
^(/5)=(/5T+((/5 + l)T + l
equals just an + /3n + 1.
Writing a natural number n in the form n = 3k +r, with r being 0, 1 or
2, we obtain
Pn(a) = Pn(P)
= a3fe+r + /53fe+r + 1
= ar + (3r + 1
f 3 if r = 0,
10 if r = 1 or r = 2.
Conclusion: T(x) divides PTC(a:) if and pnly if r ^ 0 (mod 3).
Problem 24
For every positive integer k show that the polynomial
Pk(x) = (x4 -l)(x*-x2+x-l)k+(x + l)x4k~l
is divisible by the binomial x5 + 1.
Problem 24, Solution 1
Write for brevity
p(x) = x —x +x — l, q(x) = x — p(x)
and notice that
x4 - 1 = (x + l)p(x), x5 + 1 = (x + l)q(x), (1)

62
Solutions
and thus
Pk(x)=(x4-l)p(x)k + (x + l)x4k-1=(x + l)(p(x)k+1+x4k-1). (2)
The claim will be proved by induction. For A; = 1,
Pi(x) = (x4 - l)(x3-x2+x-l) + (x + l)x3
= x7 - x6 + x5 + x2 - x + 1 = (a;2 - x + l) (x5 + l).
It is evident from (1) and (2) that the divisibility of Pk(x) by x5 + 1 is
equivalent to the divisibility of the polynomial
Qk(x)=p(x)k+1+x4k-1
by q(x). And since, by the definition of q(x),
Qk+1(x) = p{x)k+2+x4k+3
= p(x)k+2 + (p(x)+q(x))x4k-1
we see that Qk+i(x) is divisible by q(x) whenever Qk(x) is. This
completes induction.
Problem 24, Solution 2
Let p(x) and q(x) have the same meaning as in Solution 1. In view of
(1),
(x4 - l)q(x) = (x + l)p(x)q(x) = (x5 + l)p(x).
The fcth power of p(x) = x4 — q(x) equals (by the Binomial Theorem)
x4k plus the sum of terms divisible by q(x). Thus
p(x)k = x4k+q(x)Rk(x),
where Rk(x) is a polynomial. Using these equalities together with (2)
we obtain
Pk(x) = (x4-l)[q(x)Rk(x)+x4k] + (x + l)x4k-1
= (x4 - l)q(x)Rk(x) + x4k~1(x5 -x) + (x + l)*4*"1
= {x5 + l)p(x)Rk(x) + x4k-X (x5 + 1),
showing that Pk(x) is divisible by x5 + 1.
Problem 24, Solution 3
It will be enough to show that each complex root of x5 + 1 is also a root
of Pk(x). Obviously, xq = — 1 is a root of Pk(x).

Algebra
63
Let now A be any non-real root of x5 + 1 . Then by the second equality
of (1), g(A) = 0, and hence p(X) = A4, by the definition of q(x). This
inserted into equation (2) results in
Pfc(A) = (A + l)((A4)fe+1 + A4*"1) - (A + ljA4*"1^6 + 1) = 0,
just as needed.
Problem 25
Find all pairs of real numbers a, b such that the polynomials
P(x) = x4 + 2ax2 + 4bx + a2 and Q(x) = x3 + ax + b
have two distinct common real roots.
Problem 25, Solution 1
Suppose x\ and xi are real roots of P(x) and Q(x) (x\ ^ x2). They are
also the roots of
T(x) = P(x) - xQ(x) = ax2 + 36a; + a2.
Thus a/0 and the discriminant D of the trinomial T(x) must be
positive: D = 9b2 - 4a3 > 0. By Viete's Formulas,
xi + x2 — —3&/a, x\X2 = a.
Since, by assumption, x\ ^ X2 and Q(x\) — Qix^) = 0, we obtain
Q = Q{xi)-Q(x2)
x\ — x2
xl ~ x2 + axl ~ ax2
X\ — X2
= xl + x\X2 + x2 + a
— {x\+X2) —x\X2 + a
= (-3b/a)2.
So b — 0 and 0 < D = -4a3, i.e., a < 0.
And conversely, if b — 0 > a, then the polynomials
P(x) = x4+2ax2+ a2 = (x2+ a) and Q(x) = a;3 + ax = x(x2 + a)
have the common roots \J — a and — ^/ — a. Thus the pairs sought are
those of the form (a, 0) with a < 0.

64
Solutions
Problem 25, Solution 2
The derivative of P(x) equals 4Q(x). Thus if x\ and X2 are real roots
of both P(x) and Q(x), then they are double roots of P(x), and
consequently
P(x) = (x-xiy(x-x2) = x* - 2(xi + x2)x6 + (■ ■ -)xz - {■■■)x+x{x^.
Therefore 2x\ + 2x2 = 0, x\x\ — a2-> and we conclude that one of the
numbers x\, x2 must be equal to yfa| and the other to — \f\a\ (the
condition x\ ^ x2 implies a/0). Now,
P(x) = (x - y/\a\ ) (x + v^H ) = (x2 - \a\ ) = x4 - 2\a\x2 + a2.
Comparing this with the definition of P(x) we see that 6 = 0 and
a = — \a\ < 0,
and so the pair (a, b) must be of the form (a, 0) with a < 0. Conversely,
every such pair satisfies the demands of the problem (see Solution 1).
Problem 26
Let a, x, y, z be real numbers such that
cos x + cos y + cos z sin x + sin y + sin z
~, n = ^—; v— = a.
cos(x + y + z) sm(x + y + z)
Prove the equality: cos(y + z) + cos(z + x) + cos(x + y) = a.
Problem 26, Solution 1
In what follows, all sums are cyclic over the triple (x,y,z) (thus, e.g.,
the symbol ^sinx denotes the sum sinx + siny + sinz, etc.). Write
w = x +y + z. Then, by assumption,
y cos a: = acosw, y sin a: = asinw.
Hence
2_"cos(y + z) = yjcos(w — x)
= ^J(cosw cos x + sin w sin a?)
= (cos w) y ^ cos x + (sin w) y j sin x
= a cos w + a sin w = a.

Algebra
65
Problem 26, Solution 2
Using the Euler Formulas
eix + e-ix ^ eix _ e-ix
cos x = , sin x = ,
2 2i
we restate the assumptions in the form
Y^(eix + e~ix) = a(eiu; + e"™), X^ ~ e~iX) = a(e™ ~ e~™)-
Adding and subtracting these two equalities, we obtain two new ones:
Eix iw \ A — ix —iw
e = ae , / e ~ ae
Consequently,
O \ "* ix , \ "* —ire
za = —r- > e H r- > e
gllO / > g— 110 / v
— V^Ce^w-a!) _|_ e-*(w-s)\
= 2 y^cos(w — x),
and the claim results.
Problem 27
If a, 6, c are pairwise distinct real numbers, show that the value of the
expression
a — b b — c c — a
1 + ab 1 + be 1 + ca
is never equal to zero.
Problem 27, Solution 1
Multiply the given expression by the product of the three denominators
and denote the resulting expression by F(a, b, c):
F{a,b,c) = (a-b)(l + bc)(l + ca) +
+(b - c)(l + ca)(l + ab) + (c - a)(l + o&)(l + be). (1)
We have to show that if a ^ b ^ c ^ a, then F(a, 6, c) ^ 0; and this
follows directly from the transformation:
F(a,b,c) = (a-6) + (a2 - &2)c + (ca - &c)a&c
+(6 - c) + (&2 - c2)a + (a& - ca)abc
+(c - a) + (c2 - a2)6 + (6c - ab)abc
= ca — b c + ab — c a + be — a b
= (a — &)(& — c)(c — a).

66
Solutions
Problem 27, Solution 2
Consider a and b to be fixed and replace c in (1) by a variable x:
F(a, b, x ) = (a-b)(l + bx)(l + ax) + (b-x)(l + ax)(l + ab)
+ (x-a)(l + ab)(l + bx). (2)
For a, b fixed, (2) is a quadratic polynomial in x. The coefficient of x2
in (2) equals
(a - b)ba - a(l + ab) + (1 + a6)6;
this simplifies to b — a ^ 0, showing that the polynomial (2) is not equal
identically to zero. Setting in (2) x = a and x = b we get value 0 (easy
verification). A non-zero polynomial of degree 2 cannot have a third
root. Since a, b, c are three distinct numbers, we infer that the value of
(2) for x = c is different from zero; i.e., F(a, b, c) ^ 0, as needed.
Problem 27, Solution 3
Let a = tana, b = tan j3, c — tan7 with a,/3,7 € (—7r/2,7r/2). Since a,
6, c are pairwise distinct, so are a, j3, 7. From the equality
. . tan a — tan /3 a — b
tan(a — j3) =
l + tanatan/3 1 + ab
we see that the expression defined in the problem statement is equal to
tan(a-/3) + tan(/3-7) + tan(7-a). (3)
In the identity tan it + tanv = (1 — tan u tan v) tan(u + v) set for u and
v the differences j3 — 7 and 7 — a; the sum (3) is seen to be equal to
tan(a — P) + (l — tan(/3 — 7) tan(7 — a)) tan(/3 — a),
simplifying to
tan(/3 — 7) tan(7 — a) tan(a — /3). (4)
The (distinct) numbers a, j3, 7 lie in (—ir/2,7r/2); so the numbers /3 — 7,
7 — a, a — f3 lie there, too, and are different from zero. It follows that
the factors of the product (4) are different from zero, and this is just
what we need to conclude the proof.
Problem 28
Solve the system of equations:
x + y + xy = 19, y + z + yz = 11, z + x + zx — 14.

Algebra
67
Problem 28, Solution 1
From the first and the second equation,
x(y + 1) = 19 - y, z(y + 1) = 11 - y.
Evidently, y cannot be —1, so we may divide by y + 1:
19 -y 11 -y
x = , z = .
y + 1 y + 1
Substitution into the third equation of the system yields
19 -y 11 -y (19-y)(ll-y) = ^
y + l y + l (y + l)2
which is equivalent to
U(y + l)2 - (30 - 2y){y + 1) - (19 - y)(ll - y) = 0,
simplifying to y2 + 2y — 15 = 0. The solutions of this quadratic are
yi = 3 and y<z = —5; the corresponding values of x and z are computed
from the previous formulas. So there are exactly two solution triples
(x,y,z): (4,3,2) and (-6,-5,-4).
Problem 28, Solution 2
The system is equivalent to
{x + l)(y + 1) = 20, (y + \){z + 1) = 12, (* + l)(ar + 1) = 15.
The sums x + 1, y + l, z + 1 must be different from 0. Dividing the
first equation by the second we obtain (x + l)/(z + 1) = 5/3, i.e.,
x + 1 = |(,z + 1). Inserting this into the third equation, (z + l)2 = 9.
Thus z = 2 or z — —4; accordingly, a; = |(z + 1) — 1 equals 4 or —6,
and y is computed from any one of the first two equations of the system.
Outcomes as in Solution 1.
Problem 28, Solution 3
Recast the equation system into the form as in Solution 2. Multiply these
equations to obtain
Or + l)2(y + l)2(2 + l)2 = 3600;
so the product P = (x + \){y + \){z + 1) is equal to either 60 or —60.
Now,
P P
x = (x + 1) -1= - 1 = 1
V } (y + l){z + l) 12

68
Solutions
and analogously
p i p i
Setting P = 60 and F = —60 yields the two triples [x, y, z) = (4,3,2) and
(-6,-5,-4).
Problem 29
Solve the system of equations
x\(x\ — 1) = X2 — 1
^2(^2 - 1) = #3 — 1
in real numbers x\,..., xn.
Problem 29, Solution 1
Let (x\,... ,xn) be a solution. Note that xi > 1 => a^i+i > 1. Assume
xi0 < 0 for a certain iq. Then xi0+i = 1 + xi0(xi0 — 1) > 1, and all
subsequent (cyclically) xiS are > 1; in particular, xi0 > 1, a contradiction.
Thus all XiS must be positive. Now the system implies that all the
differences xi — 1 are simultaneously positive, negative or zero. In the
first two cases we multiply all the equations and cancel the non-zero
product Y\(xi ~ 1) (which appears on both sides), with the result that
Y[xi = 1- This however contradicts the fact that all xis are greater than
1 or they are all smaller than 1.
The only possibility that remains is that xi = 1 for all i. Clearly, this is
a solution.
Problem 29, Solution 2
Adding all the equations leads to
n n
^(xf-Xi) = ^2(Xi- 1);
equivalent ly,
n
Y^{4 - 2xi + 1) = 0,
i=l
i.e.,
x>? -^=°-
Thus x\ = • • • = xn = 1.

Algebra
69
Problem 30
Solve the system of equations
x +V H ;— = 1, \/x+y = x -y
x + y
in real numbers x, y.
Problem 30, Solution 1
If x, y are a solution, then clearly x + y > 0. Assuming x + y > 1, we
get from the first equation
, 2, 2 , 2xy x2+y2 2xy {x + y)2
1 = x* +y* -\ > 1 = = x + y > 1,
x+y x + y x+y x+y
a contradiction. A similar contradiction is yielded by assuming that
x + y < 1 (the inequalities have to be reversed). Thus x + y must be 1,
and the second equation of the system becomes 1 = x2 — (1 — x), with
roots x = 1 and x = —2. So the system has two solutions (x,y); these
are: (1,0) and (-2,3).
Problem 30, Solution 2
Multiply the first equation by (x +y):
(x2 + y2)(x + y) + 2xy = x + y.
Adding x2 + y2 to both sides of this equation, we are driven by standard
manipulations to a nice factorization:
{x2 + y2)(x + y) + (x + y)2 = {x2 + y2) + (x + y);
{x2 + y2){x+y-l) + (x + y)(x + y - 1) = 0;
(x2 + y2 + x + y)(x + y - 1) = 0.
The first factor cannot be zero because the sum x + y is positive (this is
obviously implied by the system). So x + y — 1 must be zero. Inserting
y = 1 — x into the second equation of the system we find the two solutions
(z,i/) = (1,0) and (a:,i/) = (-2,3).
Problem 31
Solve the system of equations
x +y +z =2, x + y + z = 2 + xyz
in real numbers x, y, z.

70
Solutions
Problem 31, Solution 1
Two equations and three unknowns? This is a clear indication that there
must be some inequality hidden behind the problem statement.
Suppose x, y, z satisfy the system. Write
u = yz, v = zx, w = xy, s = x + y + z, g = xyz.
From the first equation of the system we get x2 + (y — z)2 = 2 — 2u.
The left-side expression is a non-negative number. Hence u < 1;
analogously, v,w < 1, and therefore
(l-«)(l-u)(l-ty)>0. (1)
By the definition of s, u, v, w,
s2 = (x + y + z)2 = 2 + 2(ti + v + w),
and so u + v + w = |s2 — 1. Moreover, vw + wu + uv — sq and
uvw = g2. Thus we can transform the left side of (1) as follows:
(1 — u)(l — v)(l — w) — 1 — (u + v + w) + (vw + wu + uv) — uvw
= 1- (is2 - 1) + sq- q2 = 2- \{s - q)2 - \q2.
According to (1), this is a non-negative number. Hence follows the
inequality
\(s-q)2<2-\q2<2. (2)
Therefore \s — q\ < 2, while the second equation of the system says that
s — q = 2. This means that equality must hold in (2).
Now, the right inequality in (2) arose from q2 > 0; so it turns into
equality only if one of the numbers x, y, z equals 0. Let e.g. z = 0; then
u = v = 0 and x + y = s — s + q = 2. The left inequality in (2) comes
from condition (1); equality in (1), combined with z = 0, implies w — 1,
i.e.., xy = 1. The unique solution of the system x + y = 2, xy = 1 is
x = y = 1.
This yields the Solution 1 triple (x,y,z) — (1,1,0) (the only one with
z — 0). By symmetry, (1,0,1) and (0,1,1) are two other solution triples;
and there are no others.
Problem 31, Solution 2
Readers familiar with multivariate calculus can regard this as a
maximization problem: inspect the extrema of
f(x, y,z) = x + y + z- xyz,

Algebra
71
given that s2 + j/2 + z2= 2. The last equation describes a sphere, hence
a compact set. So a maximum must be attained at some point(s) of this
sphere. By the Lagrange Multiplier Theorem, any extremum point is a
critical point of the Lagrange function
g(x, y, z) = f(x, y, z) - X(x2 + y2 + z2 - 2);
i.e., a point such that dg/dx — dg/dy = dg/dz — 0. Thus, at an
extremum point:
1 — yz = 2Xx, 1 — zx = 2Xy, 1 — xy = 2\z. (3)
Multiplying the first of these equations by x, the second by y and the
third by z, we get
xyz = x- 2Xx2 = y- 2Xy2 = z - 2Xz2. (4)
For any fixed value of A, the function ip(t) = t — 2Xt2 can take the value
xyz at two distinct points, at most; so the system (4) forces that two of
x, y, z must be equal. Let e.g. x = y. Then the system (3), accompanied
by the equation of the sphere, becomes
1 - xz = 2Ax, 1 - x2 = 2Xz, 2 - 2x2 = z2. (5)
The second and the third equation of (5) result in z2 = 4Az. So we
have either z — 0 (yielding x — y = ±1) or A = |z, which inserted into
the first equation gives 3xz = 2. This together with the last equation
of (5) is solved in a routine way. Outcomes: x = y = \z = ±|Vo and
x = y = z — ±gVo.
Now we have the complete list of points (x,y,z) at which f(x,y,z) might
be a maximum (up to permutation of variables):
(6,6,0), (e£\/3, ei\/3, e%V3, ), {e^y/H, e%y/6, e±y/6,),
with e = ±1. Comparing the values of / at these points we find out that
2 is the maximum value of / on the sphere in question, attained only
at (1,1,0), (1,0,1) and (0,1,1). Hence, these three triples are the only
solutions (x,y,z) of the system under consideration.
Problem 32
Let n > 3 be a fixed integer and let a, b, c be fixed real numbers with
a + b + c = 0. Find all n-tuples (x\,..., xn) of real numbers satisfying
the system of simultaneous inequalities
axi—i + bxi + cxi+i > 0 for i = 1,..., n,
where by definition xq = xn, xn+\ = x\.

72
Solutions
Problem 32, Solution 1
Suppose (x\,..., xn) is a solution. Let s = xi + ■ ■ • + xn. The left side
expressions of all the given inequalities are non-negative numbers and
their sum equals as + bs + cs = 0. Thus all those numbers are equal to
zero and the inequalities of the system are in fact equations:
axi-i + bxi + cxi+i = 0 for i = l,...,n. (1)
If a = b = c = 0, then every n-tuple (x\,..., xn) is a solution.
Rejecting this trivial case from further considerations, assume that
a2 + b2 + c2 > 0.
Then at least two of the numbers a, b, c must be different from zero.
Hence a2 -f c2 > 0.
Evidently, every constant n-tuple x\ = • ■ • = xn satisfies the system (1).
Let us look for non-constant solutions.
Since c = — (a + 6), equation (1) rewrites as
axi—i + bxi = (a ■+- tyxi+i (2)
which is further transformed into successively equivalent forms (each
equation is valid for all i):
a(xi+i — xi + xi — xi_i) + b(x'i+i — Xi) = 0;
(a + b)(xi+i —xi)+a(xi —Xi-i) = 0;
a(xi — Xi-i) = c(xi+i — Xi). (3)
Set yi = xi — Xi_\. Clearly, y\ + ■ ■ • + yn = 0. Since not all the a^s are
equal, there exists a yi0 ^ 0. Equation (3) says that
a-Vi = cyi+1. (4)
This has to hold for all i. Since a2 + c2 > 0, equation (4) can be solved
either for yi+i or for yt (yi+i = {a/c)yi or yi = (c/a)yi+i). If any one of
the numbers (y\,..., yn) were zero, we could infer (inducting forward or
backward) that all the ?/;s are zero, in contradiction to yiQ ^ 0.
Consequently the product p = y\ ■ ■ ■ yn is different from zero. Multiplying the
n equations (4) we obtain anp = cTCp, and hence an = cn.
If the numbers a and c were equal, equations (4) would force that all the
yiS are equal; and this is impossible, their sum being zero and product
non-zero. Therefore a ^ c. The equality an = cn then implies that n
is an even number and c = —a ( ^ 0). Hence b = — (a + c) = 0. We go
back to the system (1), which becomes simply
Xi_i — xi+i — 0 for i = 1,..., n. (5)

Algebra
73
This means that the even-indexed x^s must be equal and the odd-indexed
xiS must be equal; if they are, system (5) is satisfied.
So we can formulate the answer:
If a = b = c = 0, the xiS can be arbitrary real numbers.
If b = 0, a = — c 7^ 0 and n is even, the general solution of the system (1)
is (x\,..., xn) = (u, v, u, v,..., u, v), with u, v arbitrary real numbers.
In all the other cases, the general solution of the system (1) is
(xi,...,xn) = (t,...,t),
with t an arbitrary real number.
Problem 32, Solution 2
Begin as in Solution 1 and reduce the given system of inequalities to the
system of equations (1).
Assume ab ^ 0. Rewrite the ith. equation of (1) in the form (2):
axi-i + bxi = (a + tyxi+i.
Squaring yields
a xi_1 + 2abxi_\xi + b xi = a xi+1 + 2abxi+1 + b xi+1.
This holds for i = 1,..., n. Adding these n equations we obtain
n n n
(a2 + b2) ^T xi + 2ab XI xi~lxi = (fl2 + *>2 + 2ab) Yl X1>
whence (in view of the assumption ab ^ 0)
n n
2^ari_iari = 2^ar?. (6)
i=l i=l
Rewrite this as
n n n
2j2*i-ixi = XX2 + X^-i'
i.e.,
n
y^Qi - xi-i)2 = 0;
i=l
the equality x\ — • • ■ = xn follows. (Another argument consists in
noticing that (6) is the instance of equality in the Cauchy-Schwarz Inequality
J2uivi — (Z)ui) (X)vi) > aPPned to Ui = x;_i, vi = xi\ and this
also implies x\ = • • • = xn.)

74
Solutions
Now assume be ^ 0; then (2) should be rewritten in the form
bxi + cxi+i = (b + c)xi_i.
Repeating the reasoning of the previous case, we again conclude that
X\ — ■ — -^n*
So, we are done with the cases where ab / 0 or be ^ 0. It remains to
consider ab — be = 0. Then necessarily 6 = 0. (Indeed: assuming 6/0,
we would obtain a = c = 0, contrary to the condition that a + 6 + c =.0.)
The equality 6 = 0 implies c = —a. Substitution into equations (1) then
yields
a(xi-\ — Xi+i) = 0 for i = 1,... ,n. (7)
If a = 0 then we have a = 6 = c — 0 and all the equations of the system
are satisfied trivially, for every choice of x\,..., xn. And if a ^ 0 then
equations (7) reduce to xi-\ = xi+\ for all i (compare equations (5) of
Solution 1), implying that n is even and the xfi assume some two values
alternately (these values may be distinct or equal).
Summing up, we have the general form of n-tuples {x\,..., xn) satisfying
the system; it is presented in detail in the final section of Solution 1.
Problem 33
Let a, 6, c be the sides of a triangle. Show that
a b c
+ + < 2.
b + c c + a a + b
Problem 33, Solution 1
By the triangle inequality a < b + c we have
a
b + c
b
< -
2a
(6 + c) + (6 + c)
26 c
<
2a
a + 6 + c
2c
<
Likewise,
c+a a+6+c' a+6 a+6+c
Adding the three inequalities we obtain the required one.
Problem 33, Solution 2
Let a + b + c = u, be + ca + ab — v. The proposed inequality is
equivalent to
a b c
+ - + <2,
u — a u — b u — c
i.e., to L < R where
L — a(u — b)(u — c) + b(u — c)(u — a) -+- c(u — a)(u — 6),
R = 2(u — a)(u — b)(u — c).

Algebra
75
Simple manipulations bring these expressions to the following forms:
L = (a + b + c)u2 - [a(b + c) + b(c + a) + c(a + b)]u + Sabc
= u — 2uv -+- Sabc,
R — 2[u — u (a -\-b + c) -+- u(bc + ca -+- ab) — abc] = 2uv — 2abc,
and the problem reduces to showing that
R- L — -u3 + 4uv - 5abc > 0. (1)
Since a, b, c are the sides of a triangle, the sum u — a + b + c exceeds
each of 2a, 2b, 2c. This yields
0 < (u - 2a)(u - 2b)(u - 2c)
= u3 - u2{2a + 2b + 2c) + u(4bc + 4ca + 4ab) - 8abc
= u — u • 2u + u • 4v — 8abc,
i.e.,
-u3 + 4uv - 8abc > 0. (2)
The claimed inequality (1) is immediately implied by (2).
Problem 34
Let a, b, c, d be positive real numbers with abed = 1. Show that
a2 +b2 + c2 + d2 +ab + ac + ad + bc + bd + cd> 10.
Problem 34, Solution 1
In view of the well-known inequality x + (1/x) > 2 for x > 0 and
because of abed = 1,
1 1 1
ab + cd + ac + bd + ad + be — ab -\ (- ac H \- ad -\ > 6.
ab ac ad
This combined with the AM-GM Inequality
a2 + b2 + c2 + d2 > 4 ■ fyaWc2d2 = 4-^=4
immediately results in the asserted inequality.
Problem 34, Solution 2
Since
a2 + b2 > 2ab, c2 + d2 > 2cd,
and since
a + b > 2yfab, c + d> 2v/cd,

76
Solutions
have
a2 4- b + c2 + <T + ab + ac + ad + be + bd + cd
= a2 + b2 + c2 +d2 + (a + b)(c + d)+ab + cd
> lab + 2cd + 2v/a6 • 2v/cd + ab + cd
1
Sab + Scd + 4 = z(ab H W 4 >
10.
Problem 34, Solution 3
We have the chain of inequalities:
a2 + b2 + c2 + d2 a + b + c + d 4
>1I1111!>^=1 (1)
4
(the root mean square, the arithmetic mean, and the geometric mean).
Denote the sum a + b + c + d by s. Then the left inequality of (1) implies
a2 + b2 + c2 + d2 > s2/4, and the right one says that s > 4. Therefore
a2 + b2 + c2 + d2 + ab + ac + ad + be + bd + cd
a2 + b2 + c2 + d2 {a + b + c + d)2
H
2
2
s s
s ¥ + T
5s2 5-16
~8~ ~ 8
= 10.
Problem 34, Solution 4
The means inequality(-ies) can be used in various ways here, of which
the following seems to be the fastest shortcut:
a2 _|_ b2 + c2 + d2 + ab + ac + ad + be + bd + cd
> 10 • V a2 • b2 • c2 • d2 ■ ab • ac ■ ad ■ be • bd ■ cd
= 10- 1\/a5b5c5d5
= 10 • 1v/l5 = 10.
Problem 35
Let a, b be non-negative real numbers with a2 + b2 = 4. Show that
ab
a + b + 2
and determine when equality holds.
< V2

Algebra
77
Problem 35, Solution 1
Applying the AM-GM Inequality to the pairs of numbers a, b and a2, b2
we have
a + b > 2v/o6 and 4 = a2 + b2 > lab. (1)
The second inequality yields
ab < 2, i.e., Vab < \[2. (2)
Instead of examining the ratio from the problem statement, we consider
its inverse, applying the first inequality of (1) and both inequalities of
(2):
a + b + 2 2Va~b + 2 / 1 1\ /l 1\ ,- ,
> = 2 -= + —)>2-= + -l = V2 + l.
ab ab \yab ab J ~ \V2 2
(This requires ab / 0; clearly, if a = 0 or b = 0, the proposed inequality
holds.) Inverting, we obtain
ah 1 rz
< -7= = V2- 1.
a + 6 + 2 _ \/2 + l
The means inequality turns into an equality only when the averaged
numbers are equal. Thus a = b = \/2 is the condition for equality.
Problem 35, Solution 2
If, for some reason, one prefers not to invert, one can start from
inequalities (1) and (2), and continue like this:
ab ab y
< y
a + b + 2 2Vab + 2 2y + 2
where y stands for y/ab; according to (2), 0 < y < \[2. It now suffices to
show
V < V2 - 1 (3)
2y +2
or, which is the same,
y2 - 2(V2 - l)y - 2(y/2 - I) < 0. (4)
The roots of this quadratic trinomial are y\ = y2 and y<i = y/2 — 2, and
hence inequality (4) reduces to
(y-V2)(y-V2 + 2)<0.
This holds because 0 < y < V2, so the second factor is positive, while the
first one is negative or zero. Equality occurs for y = y2 only; i.e., when
(1) and (2) become equalities; and this is the case only for a = b = y/2.

78
Solutions
(Another option might be to examine the left-side expression of either
(3) or (4) by calculus over y e [0, y/2\.)
Problem 35, Solution 3
Starting with the second inequality of (1) and the resulting estimate (2)
we transform the given expression as follows:
ab I— y ab
= V ab ■
a+b+2 a+b+2
r , i a b 2
'ab[ ^= + —= + —=
ab Vab Vab,
aVl + ^+7^) ' (5)
(noting that for a = 0 or b = 0 the claim holds trivially). Now, the AM-
GM Inequality implies
a b a-\-b „ , /— r- ,„s
- + \ - = —=>2, and so Vab < V2. (6)
b V a y/ab
Transformation (5) hence leads to the estimate
ab < ^b{2+4=v1 < ^(i+~yl=-^—=^2-1,
a + b + 2' V Va~b~J ~ \ V2J y/2 + 1
just as required, equality holding (in (6), hence in the claimed inequality)
if and only if a = b = V2.
Problem 35, Solution 4
The case where a — 0 or b = 0 is trivial. So we may assume ab > 0 and
invert the proposed inequality:
a+b+2 1
ab ~ y/2 - 1
equivalent ly,
1- + \ + \>V2 + l. (7)
a b ab
The given condition a2 + b2 — 4 calls for setting
a = 2sina;, 6 = 2cos:r, x G (0,7r/2).
The inequality (7) we are about to prove becomes
11 2 k ,
+ z + -—■ > V2 + 1;
2 sin x 2 cos a; 4 sin a; cos a;

Algebra
79
equivalent ly,
-^— + -^— + —?—>2V2 + 2. (8)
sin a; cos a; sm2i
Denote the left side by f(x) and examine the derivative:
, cos a; sin a; 4 cos 2x
f \x) = T~2 1 5 . 2o
sm x cos1 x snr 2x
sin x — cos3 a; sin x — cos2 a;
+
sin x cos2 a; sin x cos2 a;
This is positive when sin a; > cos a; and negative when sin a; < cos a;;
consequently, f(x) decreases in (0,7r/4] and increases in [7r/4,7r/2), attaining
the minimum value
/f^ = ?—+ 1 + 2 =^+^ + 2.
\4/ sin(7r/4) cos(7r/4) sin(7r/2)
Inequality (8) is proved, and the condition for equality is x — 7r/4, which
corresponds to a — b — y2.
Problem 36
The real numbers ai, bi, ci, di are such that 0 < ci < ai < bi < di and
ai + bi = Ci + di for i = 1, 2,..., n. Prove the inequality
n n n n
i=l i=l i=l i=l
Problem 36, Solution 1
We proceed by induction. For n = 1 we have a\ -+- b\ — c\ + d\,
according to assumption. Assume the claim holds for a certain n. Consider
n + 1. Suppose ai, bi, Ci, di (for i = 1,... ,n + 1) are numbers with
0 < Ci < ai < bi < di and ai + bi = Ci -+- di. Set
n n n n
A = ]Jai, B = ]Jbi, C = ]Jci, D = ]Jdi
i=l i=l i=l i=l
By the inductive hypothesis, A + B < C + D; rewrite this as
A-C <D-B. (1)
The following inequality is the content of the inductive claim:
Aan+i + Bbn+i < Ccn+i + Ddn+i.
(2)

80
Solutions
In view of the conditions imposed on the numbers a;, bi, c^ di, we have
an+l — cn+l — ^n+1 — ^n+l> (3)
an+i < bn+\, (4)
C < D. (5)
Note that the differences that occur in inequalities (1) and (3) are non-
negative numbers. Multiplying (1) by (4) and (3) by (5) we obtain the
inequalities
{A - C)an+1 < {D-B)
(fln+1 — Cn+\)C < (dn+i — bn+i) D.
Adding them, we get
Aan+i — Ccn+i < Ddn+i — Bbn+i,
and this is exactly the inductive claim (2). The assertion results by
induction.
Problem 36, Solution 2
By the given conditions,
ri = cii — Ci = di — bi > 0 for i = 1,..., n.
Look at the product
n
Y[di= (&i+ri)(&2 + r2)---(&n + r„).
i=l
Multiplying out, we obtain the term 6162 • "bn plus several summands
of the form
K ■ ■ ■ bikrh ■ • ■ rjn-k (0 < A; < n - 1), (6)
with distinct indices i\,..., i^ from the set {1,..., n}, complemented by
ji,..., jn-k to the whole {1,..., n}. Similarly, the product
n
YlCi — (ai ~ rl)(a2 - ^2) • • • K - rn)
i=l
is equal to plus the sum of terms
"ii'--aik(-rji)---(-rjn-k) (0<fc<n-l). (7)

Algebra
81
Since 0 < a; < bi for i = 1,..., n, we see that each term (7) is dominated,
in absolute value, by the corresponding term (6). So the joint sum of all
the numbers (6) and (7) is non-negative.
Now, the sum of all numbers (6) equals JJdi — Y[h] the sum of all
numbers (7) equals JI0*- IIa*- Consequently,
n n n n
Y[d{ Y[bi +Y[ci - Y[a{ > 0,
i=l i—1 i=l i—1
as claimed.
Problem 37
Prove the following inequality for all integers n > 1:
1-f (n + l^V-1 fl+nn
+ 2 J U + l
Problem 37, Solution 1
We show that the number nTC(n_1) can be (smartly enough) put in
between the two expressions we are about to compare:
(i±^r>—>>££)" <i>
Taking roots of order n — 1 and n, respectively, we recast the left
inequality and the right inequality of (1) into their equivalent forms:
(n + l)TC+1 + l n , n_l nn + l
± J— > nn and nn x > -—— . (2)
n -\- z n + 1
The second inequality is immediate:
(n + l)nTC_1 = nn + nn~x > nn + 1 for n > 1.
For the first one, apply the Binomial Theorem to obtain (for n > 1)
(n + 1)TC+1 + 1 = (nTC+1 + (n + l)nn + ■ ■ ■ + l) + 1
> nn+1 + (n + l)nn > nn+1 + 2nn
= nTC(n + 2).
Thus, both inequalities of (2), hence of (1), are proved.

82
Solutions
Problem 37, Solution 2
Denote the left-side expression and the right-side expression by L and R,
respectively. The sequence ((n + l)/n) tends increasingly to e.
Therefore we have for n > 2
n + l\" (3\2 9 , /n + l\n+1 1 1
*U) =4 and {^2) >~e>3 (3)
Moreover, (nn + l)/nTC = 1 + n_n < 5/4 for n > 2, and so
nTC + 1 < - nn for n > 2. (4)
4
We now estimate the ratio L/R from below:
L /(n + l)n+1 + l\n_1 (nn + IN _TC
i? V. n + 2 ) \n + \
n + 2 J \n + \
and we continue the estimate, using inequalities (4) and (3):
— > '
n+l\ n—1
R \ n + 2 J \4 n + 1
(n + l)n2+n-1n-n2 /4
(n + 2)™"1 V5.
n -I- 1 \ /4\ In + 1
n / \ 5 / \n+2
\ //™ + l\TC\ (n + 1 n + 2
Hc^)Tte
>
5/ V\ n ) ) Vn + 2 n + 1
4 n 9 n 1 n+2 2
5, 4 3 n + 1
° 9 TC 1
> 5 3;
and this number exceeds 1 for n > 2. Thus L > R, as asserted.
Problem 37, Solution 3
Taking logarithms on both sides, rewrite the claimed inequality as
. i + (n + i)»+l l + nTC
(n-l)ln -^ >nln
+ 2 n + 1

Algebra
83
or, which is the same,
lin/1 + (n + 1)n+1X 1 /1+n,
n + 2 J n — 1 \ n + 1
So the problem reduces to showing that f(n + 1) > f(n) for n > 2, where
w , 1 , fxx + l\ la(xx + 1) - \n(x + 1)
/O^) = 7 mf
X — 1 \ x + 1 / x — 1
This is done in a more or less routine way by calculus. Since
(xxY = (exlnx)' = exlnx(lnx + 1) = x*(lnx + 1),
we get
^(lnx + l) 1
/'(*) =
(^^-^T)(.-i)-(1^ + i)-.P(, + i))
(x - l)2
1 /xx(lnx + l) 1 \ ln(xx + 1) - ln(x +1)
x - 1 \ xx + 1 x + 1/ (x-1)
Since (xx -+- l)/(x + 1) < xx l for a; > 1, the numerator of the last
displayed fraction fulfills the estimate
x
+ 1
\n(xx + 1) - ln(x + 1) = In — < lnx*-1 = (a: - 1) lnx
x -+- 1
Therefore
•1 fxx(\nx + l) 1 \ In:
,,n ^ 1 /xx(lnx + l) 1 \
i-ll xx + 1 x -\- 1J x — 1
(xx+1-l)- (x + l)lnx
(x-l)(x* + l)(x + l)
In view of the well-known inequality In x < x — 1 we obtain
(xx+1 - 1) - {x + 1) lnx > (a:**1 - 1) - (a: + l)(x - 1)
= x2^-1 - 1) > 0 for x > 1,
and consequently /'(a;) > 0 for x > 1. This means that /(x) is strictly
increasing in (1, oo), and hence f(n + 1) > f(n) for n > 2.
Problem 38
Let n > 9 be an integer. Which one of the numbers (\/™) and
(Vn + 1) is greater?

84
Solutions
Problem 38, Solution 1
The answer is easy to guess, the first number is greater:
(V^)V^> (v^TT)^ for n>9. (1)
To prove this guess, take logarithms on both sides: inequality (1) is
equivalent to
vn + 1 • In y/n > \fn ■ In Vn + 1,
i.e., to
In^/n In \Jn + 1
—p- > — for n > 9.
V™ V ra + 1
This holds because the function f(x) — (lnx)/a; is strictly decreasing for
x > v9 = 3 (the derivative f'(x) — (1 — \o.x)/x'2 is negative for all x > e;
and since.3 > e, we are done).
Problem 38, Solution 2
We will use the well-known relation (l -+- ^) < e, which holds for all
positive integers n. Inequality (1) is equivalent (via squaring) to
nV^+i> (n + i)v^ for n>9.
Division by n^™ transforms this into
+ 1\V™ / l\v^
v* > (!i±±y" = (! + iy\
and raising both sides to the power y/n + 1 + y/n brings this to the form
/ 1 \ n+V'n(n-t-l)
n > fl + -J for n > 9; (2)
the last inequality is also equivalent to (1).
The exponent qn = n + y/n(n + 1) is estimated as follows:
n > 9 =» n(n + 1) < ^n2 =► ?TC < (l + v/^p)" < 2.06n.
Hence
i / i n\206
(l + ^) < ((l + ^) ) < e206 < 7.846 < 8 < 9 < n,
proving (2).

Algebra
85
Remark
The use of a calculator can be avoided if we resort to another well-known
inequality (l + ^) > e, holding for all n > 1; in particular, we have
(18/17)18 > e. Since y^ = yJl + % < 1 + ^, we get qn < (2 + ^)n
for n > 9. Knowing just that e < 2.8, we obtain e2 < 7.84, and so
(1 + I)9"<('(1 + I)"y+1/18<e^/i8 = eV/1»<7.84.H<9<n.
Problem 39
Prove the inequality
(2n)-\/3^<4TC for n=l,2,3,
Problem 39, Solution 1
The following stronger inequality will be proved by induction:
2"YV3n~+T<4n. (1)
Obviously, the proposed inequality is immediately implied by (1).
For n = 1, inequality (1) holds. Assume (1) holds for a certain integer
n > 1; we must show that
(^.vst^im^-.
(2)
This is done as follows:
'2n + 2
, . • V3n + 4
n + 1
/2ny(2n + l)(2n + 2);
\nj (n + l)(n + l)
<
2(2" + 1).f2"Vv3^TT.,/pi
n + 1 Vn/ V3n + 1
2(2n + l) „B /3n + 4
n + 1 V 3n + 1
The claim (2) will be proved if we show that
^±1 • J^±* < 2. (3)
n + 1 V 3n + 1 ~ W

86
Solutions
By squaring, relation (3) is equivalent to
(2n + l)2(3n + 4)
< 4; (4)
{n + l)2(3n + 1)
and this is recast into
12n3 + 28n2 + 19n + 4 < 12n3 + 28n2 + 20n + 4,
holding trivially. Induction is complete.
Remark
This is a very graceful example of an induction proof which requires a
strengthening of the claim in order to carry out the induction step. (In
the inductive procedure, there is a moment in which "assertion becomes
assumption".) An attempt to prove the inequality in its original form by
induction, in a straightforward way, would fail!
Problem 39, Solution 2
We transform the asserted inequality into successively equivalent forms:
(2n)lV3n~ < (2nn!)2,
l-2-3---(2n- l)-(2n) • v7^ < (2 • 4 • 6 • • • (2n))2,
l-3-5---(2n-l) • v7^ < 2-4-6---(2n),
(1 • 3 • 5 ■ • • (2n - l))2(3n) < (2 • 4 • 6 • • • (2n))2,
3-5---(2n-l)Y 1 ^2
and finally
\2-A---(2n-2)J 2n ~" 3
Denote the left side of (5) by an; thus
133557 2n-l 2n
2 2 4 4 6 6 2n-2 2n
To create an+\ out of an, two further factors have to be attached at
the end of this product. Appending only one of them we obtain an
expression, which we denote here by bn:
_ 1 3 3 5 5 7 2n-l In- 1 2n + 1
n~2'2'4'4*6' 6 " ' 2n - 2 " ~^hi 2n
Accordingly,
2n + l fR\
on = an- — > on- [p)
An

Algebra
87
On the other hand,
2n-l 2n + l An2 - 1
bn = bn-i • — • — = bn-i ■ ——5— < bn-i-
Thus b\, 62> &3» • ■ • is a decreasing sequence. And since
13355779 9 11 nfl/.fl10 2
65=2-2-4-4'6'6-8"8-l0-10=a66618--<3'
all the subsequent bns are smaller than 2/3. Hence by inequality (6),
an < 2/3 for n — 5, 6, 7,... . Also the initial terms a\, 0,2, 03, a\ are
smaller than 2/3, as can be verified directly. Thus estimate (5) is proved,
and we are done.
Remark
At calculus courses it is taught that the sequences (an) and (bn) tend to
a common limit, whose exact value is 2/n (the Wallis formula).
Problem 40
Prove that the inequality
y(t amM>o
holds for any real numbers a\, 0,2, •. ■, ar. Find conditions for equality.
Problem 40, Solution 1
Denote the given expression by Fr{a\,..., ar):
FrK...,ar) = ]r(]r^Y a)
^-J V n m + nj
n=l Nm=l '
Clearly, Fr(0,..., 0) = 0. Now, for r = 1 we have Fi(ai) = a\/2 > 0,
with equality only for a\ = 0. It is thus natural to conjecture, for each
r, that the inequality
Fr(ai,...,ar)>0 (2)
should hold for every r-tuple of real numbers (ai,..., ar) ^ (0,..., 0).
We will prove this guess by induction. The start (r = 1) has been done
already. Fix r > 2 and assume inductively
Fr-i(a\,..., ar_i) > 0 whenever (a\,..., ar-\) ^ (0,..., 0). (3)
Consider r real numbers a\, ..., ar—1» «r, not all zero. In the expression
(1), isolate the terms corresponding to n = r or m = r:
r—l /T—\
/ n V~^ I \~^ aman
.(ai,. .. ,ar_!,arJ = > > ■—
^—' V ^—' m + n
n=l Nm=l
+
a^a
ru,n
n r + n

88
Solutions
V iL—' m + r Ir 1
Nm=l '
If a\ = • • • = ar_i = 0, then automatically ar ^ 0, and therefore we have
Fr(0,..., 0, ar) = a2/{2r) > 0, as needed.
Thus assume that at least one of the numbers a\, ..., ar_i is different
from zero. Consider the expression on the right side of (4) as a function
of the variable ar, which we now denote by x:
T{x) = Fr(ai,..., ar-i,x) = Ax2 + Bx + C;
according to (4), the coefficients A, B, C are expressed by the formulas
1 r— 1 r—1 r—1
y.r ^—' r -4- n. ^—' m. -4- r -^—' r A- k.
n=l m=l fc=l
r—1 /r—1
c = E £
n=l Nm=l
Let us calculate the discriminant D = B2 — 4AC of the quadratic
trinomial T{x):
,r-\ N 2
= 4/^—)
r—1 \ /T—l
r + n I \ *-^ m + r
n=l ' Nm=l
r—1 /r—1
«EE
^-f V T (m + r) (r +
n=l sm—l K y
7—x /r—1 \ -. r—i /r—L
~~ ^-A , (m+7-)(7- + nW 2r^l^-<
n=l xm=l v y ' n=l Nm=l
hence
2 '—i /r—i \ i r—! /r—*
V r> . _ s.—*. / v—a 0>m.O>n \ 1 v—v / v—v dman
4 4 ^—f V ^-^. (m + r)(r + n) / 2r ■<:-—f V ^i wi + n
i.e.,
r—1 /-r—1
a — / v I / v cmnaman I)
n=l^m=l '
(5)
where
1
(771 + r) (r + n) 2r(m + n)
2r(m + n) — (772 + r)(r + n)
(771 + r)(r + n) • 2r(m + n)
(r — m)(r — n)
2r(m + r)(r + n)(m + n)

Algebra
89
Writing
r — k
bk = for k = 1,..., r — 1
r + k
we thus have
_ _ 1 bmbn
Cmn —
1r m + n
Inserting these expressions into formula (5) we obtain
D 1 V^/'v^ bondman
1 /
2^ 2^1 2^
_ _ Fr_i(aib1, a2^2,. • ■ , ar-lbr-l]
~ 2r
__ _ Fr_i(u1,U2,...,ur-i)
2r
(6)
where uk = afc^fc f°r & = 1> - • • ,r — 1- Since the fr^s are positive, there
is a non-zero number among the numbers ui, ..., ur-\. Thus, by the
inductive hypothesis (3) (applied to the numbers u\, ..., tir_i in place
of a\, ..., ar-i), we have Fr_i(tti, ti2, • • •, ur-i) > 0. This, in view of
the equality (6), implies D < 0. A quadratic trinomial with a negative
discriminant and a positive leading coefficient (A = l/(2r) > 0) assumes
positive values only.
We have thus shown that the inequality in (2) holds for every real
numbers a\, ..., ar_i, ar, not all equal to zero. This concludes the inductive
step.
Problem 40, Solution 2
r
Consider the polynomial P (x) = \_] anXn. By squaring,
n=l
(p(x))2 = (E^^E0'
r / r
= Ea«(Ea'
n=l \n=l
r / r
= E(Ea-a^m+n)- w
n=l \n=l
n—1 \n=l
Now introduce the polynomial
n=l xm=l

90
Solutions
The assertion of the problem is that
Q(l) > 0. (8)
Claim (8) will be proved by examining the derivative of Q(x), which
equals
r / r
n=l \n=l
Comparing equation (7), we see that
Q'(x) = - (P(x))2 > 0 for x > 0. (9)
x
Notice that Q(0) = 0, by the definition of Q{x). The function Q(x) is
continuous in [0,1] and non-decreasing, in view of the inequality in (9).
Hence Q(l) > Q(0) = 0; claim (8) is settled.
Equality holds in (8) if and only if Q(x) is constant, i.e. (see (9)), when
P(x) is the constant null function. And this is the case if and only if
a\ = • • • = ar = 0.
Problem 41
For a fixed integer n > 1 find the least value of the sum
^l + ^ + ^-H H ,
16 n
given that positive numbers satisfying
1 1 1
— + — H + — = n.
X\ X2 Xn
Problem 41, Solution 1
Denote the sum under consideration by S (= S(x\,..., xn)). The
following inequality is the key to the solution:
^- + ->1 + - for z>0, k = 1,2,3,.... (1)
k x k
Four proofs of (1) are presented below! Now, taking inequality (1) for
granted, we just match each term of S with the corresponding term of
the constraint condition, to obtain
fc=i fc=i fc=i fc=i

Algebra
91
with equality for x\ — ■ ■ • = xn = 1. The "n" cancels and we get
i 111
2 6 n
as the minimum value of S. It remains to prove inequality (1).
First proof of (1).
For x, k > 0 fixed (x real, k an integer),
fcx( — + 1-1-1^ = x{xk-l) + k{l-x)
\ k x kj
fc-1
= o;(x - l)y^x* + fc(l -x)
i=0
k
= (x- 1)^(^-1)
i=l
fc
= ^(x-l)^-l)>0
3=1
because the factors in each term of the last sum agree in sign.
Second proof of (1).
For fixed x, k consider the arithmetic mean and the geometric mean of
the k + 1 numbers, one of them being xk and the others equal to 1/x:
K + 1 \ X X J \ X X J
hence xk + (k/x) > k + 1, which is just a restatement of (1).
Third proof of (1).
The Bernoulli Inequality (1 + a)k > 1 + ka holds for all a > — 1 and
every integer k > 1. Set a — x — 1, thus obtaining: xk > 1 + k(x — 1).
Hence
xk 1 l + k(x-l) 1 / 1\ 1 1
—+ - > i L + - =(a; + _)_i + _>i + _.
fc x k x \ x) k k

92
Solutions
Fourth proof of (1).
For a fixed integer k > 1 consider the left side of (1) as a function f(x),
defined on positive reals. Since
f'(x)-xk-1-x-2 f<0 f°r xG(°'1)'
1 l J \>0 for ze(l,oo),
we see that f{x) takes at x = 1 its (global) minimum value 1 + (l/k).
Problem 41, Solution 2
The constraint imposed on the numbers x\,..., xn is that their harmonic
mean is equal to 1. So their geometric mean is at least 1; i.e., we have
x\ • X2 ■ • -xn > 1. (3)
Take the sum (2) to the common denominator
1 1 _ mi +m,2 H \-mn _ m
In n\ n\
where m^. = (n\)/k for k — 1,2,..., n, and consider the m positive
numbers:
2 2 n n
X\ , . . . , X\ , X2 > • • • > 3^2 ' " " ' ' "^n ' ' ' ' ' "^"n •
mi t«2 Tin
Their arithmetic mean compares with the geometric mean:
m1xl+m2xl-\ + mnx% / 2 nm„\17
>(xr^...xr) m (5)
Since fcmfc = n! for k = 1,..., n, the product in the parentheses equals
(3:10:2 • • • xn)n-, and we get by inequalities (5) and (3)
mixi + m2X2 + • • • + Tnnx™ > m(xiX2 • ■ ■ xn)^n'"m > m.
Division by n\ now yields (see (4))
x\ x\ xV: m „ 1 1 .^.
-Y + ^ + --- + ^> - = ! + - + ■■• + -, (6)
12 n n! 2 n
showing that the sum (2) is the least value that the expression in question
can have.
Remark
The argument of the last solution shows that the inequality in (6) is a
consequence of the condition (3), actually weaker than that given in the
problem statement (the geometric mean instead of the harmonic mean).

Algebra
93
Problem 42
On a given segment AD, find points B and C so as to maximize the
product of the lengths of the six segments AB, AC, AD, BC, BD, CD.
Problem 42, Solution 1
Without loss of generality, assume that B lies between A and C. Take
the length of AD for a unit (AD = 1) and set
x = BC, y = AB-CD; a: € [0,1], ye[-l,l].
Then AB + CD — 1 — x, and hence
AB = \{\-x+ y), CD = \(l-x- y),
AC = \(l + x + y), BD = \(l + x-y).
The product under consideration equals
P = p(x,y)
= jqx(1-x+y)(l-x-y)(l+x+ y)(l+x-y)
= £x((l-*)2-y2)((l+a:)2-y2).
Hence,
p = p(ar, y) < ^ a:(l - z)2(l + x)2 = i /(a:), (1)
where
/(a:) = a;(l-:r2)2 = a;5-2x3 + a;; (2)
equality holds in (1) if and only if y = 0.
The derivative
f'{x) = 5a:4 - 6x2 + 1 = 5 (z2 - 1) (x2 - J)
is positive for a; € (0, ^\/5) and negative for x € (^\/5, l). Thus the
maximum value of f(x) is attained at x = |Vo. Consequently, the
product p(x,y) is maximized at x = |>/5, y = 0. This corresponds to placing
points B and C symmetrically with respect to the midpoint of AD, at
the mutual distance BC — •gv/5.
Problem 42, Solution 2
As above, the problem is reduced to the maximization of the
polynomial (2). This can be done without calculus. In the weighted AM-GM
Inequality
apbq < pa + qb for a, b > 0, p, q > 0, p + q = 1,

94
Solutions
set a = Ax2, b — 1 — x2, p = 1/5, q = 4/5, to obtain
41/5/(*)2/5<f,
equality holding only when Ax2 — 1 — x2; that means, for x = ^ V^-
Conclusion as before.
Problem 42, Solution 3
The means inequality can be used in a yet smarter manner. Assuming
that B lies between A and C, set
AB = u, BC = x, CD = v;
so
AC = u + x, BD = x + v, AD — u+x + v=l.
Denoting the product under investigation again by p, we have
p = (uxv(u + x){x + v))
= (ti(a; + v))(ti(ti + a;))(v(w + a;))(v(a;-|-v))(a;2). (3)
The geometric mean of the five numbers
u
(x + v), u(u + x), v(u + x), v(x + v), x (4)
does not exceed their arithmetic mean. Thus the product on the right
side of (3) does not exceed
\{x + v) + u(u + x) + v(u + x) + f(x + f) + x \
5
The numerator of the fraction in parentheses equals
ux + uv + u + ux + v u + v x + v x + v +x = (u + v + x) =1.
Expression (3) for p now yields p < (|)
The means inequality becomes an equality only if the averaged quantities
are equal. Since the arithmetic mean of the numbers listed in (4) is 1/5,
the condition for equality takes the form
u(x + v) = u(u + x) = v(u + x) = v(x + v) — x = g .
The last system of equations (together with u + v + x = 1) is fulfilled
only for x = ^Vu and u — v — ^(1 — x). Conclusion as in Solution 1.

Algebra
95
Problem 43
Find all functions /: R —>■ R satisfying the equation
x2f{x) + /(l - x) = 2x - x4 for x <E R.
Problem 43, Solution 1
In the given equation
x2f{x) + /(l - x) = 2x - xA (1)
set 1 — x in place of x:
(1 - x)2/(l - x) + f(x) - 2(1 - x) - (1 - x)4. (2)
Multiply equation (1) by (1 — x)2:
x2(l - x)2/(x) + (1 - x)2/(l - x) = (1 - x)2(2x - x4). (3)
Subtract equation (3) from (2):
[1 - x2(l - x)2]/(x) = (1 - x) [2 - (1 - x)3 - (1 - x)(2x - x4)].
Rewrite this as
tf(x)/(x) = (l-x)M(x), (4)
K(x) and M(x) denoting the polynomials in square brackets:
K(x) = l-x2(l-x)2
= (1-x+x2)(l+x-x2),
M(x) = 2-(l-x)((l-x)2 + 2x-x4)
= 2- (l-x)(l+x2-x4)
= 1 + x-x2 + x3 + x4-x5
= (l+x3)(l+x-x2)
= (l+x)(l-x+x2)(l + x-x2)
= (l + x)K(x).
Equation (4) takes the form
;r(x)/(x) = (i-x2)*:(x),
implying f(x) = 1 — x2, unless K{x) = 0. In this latter case, we get
x2(l — x)2 = 1 (by the definition of K(x)), and this is equivalent to
saying that
x(l — x) = 1 or x(l — x) = — 1. (5)

96
Solutions
The first equation of (5) has no real roots and the second one has two
roots:
q = |(1 + V5) and /?= |(1- >/5); (6)
these roots of x2 = x + 1 satisfy
a +/3=1, a/?=-l; a2 = a + 1, /32 = 0 + 1. (7)
In conclusion, /(a;) = 1 — x2 for all x 7^ a,/?. And for these two
exceptional values of x equation (1) yields
a2/(a)+ /(/?) = 2a-a4 and f32f((3) + /(a) = 2/? - /?4. (8)
Using formulas (7) we calculate: a4 = (a2)2 = (a + l)2 = a2 + 2a + 1,
and likewise /?4 = /?2 + 2/? + 1. Equations (8) become
a2/(a)+ /(/?) =-a2-1 and /?2/(/?) +/(a) =-/?2 - 1. (9)
Multiplying the second equation of (9) by a2 we obtain, by identities (7),
/(/?) + a2f(a) = -a2/?2 - a2 = -1 - a2,
which is just the first equation of (9). Thus the two equations (9) do not
yield a unique evaluation of /(a), /(/?). In fact, /(a) can be any real
number c, and then
/(/?) = -(a2 + 1) - a2c = -(a + 2) - (a + l)c.
Thus the general solution of equation (1) is
ri-a;2 for x =£ ±(1 ± VE),
f(x) = < c (arbitrary real number) for a; = ^(1 + V^), (10)
l-i(5 + V5)-i(3 + V5)c fora:=i(l->/5).
Problem 43, Solution 2
A functional equation like (1), with polynomial coefficients and a
polynomial on its right side, is likely to have a polynomial solution. Evidently,
if a polynomial f(x) satisfies equation (1), it must be a polynomial of
second degree. Postulating f(x) = Ax2 + Bx + C we get from (1)
AxA + Bx3 + Cx2 + A(l -2x + x2) + B(l - x) + C = 2x - xA,
whence A = -1, B = 0, C = 1; i.e., f(x) — 1 - x2.
Thus we have found the solution f(x) = 1 — x2 by simple trial. It is
unique in the class of polynomials; one is tempted to conjecture that it
is unique in general. In an attempt to prove this guess, let us set
f(x) = l-x2+g(x); (11)

Algebra
97
that takes equation (1) to the form
x2(l - x2) + x2g(x) + 1 - (1 - x)2 + 0(1 -x) = 2x- x4,
equivalent to
x2g(x)+g{l-x) = 0. (12)
Replacing x by 1 — x,
(l-x)2g(l-x)+g(x) = 0. (13)
Viewing (12) and (13) as a homogenous system of two linear equations
with unknowns g(x) and g{l — x), compute its determinant:
= x2(l - x)2 - 1. (14)
If the determinant is different from zero, the system has only the
trivial solution g(x) — g(l — x) — 0. If the determinant is zero, then the
two equations (12) and (13) are linearly dependent; g(x) may be given
any value, and then g(l — x) can be computed from any one of these
equations. (We see that the uniqueness conjecture fails.)
Now, the determinant (14) vanishes if and only if x satisfies one of the
equations (5) from Solution 1; equivalently, if x is one of the numbers
a, j3 given by (6). Equation (12) with x = a and with x = j3 becomes,
respectively,
a2g{a)+g(l3) = 0 and f32g(f3) + g{a) = 0.
Since (a/?)2 = 1, the two equations (just obtained) coincide. Denote g(a)
by d; then g(j3) — —a2d. Hence by definition (11) (and formulas (7))
f(a) = l-a2 + d = d-a, f(f3) = 1 - fi2 - a2d = ~/3 - (a + l)d.
Setting, further, d — a = c, we get /(a) = c and
f(/3) = -p-(a + l)(a + c) = -P-a2-a-(a + l)c= -(Q + 2)-(a + l)c.
So we have arrived at the same formula (10) which we had found in
Solution 1.
Problem 44
Let A and B be real numbers different from zero. Prove that the function
f(x) — A sin a; + B sin(\/2 • a;) is not periodic.
v2 1
1 (1-x)2

98
Solutions
Problem 44, Solution 1
Assume / is periodic with period T > 0,
f{x +T) = f(x) = f(x - T) for all x eR.
Then of course
f(x + T)-f(x-T) = Q for x e R,
which in view of the definition of f(x) leads to the equality
A sin(x + T) - A s\n{x - T) +
+B sin(\/2 -X + V2-T) - B sin(v/2 • x - y/2 • T)
= 0,
i.e.,
2Acosa;sinr + 2JBcos(\/2-x)sin(\/2-r) =0 for xeR. (1)
Setting x — 0 we obtain
2Asinr + 2Ssin(\/2-r) = 0; (2)
and setting in(l)x = 7r/2we get
IB cos(ir/y/2) sin(V^ • T) = 0. (3)
Since B^0, equality (3) shows that sin(\/2 • T) = 0. And since also
yl 7^ 0, equality (2) now shows that sinT = 0.
It follows that each one of the two numbers T and y/2 ■ T has to be an
integer multiple of -k. This is however impossible, Vz being irrational.
Contradiction ends the proof.
Problem 44, Solution 2
The function f(x) has derivatives of order one and two:
f'(x) = Acosx + BV2cos(V2-x), f"(x) = -A sin x -2B sin(\/2- x).
We thus have the equations
f(x)+f"(x) = -Bsm(V2-x), 2f(x) + f"(x) = Asinx. (4)
Assuming that / is periodic with period T > 0, we conclude that T is
also the period of /' and /", hence also of /' + /" and 2/' + /". In view
of the equations (4) and the condition A ^ 0, B ^ 0, we infer that T is
a period of both sin a; and sin(\/2 • x).

Algebra
99
Since each period of sin a; is a multiple of 2n, and similarly that each
period of sin(v2 • x) is a multiple of v2 • 2tt, we are again led to a
contradiction with the irrationality of v2.
Problem 45
Find all monotonic functions /:R —>■ R satisfying the equation
/(4a:) - /(3a:) = 2x for xgR.
Problem 45, Solution 1
If a monotonic function / satisfies the given equation, then
rt A \ rtn \ f > 0 for
/(te) -/(te) I < 0 for
> 0 for x > 0,
a: < 0,
showing that / is strictly increasing in each one of the two intervals
(—oo,0) and (0, oo). Hence, / is increasing on R. Replacing 4x by x,
rewrite the equation as
/(*) = §* +/(fa:) for xGR. (1)
For any real number x ^ 0 and any natural number n, repeated
application of formula (1) gives
/Or) = \x + f{\x)
i« + i-i« + i-(S)2« + - + i-(S)""1« + /(«)n«)
1- l^n
!-f
i.e.,
/(z) = 2z(l-(!)")+/((!)"*). (2)
Now, keep x fixed and let n vary. The sequence ((f) a:) _i is decreasing
if a: > 0, and increasing if x < 0; the same is the behaviour of the sequence
(•^((f) a:)) =i' ^e vauie /(0) is ^s lower (upper) bound, not necessarily
sharp. Thus there exists a finite limit (maybe, depending on a:):
»w=j™'((!)"4

100
Solutions
Assume that g(u) < g(y) for some positive numbers u and v, and choose
an e with
0<e<±(g(v)-g(u)). (3)
By the definition of a limit, we have
/((|) ti) < g(u) + e for n large enough (4)
and
•^((f) v) > y(v) ~~ e f°r n large enough. (5)
Pick an integer k so large that inequality (4) holds for n = k. Next, find
an integer m so large that estimate (5) holds for n = m and, moreover,
(|) v < (^) u. Since / is strictly increasing, and in view of condition
(3), we hence obtain
0 < /((J)\) - f((l)mv) < (g(u) +e)- (g(v) - e)
= g(u)-g{v)+2e< 0
— obviously a contradiction. This means that g(u) = g(v) for any
positive numbers u and v. In other words, there exists a common limit
lim /((§) x) = c for every x > 0.
Analogously, there exists a common limit
lim f((j) x) = a for every x < 0.
So we can pass with n to infinity in formula (2), thus obtaining
f(x) = 2x + a for x < 0 and /(x) = 2x + c for x > 0.
Since / has to be increasing on R, we arrive at the final result:
2x + a
b
2x + c
for x < 0,
for x = 0,
for a; > 0,
/(x) = <^ b for x = 0, (6)
I 2x + c for x > 0,
where a, b, c are arbitrary constants such that a < 6 < c. (Clearly, every
such function satisfies the given equation.)
Problem 45, Solution 2
The reasoning becomes shorter if we resort to the well-known fact from
calculus that every function, monotonic in some real-line interval, has
one-sided finite limits (equal or not), at each point of that interval.
Accordingly, if / is a function satisfying the conditions of the problem, then
there exist the finite one-sided limits
a= lim f(x), c= lim f(x).
X—+0— x—>0+

Algebra
101
As in Solution 1, we observe that / must be increasing on R. Denoting
/(0) by b we have, as before, a < b < c. Define
h(x) = f{x) - 2x.
Then also
lim h(x) = a, lim h(x) = c.
x—*0— x—>0+
The given functional equation, recast in terms of the function h, takes
the form
(h(4x) + 2(4a:)) - (h(3x) + 2(3a:)) = 2x,
i.e., h(4x) = /i(3a;); equivalently,
h(x) = h(lx) for all i6l
So we have, for every x G R and every n G N,
M*) = A(i*) = *((j)1'*) = ••• = *(«)"«)•
When n tends to infinity, the sequence (h ((|) re)) _ tends to a, cor
b, according as x is negative, positive or zero. So we obtain, in limit,
{a for x < 0,
b ior x = 0,
c for x > 0,
which is nothing else than the formula (6), worked out in the first
solution.
Problem 46
A sequence ao, a\, a^, ■ ■ ■ of real numbers different from zero is generated
according to the rule: an+\ = (a^ — l)/(2an). Show that it contains
infinitely many positive terms and infinitely many negative terms.
Problem 46, Solution 1
If we change the signs all terms of a certain sequence that obeys the
given rule, we obtain another such sequence. Therefore it will be enough
to show that any such sequence has infinitely many negative terms.
Assume the contrary; that is, assume an > 0 for n > no. Then
a\ - 1 an
an+i = — < — tor n > n0,
Zan I
implying o^Q-j-fc <C 2 Q"no for k — 1,2,3,... . Thus, sooner or later, there
must appear a term am G (0,1). The next term am+i, equal to
(<4-l)/(2am),

102
Solutions
is negative. The assumption that "almost all" terms are positive has
driven us to a contradiction.
Problem 46, Solution 2
Let dn = an+i — an. By the recursion, 2anan+i = a„ — 1, and so
dn = an+1 - 2anan+i + an = an+l - (an - 1) + an = an+1 + 1 > 1
for all n. Now suppose we have a block ajv, ajv+i> • • • >«iv+r of consecutive
positive ans. Thus, if AT < n < N + r, then
A al~1 ~al - l ^ n ^
rfn = an+i — an = — an = —^ < 0, {I)
which combined with the inequality d^ > 1 implies: dn < — 1. So we
have
ajv > 1 + ajv+i > 2 + aiv+2 > • • ■ > r + a^v+r > r, (2)
yielding an upper bound on the length of the block (r < ajv)-
Consequently, a block of consecutive positive terms cannot be infinitely long;
a negative term must eventually occur. A similar argument shows that
any block of negative terms necessarily has a finite length; just the
inequalities in (1) and (2) have to be reversed.
Problem 46, Solution 3
The first two solutions do not differ in any essential way. The third one is
different. If not so simple as the foregoing ones, this solution gives more
insight into the nature of the problem. The sequence is determined by
its initial term ao, so the information about the positions of positive and
negative terms must be somehow encoded in that single number, and the
present proof shows how to decode it.
The clue observation is that the recursion formula imitates the well-
known trigonometric identity
cot2 0-1
cot 29 = .
2 cot0
Now, let t 6 (0,1) be the unique number such that ao = cot-7rt. Then,
according to the above, ai = cot27r£, a2 = cot47ri, and by induction,
an = cot2n7ri for n = 0,1,2,.... (3)
These values of the cotangent function are well defined. (Indeed:
assuming n is the least index such that cot2n7r£ makes no sense, i.e., 2nt is
an integer, we would get that 2n~1t is an "integer and a half", implying
an_! = cot2n-17r£ = 0, contrary to the condition that the sequence has

Algebra
103
non-zero terms.) In other words, t is not a dyadic fraction; its binary
representation
t = (O.C1C2C3 .. .)2 with Ci E {0,1} for i= 1,2,3,...
has infinitely many zeros and infinitely many ones.
Notice that
f > 0 if 12a; I is even,
COt-KX < -r 1 o 1 • J j
[ < 0 if [2x\ is odd;
therefore (see (3)) an is positive or negative according as |_2n+1£j is
even or odd. And since |_2n+1£j = (ci... cn+i)2, we see that an > 0
when cn+i — 0 and an < 0 when cn+i = 1. Thus the distribution of
positive and negative terms in the sequence corresponds exactly to the
distribution of zeros and ones in the binary expansion of the number
t — (cot-1 ao)/-K.
Problem 47
Four sequences of real numbers
«0,«l,«2,- • •, b0,bi,b2,..., c0,ci,C2,. .. , d0,di,d2,. ..
satisfy the simultaneous recursions
«n+l == 0"n + bn, bn+\ = bn + cn, cn+\ = cn + dn, dn+\ = dn + an
for n — 0,1,2,.... Suppose there exist integers k, r > 1 such that
cifc+r = afc, 6fc+r = 6^, cfc+r = Cfc, rffc+r = dfc-
Prove that a\ = b\ — ci = d\ — 0.
Problem 47, Solution 1
Define sn = an + bn + cn + dn. Conditions imposed on the given
sequences imply that Sk+r — s& and sn+i — 2sn for n — 0,3,2,... . The
last equality entails (by induction) sn — 2nso for n — 0,1,2,... . Thus
2k+rs0 = 2kso, and hence s0 = 0. This yields sn = 0 for all ra > 0.
Consequently, we get for n > 1:
«n+Cn= (fln-1 + &n-l) + (cn-l + ^n-l) = «n-l = 0. (1)
Define wn = a"^ + b^ + c^ + d^. Thus t^fc+r = ^k and
wn+i = (an + bn)2 + (bn + cn)2 + (cn + dn)2 + (dn + an)2
= 2(< + &£ + < + <) + 2(an6n +
bncn "+" cndn H" dnan)
= 2wn+2(an + cn)(bn + dn).

104
Solutions
For n > 1 we have by (1): wn+\ = 2wn. Induction yields wn = 2n lw\
for n = 1,2,3,... . In particular (setting n = k + r and n = fc),we obtain
whence wi — 0. And this is just enough to conclude
ai — bi = c\ — d\ = 0.
Problem 47, Solution 2
Introduce the polynomials
Pn 0*0 = anx + bnx2 + cnx + dn for n = 0,1,2,... .
The conditions of the problem imply that Pfc+r(aO = Pk(x) and
Pn+l{x) — (an + bn)x3 + (bn + cn)x2 + (cn + dn)x + (dn + an)
= an(x3 + 1) + bn{x3 + a;2) + cn(x2 + x) + dn(x + 1)
= (x + 1) (an(a;2 — x + 1) + 6na:2 + cna: + dn)
= (x + 1)(—an(x —x + x — 1) + anx3 + bnx2 + cnx + dn)
= (x + l)(Pn(x) - an{x - l)(x2 + 1)).
Hence, setting x = 1, x = i, and x = — i (the imaginary units),
P„+i(l) = 2Pn(l), F„+i(i) = (l+i)^n(i), Pn+iH) = (l-i)Pn(-O,
and by induction:
Pn(l) = 2nP0(l), Pn(i) = (l+*)nPoW, P„H) = (l-*)nFoH)
for n = 0,1,2,... . The polynomials P& and Pfc+r coincide; so we get
2k+rP0(l) = 2fcP0(l) and (l±i)k+r P0(±i) = (l±i)k P0{±i).
Since r > 1, we have 2r ^ 1, (l+i)r # 1, (l-*)r ^ 1, and thus
Po(l) = 0, P0(i) = 0, Po(-i) = 0.
By the definition of Po(aO, this means that ao + bo + co + do = 0 and
i(co - ao) = bo~ d0 = i(a0 - c0). (2)
The "real-imaginary" equations (2) force ao = co and bo = do, and
consequently the four numbers a\ = ao + fro, ^1 = ^0 + co, c\ — co + do,
di = do + ao are equal, their common value being
a\ = h = ci = di = ^ai + bi+Ci+di) = J(2a0 + 260 + 2c0 + 2d0) = 0.

Algebra
105
Problem 48
The sequences xq, x\, X2, ■ ■ ■ and yo, y\, 2/2, • • • are defined by:
xq = yo= 1,
Xn ' ■"
Xn+1
Xn + 1
v2 + 2
2/n+i = ^- for n = 0,1,2,... .
"tin
Show that yn = X2"_i for every integer n > 0.
Problem 48, Solution 1
Define sequences ao,ai,a2>--- and &0>^i>^2>--- by
xn- \/2 yn- V2
bn — 7= tor rc = 0,1,2,
v/2
Denote the common value of oq and 60 by A:
A = -=. = ao = o0.
l + \/2
The recursion formulas that define the sequences (a;n) and (yn) yield the
analogous formulas for (an) and (bn):
«n+l =
^n+1
-y/2
Xn+1
+ V2
\/2 1--n/2
&n+l =
zn + \/2 1 + \/2
Aan,
2/„+i - \/2
+ \/2
2/n+l
^±2 -x/2
yi±2
2y„
2
4-^
(y» + V2)

106
Solutions
Hence by obvious induction
an = An+1, bn = X2n for n = 0,l,2,....
Replacing n by 2n — 1 in the first equality we obtain
a2n_x = a*2"-1*1 = A2" = bn.
By the definition of an and 6n, this is equivalent to
^2"-! — v2 _ yn — y/2
Vn +
i.e., to
1 2V2 = 2x/2
S2»-i +
The claimed equality £2™-i = yn follows!
Problem 48, Solution 2
The inductive definition of the be rewritten as
Xn+i = f(zn) for n = 0,1,2,... ,
where f(x) = (x + 2)/(x + 1). Hence
aran = /o...o/(l), (1)
2"
the circle denoting composition.
For n = 1 and n = 2 we are dealing with the functions
g(x) = fof(x)
x + 2
x + 1
+ 2
x + 2 .,
3 '
* + 2
/°/°/°/0) = g°g{x)
3
2-
3a;
2x
Sx
+ 4
+ 3
+ 4
+ 4
-f-3
2a;+3

Algebra
107
(2)
17
_ ul^l
17 ■
Compare these expressions with the initial yns:
l2 + 2 3 (|)2 + 2 17
It is natural to guess that
/o...o/(«) = *£±2. (3)
^ + Z/n
Once guessed, this is without much trouble proved by induction;
according to equations (1) and (2), equality (3) holds for n = 1 and n = 2.
Assume it holds for a certain n. Then
/o-..o/(x) = (fo---of)o(fo---of)(x)
0nS + 2
Z/n • ; H 2
_ x + yn
ynx + 2
; H j/n
{yl + 2)x + 4yn
2ynx + (yl + 2)
y2n + 2
2z/n
+ 2
x H
2z/n
_ yn+\x + 2
^ + Z/n+i
showing that (3) holds with n replaced by n -f- 1. By induction, claim (3)
is true for every integer n > 1. Now, setting in (3) x = 1 we get in view
of representation (1)
Vn + 2
X2n = 7T— •
The number on the left side equals f(x2n-i)', that on the right side
equals f(yn)- And since f(x) is strictly decreasing, we conclude that
#2n-i = yn-

108
Solutions
Problem 48, Solution 3
Set
un = l+xn for n = 0,1,2,.... (4)
So uq = 2, and
xn + 2 1 1
un+i = 1+ xn+i = H —- = 2 H — = 2 H .
xn -f- 1 a;n + 1 wn
Consider the sequence vq,v\,v2, ■ ■ ■ denned by
vo = 1, vn+i = «nvn for n = 0,1,2,... . (5)
We obtain
/0, 1\ O , vn+l
\ unJ un
i.e.,
Vn+2 = 2v n+l + V n for n = 0,1,2,.... (6)
This is a homogeneous linear recursive equation of the second order. The
sequel is routine (see Problem 10, Solution 3, for instance): the general
solution of equation (6) has the form
vn = Aan + B/3n for n = 0,1,2,... ,
where a — 1 + y/2 and /3 = 1 — \/2 are the roots of the characteristic
polynomial t2 — 2t — 1. The constants A, B have to be determined from
the initial data vq = 1, v\ = 2, thus creating the specific solution of
equation (6) we are looking for. The result is:
Vn = \V2(an+1 - f3n+1) for n = 0,1,2,...
(simple calculations are omitted). Revisiting formulas (4) and (5), we
find
_ _ i — Vn+1 _ i — Vn+1 ~ Vn
Vn Vn
an+1{a - 1) - f3n+1(f3 - 1) _ ^ an+1 + /3n+l ^
~~ an+l _ fln+1 ~~ an+l __ gn+l '
this can be further rewritten as
Xn_1 = v-2.^J^ = V-2.^ML±1
(7)
Denote the number xin—\ just by wn. We have to prove the equality
wn — Vn for all n- Since wq = xq = 1 = yo, it will be enough to show

Algebra
109
that the wns obey the same recursion that defines the yns. That means,
we have to show that
2 .a
wn+i=^ for n = 0,l,2,.... (8)
2wn
According to formula (7), we have for n > 1
wn = x2n-i = V2 • 2n = V2 ,
(a//3)2 - 1 7n - 1
where 7„ stands for (a//5)2 ; the last equality is valid also for n = 0 (easy
verification).
Notice that 7n+i = 7n- Consequently,
wl+2 wn 1
2wn 2 w7
V^ 7n + l 1 7n~l
2 *7n-l ^*7n + l
A/2 (7n + l)2 + (7n-l)2
2 (7n-l)(7n + l)
= V^2-
7^ + 1
7
2-l
= \/2- — = wn+i for n = 0,l,2,.
7n+l ~ 1
Equality (8) is settled, and the proof is complete.
Problem 49
Two sequences of integers
0,1,0,2,0,3,...
and
bi,b2,b3,...
are defined uniquely by the equality
(2 + V3)n = an + bnV3.
Compute
lim (an/bn).

110
Solutions
Problem 49, Solution 1
Expanding (2 -+- \/3 ) and (2 — y/Z ) binomially, we obtain in both
expressions the same coefficients of terms involving the even powers
whereas those involving the odd powers of V3 differ in sign. Therefore
the equality (2 + \/3) = an -f- bny/Z implies
(2-V3)n = an-bnVZ;
this last sequence converges to zero because 2 — yZ is a number between
0 and 1.
Note that bn > 1 for all n > 1. Therefore
an 6nv/3 + (2-v/3)n R (2->/3)n
which is v3 in limit.
Problem 49, Solution 2
The implicit definition of the ans and bns can be easily made into
recursive formulas. Since
(2 + v/3)n+1 = (2 + V/3)n(2 + V/3) = (an + 6nV/3)(2 + V/3)
= (2an + 36n) + (a„ + 2bn) V3
(and since y/Z is irrational), we infer
«n+i = 2an -t- 36n, bn+i = an + 2bn (ao = 1, bQ = 0); (1)
in the matrix form,
an+i\ _ (2 3\ /an
bn+1J \l 2j\bn
It is well-known that a pair of sequences satisfying such a recurrence can
be postulated to have the form
an = Apn + Bqn, bn = Cpn + Dqn,
(2 3\
where p and q are the eigenvalues of the matrix I J, i.e., the roots
of the characteristic polynomial (2 — A) — 3:
p = 2 + V3, q = 2-y/l.
The constants A, B, C, D are evaluated from the initial conditions
ao = 1, bo = 0 and a\ = 2, b\ — 1,

Algebra
111
which yield the system of four linear equations
A + B = l, C + D = 0, Ap + Bq = 2, Cp + Dq = l,
with the solution
A = B = \, C = -D=±y/3.
Thus
a7
Apn + Bqn A + B(q/Py
bn Cpn + Dqn C + D(q/p)n
Since 0 < q/p < 1, this ratio tends to A/C = v3 as n —> oo.
Problem 49, Solution 3
We again use the recursive formulas (1). Denote the ratio an/bn by xn.
Formulas (1) imply
2an ~f~ obn lxn-\-6 , , . .
xn+l = 0, = —T = f{xn), K2-)
where
2x +3 1
/l^) = T^T = 2
x + 2 a; + 2
note that / is an increasing function in the interval (0, oo).
The initial terms of the sequence (xn) are x\ = 2, X2 = 7/4. In view
of (2) and the strict monotonicity of /, the inequality x\ > X2 implies
by induction xn > xn+\ for all n. So (xn) is a decreasing sequence of
non-negative numbers, hence convergent to a limit I > 0. Passing to the
limit in the equality (2) we obtain the equation
2/ + 3
1 + 2 '
with the unique non-negative root / = \/3.
Problem 50
The sequence (xn) is defined by
1 2n - 3
x\ = -, xn=—- xn_i for n = 2,3,4,....
I In
Prove the inequality
x\ + X2 -\ + xn < 1 for n — 1,2,3,... .

112
Solutions
Problem 50, Solution 1
Consider the auxiliary sequence yn = (2n — l)xn. The recursion formula
that defines the xns yields the analogous formula for the yns:
to ,x 2n~3 (2n-l)(2n-3) yn-i
yn = (In - 1) • — • xn_i —
2n n~l 2n 2(n - 1) - 1 '
i.e.,
2n — 1
Vn - —7, Vn-i for n = 2, 3, 4,.... (1)
In
This formula is valid also for n = 1 if we set ?/o = 1- Now,
2/n-l -Vn= 7, 7 ■yn-yn= n n , = ^n for n = 1, 2, 3, . . . , (2)
In — 1 in — 1
and therefore
ari + X2 -\ \~Xn = (j/o - 2/1) + (z/l - Z/2) H 1" (j/n-1 - 2/n)
= Z/0 - Vn = 1 - Vn < 1, (3)
as needed.
Problem 50, Solution 2
The initial xns are
— I— II — 3 _ 1 I. 3 _ 5 _ 1 I 3 5
X2 — 2ri • 4 — 2 ' 4' x3 — 3^2 " e — 2 ' 4 ' 6' ^4 — ^3'g— 2 " 4 " 6 " 8 '
and in general (by induction)
113 5 7 2fc-3
£*:= ^••T'TT'"^'-T*" —~ lor K = 1, 2, O, . . . .
2 4 6 8 10 2k
Multiply the numerator and the denominator of this fraction by the
product of even integers from 2 to 2k — 2:
(1 • 3 • 5 • 7 • • • (2k - 3)) (2 • 4 • 6 • • • (2k - 2))
(2-4-6---(2k-2))2(2k)
(2k - 2)\
(2k-1(k-l)\)2(2k)
2k - 2\ 1
Ak~l \ k - 1 J 2k'
Continue the transformation as follows:
1 (2k - 2\ ( 2k
Xk =
4k~l \k-lj\ 2k
1 (2k - 2\ 1_ (2k - 2\ (2k - l)(2fc)
4fc-i V A; - 1 J 4fc~1 V k - 1 ) 4k2
1 (2k -2\ 1 /2fcN
. , . , ,. . . for fc= 1,2,3,.... (4)
4*-1 V A: — 1 7 4k\ k ' w

Algebra
113
Fix an integer n > 1 and set in (4) k — 1,2,... ,n; adding the equalities
that result we obtain, by telescoping,
1 /0\ 1 (2n\ i 1 (2n\
si+ioH \-xn—-F:\ =1 . (5)
This number is smaller than 1. Done.
Remark
Solution 2 does not differ from Solution 1 in any essential way; the yns of
Solution 1 are expressed by the explicit formula yn — 4-n ( ^); equalities
(2) and (3) closely correspond to (4) and (5). (In fact, Solution 2 indicates
how the idea of introducing the sequence (yn) in Solution 1 might have
arisen.)
Problem 50, Solution 3
It is obvious that all the a^s are positive numbers. Rewrite the given
recurrence as
2kxk = (2k - 3)xfe_i for A: = 2,3,4,... . (6)
Fix n > 2 and set in (6) k = 2,3,..., n, n+1; if we add all the resulting
equalities and cancel the summands that occur on both sides, we get
xi + xs -\ V xn + (2n + 2)xn+i = x\.
Hence
x\ + X2 + X3 -\ \- xn = 2x\ — (2n + 2)xn+i = 1 — (2n + 2)xn+i.
Since xn+\ is a positive number, the value of this sum is smaller than 1;
the proof is complete.
Problem 50, Solution 4
Assume the converse inequality to the asserted one:
xi+X2 + x$-\ \-xn > 1 (7)
(for a certain n > 2); equivalently: X2 + x^ + ■ ■ ■ + xn > 1 — x\, i.e.,
x2 + x3 + ...+xn >J__1 = 1 (g)
Xl X\
(as si = i). We claim that then
Xk+1 + '-' + Xn>2k-l (9)
Xk

114
Solutions
for k = 1,2,..., n—1. We are going to show this by induction. For k = 1
the inequality (9) coincides with (8). Assume that the estimate (9) is
true for some k (1 < k < n — 2); multiply (9) by xk/xk+i and subtract
1 from both sides of the resulting inequality:
xk+2 + --- + xn ^ ^ _ i)_xfL_ _l = 2k + 1. (1Q)
Xk+1 Xk+l
the last equality follows from xk+i/xk = {2k — l)/(2fc + 2) (the
recursion formula from the problem statement). The induction step (from (9)
to (10)) is done; thus inequality (9) holds for all fc = 1, 2,..., n—1.
Now set in (9) k = n — 1:
-^>2n-3. (11)
The fraction on the left equals (2n — 3)/(2n), according to the definition
of the sequence. So the estimate (11) yields l/(2n) > 1 — obviously a
contradiction. Hypothesis (7) must have been wrong, which means that
the assertion is true.
Problem 51
A sequence of real numbers ao,a\,a2,... satisfies the recurrence \an\ =
an_i + an+i for n = 1,2,3,.... Show that an+g = an for all n.
Problem 51, Solution 1
The sequence contains infinitely many non-negative terms. Choose one
of them. By the given recurrence, it is equal to the sum of the two
neighbouring terms, one of which must be non-negative. So we have two
non-negative terms in succession: am > 0, am+i > 0. Then
0"m—l == am am+li am+2 — am+l am-
One of these two differences is non-negative. This gives us a third non-
negative term adjacent to the two already found.
Now, we have three successive non-negative terms, the middle one equal
to the sum of the other two. Denote them by a, a + b, b (a, b > 0).
Assume a < b. The recurrence determines the sequence forward and
backward, and we are able to control the signs of the four terms that
follow the block a, a + b, b, as well as the signs of the four terms that
precede that block. Hence, this is a piece of our sequence:
... , b, 26 — a, b — a, —b, a, a-\-b, b, —a, a — b, b, 2b —a, ... .
In the case where a > b, the corresponding piece is
... , 2a —b, a, b — a, —b, a, a + b, b, —a, a — b, 2a —b, a, ... .

Algebra
115
In either case, the two leftmost listed terms coincide with the two
rightmost ones, the two pairs being separated by a block of length 7. This
yields the desired periodicity.
Problem 51, Solution 2
Define a transformation of the coordinate plane R2 into itself by the
formula f(x, y) = (y , \y\ — x); its relevance to the problem is apparent
in view of
/K-l , «n) = (an , «n+l)- (1)
Fix a positive number r and consider the closed polygonal line
ABCDEFGHJA
with vertices
A = (0,-r), B = (-r,0), C = (-r,r), D = (0,r), E = (r,2r),
F=(r,r), G = (2r,r), H = (r,0), J = (r,-r);
denote this line by Cr. Pick a point P from the segment AB; thus
P = (x, y), with ?/ = —r — x, —r < a; < 0, and hence its image
Q = f(P) = (—r — x, | — r — x\ — x) = (—r — a;, r)
lies on the segment CD and partitions it in the same ratio as P partitions
AB: CQ/QD — AP/PB. In an analogous fashion we show that CD is
mapped by / onto the segment EF, and so on: every side of the polygon
Cr is mapped onto the next-to-neighbouring side (in the clockwise sense):
AB^CD^EF^GH^JA->BC^DE^FG^HJ^ AB.
Restricted to each particular side, the mapping / is linear; that is to say,
if a point divides a side in some proportion, then its image divides the
corresponding (oriented) side in the same proportion.
It follows that the nine-fold application of / maps each point P G Cr
onto itself: f9(P) = P- And since the union of all polygons £r (as the
parameter r varies) covers the whole plane (except the origin, which is
obviously a fixed-point of /), we conclude that the ninth iterate f9 is the
identity map. This in view of equation (1) proves that an+g = an.
Problem 51, Solution 3
The forward recurrence an+i = \an\ — an_i yields the backward
recurrence an-i — \an\ — an+i. Fix an index m > 0; consider the terms am
and am+9, and write for brevity am+4 = x, am+5 = y. Starting from
the pair x,y and applying four times the recurrence in its forward form

116
Solutions
and in its backward form, we express am and am+Q through x and y as
follows:
lm+9
\y\ - x\ -y - \y\ +x \-\\y\ - x\ + y, (2)
|x| —y| —a; - \x\ +y —\\x\ - y\ +x. (3)
If we denote the expression on the right side of equation (2) by g(x,y),
we get that the right side of equation (3) is just g(y,x). So the problem
reduces to showing that g(x, y) = g(y, x). The verification of this identity
is a more or less automatic task, rather tedious. (Without going too much
into details, let us just observe that in view of the symmetry between the
roles of x and y, one only needs consider three main cases: 0 < x < y;
^<0<?/; x < y < 0; but then they split into subcases...)

Solutions: Geometry
Problem 52
Construct a right triangle ABC with a given hypotenuse c such that two
of its medians are perpendicular.
Problem 52, Solution 1
Assume the right angle is at C and the two perpendicular medians are
issued from the vertices A and C. Choose the coordinate system with
origin at B and with A on the x-axis. Let R be the midpoint of AB and
P the midpoint of BC. Suppose C has coordinates (u,v); thus
A = (c, 0), B = (0,0), C = (u,v), P = (u/2, v/2), R = (c/2,0).
The orthogonality condition APA.CR is restated in terms of the inner
product of vectors:
-(5-«)(§-)-T--
Since C lies on the circle with centre R and radius c/2,
Ml)'-(-§)'■
Substitute this into the former expression to get u = |c. So the point
Z) = (|c, 0) is the foot of the altitude from C.
The method of construction follows: draw the semicircle with diameter
AB of the given length c; partition this segment in the ratio
AD : DB = 1:2.
Draw the perpendicular to AB through D; it will intersect the semicircle
at C, the third vertex of the triangle sought.
Problem 52, Solution 2
Assume the triangle ABC, right-angled at C, has its medians AP and
CR perpendicular. They intersect at S, the centroid of ABC. Let Q be
the midpoint of AC and let T be the projection of S on BC. Since S
partitions AP in the ratio AS : SP = 2:1, the segment CP is partitioned
by T in the same ratio. If CSP has to be a right angle, S must lie on
the circle with diameter CP.
This yields the following method of construction: draw an arbitrary
segment BC, find its midpoint P and the point T on CP such that
A~P-Wk =
u/2-c
v/2
c/2

118
Solutions
CT : TP = 2:1. Draw the semicircle on CP as diameter; then draw the
perpendicular to BC through T; it cuts the semicircle at S, the centroid
of the triangle. Find A as the point of intersection of PS and the line
perpendicular to CB at C. Triangle ABC has the desired shape, but
not the desired size. Transform everything using a suitable similarity to
obtain AB — c.
Problem 52, Solution 3
Let P be the midpoint of side BC and S be the centroid of the triangle
ABC we wish to construct (right-angled at C, with perpendicular
medians from A and C). Let R and W be the midpoints of AB and BR,
respectively.
Construction: Draw segment AB of length c and erect semicircles k, k\,
&2 and &3 over AB, BR, AR and AW as diameters (in one of the two
half-planes determined by AB). Since ACB and ASR are assumed to be
right angles, points C and S have to lie on k and &2, respectively. Circle
k\ is the image of k in the homothety with centre B and coefficient 1/2,
and so P (the midpoint of BC) lies on k\. The centroid S divides AP
so that AP = \AS. Therefore P lies on the circle £3, which is the image
of ki in the homothety with centre A and coefficient 3/2.
A R W B
Hence, P is obtained as the point of intersection of k\ and £3. The vertex
C is the point of intersection of line BP and circle k.
Problem 53
Let ABC be a triangle, AC / BC. Assume that the internal bisector of
angle ACB bisects also the angle formed by the altitude and the median
emanating from vertex C. Show that ABC is a right triangle.
Problem 53, Solution 1
Denote by E the midpoint of AB and by He the foot of the altitude
dropped from C. The perpendicular bisector oi AB intersects the cir-
cumcircle in two points, one of which lies on the other side of line AB
than vertex C; denote this point by D.

Geometry
119
Let O be the circumcentre of triangle ABC. Since AD — BD, the arcs
AD and BD are equal, and so they subtend equal angles ACD and
BCD; thus ray CD is the bisector of angle C. According to assumption,
it bisects angle HcCE; in other words, angles HqCD and DCE are
equal.
Lines CHq and DE are parallel (both are perpendicular to AB).
Therefore
LEDC = IHCCD = LDCE,
which means that CDE is an isosceles triangle: CE = DE. Note that
also triangle CDO is isosceles: CO = DO. Since O lies on line DE,
EO = ±(DO - DE) = ±(CO -CE) (1)
(plus sign if E lies on segment DO, minus sign otherwise). Hence, points
E and O coincide; otherwise CEO would be a non-degenerate triangle
and equality (1) could not hold. The circumcentre coincides with the
midpoint of side AB only if AB is the diameter of the circumcircle.
Thus LACB = 90°.
Problem 53, Solution 2
Let E and He have the same meaning as in Solution 1; let a, b, c be the
lengths of sides BC, CA, AB and let a, (3, 7 be the sizes of angles A, B,
C, respectively. By assumption, angles ACB and HqCE have a common
bisector, and this means that angles AC He and BCE are equal:
LBCE = IACHC = 90° - LCAHC = 90° - a;

120
Solutions
hence
LACE = LACB - LBCE = 7 - (90° - a) = a + 7 - 90° = 90° - /5.
Apply the Law of Sines to triangles ACE and BCE:
AE
C~E~
BE
~CE
Since E is the midpoint of AB, the left-side terms of (2) and (3) are
equal. Equating the right-side terms we obtain sin a cos a = sin/5 cos/5,
i.e.,
sin 2a = sin 2/5. (4)
Sides AC and BC are not equal. Hence a ^ /5, and so equation (4) yields
2a + 2/5 = 180°, which means that 7 = 90°.
Problem 54
If ABCDEF is a convex hexagon with
AB = BC, CD = DE, EF = FA,
prove that the altitudes (produced) of triangles BCD, DEF, FAB,
emanating from vertices C, E, A, concur.
Problem 54, Solution 1
Consider three circles u)\, u)i, ^3, centred at D, F, B, respectively; tu\
passing through C and E; 002 passing through E and A; and u^ passing
through A and C. Let cu2 and u^ intersect at A and A'. Similarly, let u^
and loi intersect at C and C'. Finally, let lu\ and cu2 intersect at E and
E'.
Points A and A' are symmetric across the line connecting the centres F
and B of circles 002 and ^3; thus A A'A. FB. This means that the altitude
of triangle FAB, dropped from A, is contained in line A A'. Analogously,
the other two altitudes considered in the problem are contained in lines
CC' and EE'.
(2)
sin LACE
sin LCAE
sin(90° - /5)
sin a
cos/5
sin a
sin LBCE
sin LC BE
sin(90° - a)
sin/5
~- (3)
sm/5 v '

Geometry
121
Now, line A A' is the power axis of circles 002 and 0*3; lines CC' and EE'
are the power axes of the pairs 0*3, w\ and cui, ui- For a triple of pairwise
intersecting circles whose centres are not collinear, it is a well-known fact
that the three power lines determined by pairs of these three circles are
concurrent. This proves the claim.
Problem 54, Solution 2
The altitudes (produced) of triangles FAB and BCD, issued from
vertices A and C, intersect at some point P; so PAA.BF and PCA.BD.
It will be enough to show that also PEA.DF. In terms of vectors (and
their inner products), we have to prove that the equalities
P~1-B~F = 0 and P~C -D~B =0
imply P~E • F~D = 0.
Points B, D, F lie (respectively) on the perpendicular bisectors of
segments AC, CE, EA, concurrent at O, the circumcentre of triangle ACE.
Thus OB* ■ 16 = 0, 0~S ■ CEJ = 0, Of • El = 0, and hence
0 = OB-A~d + 0~5'CE + OF'E~l
= of-ipd -o~i) + o~d-{pf -od) + of-{ol-o~f)
= 0~l'(OF -OB) +0~d -(OB -0~3) +OE-(OD -OF)
= 0~1-B~F+ 0~d-DB+0~E-F~D
= (P~l -P~6)-WP + (P~d - ¥d) • D~f + (Ff -P~d)-¥D
= P^-B~F+ ¥d-D~f+ P~f-¥^+ P~d-(B~^+ D~f+ ¥f).
In the sum obtained, the first two summands vanish, according to
assumption; and the vector sum in the parentheses is the zero vector.
Therefore PE • FD — 0, and this is just what we wished to prove.
Problem 55
Let ABCDEF be a regular hexagon with M and iV points on diagonals
CA and CE (respectively) such that AM = CN. If M, N and B are
collinear, prove that AM = AB.
Problem 55, Solution 1
Triangles ABM and CDN are congruent, as AB — CD = a (the length
of the side of the hexagon), AM = CN (by assumption), and
LMAB = LNCD = 30°.
Therefore
LDNC = LBMA= LNMC,

122
Solutions
and consequently
IDNB = IDNC + ICNB
= INMC + LCNM
= 180° - LMCN
= 180° - 60°
= 120°.
Also LDOB = 120°, where O denotes the centre of the hexagon. Since
O lies on the circle with centre C and radius a, it follows that also N lies
on this circle. Hence AM = CN = CO = a = AB.
Problem 55, Solution 2
Let AC — CE = 1; then AB — ^\/3. Denote the common length of AM
and CN by x; then CM = EN = 1 — x, and we have the vector equalities
CA? = (1 - x) ■ Cl, C~N' = x-C~E.
Since B lies in line with M and N, there exists a real number £ such that
C~B = (1 - t) ■ C~M +1 ■ C~N = (1 - i)(l - x) ■ Cl + tx ■ C~E.
On the other hand, E~B = §(E~^ + WA), whence
Cl$ = cl + E~^ = CE + ^(-C~E+ [C~l-C~l)) = l-C~l- \-C~^.
The representation of a vector as a linear combination of CA and CE is
unique. Thus, equating the coefficients in the formulas above we obtain
(l-t)(l-*) = §, tx = -l
These equations, combined, yield t + x — 0. Hence t = — x and the
second equation becomes x1 — ^. Thus AM — x = |\/3 = AB.
Problem 55, Solution 3
Let points A, B, C, D, E, M, N be represented by the complex numbers
a, 6, c, d, e, m, n, chosen as follows:
A t l+n/3 3 + i\/3 , l-i\/3 3-«\/3
c = 0, o = , a — , d = , e = .
2 2 2 2
Writing CN :CE = AM : AC = A, we have CM : CA = 1 - A, so that
m = (1 — X)a, n = Xe (A real positive).

Geometry
123
The collinearity of B, M, N requires that the following quotient q be a
real number:
m-b _{l-X)a-b (1 - A)a - (a - 1) 1 - aX
n — b Xe — b Xe — b eX — b
Since a = e and b — d (bar denoting complex conjugation), the required
equality q = q takes the form
1 — aX 1 — eX
eX — b aX — d
Substitution of the numerical values of a, b, d, e simplifies this to:
3A2 = 1. Hence AM = X ■ AC = X ■ \a\ = J\ ■ J\ + \ = \ = AB.
Problem 56
Let ABC be an acute triangle with altitudes BD and CE. Points F and
G are the feet of perpendiculars BF and CG to line DE. Prove that
EF = DG.
Problem 56, Solution 1
Since IBDC and LBEC are right angles, BCDE is a cyclic
quadrilateral, and hence
IBCD = 180° - LBED = LBEF. (1)
Therefore BEF and BCD are similar triangles, and we get
EL = £R. (2)
BE BC W
Analogously, considering the similar triangles CDG and CBE, we have
™ = ™. (3)
BE CB w
The asserted equality EF — DG follows immediately from relations (2)
and (3).
Problem 56, Solution 2
A slight variation of the previous solution: by equation (1),
EF = BE ■ cos(lBEF) = BE • cosC = BC ■ cos B ■ cos C, (4)
where of course B and C are the angles of triangle ABC. The roles of
the point systems B, E, F and C, D, G are symmetric, and therefore we
may replace each character from the first system by the corresponding
one from the second. Formula (4) thus yields
DG = CB cosC cosB. (5)

124
Solutions
Since the right sides of equations (4) and (5) are equal, so are the left
sides.
Problem 56, Solution 3
Let H and H\ be the midpoints of BC and FG. Quadrilateral BCGF
is a trapezoid; thus HH\ is parallel to BF and CG, hence perpendicular
to DE. As in Solutions 1 and 2, notice that D and E lie on the circle
with diameter BC. Line HH\ passing through its centre H and
perpendicular to chord DE, must be the perpendicular bisector of that chord:
Consequently H\ is the common midpoint of DE and FG, and therefore
EF = DG.
Problem 56, Solution 4
The repeated use of the Pythagorean Theorem will also do the job:
ABFE
ACGD
ABEC
ABDC
ACGE
ABFD
EF2 + BF2
CD2
BE2 + CE2
BC2
CG2 + EG2
BD2
=
=
=
=
=
=
BE2;
CG2 + DG2;
BC2;
BD2 +CD2;
CE2;
BF2 + DF2.
If we add these six equalities (and cancel the terms BF2, BE2, CD2,
CG2, CE2, BC2, BD2 that appear on both sides), we are left with
EF2 + EG2 = DG2 + DF2.
Since EG = DE + DG, DF = DE + EF, this is equivalent to
EF2 + DE2 + DG2 + 2DE DG = DG2 + DE2 + EF2 + 2 • DE • EF.
Hence DE ■ DG = DE ■ EF, and consequently DG = EF.
Problem 57
Consider the right triangle ABC with LC = 90°. Let A\ and B\ be two
points on line AB (produced beyond A and B) such that
AAi = AB = BBi
and let iV be the foot of the perpendicular from A\ to line B\C. Show
that the rectangle with sides B\C and CN has area twice as large as the
square with side AB.
Problem 57, Solution 1
Let CC\ be the altitude in triangle ABC and let NP be the altitude in
triangle A\BiN.

Geometry
125
Ai P c A Ci B c Bi
Write
AB = c, CiB=p, CCi = h, BiC = x, CN = y. (1)
We have to show that BXC ■ CN = 2 • AB2; that is, xy = 2c2.
The right triangles B\C\C and B\NA\ are similar [lAB\N being their
common angle), and therefore B\C\ : B\C = B\N : BiAi; equivalently,
(c + p) : x = (x + y) : (3c), or
xy = 3c + 3cp — x . (2)
The altitude of the right triangle ABC satisfies the well-known equality
h2 = p(c — p); hence, by the Pythagorean Theorem for triangle BiC\C,
x2 = (c + p)2 + h2 = (c + p)2'+ p(c -p) = c2 + Zcp.
Inserting this into equation (2) we obtain
xy = (3c2 + 3cp) - (c2 + 3cp) = 2c2,
as wished.
Problem 57, Solution 2
Segments AB and AiBi are diameters of two concentric circles whose
common centre is M, the midpoint of AB. Since LACB and LA\NB\
are right angles, points C and iV lie on those circles. Line B\N cuts
the smaller circle in two points (which can coincide, in the limit case).
Denote them by X and Y, with X lying closer to B\ and Y closer to N;
point C coincides with either X or Y.

126
Solutions
Let S be the foot of the perpendicular from M to line BiN. Chords
XY and B\N of the two circles are perpendicular to line MS. Since M
is the common centre of those circles, MS is the common perpendicular
bisector of XY and B\N. Therefore SB1 = SN and SX = SY; denote
the common length of SX and SY by d. We get
BXX = NY (= BiS - d) and
Our task is to prove the equality
BiY = NX (=B1S+d).
BiC -NC = 2AB'
(3)
(4)
According as C — X or C = Y, the product B\C ■ NC is either equal to
BiX ■ NX or to BiY ■ NY. By virtue of (3), we have
BiC -NC = BiX -BiY
in each case. Considering segments intercepted by circle (ABC) on rays
B\N and B\A\, we have by polarity
BiX -BiY = BiA-BiB.
And since B\A = 2 • AB and 5i5 = ^4.6, claim (4) results.
Problem 57, Solution 3
This is a variation of Solution 1, from which we preserve notation (1).
Moreover, let AC\ = q. The altitude CC\ = h of the right triangle ABC
satisfies: h2 — pq.
The Pythagorean Theorem now implies:
for triangle AiNBi : Axb\
for triangle AXNC : AXC2
for triangle A\C\C : A\C2
for triangle BXCXC : BXC2
AXN2 +NB2,
AiN2 +NC2,
AxCl + dC2,
BXC\ + CXC2.
(5)
(6)
(7)
(8)

Geometry
127
Elimination of A\N2 and A\C2 from equations (5), (6), and (7) gives
NB\ - NC2 = AiB2 - AiC2 = AXB\ - (AiCf + CiC2),
i.e.,
(x+y)2 -y2 = (3c)2 - ((c + g)2 + h2). (9)
Equation (8) says that x2 — (c + p)2 + h2. Substituting this into
equation (9) (whose left side reduces to 2xy + x2) we obtain
2xy + (c + pf + h2 = 9c2 - (c + q)2 - h2.
Hence, in view of h2 — pq and p + q = c ,
2xy = 9c2-((c + p)2 + {c + q)2)-2h2
= 9c2 - (2c2 + 2c(p + q) + (p2 + q2)) - 2pq
= 9c2 - 2c2 - 2c(p + q)-(p + q)2 = 4c2,
showing that xy = 2c2.
Problem 58
Let ABCDE be a convex pentagon inscribed in a circle. The distances
from A to lines BC, CD, DE, and BE are a, b, c, and d, respectively.
Express d in terms of a, b, c.
Problem 58, Solution 1
Denote the feet of the perpendiculars from A to lines BC, CD, DE
and BE by H, N, P and K, respectively; so a = AH, b = AN, c = AP,
d — AK. Assume, for definiteness, that N lies on segment CD, K lies
on segment BE, H lies on line CB produced beyond B, and P lies on
line DE produced beyond E. Obviously, other configurations are also
possible; the reasoning then requires but minor changes. The reader is
invited to find out what cases can occur and to draw suitable diagrams.
Now, in the case at hand: quadrilaterals AHBK, AHCN and AN DP
are cyclic, each of them having two right angles at opposite vertices (at
H, K, N, P). So
LHAK = 180° - LHBK = LCBE, (1)
/.HAN = 180° - LHCN = 180° - LBCD, (2)
LNAP = 180° - IN DP. (3)
Since also BCDE is a cyclic quadrilateral (inscribed in the given circle),
LCBE = 180° - LCDE = 180° - IN DP, (4)
/.BED = 180° - /BCD. (5)

128
Solutions
Comparing equations (2) and (5), we see that angle HAN equals BED,
hence also BAD (inscribed angle subtended by the same arc BD).
Therefore
LHAB = LH AN - IB AN = IB AD - IB AN = IN AD. (6)
Comparing equations (3) and (4), we see that INAP = LCBE, and in
view of (1) we get LHAK = INAP; thus by (6):
LBAK = LHAK - LHAB = LNAP - LNAD = LDAP. (7)
On account of relations (6) and (7), we have the following pairs of similar
right triangles:
AHAB ~ AN AD, L\BAK ~ ADAP.
Consequently AH BK and AN DP are similar quadrilaterals, which
implies that HAK and NAP are similar triangles. Thus
AK _ AP_
A~H ~ ~AN '
In other words, d/a — c/b, and we obtain the desired result:
Problem 58, Solution 2
Preserving notation of Solution 1, consider the angles:
(j) = LABE = LADE, e= LAEB = LACB
((f) is the size of any angle subtended by arc EA, and e is the size of any
angle subtended by arc AB); and let
a = LDEA = 180° - LACD,
the last equality following from the fact that quadrilateral ACDE is
inscribed in the given circle.
Assume for the while that the projection points H, N, P, K are situated
as in Solution 1. Considering the right triangles AKB, APD, AHC,
AKE and ANC we see that
AK . ,
= sin LABK
AB
= sin^>
= sin LADP

Geometry
129
AH
~AC
AP
AD'
sin LACH
sine
sin IAEK
AK
AE '
(8)
(9)
AN
A~C
sin LACN
= sin LACD
= sin(180° - a)
= sin a. (10)
In the general case, each one of LABK and LADP might be equal either
to (j) or to 180° — (j>. This however does not affect the validity of formulas
(8), as sin(180° — 4>) — sin^>; the same observation applies to the
formulas in line (9), while in line (10) angle ACN can be either equal or
complementary to ACD, without affecting the formula. Thus, equalities
(8), (9), (10) are true in any case.
From (8) and (9) we have
AB AK d
A~D ~ A~P ~ c
2se equalities,
d2
ac
and
AB
~ AC
AE
~AC =
■AE
■AD
_ AK
" AH ~
d
a
(11)
(a nice formula in itself). Now, applying the Law of Sines to triangle
ADE and using equations (8) and (10) we obtain
Hence
AE
AD
sin^>
sin a
AK:AB AK■AC
AN:AC AN-AB
AB-AE d
AC-AD b
d
~ b
AC
AB
(12)
Equations (11) and (12) result in d2/(ac) = d/b, and so, finally, d — ac/b.
Problem 58, Solution 3
Denote the radius of the given circle by R. It is the circumradius of
each triangle determined by any three points out of A, B, C, D, E. To

130
Solutions
express the area of any one of these triangles, we may apply either the
formula: (product of sides)/(4R) or: (base times altitude)/2. And thus:
ABBCAC BCAH AC
area ABC = = =>■ a = AH = AB ,
AR 2 2R '
ACADCD CD-AN AD
area ACD = = => b = AN = AC ,
4R 2 2R
AD-AE-DE DE-AP A AE
area ADE = = => c = AP = AD ,
4R 2 2R
AB-AE-BE BE-AK AE
area ABE = = =>■ d = AK = AB .
AR 2 2R
AB ACADAE
aC= 4^ = M>
Therefore
implying d = ac/b.
Remark
The last solution is shortest, easiest to comprehend (though not to invent,
perhaps), and it does not depend on any picture or assumption about
the particular configuration (unlike Solution 1 and, to some extent, also
the second one). Moreover, it shows that A, B, C, D, E might be any
five distinct points on a circle, not necessarily the consecutive vertices of
a pentagon.
Problem 59
Let ABC be an isosceles triangle with base AB. Let U be its circumcen-
tre and M be the centre of the excircle tangent to side AB and to sides
CA and CB produced. Show that 2 • CU < CM < 4 • CU.
Problem 59, Solution 1
Let D be the intersection point of the circumcircle of triangle ABC and
line CM. Denote the incentre of triangle ABC by J. Rays AI and AM
are the internal and the external bisectors of angle A, hence they are
perpendicular and I AM is a right triangle.
Thus AIM A = LIAB = a/2 (where of course a = LCAB).
The orthogonality relations AC J-AD and AI±AM also yield the equality
LMAD = LI AC = a/2. It follows that LM AD = /.AMD, i.e., DAM
is an isosceles triangle and we have DM = DA < CD; the last
inequality holds because CD is the diameter and AD is another chord of the
circumcircle of ABC.

Geometry
131
Note that D lies between C and M. Thus
CD < CM = CD + DM < 2 • CD.
And since CD = 2 • CU, the claim results.
Problem 59, Solution 2
Let /ic be the altitude from C and let pc be the exradius from M to the
midpoint of AB. With the usual notation
BC = a, CA = b (= a), AB = c, a + b + c = 2s,
R = UA = UB = UC, F = area(ABC)
we restate the claim as
2R < hc + pc < 4R.
Using the well-known formulas
abc a2c 2F _ F
AF AF c s - c
we recast inequalities (1) into the form
rt o 8F2 4F2 A o
2a^c < 1 < 4a^c.
c s — c
The area F is expressed by Heron's Formula
F2 = s(s - a)(s - 6)0 - c) = s(s - a)2(s - e) = —
(1)
(2)
(s-c); (3)
we have used the fact that the triangle is isosceles (a = b), so that
a + b + c 2a + c c
s — a = a = a = — .
2 2 2

132
Solutions
In view of formula (3), claim (2) becomes just
2a2 < s(2s-c) < 4a2;
and since 2s — c = a + b= 2a, division by 2a reduces this inequality to
a < s < 2a.
The left part holds trivially, and the right part follows, for instance, from:
2a — s = (a + b) — s = (2s — c) — s = s — c > 0. The claimed inequality
(2) is thus proved.
Problem 59, Solution 3
Let H be the midpoint of side AC. Suppose the excircle in question
touches side AB at T\ and the lines AC and BC at Ti and T3,
respectively.
The segments AT\ and AT2 are- equal, as they are the tangents from A
to the excircle. Thus AT\ = AT2 = c/2, and consequently CT2 = a + c/2
(with a and c standing for the lengths of BC and AB). The right triangles
CHU and CT2M are similar, and hence
CM _ CT2 _ o + c/2 £
"CCT ~ "elf ~ a/2 ~ + a'
The proposed inequality says that the ratio CM : CU should be
comprised between 2 and 4, and so we are left with showing that
0< -<2.
a
The lower estimate is evident, and the right one is so too, due to the
triangle inequality c<a + o = 2a.

Geometry
133
Problem 60
The diagonals AC and BD of a convex quadrilateral ABCD intersect in
E. Let Fi, F% and F be the areas of triangles ABE, CDE and
quadrilateral ABCD, respectively. Show that y/Fi + \JF<i < vf. When does
equality hold?
Problem 60, Solution 1
Denoting the areas of triangles BCE and DAE by F$ and F4, we have
to show that
y/F\ + y/F2< y/Fi + F2 + F3 + F4.
By squaring, this is equivalent to
2y/KF2~<F3 + F4. (1)
Let K and L be the feet of perpendiculars dropped to line AC from D
and B, respectively. (They can lie on or outside segment AC.) Write
BL = 6, DK = d, AE = m, CE = n. Then
F\ = \mb, F2 = \nd, F3 = |n&, F4 = |md.
The inequality (1) we are about to prove becomes
ymb • nd < 2(n& + Tnd);
and this is just the inequality between the arithmetic mean and the
geometric mean of the two products nb and md.
To achieve equality, we need equality between the averaged quantities nb
and md; and this is equivalent to
b : d = m : n. (2)

134
Solutions
Lines BL and DK are parallel. So b : d = BL : DK = BE : DE, by the
Intercept Theorem, and we can restate (2) as
** = :**. (3)
DE CE w
By the (inverse) Intercept Theorem, equation (3) holds if and only if
lines AB and CD are parallel, i.e., ABCD is a trapezoid with AB\\CD.
This is the condition for equality in (1).
Problem 60, Solution 2
Reduce the problem to inequality (1), as in Solution 1. Everything
goes even faster if we write BE = p, DE = q (preserving the notation
AE = m, CE = n) and express the areas Fi as
Fi=^mpsma, F2 = \nq sin a, F3=|npsin/3, i<4=|mgsin/3,
where
a = LAEB = ICED, (3 = LBEC = IDEA = 180° - a.
Hence sin a = sin/3; denote this common value by s. Since a is a convex
angle, s is a' positive number. Inserting the trigonometric expressions for
the FiS into (1) we obtain the inequality
y/mps • nqs < -^nps + i^rnqs
(to prove). Factor s cancels and we are left with
\fmp ■ nq < \{np + mq),
the AM-GM Inequality for np and mq.
Equality requires that np = mq, i.e., p/q = m/n; and this is nothing else
than equality (3) from Solution 1. Conclusion as before.
Problem 61
Let P\Pi be a fixed chord (not a diameter) of a circle k. The tangents to
k at Pi and P2 intersect at Aq. Let P be a variable point on the minor
arc P\P2- The tangent to k at P intersects lines A$P\ and AqPi at A\
and A2, respectively. Determine the position of P for which the area of
triangle A0A1A2 is a maximum.
Problem 61, Solution 1
Let M and r be the centre and the radius of k. Consider k as the
excircle of triangle A0A1A2 escribed at side A\A%. Denoting by s the
semiperimeter of A0A1A2, and by F its area, we have the formula
F = r(s-A1A2). (1)

Geometry
135
(Readers who have not encountered that formula are invited to provide a
proof, which is not at all difficult — using, e.g., the more familiar F = ps,
with p the inradius, plus a similarity argument.)
The factor (s — A1A2) in (1) is the distance from Aq to the point of
contact of the incircle with side AqA\. To make it a maximum, the
incentre should be chosen on ray AoM as far from Aq as possible; and
this is the case (given the conditions of the problem) when P is the
midpoint of arc P\P2-
Problem 61, Solution 2
Choose M, the centre of k, to be the origin of a coordinate system, with
the radius of k as unit (r = 1). Thus the equation of k is x2 + y2 = 1.
Choose P\P2 parallel to y-axis; in coordinates, let
Pi = (u,v), P2 = (u,-v),
and let P = (p,g). Assume u,v > 0, without loss of generality; then
u < p < 1. The lines t\, t2 and £3, tangent to A; at Pi, Pi and P, are
described by the equations
t\\ ux + vy = 1; <2-' ux — vy = 1; £3: px + qy = 1.
They intersect pairwise at the points
v — q p — u \ / v + q u — p \
*,= (±o), Al=(^L.J^-), W-
\u / \pv—qu pv—qu/ \j
<pv—qu pv—qu/ \pv-\-qu pv+qu/
(A0 = t1n t2, Ax = ti n *3, A2 = t2n t3).
The area F of triangle A0A1A2 is expressed by the determinant formula
F = 5[so(1/1 -2/2) +xi(y2 -yo) +x2(yo - Vi)],
Xi and yi standing for the coordinates of Ai. Substituting these
coordinates,
1 rl / p — u p — u \
F = -\-(— + — ) +
I lu \pv — qu pv + qu/
v + q
+ — +
—]
— qui
pv — qu pv + qu pv + qu pv — qu.
1 {{p — «)/«) • 2pv + 2v(u — p)
2 (pv — qu)(pv + qu)
v (p — u)
~ ' ~2 2 2 ? '
u p*v* — g^u'4

136
Solutions
here u, v are constants and p, g are variables satisfying p2 + q2 = 1 =
2 , 2
Therefore p2w2 — g2w2 = p2v2 — (1 — p2)w2 = p2 — u2, and hence
t; (p — u) v p — u v / 2w \
w p2 — «2 « p + u u\ p + u)
Recalling that 0 < w < p < 1, we see that F is a maximum when
2u
p + u
is a minimum, i.e., when p is a maximum, i.e., when p = 1. This
corresponds to P lying on the z-axis, hence coinciding with the midpoint of
arc P\P2-
Problem 61, Solution 3
Again, consider k to have centre M and radius r = 1.
*2
Let the angles Ao, A\, A2 of triangle A0A1A2 have sizes a, /3, 7. Now,
AiM is the bisector of /.PiA1A2; therefore IP1A1M = 90° - (/3/2), so
that (in view of P\M = r = 1)
/3 7
PiAi = cot(/Pi^iM) = tan — ; and similarly, P2^2 = tan — .
Knowing AqP\ = A0P2 = rcot(a/2) = cot(«/2), we can calculate the
area F of triangle A0A1A2 from the trigonometric formula
F — - ■ AqA\ ■ A0A2 • sin a
= -{A0Pl - P1A1)(A0P2 - P2A2) sin a

Geometry
137
Since
sin a / a /3\ / a 7 \
—-— ( cot tan — 1 [ cot — — tan — 1
2 V 2 2/V 2 2/
sin a / o a a / j3 7 \ /5 7 \
—-— cot cot — (tan — + tan — J + tan — tan — .
2 V 2 2\ 2 2/ 2 2/
a (3 (3 7 j a
tan — tan — +tan — tan — +tan — tan — = 1,
Li Li Li Li Li Li
we can express the product of the numbers tan(/5/2) and tan(7/2) by
their sum:
j3 7 a ( P 7\
tan — tan — = 1 — tan — I tan —h tan — ).
2 2 2V 2 2/
Hence
sin a ( o a _ / a «\/ P 7\\
F = — [cot 2 + x" (tan 2+ cot 2) (tan 2+ tan 2))■
The angle a is constant. Consequently the area F is maximized when
the sum tan(/3/2) + tan(7/2) is minimized.
Now, one can set 7 = 180° — a — (3 and examine this sum by calculus,
as a function of the single variable /?; one can also use the convexity of
tana; to deduce that this sum is a minimum when /5 = 7. But we prefer
to use a more elementary argument:
• fP
sin
KH)
P 7
tan — + tan —
2 2 Pi
cos — cos —
2 2
P
2 sin
(H)
cos(f+ i)+cos(f-|)
a
2 cos —
2
. a P ~ 1
sm — + cos —-—
2 2
For a fixed a, this is a minimum when cos((/5 — -y)/2) = 1, i.e., when
P = 7, and we arrive at the same conclusion as in the two previous
solutions.
Problem 62
Let P be a point inside a parallelepiped whose edges have lengths a,
b and c. Show that there is a vertex whose distance from P does not
exceed \^Ja2 + b2 + c2.

138
Solutions
Problem 62, Solution 1
Consider the six planes containing the faces of the parallelepiped. Let
■k be the plane whose distance from P is a minimum, let ABCD be the
face contained in -k and let N be the foot of the perpendicular dropped
from P to 7T. Then N lies within ABCD; otherwise the segment PN
would intersect another face, less distant from P than 7r, contrary to the
choice of it. Assume without loss of generality that the edges not parallel
to 7r have length c. Then PN < c/2.
Now, N is a point inside parallelogram ABCD, with sides of lengths
a and 6. Repeating the previous reasoning (one dimension lower), we
find a side of ABCD whose distance from N is a minimum. Assume
(relabeling if necessary) that this is side AB, with AB = a. Denote by
K the foot of the perpendicular from N to line AB; then K is a point of
the segment AB. Note that NK < 6/2. We may also assume AK < BK.
Thus A K <a/2.
The three segments AK, KN, NP are the edges of a rectangular box
and PA is its space diagonal. Hence, finally,
PA = ^AK2 + KN2 + NP2
= ±Va2 + 62 + c2.
Problem 62, Solution 2
Let O be the centre of the parallelepiped and let u, v, w be vectors of
lengths a/2, 6/2, c/2, parallel to the respective edges. The vertices can
be labeled so that
OA\ — u + v + w, OA2 = —u — v — w,
OA3 = — u + v+w, OA±= u —v + w, OA$= u + v —w,
OAq = u — v — w, OAr=— u + v — w, OAg = — u — v + w.
(In fact, vectors u, v, w provide a basis of a non-orthogonal coordinate
system in the space.) The vector OP determined by the given point P
has representation
OP = xu + yv + z1w with —l<x,y,z<l.
Consider the eight non-negative numbers |(1 + ix)(1 + jy)(l + kz) with
i, j, k taking independently values +1 and —1. Denote them bypi,...,p&
according to the rule:
■ r —r-> , (l+ix)(l+jy)(l + kz)
if OAm = iu + jv + A;w then Pm = ^^—-—r^^ -• (1)
8

Geometry
139
Compute their sum:
8 1
2^?™=- 2^ {l+ix+j y + kz + ij xy+ ik xz+jkyz+ijk xyz).
m=l {^^€{+1,-1}
When (i,j, k) range over the set of the eight triples of plus-minus ones,
then each one of the expressions i, j, k, ij, ik, jk, ijk takes values +1
and —1 equally often. Therefore the sums J^i, Ylh X^> ^Z^h X^*^>
^2jk, J2iJk are zer0> an(l hence
^Pm = -(8 + a;^H h xyz ^ lJk ) = 1-
m=l ^ i,i,k i,i,k '
(2)
Choose an index m € {1,2,3,4,5,6,7,8}; it corresponds to a certain
configuration of plus ones and minus ones, in agreement with (1). For
those values of i, j, k:
PA2m = (OA^-OP)2
= [(i - x)u + (j - j/)v + (A; - z)w]
= [i(l — ix)u + j(l — jy)v + k(l — fcz)w]
= Um + Vm + Wm,
where
v2„2
Um = (l- ixYu' + 2jk(l - jy){\ - kz){y • w),
(3)
(4)
Vm is obtained from Um by the cyclic shift i —*■ j —> A; —* i and the
simultaneous shift x —► y —> z —► x, and Wm arises from Vm in the same
manner. By (1) and (4),
(l-x2)(l-ix)(l+jy)(l + kz) 2
PmUm = ~ U +
| (jk+ijkx)(l-y2)(l-z2) _
Summing over m = 1,... ,8 (that is, over all possible configurations of
signs i, j, k) we obtain
8 n
X^™*7™ = o l^C1 ~ ix)(l + -^X1 + kz)
m=l
L i,j,k
+
2\„2
(i-^K +
2jO'A; + zj/jcc)
(l-<,2)(l-*2)(vw).
1,3,'

140
Solutions
The first sum in square brackets equals 1, and the second one equals 0;
see the argument preceding definition (2). Thus
8
2_J PmUm = (1 - X2)u2.
m=l
Analogously, by cyclicity,
8 8
^ PmVm = (1 - Z/2)V2, Yl PmWm =(1~ *2)W2-
m=l 77i=l
Equalities (3), which hold for m = 1,..., 8, now imply
Y^Pm-PAl = (1-,V + (1-1/2)V2 + (1-V
m=l
< u2 + v2 + w2
a2+62 + c2
4
In view of (2), this sum is a weighted mean of the eight numbers
pa{,...,paI
(with weights pi,... ,Ps)- At least one of those numbers does not exceed
the mean. Consequently, there exists an m such that
2 a2 + b2 + c2
and this is exactly what had to be proved.
Problem 63
Do there exist two cubes such that each face of one of them meets each
face of the other one (possibly at an edge or a corner)?
Problem 63, Solution 1
Suppose a cube C has vertices (±1,±1,±1) and let -k be a plane not
passing through the origin O = (0,0,0) and having points in common
with all the six faces of C. The equation of -k can be written in the general
form ax + by + cz = k, with k ^ 0, a2 + b2 + c2 > 0. The distance
from O to 7r equals d = \k\/\/a2 + b2 + c2. In view of the standard
symmetries of C, there is no loss of generality in assuming c > b > a > 0.
By assumption, -k meets (in particular) the two faces of C, perpendicular
to the .z-axis. So there exist points P = (p, q, —1) and U = (u, v, 1), both
lying on 7r, with coordinates p,q,u,v € [—1,1]. Consequently,
k = ap + bq — c < a-\-b — c < a and k = au + bv-\-c > —a — b + c > —a;

Geometry
141
these two inequalities jointly imply a > \k\. So a > 0, and hence
\k\ a a 1
~ Va2 + b2 + ^ ~ Va2 + b2 + c2 _ Ta2 + a2 + a2 ~ 71 <
Thus if a plane meets all faces of a cube, its distance from O, the cube
centre, is shorter than the distance of any face of that cube from O.
Assuming that two opposite faces of another cube C meet all faces of C,
we are led to the conclusion that C' has strictly smaller size than C. And
since the roles of the two cubes in the problem statement are symmetric,
the negative answer results.
Problem 63, Solution 2
Let C, C be the two cubes. Assume C has edge length 1 and C has edge
length > 1. Choose two opposite faces of C; visualize them horizontally
and call them B and T (base and top). Denote by H the half-space
consisting of all those points that lie below or on the plane of B. Suppose
it contains at least two non-adjacent vertices A, B of C. Let M be the
midpoint of AB. Clearly, M belongs to 7i.
If AB is a space diagonal of C then M is the centre of C, and consequently
every point of C lies within distance |vo from M. Since the distance
between B and T is at least 1, the top face T is disjoint from C.
If AB is a face diagonal of C then M is the centre of the corresponding
face, whose all points lie therefore within distance \y/2 from M. Since
also this number is smaller than 1, the face in question (of C) cannot
reach T.
Now assume there are no two non-adjacent vertices of C in 7i. This
means that 7i contains either no vertex or exactly one vertex of C, or
exactly two vertices of C, linked by an edge. Among the remaining (8 or
7 or 6) vertices of C one can find four points that span a face of C. As
they are situated strictly above the plane of B, that face has no point in
common with B.
Thus, in any case, C has a face that does not meet either B or T. A pair
of cubes with the proposed property does not exist.
Remark
An analogous problem might be considered in the four-dimensional space:
do there exist two 4-cubes in R4, each 3-face of one cube meeting each
3-face of the other one? The answer, rather unexpectedly, is yes.
Example: let C be the 4-cube whose vertices are the 16 points
(±1,±1,±1,±1).
Pick those points that have an even number (four, two or none) of
coordinates equal to 1 — there are eight of them — and adjoin to that

142
Solutions
set another eight points, each having one coordinate equal to 2 or —2,
and the remaining three coordinates 0. These sixteen points also span a
4-cube C' with the property as needed: if you choose arbitrarily a 3-face
of C and a 3-face of C', those two "faces" (3-cubes) will have at least one
common vertex! (To verify this, without having to deal with too many
cases, can be a nice challenging exercise in itself.)
The olympiad problem, discussed above, has been motivated by this
four-dimensional example.
Problem 64
Let Ai, A2, A3, A4 be points on the sphere circumscribed about the
regular tetrahedron with edge 1 such that AiAj < 1 for i ^ j. Prove
that these four points lie on one side of a certain great circle of the
sphere.
Problem 64, Solution 1
To say that the points lie on a certain hemisphere is as much as to claim
that the tetrahedron spanned by these points does not contain the centre
of the sphere in its interior. Thus assume that O, the centre of the sphere,
lies inside tetrahedron A1A2A3A4, which is therefore the union of four
pyramids (numbered 1 through 4), with a common vertex at O, the ith
pyramid having for its base the face of A1A2A3A4 opposite to Ai. Let V*
be the volume of the ith. pyramid and let di be its altitude issued from
vertex O; without loss of generality assume d\ > d2 > d$ > d^.
Further, denote by hi (i = 1,2,3,4) the altitude of the "large"
tetrahedron A1A2A3A4 dropped from vertex Ai to the opposite face and let V
be the volume of A1A2A3A4. Thus Vi/V = di/hi (the ratio of volumes of
those two pyramids equals the ratio of their altitudes, dropped to their
common base).
The foot of altitude d\ of pyramid OA^A^Az coincides with O', the
circumcentre of triangle A1A2A3. This triangle cannot be obtuse-angled;
for if, say, LA% were obtuse, then the points O' and A3 would lie on
distinct sides of line A\A2 (within plane A1A2A3), so O and O' would
lie on distinct sides of plane A1A2A4, and the distance from O to that
plane would be smaller than OOr, in contradiction to ^3 > d±.
Let Vm = min(Vi, V2, V3, V4). Since V = V1 + V2 + V3 + V4, the volume
Vm does not exceed |v. Note that hm < dm + R, where R denotes the
radius of the sphere. Thus
+ R
m y ~ 4 ~ 4
whence
\R > dm > dA. (1)

Geometry
143
Now, visualize a regular tetrahedron inscribed into the given sphere so
that one of its faces (call it A) is parallel to plane A1A2A3. By
hypothesis, all edges of A have length 1. Point O, which is simultaneously the
circumcentre, orthocentre and centroid of the regular tetrahedron,
partitions each of its altitudes in ratio 3:1. Hence, the distance from O to
A is exactly |i2. Comparing this with inequalities (1) we see that the
plane A1A2A3 is less (or equally) distant from O than (as) the plane of
A. Consequently the circumradius of triangle A1A2A3, denote it by r,
is not smaller than the circumradius of A:
r > IVS. (2)
In triangle A1A2A3, let LAk be the greatest angle and let i,j be the
two remaining indices in {1,2,3}. The triangle is not obtuse-angled,
and so the size of LAk is comprised between 7r/3 and 7r/2. As O' is
the circumcentre of A\A2A$, the angle LAiO'Aj = 2 • LAk is comprised
between 27r/3 and it. Therefore cos(LAiO'Aj) < —1/2 and we obtain,
by the Law of Cosines and by inequality (2),
(AiAj)2 = {O'Aif + (O'Aj)2 - 2 • O'Ai ■ O'Aj ■ cos(LAiO'Aj)
= 2r2(l - cosiLAiO'Aj)) > 3r2 > 1.
This is however impossible, according to the condition of the problem.
Contradiction ends the proof.
Problem 64, Solution 2
As in Solution 1, denote by O and R the centre and the radius of the
given sphere. Let T1T2T3T4 be any regular tetrahedron inscribed in that
sphere. The conditions of the problem require that
AiAj < TiTj for i, j = 1, 2,3,4;' i ^ 3. (3)
Consider the following vectors:
uk = OAk, wk = OTk (k = 1,2,3,4).
Relations (3) can be translated into the language of inner products:
\AiAj) — AiAj ' AiA^
= (OAj - OAi) -{OAj - OAi)
= (oTjf - 2 • 0~Xi • 0~Tj + (OA*i)2
= 2(R2 - Ui • Uj)
and similarly
(TiTj)2 = 2(i22-vi.vJ),

144
Solutions
so that inequalities (3) become
u* • Uj > \i • Vj for i =£ j. (4)
Denote by w the sum
w = ui + u2 + u3 + u4. (5)
The analogous sum of vectors V& is the zero vector:
0 = V! + v2 4- V3 + v4; (6)
this is just a restatement, in terms of vectors, of the fact that point O is
the gravicentre of the system of equal point masses placed in the vertices
of the regular tetrahedron.
We now multiply, in the sense of inner product, both sides of equation
(5) by vector ui:
ui«w = ui'(111 + 112 + 113 + 114). (?)
Similarly, multiplying equation (6) by vi we obtain
0 = vi -(vi + v2 + v3 + v4). (8)
Subtracting equation (8) from (7) (and making use of the fact that
ui • ui = vi • vi = R2) we get
Ui • W = (ui • 112 — Vi • V2) + (Ui • U3 — Vi • V3) + (Ui • U4 - VX • V4).
In view of estimates (4), the three numbers in parentheses are positive.
Therefore ui • w > 0. The same argument may be repeated with any
one of the vectors u& in place of iii. Thus
ufc-w>0 for fe = 1,2,3,4. (9)
The inner product of two vectors is positive if and only if they form an
acute angle. Inequality (9) thus says that all the four vectors OAk are
inclined to the vector w under acute angles. If we now draw through
O the plane orthogonal to w, we get the four points A\, A2, A3, A4
collected on one side of it — and this is exactly what we need.
Problem 64, Outline Solution 3
Assume, contrary to assertion, that O is an interior point of tetrahedron
A1A2A3A4. The four solid angles OAiAjAk dissect the sphere into four
non-overlapping spherical triangles, of joint area 4-kR2. Hence, at least
one of them has area greater than or equal to -kR2. Since the distance
between any two points Ai, Aj is less than 1, their "angular distance"

Geometry
145
(size of angle AiOAj) is smaller than the angular distance between any
two vertices of a regular tetrahedron (of edge 1) inscribed in the sphere.
The analogous construction involving solid angles, performed with use
of a regular tetrahedron, produces a partition of the sphere into four
congruent triangular quarters (spherical triangles), of area ttR2 each.
We have shown that the largest of the spherical triangles AiAjAk has
area at least irR2, whereas its "sides" (circular arcs) are strictly shorter
than those of a triangular quarter.
These two inequalities contradict each other. Intuitively, this is easy to
believe; a rigorous proof is less easy!

u
D
\
I
>\2
OAj + (OAi)
lVlarcin E Kuczma
graduated with a PhD
in Pure Mathematics
"" from the University of
Warsaw. He is now a
Senior Instructor in
Pure Mathematics in
the University's
Institute of Mathematics.
His research specialty is real analysis.
He has much experience as a problem
composer and jury member of the Polish,
Austrian/Polish and International
Mathematical Olympiads and is an author
of a book on the Austrian-Polish
mathematical Olympiads. He has composed
four problems in the International
Mathematical Olympiad and had many
more shortlisted.
Dr Kuczma is problem contest editor in the
journal Delta, is a frequent contributor to
problem columns in several journals and in
1992 was awarded the WENMC David
Hilbert Award for his significant
contribution to the enrichment of
mathematics learning internationally.
V
(p-
2 2
Australian Mathematics Trust
Erich Windischbacher
has worked as a high
school teacher in
»v Graz, Austria for more
than 30 years. He has
also taught at the Karl
Eranzens University in
Graz and at the
Pedagogical Institute
for teachers.
Since 1969 he has been very much engaged
with mathematics competitions and the
Austrian Mathematical Olympiad. Prof
Windischbacher co-authored several books
e.g. Osterreichische Mathematik
Olympiaden 1970-1989 and Wege zur
Mathematik - Anregungen und
Vertiefungen.
Enrichment Series
ISBN 1 876420 02 2