UROŠ MILUTINOVIĆ–DARKO ŽUBRINIĆ

BALKANIAN MATHEMATICAL

OLYMPIADES

1984 – 1991 For nonprofit use only Figures are missing

ZAGREB, 1991

Introduction

The organization of Balkan mathematical olympiads was initiated by Prof. Dimitrios Kontogiannis froma Athens (Greece) and Prof. Ivan Tonov from Sofia (Bulgaria) in a friendly chat during the 24th IMO in Paris, 1983. The first competition was held in Athens in 1984. The main objective of Balkan olympiads is to develop friendly relations among Balkan countries (Greece, Cyprus, Bulgaria, Romania and Yugoslavia; we hope that Albania and Turkey will soon join the competition) and to train national teams for the International mathematical olympiad. Let us mention that Yugoslavia participates this competition from the fourth Olympiade.

The competition is held every year in May. Each team has six pupils plus three leaders. Problems are selected by the international jury just before the contest. Duration of the exam is 4,5 hours during which pupils solve four problems. Each problem is worth 10 points, although they are not of equal difficulty. As a rule problems are listed with incresing difficulty. Up to now there were only two problems that were not completely solved during the competiton (problems no. 6.2. and 6.4.).

We decided to present also some of the proposals that have not been selected by the jury. Majority of problems in this book are published for the first time.

Let us mention that in 1989 Balkan summer school was intiated (for younger competitors). It is held usually in some tourist resort at the coast. Every participanting country is represented by ten students and three leaders, who are also supposed to be lecturers. The official language is English.

In the course of past ten years there appeared many new regional competitions, and this trend is certainly going to continue. Let us mention a competition among Austria and Poland, initiated by the cultural agreement between the two states, Ibero–American competition, (South American countries and Spain), Maghrebian competition of north–african countries, Nordic competition and since recently Asian–Pacific competition.

The numbering of figures in this book is related to corresponding problems. The authors are deeply indepted to Prof. Willie Yong who suggested us to

write this book. Our thanks are due to students Miroslav Šilović and Igor Dolinka, and especially to our colleagues Željko Hanjš and Ilko Brnetić who made many corrections during proofreading.

Uroš Milutinović and Darko Žubrinić

\begin{matrix}c \\ ◯ \end{matrix} by the authors

NOTATIONS

• N = {1, 2, 3,… }, the set of positive integers

• N_{0} = N ∪ {0}

• Z, Q, R sets of integers, rational and real numbers

• Euler’s function φ(n): the number of positive integers not greater than n and relatively prime to n ∈ N.

• ⌊x⌋ the greatest integral part of x ∈ R (i.e. the greatest integer not exceeding x).

• iff ≡ if and only if

• We shall adopt the notation (a, b) for both the ordered pair and the open interval, which will be easy to destinguish from the context. Closed intervals will be denoted by [a, b].

• |S| =cardinality of the set S.

1st BALKANIAN MATHEMATICAL OLYMPIAD

ATHENS, Greece, 1984

1.1. Let a_{1}, a_{2},…, a_{n} be positive real numbers (n ≥ 2) such that a_{1}+a_{2}+⋯+a_{n} = 1. Prove that

\frac{a_{1}}{1 + a_{2} + a_{3} + ⋯ + a_{n}} + \frac{a_{2}}{1 + a_{1} + a_{3} + ⋯ + a_{n}} + …

+\frac{a_{n}}{1 + a_{1} + a_{2} + ⋯ + a_{n−1}} ≥ \frac{n}{2n − 1}.

(Greece)

1.2. Let ABCD be inscribed quadrelateral and H_{A}, H_{B}, H_{C}, H_{D} intersections of altitudes of triangles BCD, CDA, DAB and ABC respectively. Prove that quadrelaterals ABCD and H_{A}H_{B}H_{C}H_{D} are congruent.

(Romania)

1.3. Prove that for every natural number m there exists n, n > m, such that the decimal representation of 5^{n} is obtained from the decimal representation of 5^{m} by adding a certain number of digits to the left.

(Bulgaria)

1.4. Find all real solutions of the system

ax + by = (x − y)^{2}
by + cz = (y − z)^{2}
cz + ax = (z − x)^{2},

where a, b, c are given positive real numbers.

(Romania)

2nd BALKANIAN MATHEMATICAL OLYMPIAD

SOFIA, Bulgaria, May 1985.

2.1. Let O be the circumcenter of a triangle ABC, D the midpoint of AB and E the barycenter of the triangle ACD. Show that CD⊥OE if and only if AB = AC.

(Bulgaria)

2.2. Let a, b, c, d ∈ [−\frac{π}{2} , \frac{π}{2} ] be such that

sin a + sin b + sin c + sin d = 1

and

cos 2a + cos 2b + cos 2c + cos 2d ≥ \frac{10}{3}.

Show that a, b, c, d ∈ [0, \frac{π}{6} ].

(Romania)

2.3. The real points of the form 19a + 85b, where a, b ∈ N_{0}, are coloured red, while all the rest of the integral points of R are coloured green. Examine whether there is a point A ∈ R such that for every pair (B, C) ∈ Z × Z with B, C symmetrical with respect to A, the colours of B and C are different.

(Greece)

2.4. 1985 people participate a conference. In each group of three people there are at least two speaking a common language. If each person speaks at most five languages, show that there are at least 200 persons on this conference speaking a common language.

(Romania)

3rd BALKANIAN MATHEMATICAL OLYMPIAD

BUCHAREST, Romania, May 1986.

3.1. A straight line passing through the center I of the incircle of the triangle ABC intersects its circumscribed circle in points F and G, and the incircle in points D and E, where D lies between I and F. Prove that DF · EG ≥ r^{2}, where r is the radius of the incircle. When does the equality hold?

(Greece)

3.2. Let ABCD be a thetraedron and E, F, G, H, K, L points lying on AB, BC, CA, DA, BD DC respectively. Prove that if AE·BE = BF ·CF = CG·AG = DH·AH = DK·BK = DL·CL, then points E, F, G, H, K, L lie on a sphere.

(Bulgaria)

3.3. The sequence a_{1}, a_{2},… is defined by a_{1} = a, a_{2} = b and a_{n+1} = (a_{n}^{2}+c)/a_{n−1}

for n = 2, 3,…, where a, b, c are real numbers, such that ab ≠ 0, c > 0.

Prove that a_{n} (n = 1, 2,…) are integers if and only if a, b and (a^{2} + b^{2} + c)/ab are integers.

(Bulgaria)

3.4. A triangle ABC and a point T lie in a plane, so that the triangles T AB,

T BC, T CA have the same circumference and the same area. Prove that a) if T is in the interior of the triangle ABC, then ABC is equilateral,

b) if T is not in the interior of the triangle ABC, then ABC is rectangular.

(Romania)

4th BALKANIAN MATHEMATICAL OLYMPIAD

ATHENS, Greece, May 1987.

4.1. Let a be a real number and f: R → R a function such that for all x, y ∈ R

f(x + y) = f(x)f(a − y) + f(y)f(a − x)

f(0) = \frac{1}{2}

Prove that f is a constant function.

(former Yugoslavia)

4.2. Let x ≥ 1 and y ≥ 1 be such that

a = \sqrt{x − 1} + \sqrt{y − 1}
b = \sqrt{x + 1} + \sqrt{y + 1}

are nonconsecutive integers. Prove that b = a + 2 and x = y = \frac{5}{4}.

(Romania)

4.3. In a triangle ABC the following relation holds:

sin^{23} \frac{α}{2} · cos^{48} \frac{β}{2} = sin^{23} \frac{β}{2} · cos^{48} \frac{α}{2},

where α and β are the corresponding angles at A and B. Find the ratio AC/BC.

(Cyprus)

4.4. Two circles k_{1} and k_{2} with centers at O_{1} and O_{2} with radii 1 and \sqrt{2} intersect in two points A and B, and O_{1}O_{2} = 2. Let AC be a chord on k_{2}. Find the length of AC, if the midpoint of AC lies on k_{1}.

(Bulgaria)

5th BALKANIAN MATHEMATICAL OLYMPIAD

NICOSIA, Cyprus, May 1988.

5.1. Let CH, CL and CM be altitude, bisector and a median of the triangle ABC with points H, L and M lying on AB. The ratio of areas of triangles HMC and ABC is \frac{1}{4}, while the corresponding ratio for triangles LMC and ABC is 1 − \frac{\sqrt{3}}{2}. Determine the angles of the triangle ABC.

(Bulgaria)

5.2. Find all polynomials P (x, y) in two variables, such that

P (a, b) · P (c, d) = P (ac + bd, ad + bc)

for all real numbers a, b, c, d.

(former Yugoslavia)

5.3. Prove that every thetraedron A_{1}A_{2}A_{3}A_{4} can be situated between two parallel planes whose distance is not greater than \frac{1}{2} \sqrt{P/3}, where

P = (A_{1}A_{2})^{2} + (A_{1}A_{3})^{2} + (A_{1}A_{4})^{2} + (A_{2}A_{3})^{2} + (A_{2}A_{4})^{2} + (A_{3}A_{4})^{2}.

(Greece)

5.4. Find all pairs a_{n}, a_{n+1} of consecutive members of the sequence a_{1}, a_{2} …, defined by a_{n} = 2^{n} + 49, so that

a_{n} = p · q, a_{n+1} = r · s

where p, q, r, s are prime numbers such that

p < q, r < s, q − p = s − r.

(Romania)

6th BALKANIAN MATHEMATICAL OLYMPIAD

SPLIT, former Yugoslavia, May 1989.

6.1. Let d_{1}, d_{2},…, d_{k} be all the divisors of a positive integer n and let 1 = d_{1} < d_{2} < ⋯ < d_{k} = n. Find all numbers n for which k ≥ 4 and

d_{1}^{2} + d_{2}^{2} + d_{3}^{2} + d_{4}^{2} = n.

(Bulgaria)

6.2. Let \overline{a_{n}a_{n−1} … a_{1}a_{0}} = a_{n}10^{n} + a_{n−1}10^{n−1} + ⋯ + 10a_{1} + a_{0} be the decimal representation of a prime number. Assuming that n > 1 and a_{n} > 1, show that the polynomial

P (x) = a_{n}x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0}

is irreducible, i.e. it cannot be the product of two polynomials of positive degree and with integral coefficients.

(former Yugoslavia)

6.3. Let ABC be a triangle and let ℓ be a straight line intersecting the sides AB and AC at the points B_{1} and C_{1} respectively, so that the vertex A and the barycentre G of ABC lie on the same half–plane defined by the line ℓ. Show that

Area(BB_{1}GC_{1}) + Area(CC_{1}GB_{1}) ≥ \frac{4}{9}Area(ABC).

When does the equality hold?

(Greece)

6.4. We consider families F of subsets of {1, 2,…, n}, (n ≥ 3), such that: (i) If A ∈ F, then |A| = 3; (ii) If A ∈ F, B ∈ F, A ≠ B, then |A ∩ B| ≤ 1. Let f(n) be the maximum value of |F| for all such families F. Show that

\frac{1}{6}(n^{2} − 4n) ≤ f(n) ≤ \frac{1}{6}(n^{2} − n),

(|S| denotes the cardinality of a set S).

(Romania)

7th BALKANIAN MATHEMATICAL OLYMPIAD

SOFIA, Bulgaria, May 1990.

7.1. Let a_{1} = 1, a_{2} = 3 and a_{n+2} = (n + 3)a_{n+1} − (n + 2)a_{n} for every integer

n ≥ 1. Find all values of n for which 11 divides a_{n}.

(Greece)

7.2. Consider the polynomial defined by

a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{2n}x^{2n} = (1 · x + 2 · x^{2} + ⋯ + n · x^{n})^{2}.

Show that

a_{n+1} + a_{n+2} + ⋯ + a_{2n} = \frac{n(n + 1)(5n^{2} + 5n + 2)}{24}.

(Bulgaria)

7.3. Let A_{1}B_{1}C_{1} be the orthocentric triangle of sharp–angled, non–equilateral triangle ABC. Let A_{2}, B_{2}, C_{2} be points where the inscribed circle to the triangle A_{1}B_{1}C_{1} meets its sides. Prove that Euler’s lines of triangles ABC and A_{2}B_{2}C_{2} coincide. Remark:

(I) Vertices of orthocentric triangle are feet of heights of the given triangle. (II) Euler’s line of the given triangle ABC is by definition determined by its

orthocenter and the center of the incircle.

(former Yugoslavia)

7.4. Find the minimal cardinality of a finite set A, for which there is a function

f: N → A such that if the number |i − j| is prime, then f(i) ≠ f(j).

(Romania)

8th BALKANIAN MATHEMATICAL OLYMPIAD

CONSTANŢA, Romania, 1991.

8.1. Let M be a point on the arc AB of the circumcircle of a tringle ABC. The perpendicular to the radius OA drawn from M intersects the sides AB, AC at the points K, L respectively (O is the center of the circumcircle). Similarly, the perpendicular to the radius OB drawn from M intersects the sides AB, BC at the point N, P respectively. If KL = MN, compute the angle ^{}M̸LP.

(Greece)

8.2. Prove that there are infinitely many noncongruent triangles T such that (i) the lengths a, b, c of T are relatively prime integers; (ii) the area of the triangle T is an integer; (iii) no altitude of T is an integer.

(Yugoslavia)

8.3. A regular hexagon of area H is inscribed in a convex polygon of area P (all vertices of the hexagon lye on the boundary of the polygon). Prove that P ≤ \frac{3}{2}H. When does the equality hold?

(Bulgaria)

8.4. Prove that there exists no bijection f: N → N_{0} such that

f(mn) = f(m) + f(n) + 3f(m)f(n)

for all m, n ≥ 1.

(Romania)

PROPOSALS OF PROBLEMS

Combinatorics

1. Let us 3–colour the points in the plane. Prove that there are two points at distance 1 having the same colour.

2. Let F be a collection of subsets of N, no one containing another. Let C(F) consist of all subsets M of N with the following properties:

(i) M intersects every member of F; (ii) There is no proper subset M′ of M with the property (i).

Give an example of a collection F such that C(F) is empty and 1989 belongs to exactly 1989 members of collection F.

3. For an arbitrary polyhedron we denote by n_{k} the number of faces with exactly k vertices. Prove that at least one of the two following sentences is true:

(i) there exists k such that n_{k} ≥ 3; (ii) there exists k ≠ h such that n_{k} ≥ n_{h} ≥ 2.

4. Let n^{2} distinct integers be given, each placed on a square of n × n chessboard (n ≥ 2).

Show that it is possible to select n numbers, one from each row and column, so that if the number selected from any row is greater than another number in this row, then this last number is less than the number selected from its column.

Algebra

5. The sequence of functions P_{n} satisfies the following relations:

P_{1}(x) = x, P_{2}(x) = x^{3},

P_{n+1}(x) = \frac{P_{n}^{3}(x) − P_{n−1}(x)}{1 + P_{n}(x)P_{n−1}(x)}, n = 2, 3,…

Prove that all functions P_{n} are polynomials.

6. Solve the following system in real numbers:

2^{x^{2}+y} + 2^{x+y^{2}} = 8
\sqrt{x} + \sqrt{y} = 2.

Analysis

7. Let k be a natural number and

a_{n} = \frac{1^{k} + 2^{k} + ⋯ + n^{k}}{n^{k+1}} , n ∈ N.

Prove that the sequence (a_{n}) is decreasing.

8. Find all continuous functions f: R → R such that

f(x + f(y)) = f(x) + y

for every x, y ∈ R.

Geometry

9. Let ABC be a triangle and let CX and CY be two semilines (in the semiplane determined by the line AC and containing the point B) such that CX is parallel to AB and CX is in the interior of the angle ^{}B̸CY.

A variable line through the point B meets CX in D and CY in E, while the line AD meets BC in F. Show that the lines EF pass through a fixed point.

10. Let ABC be a triangle with BC = 2 · AC − 2 · AB, and D be a point on the side BC. Prove that ^{}A̸BD = 2^{}A̸DB if and only if BD = 3 · CD.

11. Three points A, B and C are given in the plane. Prove that C is a midpoint of the line–segment AB if and only if

P A^{1989} + P B^{1989} ≥ 2 · P C^{1989}

for every point P in the plane.

12. Let ABCD be a regular triangular pyramid in which the side edges AD, BD, and CD are pairwise perpendicular. Find all points X in the interior or on the boundary of ABCD for which the volume of the tetrahedron with vertices the orthogonal projections of X on faces of the pyramid ABCD is maximal.

13. A convex n–gon is situated in a square with a side 1. Prove that there are three vertices A, B, C of the given n–gon, such that the area of triangle ABC does not exceed 8/n^{2}.

Number theory

14. Let n ≥ 3 be a natural number. Prove that

1989 | n^{n^{n^{n}}} − n^{n^{n}}.

15. Let a_{0}, a_{1},…, a_{8} be integers for which

a_{n+1} = a_{n}^{2} − a_{n} + 5, n = 0, 1,…, 7.

Prove that at least two of these numbers are not relatively prime.

16. Are there 1989 positive integers a_{1}, a_{2},…, a_{1989} such that for every i = 3, 4,…, 1989 we have

a_{i} + S_{i} = (a_{i}, S_{i}) + [a_{i}, S_{i}],

where S_{i} = ∑_{j=1}^{i} a_{j} and (·, ·) and [·, ·] are the greatest common divisor and the lowest common multiple respectively.

17. Find all positive integers (x, y, z, n), such that

x^{3} + y^{3} + z^{3} = nx^{2}y^{2}z^{2}.

18. Find all integers p for which there exist rational numbers a and b, such that the polynomial x^{5} − px − 1 has at least one common root with a polynomial x^{2} − ax + b.

SOLUTIONS

1.1. The inequality given in the problem is equivalent to

∑_{k=1}^{n} \frac{a_{k}}{2 − a_{k}} ≥ \frac{n}{2n − 1}.

Noting that

(1)  \frac{a_{k}}{2 − a_{k}} = −1 + \frac{2}{2 − a_{k}}

and

∑_{k=1}^{n}(2 − a_{k}) = 2n − 1,

it is reasonable to introduce a new variable

x_{k} = \frac{2 − a_{k}}{2n − 1} > 0

for which

∑_{k=1}^{n} x_{k} = 1.

Then substituting (1) into the given inequality, we see that it is equivalent to

(2)  ∑_{k=1}^{n} \frac{1}{x_{k}} ≥ n^{2}.

But this is a direct consequence of the harmonic mean–arithmetic mean inequality:

(3)  \frac{n}{\frac{1}{x_{1}} + ⋯ + \frac{1}{x_{n}}} ≤ \frac{x_{1} + ⋯ + x_{n}}{n}

where x_{k} > 0.

REMARK It is easy to prove (2) by induction. For n = 1 the statement is trivial.

Assume that (2) is true for n − 1 and let ∑_{k=1}^{n} x_{k} = 1. Then

∑_{k=1}^{n−1} \frac{x_{k}}{1 − x_{n}} = 1

and from the inductive hypotheses we have

∑_{k=1}^{n−1} \frac{1 − x_{n}}{x_{k}} ≥ (n − 1)^{2}

i.e.

∑_{k=1}^{n} \frac{1}{x_{k}} ≥ \frac{(n − 1)^{2}}{1 − x_{n}} + \frac{1}{x_{n}} ≥ n^{2}

The last inequality is verified directly.

Note that, conversly, the inequlity (3) is almost immediate consequence of (2).

1.2. The idea of the proof is to show that ABH_{A}H_{B}, BCH_{B}H_{C}, CDH_{C}H_{D} and DAH_{D}H_{A} are parallelograms. From this will follow that the quadrelaterals ABCD and H_{A}H_{B}H_{C}H_{D} are symmetric with respect to a point.

Figure 1.2.

It suffices to show that CDH_{C}H_{D} is a parallelogram. First we show that the quadrelateral AH_{D}BH_{C} is inscribed. Indeed, we have

A̸H_{D}B = ^{}A̸CB = ^{}A̸DB = π −^{}B̸H_{C}A

The second, third and fourth equality follow from the fact that the quadrelateral A′H_{D}CB′′ is inscribed (note that ^{}C̸B′′H_{D} = ^{}C̸A′H_{D}), as well as ABCD and DB′H_{C}A”. This proves that AH_{D}BH_{C} is inscribed.

Therefore we have

H̸_{D}H_{C}D = ^{}B̸H_{C}D +^{}B̸H_{C}D
= (π −^{}B̸AD) +^{}B̸AH_{D}
= ^{}D̸CB +^{}B̸CH_{D} = ^{}D̸CH_{D}

where in the second line we used the fact that the quadrelateral AD′H_{C}B′ is inscribed.

In a similar way we get

H̸_{C}H_{D}C = ^{}A̸H_{D}C −^{}A̸H_{D}H_{C}
= (π −^{}A̸BC) −^{}A̸BB′
= ^{}A̸DC −^{}A̸DD′ = ^{}H̸_{C}DC

Therefore CDH_{C}H_{D} is a parallelogram. The degenerated case where, say, the angles ^{}A̸DC and ^{}A̸BC are π/2 (and so B = H_{D}), can be treated in a more direct way:

\begin{matrix}^{}B̸H_{C}D = ^{}B̸′H_{C}D′ = π −^{}B̸′AD′ = ^{}D̸CB \\ = ^{}H̸_{C}DC = ^{}A̸DC −^{}A̸DD′ = ^{}A̸BC −^{}A̸BB′ = ^{}H̸_{C}BC. \end{matrix}

1.3. If n > m, then the statement in the problem is equivalent to

5^{m} = \overline{a_{k_{m}} … a_{0}}
5^{n} = \overline{a_{k_{n}} … a_{k_{m}} … a_{0}},

where the right–hand sides represent the corresponding decimal representations. This is equivalent to

(1)  5^{n} − 5^{m} ≡ 0 (mod 10^{k+1})

with k = k_{m}. It is clear that k + 1 ≤ m, because 5^{m} = a_{k} · 10^{k} + …, a_{k} ≥ 1. Therefore 5^{n} − 5^{m} is divisible by 5^{k+1} for any n > m. In view of (1), it is only left to find n, n > m, such that 5^{n} − 5^{m} is divisible by 2^{k+1}, or equivalently

5^{n−m} − 1 ≡ 0 (mod 2^{k+1}).

But by the Euler formula we have

5^{φ(2^{k+1})} − 1 ≡ 0 (mod 2^{k+1})

(note that 5 and 2^{k+1} are relatively prime). So with n = m + φ(2^{k+1}) we are done.

1.4. Let us introduce new variables

s = x − y, t = y − z,

Then the system becomes

a(s + y) + by = s^{2}
by + c(y − t) = t^{2}
c(y − t) + a(s + y) = (s + t)^{2} = s^{2} + 2st + t^{2}
= 2st + [a(s + y) + by] + [by + c(y − t)]

The last relation gives y = −st/b. After substituting, from the first two equations we obtain the following system in s and t:

[ab − (a + b)t]s = s^{2}
[−(b + c)s − bc]t = t^{2}

We have three possibilities.

a) If s = 0, then −ct = t^{2} and we have either t = 0, i.e.

(x, y, z) = (0, 0, 0),

or t = −c, i.e.

(x, y, z) = (0, 0, c);

b) In a similar way, for t = 0 we obtain s = a and:

(x, y, z) = (a, 0, 0)

c) If s ≠ 0 and t ≠ 0, then

ab − (a + b)t = bs
−bc − (b + c)s = bt.

As a, b, c > 0, the determinant of this system is different from 0. Solving it for instance by elimination, we get s = −b, t = b and one more solution:

(x, y, z) = (0, b, 0).

Figure 2.1.

2.1. It is clear that \overrightarrow{OD} = \frac{1}{2}(\overrightarrow{OA} + \overrightarrow{OB}) and

\overrightarrow{OE} = \frac{1}{3}(\overrightarrow{OA} + \overrightarrow{OD} + \overrightarrow{OC}) = \frac{1}{6}(3\overrightarrow{OA} + \overrightarrow{OB} + 2\overrightarrow{OC}).

We also have

\overrightarrow{CD} = \overrightarrow{OD} − \overrightarrow{OC} = \frac{1}{2}[\overrightarrow{OA} + \overrightarrow{OB} − 2\overrightarrow{OC}].

After a short computation, from \overrightarrow{OE} · \overrightarrow{CD} = 0 (note that OA = OB = OC) we

get \overrightarrow{OA} · \overrightarrow{OB} = \overrightarrow{OA} · \overrightarrow{OC}, i.e. \overrightarrow{OA}⊥\overrightarrow{BC}. But this is easily seen to be equivalent to AB = AC.

2.2. Let us introduce the following notation:

x = sin a, y = sin b, z = sin c, u = sin d.

In view of the symmetry it suffices to prove that x ∈ [0, \frac{1}{2}]. From cos 2a = 1−2x^{2}, cos 2b = 1 − 2y^{2}, cos c = 1 − 2z^{2} and cos 2d = 1 − 2u^{2} we deduce:

x + y + z + u = 1

x^{2} + y^{2} + z^{2} + u^{2} ≤ \frac{1}{3}.

Eliminating u in the inequality, after a short computation we arrive to the following quadratic inequality in z:

z^{2} + (x + y − 1)z + (x^{2} + y^{2} + xy − x − y + \frac{1}{3}) ≤ 0.

In order to have a solution z, the corresponding discriminant must be nonnegative, that is

(x + y − 1)^{2} − 4(x^{2} + y^{2} + xy − x − y + \frac{1}{3}) ≥ 0.

But this yields another quadratic inequality

3y^{2} + 2(x − 1)y + (3x^{2} − 2x + \frac{1}{3}) ≤ 0

in the variable y. For the analogous reason as before, its discriminant must be nonnegative:

4(x − 1)^{2} − 4[9x^{2} − 6x + 1] ≥ 0,

i.e.

x(x − \frac{1}{2}) ≤ 0.

From this we immediately conclude that x ∈ [0, \frac{1}{2}].

2.3. The general solution of the Diophant equation

(1)  19x + 85y = n

is

x = 19t − 2n, y = 9n − 85t, t ∈ Z.

We shall use the fact that 1 = 9 · 19 − 2 · 85, i.e. n = 9n · 19 − 2n · 85. The condition x, y ≥ 0 is equivalent to

\frac{2n}{19} ≤ t ≤ \frac{9n}{85}.

Therefore we see that the point n ≥ 0 will be coloured red if and only if the interval

(2)  [\frac{2n}{19}, \frac{9n}{85}]

contains an integer. By the way, it is clear that all negative integers are coloured green.

We check directly that all integers ≥ 1512 are coloured red. Namely, by using

(3)  1 = 9 · 19 − 2 · 85
(4)  1 = (−76) · 19 + 17 · 85

we have

1512 = 8 · 19 + 16 · 85
1513 = 17 · 19 + 14 · 85
1514 = 26 · 19 + 12 · 85
1515 = 35 · 19 + 10 · 85
1516 = 44 · 19 + 8 · 85
1517 = 53 · 19 + 6 · 85
1518 = 62 · 19 + 4 · 85
1519 = 71 · 19 + 2 · 85
1520 = 80 · 19 + 0 · 85
1511 = 4 · 19 + 17 · 85
1522 = 13 · 19 + 15 · 85
1523 = 22 · 19 + 13 · 85
1524 = 31 · 19 + 11 · 85
1525 = 40 · 19 + 9 · 85
1526 = 49 · 19 + 7 · 85
1527 = 58 · 19 + 5 · 85
1528 = 67 · 19 + 3 · 85
1529 = 76 · 19 + 1 · 85
1530 = 0 · 19 + 18 · 85
1531 = 8 · 19 + 16 · 85

and so on (note that (4) is used only at boxed numbers). In this way we see that all integers n ≥ 1512 are red.

For n = 1511 the corresponding interval (2) is [159\frac{1}{19}, 159\frac{84}{85}], which contains no integer, and is therefore coloured green.

So, if there is A with the property described in the problem, then it must be the midpoint of the interval [0, 1511], i.e. A = 755\frac{1}{2}.

It is only left to prove that for any integer n ∈ [0, 1511] the integers n and 1511 − n have different colours (they are symmetric with respect to A).

a) Let us prove that for any integer n ∈ [0, 1511] which is red, the integer 1511 − n must be green.

Suppose by contradiction that they are both red, i.e.

n = 19a + 85b
1511 − n = 19c − 85d

with a, b, c, d ≥ 0. Then we would have the integer

1511 = 19(a + c) + 85(b + d) coloured red, a contradiction (note that a + c, b + d ≥ 0).

b) If n is coloured green, then

\frac{2n}{19}, \frac{9n}{85} ∈ (k, k + 1)

for some k ∈ Z, so that

\frac{2n}{19} = k + \frac{α}{19}, α ∈ \{1,…, 18\},
\frac{2n}{85} = k + \frac{β}{85}, β ∈ \{1,…, 84\}.

Now we have

\frac{2(1511 − n)}{19} = 159\frac{1}{19} − k − \frac{α}{19} ∈ (158 − k, 159 − k],
\frac{9(1511 − n)}{85} = 159\frac{84}{85} − k − \frac{β}{85} ∈ [159 − k, 160 − k),

and from

159 − k ∈ [\frac{2(1511 − n)}{19}, \frac{9(1511 − n)}{85}]

we see that the integer 1511 − n is coloured red.

Therefore the point A = 755\frac{1}{2} has the desired properties.

2.4. Consider the following two possibilities.

a) Let any two persons speak at least one common language. The person A speaks with the remaining 1984 people a common language, and speaks at most five languages, so at least there is one language spoken by at least

⌊\frac{1984}{5}⌋ > 200

participants of the congress.

b) The second possibility is that there are two persons A and B who do not speak any language in common. Then every of the remaining 1983 persons can speak to at least one of the persons A and B (this follows from the three men condidition). So at least 992 participants can speak with one of these two persons (say A). This implies that A can speak the same language to at least 199 people, because otherwise he could speak to at most 5 · 198 < 992 people. These group together with the person A constitutes the desired 200 participants speaking the same language.

3.1. In order to prove the inequality, note that

DF = IF − r
EG = IG − r
IF · IG = R^{2} − IO^{2},

Figure 3.1.

where R is a radius of the circle circumscribed to the triangle ABC (the last relation represents a well known property of the power of point I with respect to the circle). Then

DF · EG ≥ r^{2}

is equivalent to

F G ≤ \frac{R^{2} − IO^{2}}{r} .

As the line given in a problem is arbitrary, we have to prove that

2R ≤ \frac{R^{2} − IO^{2}}{r} ,

i.e.

IO^{2} ≤ R(R − 2r).

But, according to the well known Euler’s formula, we have IO^{2} = R(R − 2r)!

The equality holds true if and only if the straight line passes through O and I.

3.2. First describe a sphere around the tetrahedron ABCD. Its intersection with the plane ABC is a circle k_{D} circumscribed to the triangle ABC. Denote its center by O_{D} and radius by r_{D}.

The same for the remaining three triangles (sides of ABCD).

Figure 3.2.a) Figure 3.2.b)

The condition

AE · EB = BF · F C = CG · GA

means that powers of points E, F, G are the same with respect to k_{D}. If distances of E, F and G from O_{D} are e, f and g respectively, then we have

(r_{D} − e)(r_{D} + e) = (r_{D} − f)(r_{D} + f) = (r_{D} − g)(r_{D} + g).

From this we conclude e = f = g, so that points E, F and G lie on a circle of radius r̃_{D}, concentric to k_{D}. The same for the remaining three triangles.

Figure 3.2.c)

Let d_{E}, d_{F} ,… be distances of points E, F … from the center O. Now as OO_{D} is perpendicular to the side ABC, we have

d_{F}^{2} = r̃_{D}^{2} + OO_{D}^{2} = d_{E}^{2} = r̃_{C}^{2} + OO_{C}^{2} = d_{H}^{2}.

The same holds for all the other pairs of points from the problem, which means that they lie on a sphere with a center at O.

3.3. It is clear that a_{n−1} ≠ 0 implies a_{n+1} ≠ 0, so that a_{n} ≠ 0 for all n. Note first that for all n we have

\frac{a_{n}^{2} + a_{n+1}^{2} + c}{a_{n}a_{n+1}} = \frac{a_{n}^{2} + (\frac{a_{n}^{2}+c}{a_{n−1}})^{2} + c}{a_{n} \frac{a_{n}^{2}+c}{a_{n−1}}} = \frac{a_{n−1}^{2} + a_{n}^{2} + c}{a_{n−1}a_{n}}.

By induction we see that

\frac{a_{n}^{2} + a_{n+1}^{2} + c}{a_{n}a_{n+1}} = \frac{a^{2} + b^{2} + c}{ab}.

a) To prove the sufficiency of the condition in the problem, note that

a_{n+1} = \frac{a_{n}^{2} + c}{a_{n−1}}

= \frac{a_{n−1}^{2} + a_{n}^{2} + c}{a_{n−1}a_{n}}a_{n} − a_{n−1}

= \frac{a^{2} + b^{2} + c}{ab}a_{n} − a_{n−1}.

By induction we get that all a_{n} are in Z.

b) Conversly, assume that a_{n} ∈ Z for all n. Let

\frac{a^{2} + b^{2} + c}{ab} = \frac{p}{q},

where p ∈ Z, q ∈ N, are relatively prime. Then we have

(1)  a_{n+1} = \frac{p}{q}a_{n} − a_{n−1}, ∀n ≥ 2.

From this we see that \frac{p}{q}a_{n} ∈ Z, i.e. a_{n} = qa_{n}^{(1)}, where a_{n}^{(1)} ∈ Z. From (1) we get

(2)  a_{n+1}^{(1)} = \frac{p}{q}a_{n}^{(1)} − a_{n−1}^{(1)}, ∀n ≥ 3.

We have again that a_{n}^{(1)} = qa_{n}^{(2)}, i.e. a_{n} = q^{2}a_{n}^{(2)}. Repeating this procedure, we arrive to

a_{n} = q^{k}a_{n}^{(k)}, ∀n ≥ k + 1,

Let us write shorter a_{k+1} = q^{k}b_{k+1}. Now note that

c = a_{k+1}a_{k−1} − a_{k}^{2} ∈ Z,

so that

\frac{p}{q} = \frac{a_{k}^{2} + a_{k+1}^{2} + c}{a_{k}a_{k+1}} = \frac{q^{2k}b_{k+1}^{2} + q^{2k−2}b_{k}^{2} + c}{q^{2k−1}b_{k}b_{k+1}}.

From this it immediately follows that q^{2k−2} must devide c for every k, and this is possible only for q = 1.

3.4. a) It is clear that the triangle satisfying the conditions of the problem cannot be degenerated. Let P be the area of each of the triangles T AB, T BC, T CA (these areas are equal). The line AT divides the side BC into two parts of lengths a_{1} and a_{2}, and the triangle BT C into two triangles of areas P_{1} and P_{2}. Denote the altitudes of triangles ABA′ and BT C, drawn from A and T respectively, by v and v′. Then from

Figure 3.4.a_{1})

\frac{a_{1}v}{2} = P + P_{1}, \frac{a_{2}v}{2} = P + P_{2}

we have

(1)  \frac{a_{1}}{a_{2}} = \frac{P + P_{1}}{P + P_{2}} .

Also from

\frac{a_{1}v′}{2} = P_{1}, \frac{a_{2}v′}{2} = P_{2}

we get

(2)  \frac{a_{1}}{a_{2}} = \frac{P_{1}}{P_{2}} .

Figure 3.4.a_{2})

Now relations (1) and (2) yield P_{1} = P_{2}, i.e. a_{1} = a_{2}, and in a similar way for the remaining sides of the triangle ABC. So T must be the barycenter of the triangle ABC.

From the condition in the problem we have

c + \frac{2}{3}(t_{a} + t_{b}) = a + \frac{2}{3}(t_{b} + t_{c}),

i.e.

c − a = \frac{2}{3}(t_{c} − t_{a}).

Assuming c ≠ a, it is easy to see that t_{c} ≠ t_{a}. From

(c − a)(t_{c} + t_{a}) = \frac{2}{3}(t_{c}^{2} − t_{a}^{2}) = \frac{2}{3}(\frac{a^{2} + b^{2}}{2} − \frac{c^{2}}{4} − \frac{b^{2} + c^{2}}{2} + \frac{a^{2}}{4} )= \frac{1}{2}(a^{2} − c^{2})

we get

t_{a} + t_{c} = −\frac{a + c}{2},

which is impossible. So c = a and similarly a = b. Therefore, the triangle ABC is isosceles.

b) It is clear that the point T cannot lie on the boundary of the triangle ABC. Otherwise we would not have equality of all the areas, because of the degeneration of some of the triangles.

Let us first show that T can be neither in sector I, nor on lines AB, AC, BC.

Figure 3.4.b_{1})

Figure 3.4.b_{2})

Indeed, assume by contradiction that T is in the sector I. Then the line T A intersects the side BC in point D. Without loss of generality we can assume that D ≠ C. Now we have

P (T AC) = P (T BC) ≥ P (T DC) = P (T AC) + P (ADC) > P (T AC),

where P is the corresponding area, and this is a contradiction.

Figure 3.4.b_{3})

We can therefore take that the point T lies in the sector II, say opposite to B. Denote the intersection of lines BT and AC by D. Let x, y, z, u be lengths of sides and P_{1}, P_{2}, P_{3}, P_{4} areas of triangles like on the picture. Then we have

P_{1} + P_{2} = P_{3} + P_{4} = P_{2} + P_{3},

from which it follows

P_{1} = P_{3}, P_{2} = P_{4}.

This implies (using for instance the sine theorem) xy = uz, xu = yz. Multiplying these relations we get x = z, y = u, i.e. ABCT is a parallelogram. But we also have

a + c + 2y = a + c + 2x

i.e. x = y. Therefore the point B lies on the circle of the diameter AC, so that ABC is a right–angle triangle and T is the fourth vertix of ABCT, having the desired property.

4.1. Substituting y = 0 and then x = a into the relation, we have

(1)  f(x) = f(x)f(a) + f(0)f(a − x)
f(a) = [f(a)]^{2} + \frac{1}{4}.

Therefore (f(a) − 1/2)^{2} = 0 and f(a) = 1/2. From (1) we obtain

(2)  f(x) = f(a − x).

So the relation given in the problem now becomes

f(x + y) = 2f(x)f(y).

Now we have

\frac{1}{2} = f(a) = 2f(x)f(a − x) = 2[f(x)]^{2},

and from this f(x) = ±1/2.

If we had b such that f(b) = −1/2, then we would have

−\frac{1}{2} = f(b) = f(\frac{b}{2} + \frac{b}{2}) = 2f(\frac{b}{2})^{2},

which is impossible. Therefore f(x) = 1/2 for all x.

Alternate solution. Substituting x = y = 0 we obtain f(a) = \frac{1}{2}. Now change y by 0 and next by a in the relation. Thus we get

f(x) = f(a − x), f(x) = f(a + x)

and for any real x it follows

f(−x) = f(a − (−x)) = f(a + x) = f(x).

Let x and y be arbitrary real numbers. Using the above together with the identity in the problem, we have

f(x − y) = f(x)f(a + y) + f(−y)f(a − x)
= f(x)f(a − y) + f(y)f(a − x) = f(x + y)

Putting y = x into this relation we finally obtain f(2x) = f(0) = 1/2, i.e. f(x) = 1/2 for all x.

4.2. First we have

b − a = \frac{2}{\sqrt{x + 1} + \sqrt{x − 1}} + \frac{2}{\sqrt{y + 1} + \sqrt{y − 1}} ≥ 2.

Without loss of generality we can assume that x ≥ y. Therefore

\frac{2}{\sqrt{y + 1} + \sqrt{y − 1}} ≥ 1.

After squaring twice the inequality 2 − \sqrt{y − 1} ≥ \sqrt{y + 1}, we obtain y ≤ 5/4. If we had b − a ≥ 3, then we would have

\frac{2}{\sqrt{y + 1} + \sqrt{y − 1}} ≥ \frac{3}{2},

i.e. 4/3 − \sqrt{y − 1} ≥ \sqrt{y + 1}, and after squaring

\frac{8}{3}\sqrt{y − 1} + \frac{2}{9} ≤ 0,

which is impossible.

So we have b − a = 2. Denote

x + y = s
xy = p.

Then

a^{2} = x − 1 + y − 1 + 2\sqrt{xy − x − y + 1}
b^{2} = a^{2} + 4a + 4 = x + 1 + y + 1 + 2\sqrt{xy + x + y + 1}.

i.e.

a^{2} + 2 − s = 2\sqrt{p − s + 1} ≥ 0
a^{2} + 4a + 2 − s = 2\sqrt{p + s + 1}

and from this after squaring and substracting both relations we obtain

a^{3} + 2a^{2} + 2a = (a + 1)s ≤ (a + 1)(a^{2} + 2).

Finally, we obtain a^{2} ≤ 1, that is a = 1, and from this s = 5/2, p = 25/16, x = y = 5/4.

REMARK We can obtain b = a + 2 more directly by noting that the obvious inequality

\sqrt{t + 1} + \sqrt{t − 1} ≥ \sqrt{2}, ∀t ≥ 1

implies

0 < b − a = \frac{2}{\sqrt{x + 1} + \sqrt{x − 1}} + \frac{2}{\sqrt{y + 1} + \sqrt{y − 1}} ≤ 2\sqrt{2}.

4.3. For every s and t such that 0 < s < t < π/2, we have sin^{23} s < sin^{23} t and cos^{48} s > cos^{48} t. Therefore the function

f(t) = \frac{sin^{23} t}{cos^{48} t}

is strictly increasing on (0, π/2). So from f(α/2) = f(β/2) we get α = β, that is AC/BC = 1.

Figure 4.4.

4.4. Let M be the midpoint of AC and AM = x, ^{}A̸MO_{1} = φ. As the angle A̸MO_{2} is equal to π/2, we have MO_{2} = \sqrt{2 − x^{2}}. From the cosine theorem for triangle △O_{1}O_{2}M we get:

sin φ = − cos(\frac{π}{2} + φ) = \frac{1 + x^{2}}{2\sqrt{2 − x^{2}}} .

As the triangle AMO_{1} is isosceles, we also have cos φ = \frac{x}{2}, i.e. sin φ = \sqrt{1 − x^{2}/4} (note that 0 < φ < π/2). Introduce a new variable t = x^{2}, 0 < t < 2. The unique solution of

\frac{1 + t}{2\sqrt{2 − t}} = \sqrt{1 − \frac{t}{4}}

is t = 7/8. Therefore x = \sqrt{t} = \sqrt{7/8} and

AC = 2x = \sqrt{\frac{7}{2}}.

5.1. Let AB = c, AC = b and BC = a. Without loss of generality we may assume that 0 < b < a, so that the points H and L lie on the segment AM. From the conditions of the problem we have

Figure 5.1.

\frac{P (HMC)}{P (ABC)} = \frac{HM · HC}{AB · HC} = \frac{HM}{AB} = \frac{1}{4}
\frac{P (LMC)}{P (ABC)} = \frac{LM · HC}{AB · HC} = \frac{LM}{AB} = 1 − \frac{\sqrt{3}}{2}.

It is well known that for bisectors we have the following relation:

\frac{AL}{b} = \frac{c − AL}{a},

so that

AL = \frac{bc}{a + b}.

Therefore

LM = \frac{c}{2} − AL = \frac{c(a − b)}{2(a + b)}.

As LM/c = 1 − \sqrt{3}/2, we obtain that a = \sqrt{3} b. On the other hand, from the cosine theorem

a^{2} = b^{2} + c^{2} − 2bc cos α = b^{2} + c^{2} − 2c · AH

follows

HM = \frac{c}{2} − AH = \frac{a^{2} − b^{2}}{2c} = \frac{b^{2}}{c} ,

and from this

\frac{1}{4} = \frac{HM}{c} = \frac{b^{2}}{c^{2}} ,

i.e. c = 2b. Therefore α = 60 deg , β = 30 deg , γ = 90 deg .

Alternate solution.

1. From AH = HM we obtain ^{}H̸MC = α, and from this CM = AC = b.

2. As LM = (1 − \sqrt{3}/2)c, we have LB = \frac{3−\sqrt{3}}{2}c and from AL : LB = b : a we deduce

a = \sqrt{3} b.

3. Now HB = HM + MB = 3HM = 3AC cos α and HB^{2} + HC^{2} = BC^{2}, so that 9 cos^{2} α + sin^{2} α = 3, i.e. cos α = 1/2 (cos α cannot be negative). Hence α = 60 deg .

4. We conclude that AM = MC = MB, and therefore M is the center of the circumscribed circle, i.e. γ = 90 deg .

5.2. First we note that

(1)  P (tx, ty) = P (t, 0)P (x, y)
(2)  P (ts, 0) = P (t, 0)P (s, 0)

Define p(x) = P (x, 0) = a_{k}x^{k} + ⋯ + a_{0}. From (2) one gets easily (comparing coefficients on both sides) that either p(x) = 0, or p(x) = 1, or p(x) = x^{k} with k ≥ 1, for all x.

Therefore, either P (x, y) = 0, or P (x, y) = 1, or

(3)  P (tx, ty) = t^{k}P (x, y)

Consider (3):

P (x, y)P (1, 1) = P (x + y, x + y) = (x + y)^{k}P (1, 1)
P (x, y)P (1, −1) = P (x − y, x − y) = (x − y)^{k}P (1, −1).

Now we have three cases:

a) If P (1, 1) ≠ 0, then P (x, y) = (x + y)^{k}, which is easily verified to satisfy the condition of the problem.

b) If P (1, −1) ≠ 0, then P (x, y) = (x − y)^{k}, which also satisfyes the condition in the problem.

c) Assume that P (1, 1) = P (1, −1) = 0. Keeping y fixed, and dividing P (x, y) by x^{2} − y^{2} we obtain

P (x, y) = (x^{2} − y^{2})Q(x, y) + xR(y) + S(y),

for all x, y ∈ R. Substituting (x, y) = (t, t) and (x, y) = (t, −t) and using (3) we obtain

tR(t) + S(t) = 0
−tR(t) + S(t) = 0,

from which we obtain R(t) = S(t) = 0 for all t. Therefore

P (x, y) = (x^{2} − y^{2})Q(x, y)

in this case.

The polynomial Q also satisfies the condition in the problem like P, and its degree is equal to k − 2. So, we can again repeat the whole procedure with three possible cases for Q, instead of P. After finitely many steps we arrive to

(4)  P (x, y) = (x + y)^{m}(x − y)^{n},

where m, n ≥ 0 are integers. Therefore all solutions of the problem are constants 0, 1 and polynomials given by (4). REMARK Let us state the problem analogous to the preceding one: Find all polynomials P (x, y, z) in three variables, such that

P (a, b, c) · P (x, y, z) = P (ax + bz + cy, ay + bx + cz, az + by + cx)

for all real numbers a, b, c, x, y, z. It can be shown that all solutions are either constants 0 and 1, or

P (x, y, z) = (x + y + z)^{m}(x^{2} + y^{2} + z^{2} − xy − yz − zx)^{n},

where m, n ≥ 0 are integers. Try to prove this!

5.3. Denote a_{1} = A_{1}A_{2}, a_{2} = A_{3}A_{4}, a_{3} = A_{1}A_{4}, a_{4} = A_{2}A_{3}, a_{5} = A_{2}A_{4}, a_{6} = A_{1}A_{3}.

Let M_{1}, M_{2}, M_{3}, M_{4} be midpoints of edges indicated on the diagram.These are the vertices of a parallelogram.

Analogously, we have two more midpoints M_{5} and M_{6} and the corresponding parallelograms.

The opposite edges of the tetrahedron define nonparallel lines. Denote the smallest distance of these three pairs of nonparallel lines by d. It is clear that the pair of lines with minimal distance defines two parallel planes containing them and the whole tetrahedron is in between. Therefore

d ≤ M_{1}M_{2}
d ≤ M_{3}M_{4}
d ≤ M_{5}M_{6}.

Figure 5.3.

Using the parallelogram equality we obtain

3d^{2} ≤ |M_{1}M_{2}|^{2} + |M_{3}M_{4}|^{2} + |M_{5}M_{6}|^{2}

= \frac{1}{2}(|M_{1}M_{2}|^{2} + |M_{3}M_{4}|^{2}) + \frac{1}{2}(|M_{1}M_{2}|^{2} + |M_{5}M_{6}|^{2})

+ \frac{1}{2}(|M_{3}M_{4}|^{2} + |M_{5}M_{6}|^{2})

= \frac{1}{4}[(a_{5}^{2} + a_{6}^{2}) + (a_{3}^{2} + a_{4}^{2}) + (a_{1}^{2} + a_{2}^{2})] = \frac{P}{4} ,

i.e. d ≤ \frac{1}{2} \sqrt{P/3}.

Alternate solution. The opposite edges of the tethraedhron define two parallel planes containg them. These six plains define a parallelepiped. Denote lengths of its edges by a, b, c, and let d be the smallest of distances between three pairs of parallel planes introduced above. Then by the parallelogram identity the sum of squares of opposite edges is equal to

2a^{2} + 2c^{2}, 2a^{2} + 2b^{2}, 2b^{2} + 2c^{2}.

From this we have

P = 4(a^{2} + b^{2} + c^{2}) ≥ 4(d^{2} + d^{2} + d^{2}) = 12d^{2}.

5.4. We shall prove that the single pair of consecutive terms which verifies the given condition is (a_{7}, a_{8}).

Let us put q − p = s − r = x. Then we have

a_{n} = p(p + x), a_{n+1} = r(r + x).

The function p ↦ p(p+x) is increasing, therefore p < r. For every odd n = 2k +1 we have

a_{n} = 2^{n} + 49 ≡ 2^{n} + 1 = 2(3 + 1)^{k} + 1 ≡ 0 (mod 3)

and 2^{n} + 49 is obviously odd. So, p = 3.

We have

(1)  a_{n+1} = 2a_{n} − 49 < 2a_{n},

which implies r < 2p. Indeed, if r ≥ 2p, then

a_{n+1} = r(r + x) ≥ 2p(2p + x) > 2p(p + x) = 2a_{n}.

Hence 3 < r < 6 and therefore r = 5. Substituting the values p = 3 and r = 6 into the recurrence relation (1), one finds 5(5 + x) = 6(3 + x) − 49, hence x = 56. It follows that a_{n} = 3·59 and a_{n+1} = 5·61. One verifies directly that these numbers are a_{7} = 2^{7} + 49 and a_{8} = 2^{8} + 49.

Alternate solution. Denote y = s − q = r − p. Like in the previous solution we get

a_{n} = 3q, a_{n+1} = (3 + y)(q + y).

Therefore (3 + y)(q + y) = 2^{n+1} + 49 = 2^{n} + 3q, i.e.

(1)  y(\frac{2^{n} + 49}{3} + y + 3) = 2^{n}.

If y ≥ 3, then the left hand side of (1) is bigger than the right hand side, which is impossible. Also in case y = 1 we have a contradiction: a_{n+1} = 4(q + 1). So the only possibility left is y = 2. Now from (1) we compute n = 7 and the result follows easily.

6.1. If d_{2} > 2, then n, d_{2}, d_{3} and d_{4} are odd. So d_{1}^{2} + d_{2}^{2} + d_{3}^{2} + d_{4}^{2} is even, which is a contradiction. Therefore d_{2} = 2, n is even and from the equality n = 1^{2} +2^{2} +d_{3}^{2} +d_{4}^{2} we obtain that exactly one of the numbers d_{3} and d_{4} is even.

a) Let d_{3} be even, i.e. d_{3} = 2a, a ≥ 1. Then a < d_{3} is a divisor of n and hence a = d_{1} = 1, or a = d_{2} = 2. It is easy to check that both cases are impossible.

b) If d_{4} is even, d_{4} = 2a, a ≥ 1, a similar reasoning shows that a = 1, a = 2 or a = d_{3}. The case a = 1 leads to a contradicition. If a = 2, then d_{4} = 4, so that d_{3} = 3. Therefore n = 1^{2} + 2^{2} + 3^{2} + 4^{2} = 30, which is not divisible by four.

Now it suffices to consider the case a = d_{3}. We have d_{4} = 2d_{3}, and then

n = 1^{2} + 2^{2} + d_{3}^{2} + (2d_{3})^{2} = 5(d_{3}^{2} + 1).

Since d_{3} divides n, we obtain that d_{3} = 5, d_{4} = 10, n = 1^{2} + 2^{2} + 5^{2} + 10^{2} = 130. All the divisors of 130 are 1, 2, 5, 10, 13, 26, 65, 130. Hence, n = 130 is the unique solution.

6.2. Observe that if P (x) = 0, then |x| < 9. Indeed, if |x| ≥ 9, then:

|P (x)| = |a_{n}x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{0}|

≥ 2|x|^{n} − 9(|x|^{n−1} + ⋯ + 1) = \frac{2|x|^{n+1} − 11|x|^{n} + 9}{|x| − 1}

> \frac{2|x|^{n}(|x| − 9) + 9}{|x| − 1} > 0.

Suppose by contradiction that P (x) = Q(x)R(x), where Q and R are polynomials with integer coefficients. We have

\overline{a_{n}a_{n−1} … a_{0}} = P (10) = Q(10)R(10).

By the above we have that |Q(10)| > 1 and |R(10)| > 1, which is impossible (P (10) is prime). Namely, since Q(x) = a ∏_{i<k}(x − x_{i}), a ∈ Z, then |x_{i}| < 9 and so |Q(10)| = |a| ∏_{i<k} |10 − x_{i}| > 1.

REMARK The conclusion of the problem is valid also for the case a_{n} = 1, but it requires a different proof (see the problem book of Pólya–Szegö).

6.3. Let us denote the corresponding areas shortly in round brackets. Define

E_{1} = (AB_{1}G), E_{2} = (AC_{1}G).

As G is the barycentre of ABC, the altitude of the triangle AGC_{1} from the vertix G is one third of the altitude of triangle ABC_{1} drawn from B. Similarly for triangles AB_{1}C and AB_{1}G. Therefore

(1)  (ABC_{1}) = 3E_{2}, (AB_{1}C) = 3E_{1}.

Note that

(ABC_{1}) = E_{1} + E_{2} + (BB_{1}GC_{1}) = 3E_{2}
(AB_{1}C) = E_{1} + E_{2} + (CC_{1}GB_{1}) = 3E_{1},

Figure 6.3.

so that

(2)  (BB_{1}GC_{1}) + (CC_{1}GB_{1}) = E_{1} + E_{2}.

Moreover

(3)  \frac{(ABC)}{(ABC_{1})} = \frac{AC}{AC_{1}} , \frac{(ABC)}{(AB_{1}C)} = \frac{AB}{AB_{1}} .

From (1) and (3) we get

\frac{(ABC)}{E_{2}} = 3\frac{AC}{AC_{1}} , \frac{(ABC)}{E_{1}} = 3\frac{AB}{AB_{1}} .

From this we have

\frac{E_{1} + E_{2}}{(ABC)} = \frac{1}{3}(\frac{AC_{1}}{AC} + \frac{AB_{1}}{AB} )

≥ \frac{2}{3}\sqrt{\frac{AC_{1} · AB_{1}}{AC · AB}}

= \frac{2}{3}\sqrt{\frac{(AB_{1}C_{1})}{(ABC)}}

≥ \frac{2}{3}\sqrt{\frac{E_{1} + E_{2}}{(ABC)} ,}

and the desired inequality follows from (2). The equality holds if and only if AC_{1}/AC = AB_{1}/AB and (AB_{1}C_{1}) = E_{1} + E_{2}, that is if and only if the line ℓ is parallel to BC and contains G.

6.4. For the upper bound, let F be an arbitrary family of 3–element subsets of {1,…, n}, such that |A ∩ B| ≤ 1 for any A, B ∈ F. All 2–element subsets of all elements of F must be different. Each A ∈ F contains \binom{3}{2} = 3 different 2–element subsets and all of these are required to be distinct. Therefore, since the total number of 2–element subsets of \{1,…, n\} is \binom{n}{2}, we have

(1)  3|F| ≤ \binom{n}{2}.

As F was arbitrary, it follows that

(2)  f(n) ≤ \frac{1}{3}\binom{n}{2} = \frac{n^{2} − n}{6},

which proves the upper bound.

For the lower bound, consider the family F_{0} of all 3–element subsets A = {a, b, c} of {1,…, n}, such that a + b + c = n, or a + b + c = 2n. Evidently, if a + b + c_{1} ∈ {n, 2n} and a + b + c_{2} ∈ {n, 2n}, then c_{1} = c_{2} (otherwise we would have |c_{1} − c_{2}| = n, which contradicts the fact that c_{1}, c_{2} ∈ {1,…, n}). Thus the family F_{0} has the desired property, and hence f(n) ≥ |F_{0}|. Now we estimate |F_{0}|.

For selecting an arbitrary A = {a, b, c} ∈ F_{0}, we have n possibilities for a, and (for fixed a) at least n − 4 possibilities for b (since b ≠ a, b ≠ (n − a)/2, b ≠ (2n − s)/2, b ≠ s − 2a, and 1 ≤ b ≤ n, where s = a + b + c ∈ {n, 2n}; these conditions come from the fact that {a, b, c} must be a 3–element subset, that is a ≠ b, b ≠ c and c ≠ a). But in this way we select ordered triples (a, b, c) in F_{0}. Since a 3–element subset can be permuted in 3! = 6 ways, it follows that any A ∈ F_{0} is counted exactly 6 times. By the above we obtain

6|F_{0}| ≥ n(n − 4),

that is

f(n) ≥ |F_{0}| ≥ \frac{n^{2} − 4n}{6}.

This proves the lower bound and concludes the solution of the problem.

REMARK 1. We can obtain slightly better lower bound as follows. Observe that the condition b ≠ (n − a)/2 in the argument above is “effective” only for those a, 1 ≤ a ≤ n, with a ≡ n (mod 2). Also, the condition b ≠ (2n − a)/2 is “effectove” only for even a. It follows that for odd n (and fixed a) b can be selected in at least

\{ \begin{matrix}n − 2 ways, for odd a \\ n − 4 ways, for even a. \end{matrix}

Using a similar argument as in the solution above, we obtain thus

f(n) = \{ \begin{matrix}\frac{n(n−3)}{6} & for odd n \\ \frac{1}{6}[\frac{n}{2}(n − 2) + \frac{n}{2}(n − 4)] = \frac{n(n−3)}{6} & for even n. \end{matrix}

Hence, finally

f(n) ≥ \frac{n(n − 3)}{6}.

Alternate solution and generalization. Let us prove the lower bound defining again

F_{0} = { {a, b, c} ⊆ {1, 2,…, n}: a + b + c ∈ {n, 2n}, a ≠ b ≠ c ≠ a }.

As we saw in previous solution, the set F_{0} has properties (i) and (ii). The idea is to compute effectively the cardinality of this set.

It is clear that any {a, b, c} ∈ F_{0} defines precisely six different ordered triples of its elements. Let us count all such ordered triples (a, b, c) from F_{0}.

If a, b ∈ {1,…, n} are any two elements for which a ≠ b, then c is uniquely determined:

1) if a + b < n, then c = n − (a + b);

2) if a + b ≥ n, then c = 2n − (a + b). From all such pairs (a, b) we shall have to exclude those, for which the

corresponding c is equal to a or b (see the definition of F_{0}). We are led to the following two cases: 1’) Let a + b < n. Then c = a iff 2a + b = n and c = b iff a + 2b = n; 2’) Let a + b ≥ n. Then c = a iff 2a + b = 2n and c = b iff a + 2b = 2n.

So, the desired number of ordered triples (a, b, c) will be equal to the number of pairs which are left in the ‘square’

{ (a, b): a, b ∈ {1,…, n} }

when we remove points on ‘lines’

a = b
2a + b = n, a + 2b = n,
2a + b = 2n, a + 2b = 2n.

Let us count all such pairs (a, b). We consider the following four cases.

I. n = 2k ≢ 0 (mod 3). From the ‘square’ having n^{2} = (2k)^{2} points we have to remove

• 2k points on ‘line’ a = b;

• k − 1 points on ‘line’ a + 2b = n (for b = 1,…, k − 1) and k − 1 points on ‘line’ 2a + b = n (for a = 1,…, k − 1); • k points on ‘line’ a + 2b = 2n (for b = k,…, 2k − 1) and k points on ‘line’

2a + b = 2n (for a = k,…, 2k − 1).

We recommend you to draw the ‘square’ and ‘lines’ for, say, n = 8.

It is left to see that among points removed there are no those counted twice. Indeed, if we had

2a + b = a + 2b = n,

then we would have a = b = n/3, a contradiction. Therefore

6|F_{0}| = (2k)^{2} − 2k − 2(k − 1) − 2k = n^{2} − 3n + 2.

The remaining cases can be treated in a similar way, so we leave the details to the reader.

II. n = 2k + 1 ≢ 0 (mod 3). By repeating the procedure like in I. we arrive to

6|F_{0}| = (2k + 1)^{2} − (2k + 1) − 4k = n^{2} − 3n + 2.

III. n = 2k ≡ 0 (mod 3). In this case we have

6|F_{0}| = (2k)^{2} − (2k) − 2(k − 2) − 2(k − 1) = n^{2} − 3n + 6.

IV. n = 2k + 1 ≡ 0 (mod 3). Here we have

6|F_{0}| = (2k + 1)^{2} − (2k + 1) − 4(k − 1) = n^{2} − 3n + 6.

Finally, we arrive to the following conclusion

|F_{0}| = \{ \begin{matrix}\frac{n^{2}−3n+2}{6}, & n ≢ 0 (mod 3) \\ \frac{n^{2}−3n+6}{6}, & n ≡ 0 (mod 3), \end{matrix}

i.e.

|F_{0}| = ⌊\frac{n^{2} − 3n}{6}⌋ + 1.

From this it is clear that

f(n) > \frac{n^{2} − 3n}{6} ≥ \frac{n^{2} − 4n}{6}.

REMARK 2 It should be noted that the family F_{0} is not necessarily maximal, i.e. its cardinality could be less than f(n). For instance, if n = 8, then by the above formula |F_{0}| = 7. On the other hand, the family

F = { {1, 2, 8}, {2, 3, 4}, {4, 5, 6}, {6, 7, 8},
{1, 3, 6}, {2, 5, 7}, {1, 4, 7}, {3, 5, 8} }

satisfies the conditions (i) and (ii), and contains 8 elements.

7.1. By direct calculation we get

a_{1} ≡ 1 (mod 11)
a_{2} ≡ 3 (mod 11)
a_{3} ≡ 9 (mod 11)
a_{4} ≡ 0 (mod 11)
a_{5} ≡ 10 (mod 11)
a_{6} ≡ 4 (mod 11)
a_{7} ≡ 6 (mod 11)
a_{8} ≡ 0 (mod 11)
a_{9} ≡ 1 (mod 11)
a_{10} ≡ 0 (mod 11)
a_{11} ≡ 0 (mod 11).

So from the relation in the problem we obtain that for every n ≥ 10 we have a_{n+2} ≡ 0 (mod 11). The answer is:

n ∈ {4, 8} ∪ {n ∈ N: n ≥ 10}.

Alternate solution. From the recurrence relation in the problem we immediately see that for n ≥ 3 we have

a_{n} − a_{n−1} = n(a_{n−1} − a_{n−2})
a_{n−1} − a_{n−2} = (n − 1)(a_{n−2} − a_{n−3})

⋮

a_{4} − a_{3} = 4(a_{3} − a_{2})
a_{3} − a_{2} = (a_{2} − a_{1})

After consecutive substitutions we arrive to:

a_{n} − a_{n−1} = 3 · 4 . . . · n · (a_{2} − a_{1}) = n!

i.e.

(1)  a_{n} = a_{n−1} + n!,

and therefore a_{n} = 1! + 2! + 3! + ⋯ + n!

Now we have

a_{1} = 1 a_{2} = 3 a_{3} = 9 ≡ −2
a_{4} ≡ −2 + 2 · 3 · 4 = 0 a_{5} ≡ 2 · 3 · 4 · 5 ≡ −1 a_{6} ≡ −1(−1) · 6 ≡ −7 ≡ 4

and in a similar way a_{7} ≡ 6, a_{8} ≡ 0, a_{9} ≡ 1, a_{10} ≡ 0. All congruences are modulo 11. As for n ≥ 11 we have n! ≡ 0, from (1) it follows that then a_{n} ≡ 0, as well as for n = 4, 8.

7.2. Defining b_{i} = ix^{i} we can write:

(x + 2x^{2} + ⋯ + nx^{n})^{2} = ∑_{i=1}^{n} b_{i} · ∑_{n=1}^{n} b_{i} = ∑_{i=1}^{n} ∑_{j=1}^{n} b_{i}b_{j}.

The power of the monomial b_{i}b_{j} is equal to i + j. Hence, instead of summing up numbers a_{i}, i = n+1,…, 2n, it suffices to sum up the products b_{i}b_{j}, for which x = 1 and i + j ≥ n + 1. As b_{i}b_{j} |_{x=1} = ij, we can write

∑_{i=n+1}^{2n} a_{i} = ∑_{\begin{matrix}i,j≤n \\ i+j>n \end{matrix}} ij = ∑_{i=1}^{n} ∑_{j=n−i+1}^{n} ij =

= ∑_{i=1}^{n} i · \frac{i(2n − i + 1)}{2} = \frac{2n + 1}{2} ∑_{i=1}^{n} i^{2} − \frac{1}{2} ∑_{i=1}^{n} i^{3}

= \frac{2n + 1}{2} · \frac{n(n + 1)(2n + 1)}{6} − \frac{1}{2} \frac{n^{2}(n + 1)^{2}}{4}

= \frac{1}{24}n(n + 1)(5n^{2} + 5n + 2),

where we used well known summation identities, that are easy to prove by induction.

Alternate solution. Let us prove the claim by induction. For n = 1 it is checked directly. Denote the polynomial introduced in the problem by f_{n}(x) and define

S_{n} = a_{n+1} + ⋯ + a_{2n}.

Suppose that the claim is valid for n. Then we have

f_{n+1}(x) = b_{0} + b_{1}x + ⋯ + b_{2n+2}x^{2n+2} =
= (x + ⋯ + nx^{n} + (n + 1)x^{n+1})^{2} =
= (x + ⋯ + nx^{n})^{2} + (n + 1)^{2}x^{2n+2} + 2(x + ⋯ + nx^{n})(n + 1)x^{n+1}
= a_{0} + a_{1}x + ⋯ + a_{2n}x^{2n}
+ [2(n + 1)x^{n+2} + … 2nx^{2n+1} + (n + 1)^{2}x^{2n+2}],

Figure 7.3.

from which it follows

(1)  \begin{aligned}S_{n+1} & = b_{n+2} + ⋯ + b_{2n+2} \\ & = a_{n+2} + ⋯ + a_{2n} + 2(n + 1)(1 + ⋯ + n) + (n + 1)^{2} \\ & = (S_{n} − a_{n+1}) + (n + 1)^{3}. \end{aligned}

It is only left to determine a_{n+1}, i.e. the coefficient at x^{n+1} for the polynomial

f_{n}(x) = (x + 2x^{2} + ⋯ + nx^{n}) · (x + 2x^{2} + ⋯ + nx^{n}).

Substituting

a_{n+1} = 1 · n + 2 · (n − 2) ⋯ + n · 1 = ∑_{i=1}^{n} i(n + 1 − i) =

= (n + 1) ∑_{i=1}^{n} i − ∑_{i=1}^{n} i^{2} = (n + 1)\frac{n(n + 1)}{2} − \frac{1}{6}n(n + 1)(2n + 1)

= \frac{1}{6}n(n + 1)(n + 2)

into (1), we obtain

S_{n+1} = \frac{1}{24}(n + 1)(n + 2)[5(n + 1)^{2} + 5(n + 1) + 2],

which proves the statement.

7.3. a) Let us first prove that the altitudes of the triangle △ABC bisect the angles ^{}C̸_{1}A_{1}B_{1}, ^{}A̸_{1}B_{1}C_{1} andi ^{}B̸_{1}C_{1}A_{1}. Let H be the orthocenter of △ABC.

It suffices to prove that ^{}B̸_{1}C_{1}C = ^{}A̸_{1}C_{1}C. As ^{}H̸C_{1}B = ^{}H̸A_{1}B = π/2, the quadrelateral HC_{1}BA_{1} is inscribed, so that ^{}H̸C_{1}A_{1} = ^{}H̸BA_{1} = ^{}B̸_{1}BA_{1}. Similarly ^{}H̸C_{1}A = ^{}H̸B_{1}A, which implies that the quadrelateral HB_{1}AC_{1} is also inscribed, and then ^{}B̸_{1}C_{1}H = ^{}B̸_{1}AH = ^{}B̸_{1}AA_{1}. Finally ^{}B̸B_{1}A = A̸A_{1}B = π/2, so that as ABA_{1}B_{1} is inscribed, we conclude

B̸_{1}C_{1}C = ^{}B̸_{1}C_{1}H = ^{}B̸_{1}AA_{1} = ^{}B̸_{1}BA_{1} = ^{}H̸C_{1}A_{1} = ^{}A̸_{1}C_{1}C,

which proves the claim a).

b) Denote by S the center of the incircle. From a) we have that H is the center of the circle inscribed to the triangle △A_{1}B_{1}C_{1}, and it is at the same time circumscribed to the triangle △A_{2}B_{2}C_{2}. The sides B_{1}C_{1} and A_{1}C_{1} are tangent to this circle, so that HA_{2}⊥B_{1}C_{1} and HB_{2}⊥A_{1}C_{1}. As HC_{1} is a bisector of the angle ^{}A̸_{2}C_{1}B_{2}, the triangles △HA_{2}C_{1} and △HB_{2}C_{1} are similar. Therefore HC_{1} is a ‘line’ of symmetry of A_{2}B_{2}, so that we have A_{2}B_{2}⊥HC_{1}⊥AB and then A_{2}B_{2}∥AB. Similarly B_{2}C_{2}∥BC and C_{2}A_{2}∥CA, so that the triangles △ABC and △A_{2}B_{2}C_{2} have parallel sides. But then the Euler’s “line’s’ are parallel, and as H is the orthocenter of △ABC and the center of the circle inscribed to △A_{2}B_{2}C_{2}, these two “line’s’ coincide.

7.4. For integers 1, 3, 6, 8, differences of any two are primes. According to the condition in our problem, f(1), f(3), f(6), f(8) must all be mutualy different, so that A has at least four elements.

Let us define A = {1, 2, 3, 4} and f(n) ≡ n (mod 4). From f(i) = f(j) we conclude i ≡ j (mod 4), i.e. four divides |i−j|, so that |i−j| not prime. Therefore the minimal cardinality of A is 4.

8.1. Let us prove that \overline{MK} = \overline{KL} = \overline{MN} = \overline{NP}. From
O̸AB = ^{}O̸BA = \frac{1}{2}(π − 2^{}A̸CB) = \frac{π}{2} −^{}A̸CB,
A̸KL = ^{}B̸NP = ^{}A̸CB

we obtain

(1)  \overline{MK} = \overline{MN} = \overline{KL}.

The triangles AKL and P NB are congruent (they are both conguent to ABC, so that

(2)  \overline{AK} · \overline{BN} = \overline{KL} · \overline{P N}.

The triangles AMK and MBN are congruent as well, therefore

(3)  \overline{AK} · \overline{BN} = \overline{MK} · \overline{MN}.

From (1), (2) and (3) we have \overline{MK} = \overline{MN} = \overline{KL} = \overline{NP}. Therefore KN ∥ P L, and so ^{}M̸LP = ^{}M̸KN = ^{}A̸CB.

8.2. Let P be the area of the triangle and s = \frac{1}{2}(a + b + c). By Heron’s formula we have P = \sqrt{s(s − a)(s − b)(s − c)}, (s − a) + (s − b) + (s − c) = s. For any natural number k define s − a = k^{4}, s − b = 4k^{2} i s − c = 4. We have s = (k^{2} + 1)^{2} and

a = 4(k^{2} + 1), b = k^{4} + 4, c = k^{2}(k^{2} + 4).

Let k be odd and k > 1. Then a and c are relatively prime, which proves (i) and (ii). From h_{a} = 2P/a and similarly for remaining altitudes, we get

h_{a} = \frac{2k^{3}(k^{2} + 2)}{k^{2} + 1}, h_{b} = \frac{8k^{3}(k^{2} + 2)}{k^{4} + 4}, h_{c} = \frac{8k(k^{2} + 2)}{k^{2} + 4}.

As k^{4} + 4 = (k^{2} − 2)(k^{2} + 2) + 8 and k is odd, fractions by which h_{b} and h_{c} are expressed cannot be canceled, while the fraction representing h_{a} can be canceled by 2. This proves (iii).

8.3. By convexity, the convex polygon in the probelm is contained inside the starshaped region on the picture, whose vertices are A_{i}, M_{i}, i = 1,…, 6. The convexity implies also that the area of the part of convex polygon inside the union of congruent triangles A_{1}M_{1}A_{2} i A_{2}M_{2}A_{3}, is not greater than any of its areas (prove this!). Considering in the same way the remaining parts of the convex polygon that are outside the regular hexagon, we conclude that the area of the part of convex polygon outside of hexagon is not greater than the triple

Figure 8.3.

area of the triangle with the side equal to the side of hexagon, i.e. it is not greater than a half of the area of the regular hexagon. This proves the desired inequality.

The equality holds if and only if the vertices of the convex polygon lie on sides of the starshaped region on the picture, i.e. if and only if the convex polygon is a triangle (prove this!).

8.4. Supose by contradiction that such bijection does not exist. For m = n = 1 we get f(1) + 3f(1)^{2} = 0, i.e. f(1) = 0. By bijectivity of f it follows f(n) ≥ 1 for all n ≥ 2. If m, n ≥ 2, then f(mn) ≥ 1 + 1 + 3 = 5, so that f(k) ≥ 2 for every nonprime integer k. Therefore there exist different primes n_{1} and n_{3} such that f(n_{1}) = 1, f(n_{3}) = 3 and an integer n_{8} such that f(n_{8}) = 8. Then f(n_{3}^{2}) = 3 + 3 + 3 · 3 · 3 = 33 and f(n_{1}n_{8}) = 1 + 8 + 3 · 1 · 8 = 33. From this we conclude n_{3}^{2} = n_{1} · n_{8}, i.e. n_{1} | n_{3}^{2}, which is impossible, because n_{1} and n_{3} are two different primes. Remark. If we denote g(m) = 3f(m) + 1, the property of f is translated into g(mn) = g(m)g(n), g: N → 3N_{0} + 1, hence the monoids (N, ·) and (3N_{0} + 1, ·) are not isomorphic.

Figure 1

SOLUTIONS OF PROPOSALS

1. Let the points of the plain be 3–coloured. Consider the configuration (see Figure 1) in which all lines have a unit length.

Let A have, say, red colour. Then points B and C must be blue and green (in some order). Therefore F must be red. Similarly G must be red. But then F and G form a pair at distance 1 with the same colour.

2. First we shall solve a similar problem for a collection S of subsets of N×N, no one containing another. Let S be a collection of subsets A_{n} of N × N, defined by

A_{n} = {(p, q): p ≠ n and q ≥ n},

for each n ∈ N.

Note that if m ≠ n, then A_{m} ⊈ A_{n}. Suppose that B intersects every A_{n}. Then B must be infinite. If there exists n_{0} such that a set

{q: (n_{0}, q) ∈ B}

is infinite, then let (n_{0}, q) ∈ B and let B′ = B \ {(n_{0}, q)}. If there is no such n_{0}, let (p, q) be arbitrary and let B′ = B \ {(p, q)}. In either case B′ still intersects every A_{n}. This shows that C(S) must be empty.

Figure 4

Let f: N × N → N be a bijection such that f(1990, 1989) = 1989. Let

F = {f(A_{n}): A_{n} ∈ S}.

The collection F is our example.

3. There exist natural numbers x so that n_{x} ≠ 0; let m be the biggest and F a face with m vertices. There are m distinct faces F_{i} adjecent to F. The number v_{i} of F_{i}’s vertices satisfies 3 ≤ v_{i} ≤ m, hence there are at most (m − 2) values k for v_{i}.

If there exists k so that at least three faces F_{i} have k vertices, (i) is true. If (i) is not true, there will be at least two distinct values k and h such that

two faces F_{i} have k vertices and two have h vertices; in this situation (ii) is true.

4. We shall construct the desired n numbers by repeating a phase of temporary selections. In the first phase we choose the least element in each row, and then for each column we choose the biggest of the numbers selected (if any). If there is one selected number in each column, we are finished, otherwise there are columns for which some of the row selected numbers are rejected. We shall call these rows free and we pass to the next phase.

For any subsequent phase we choose for each free row the least element fromm those not yet tried. If each column contains a selected number, we are finished, otherwise we consider the biggest number in each column (if any), call rejected rows free, and go to the next phase.

Let us note that an arbitrary row can be rejected at most n − 1 times, hence in the worst case we can have at most n(n − 1) + 1 phases. Thus the construction just described is finite.

The final selection of the n numbers has the desired property. Indeed, if a_{ii} is the number selected in row i and a_{ik} is such that a_{ik} < a_{ii}, then in our construction we must have a phase in which the selected number in row was a_{ik}. However, this number was rejected during the construction by choosing at least another number in column k bigger than a_{ik}. Hence the final selected number in column k is bigger than a_{ik}.

5. From the recurrence relation we have

P_{n+1}(x) = P_{n}(x)\frac{P_{n}^{2}(x) + P_{n−1}^{2}(x)}{1 + P_{n}(x)P_{n−1}(x)} − P_{n−1}(x),

i.e.

(1)  \frac{P_{n+1}(x) + P_{n−1}(x)}{P_{n}(x)} = \frac{P_{n}^{2}(x) + P_{n−1}^{2}(x)}{1 + P_{n}(x)P_{n−1}(x)}.

On the other hand

\frac{P_{n}^{2}(x) + P_{n−1}^{2}(x)}{1 + P_{n}(x)P_{n−1}(x)} = \frac{(\frac{P_{n−1}^{3}(x)−P_{n−2}(x)}{1+P_{n−1}(x)P_{n−2}(x)})^{2} + P_{n−1}^{2}(x)}{1 + \frac{P_{n−1}^{3}(x)−P_{n−2}(x)}{1+P_{n−1}(x)P_{n−2}(x)}P_{n−1}(x)} =

= \frac{(P_{n−1}^{3}(x) − P_{n−2}(x))^{2} + P_{n−1}^{2}(x)(1 + P_{n−1}(x)P_{n−2}(x))^{2}}{(1 + P_{n−1}(x)P_{n−2}(x))^{2} + (P_{n−1}^{3}(x) − P_{n−2}(x))P_{n−1}(x)(1 + P_{n−1}(x)P_{n−2}(x))}

= \frac{(1 + P_{n−1}^{4}(x))(P_{n−1}^{2}(x) + P_{n−2}^{2}(x))}{(1 + P_{n−1}^{4}(x))(1 + P_{n−1}(x)P_{n−2}(x))}

= \frac{P_{n−1}^{2}(x) + P_{n−2}^{2}(x)}{1 + P_{n−1}(x)P_{n−2}(x)}.

Thus we have

\frac{P_{n}^{2}(x) + P_{n−1}^{2}(x)}{1 + P_{n}(x)P_{n−1}(x)} = ⋯ = \frac{P_{2}^{2}(x) + P_{1}^{2}(x)}{1 + P_{2}(x)P_{1}(x)} =

= \frac{x^{6} + x^{2}}{1 + x^{4}} = x^{2}.

Finally from (1) we get

P_{n+1}(x) + P_{n−1}(x) = x^{2}P_{n}(x),

and our assertion follows by an easy induction.

REMARK This problem is related to the problem no. 6 from the 1988 IMO held in Australia.

6. From the first equation we deduce

8 = 2^{x^{2}+y} + 2^{x+y^{2}} ≥ 2\sqrt{2^{x^{2}+y} · 2^{x+y^{2}}},

or equivalently

4 ≥ x^{2} + x + y + y^{2}.

Since (x + y)^{2} ≤ 2(x^{2} + y^{2}), we get further

(x + y)^{2} + 2(x + y) − 8 ≤ 0.

From this relation we deduce that

x + y ≤ −1 + \sqrt{9} = 2.

On the other hand from x, y ≥ 0 and from

(\sqrt{x} + \sqrt{y})^{2} ≤ 2(x + y)

it follows, using the second equation, that

x + y ≥ 2

and therefore x + y = 2. Now after squaring the second equation and using x + y = 2 we deduce that \sqrt{xy} = 1, i.e. xy = 1. This together with x + y = 2 implies x = y = 1.

7. We shall prove that a_{n} > a_{n+1} inductively. For n = 1 the statement is trivial.

Assume that for a given n we have a_{n−1} > a_{n}, and let us prove that a_{n} > a_{n+1}. Since

a_{n} = \frac{a_{n−1}(n − 1)^{k+1} + n^{k}}{n^{k+1}} > \frac{a_{n}(n − 1)^{k+1} + n^{k}}{n^{k+1}} ,

we have

(∗)  a_{n}(n^{k+1} − (n − 1)^{k+1}) > n^{k}.

Since

a_{n+1} = \frac{a_{n}n^{k+1} + (n + 1)^{k}}{(n + 1)^{k+1}} ,

we must show that

((n + 1)^{k+1} − n^{k+1})a_{n} > (n + 1)^{k}.

From (∗) we conclude it is sufficient to prove

\frac{n^{k}}{n^{k+1} − (n − 1)^{k+1}} ≥ \frac{(n + 1)^{k}}{(n + 1)^{k+1} − n^{k+1}} .

This may be written equivalently as

\frac{n^{k+1} − (n − 1)^{k+1}}{n^{k}} ≤ \frac{(n + 1)^{k+1} − n^{k+1}}{(n + 1)^{k}} ,

or as

n(1 − (\frac{n − 1}{n})^{k+1}) ≤ (n + 1)(1 − (\frac{n}{n + 1})^{k+1}),

or as

n((\frac{n}{n + 1})^{k+1} − (\frac{n − 1}{n})^{k+1}) ≤ 1 − (\frac{n}{n + 1})^{k+1},

or as

n^{2k+2} − (n^{2} − 1)^{k+1} ≤ n^{k}((n + 1)^{k+1} − n^{k+1}),

or as

(k + 1)n^{2k} − \binom{k + 1}{2}n^{2k−2} + ⋯ ≤ n^{k}((k + 1)n^{k} + \binom{k + 1}{2}n^{k−1} + …),

which is obviously true.

8. By setting x = 0 and then y = 0 in the relation, we get

(1)  f(f(y)) = y + f(0), f(x + f(0)) = f(x).

Now

f(x) = f(x + f(0)) = f(f(f(x))) = f(x) + f(0),

and hence f(0) = 0. Thus from (1) we have f(f(y)) = y. Now

f(x + y) = f(x + f(f(y))) = f(x) + f(y)

and the continuity of f implies that f(x) = ax for some a ∈ R. From the relation in the problem we get

a(x + ay) = ax + y

Figure 9

for all x, y ∈ R, i.e. a = ±1. Therefore

f(x) = x or f(x) = −x.

9. Let us denote by M the point where the line EF meets the line AB. Remark that by construction M belogns to the segment AB. We shall show that M is a fixed point, namely

(1)  \frac{MB}{MA} = \frac{BN}{AB} .

where N is the point where the line CE meets the line AB.

Using Menelaus theorem in the triangle ABD, applied for the transversal EF, we get

\frac{MB}{MA} · \frac{F A}{F D} · \frac{ED}{EB} = 1,

ie.

(2)  \frac{MB}{MA} = \frac{F D}{F A} · \frac{EB}{ED} .

Since CD is parallel to AB, then we have that

△AF B ∼ △DF C, △ECD ∼ △ENB,

and therefore

\frac{F D}{F A} = \frac{CD}{AB} , \frac{EB}{ED} = \frac{BN}{CD} .

Substituting this relations in (2) we get (1).

10. Let E be a point on the line BC such that AE = AB and denote by AH the altitude in the isosceles triangle BEA. We consider the case when E is between B and C (if B is between E and C or AH⊥BC, the reasoning is similar). Since

AC^{2} − CH^{2} = AB^{2} − BH^{2},

Figure 10

we have

AC^{2} − AB^{2} = CH^{2} − BH^{2} =
= (CH − BH)(CH + BH) = (CH − EH)BC =
= CE · BC.

Now the equality BC = 2AC − 2AB implies

(1)  2AB + \frac{1}{2}BC = 2CE.

a) If ^{}A̸BD = 2^{}A̸DB, then ^{}A̸EB = 2^{}A̸DE and the triangle ADE is isosceles, so that AB = AE = DE. Hence (1) shows that 2DE + \frac{1}{2}BC = 2CE, which is equivalent to BD = 3CD.

b) Conversly, from BD = 3CD it follows that 2DE+ \frac{1}{2}BC = 2CE, and (1) implies AB = DE. Since AB = AE, we have AE = DE. Hence ^{}A̸BD = 2^{}A̸DB.

11. a) Assume the inequality in the problem holds. If A = B, then P A ≥ P C for each P and so A = C.

Let A ≠ B. First we shall prove that C lies on the line AB. Suppose by contradiction that C ∉ AB and let P be a point from the perpendicular bisector of the line–segment AB such that P and C are from different sides of the perpendicular bisector of AC. Then P A = P B, P A < P C, so that

P A^{1989} + P B^{1989} = 2P A^{1989} < 2P C^{1989},

which is a contradiction. Therefore C lies on the line AB.

Denote by O the midpoint of the line–segment AB. Without loss of generality we may assume that O is between B and C. Consider a point P ∈ AB on the right of B and let P O = x, OC = c, AO = BO = a. Then by the inequality in the problem it follows that

f(x) = (x − a)^{1989} + (x + a)^{1989} − 2(x + c)^{1989} ≥ 0

for all x ≥ 0. It is easy to see that f(x) is a polynomial whose free term is equal to −2c^{1989}. Since c ≥ 0 and f(x) ≥ 0 for all x ≥ 0, it follows that c = 0, i.e. C is the midpoint of AB.

b) Conversly, let C be the midpoint of AB. Then

\frac{P A + P B}{2} ≥ P C

for every point P, and from the well known inequality

\frac{x^{n} + y^{n}}{2} ≥ (\frac{x + y}{2} )^{n}, ∀x, y ≥ 0

we obtain

\frac{P A^{1989} + P B^{1989}}{2} ≥ (\frac{P A + P B}{2} )^{1989} ≥ P C^{1989},

which was to be proved.

The assertion remains true if 1989 is replaced by an arbitrary natural number n.

12. Let X be an arbitrary point in ABCD. Denote by M, N, P, Q the orthogonal projections of X on the faces BCD, CAD, ABD, ABC respectively, and let

XM = x, XN = y, XP = z, XQ = t.

Since XM, XN and XP are pairwise perpendicular, we have

V_{MNP X} = \frac{1}{6}xyz.

Figure 12

It can be easily verified that

V_{P QMX} = \frac{1}{6}xzt sin α,

where α is the angle between the line XQ and its orthogonal projection on the plane (XP M). Since the planes (XP M) and (ACD) are parallel, α is the angle between the altitude of the pyramid from the vertex D and one of the side faces. We may assume that AD = BD = CD = 1. Then AB = BC = CA = \sqrt{2} and sin α = \sqrt{3}/3. So

V_{P QMX} = \frac{1}{6} \frac{\sqrt{3}}{3}xzt, V_{QMNX} = \frac{1}{6} \frac{\sqrt{3}}{3}xyt,

etc. Therefore

V (X) = V_{MNP Q} = \frac{1}{6}(xyz + \frac{\sqrt{3}}{3}t(xy + yz + zx)).

Let x′, y′, z′ be distances from Q to the faces BCD, CAD and ABD of the pyramid. Then

x′ = x + t sin α = x + \frac{t}{\sqrt{3}},
y′ = y + \frac{t}{\sqrt{3}},
z′ = z + \frac{t}{\sqrt{3}}.

Now we obtain

V (Q) = \frac{1}{6}(x + \frac{t}{\sqrt{3}})(y + \frac{t}{\sqrt{3}})(z + \frac{t}{\sqrt{3}})

≥ \frac{1}{6}(xyz + \frac{\sqrt{3}}{3}t(xy + yz + zx)) = V (X),

and equality occurs only for t = 0, i.e. for X = Q. Hence we may consider that X lies in the triangle ABC. In this case t = 0 and

\frac{1}{6} = V_{ABCD} = \frac{1}{6}(x + y + z),

i.e.

x + y + z = 1.

Since V (X) = \frac{1}{6}xyz, we obtain by the arithmetic mean–geomteric mean inequality that V (X) is maximal if x = y = z = \frac{1}{3}, i.e. when X is the barycenter of the triangle ABC.

13. Let A_{1}, A_{2},…, A_{n} be vertices of the n–gon, α_{i} the angle at the vertix A_{i},

a_{1} = |A_{1}A_{2}|, a_{2} = |A_{2}A_{3}|,…, a_{n} = |A_{n}A_{1}|,

and S_{i} the area of the triangle A_{i−1}A_{i}A_{i+1}, i = 1, 2,… n (A_{0} = A_{n}, A_{n+1} = A_{1}). Then we have

2S_{i} = a_{i−1}a_{i} sin α_{i}.
Let S = min(S_{1}, S_{2},…, S_{n}). We have
2S ≤ a_{i−1}a_{i} sin α_{i} (i = 1, 2,…, n)

and

(2S)^{n} ≤ ∏_{i=1}^{n} a_{i}^{2} ∏_{i=1}^{n} sin a_{i} ≤ ∏_{i=1}^{n} a_{i}^{2}.

Figure 13

Using the inequality

(∏_{i=1}^{n} a_{i})^{\frac{1}{n}} ≤ \frac{∑_{i=1}^{n} a_{i}}{n} ,

we obtain

2S ≤ (\frac{∑_{i=1}^{n} a_{i}}{n} )^{2}.

If p_{i} and q_{i} are lengths of the projections of a_{i} over the sides of the square, then

a_{i} ≤ p_{i} + q_{i}

i.e.

∑_{i=1}^{n} a_{i} ≤ ∑_{i=1}^{n} p_{i} + ∑_{i=1}^{n} q_{i} ≤ 4.

Therefore

S ≤ \frac{8}{n^{2}} .

Alternate solution. Denote by p′_{i} and q′_{i} the corresponding lengths of projections of A_{i−1}A_{i+1}. Retaining the notation from the preceding solution, we have as a direct consequence of the convexity of n–gon the following inequality:

∑_{i=1}^{n} p′_{i} ≤ ∑_{i=1}^{n}(p_{i−1} + p_{i}) = 2 ∑_{i=1}^{n} p_{i} ≤ 4,

and analogously ∑_{i=1}^{n} q′_{i} ≤ 4. Then from

(p′_{1} + q′_{1}) + (p′_{2} + q′_{2}) + ⋯ + (p′_{n} + q′_{n}) ≤ 8,

using the Dirichlet principle we see that there is i such that p′_{i} + q′_{i} ≤ 8/n. So, for the area of the corresponding triangle we have

S_{i} ≤ \frac{1}{2}p′_{i}q′_{i} ≤ \frac{1}{2}p′_{i}(\frac{8}{n} − p′_{i}) ≤ \frac{8}{n^{2}} .

14. Let n_{1} = n^{n^{n^{n}}} − n^{n^{n}} and n_{2} = n^{n^{n}} − n^{n}. Then
n_{1} = n^{n^{n}}(n^{n_{2}} − 1).

We shall show that

(1)  3 · 2^{4} | n_{2}.

Observe that n_{2} = n^{n}(n^{n^{n}−n} − 1) and n^{n} − n is even, thus φ(3) | n^{n} − n, hence

(2)  3 | n_{2}.

If n is even, then n^{n} | n_{2}, thus

(3’)  2^{n} | n_{2}.

and 2^{4}|n_{2}, because n ≥ 3. If n is odd, n = 2k + 1, then

n^{n} − n = (2k + 1)((2k + 1)^{2k} − 1) =
= (2k + 1)((4k(k + 1) + 1)^{k} − 1) =
= (2k + 1)((8l + 1)^{k} − 1) = 8p.

Thus 8 | n^{n} − n. Since φ(2^{4}) | n^{n} − n, we have

(3”)  2^{4} | n^{n^{2}−n} − 1.

From (2), (3’) and (3”) we have (1).

From (1) we obtain φ(3^{2}) = 6 | n_{2}, thus

(4)  3^{2} | n^{2}(n^{n_{2}} − 1).

Similarly φ(13) | n_{2} and φ(17) | n_{2}, so that

(5)  13 | n(n^{n_{2}} − 1)
(6)  17 | n(n^{n_{2}} − 1).

From (4), (5) and (6) we conclude that 1989 = 3^{2} · 13 · 17 | n_{1}.

15. Note that if a_{k} ≡ 0 (mod 11), then

a_{k+1} ≡ 0^{2} − 0 + 5 ≡ 5 (mod 11),
a_{k+2} ≡ 5^{2} − 5 + 5 ≡ 3 (mod 11),
a_{k+3} ≡ 3^{2} − 3 + 5 ≡ 0 (mod 11).

Therefore it suffices to prove that at least one of the numbers

a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}

is divisible by 11. We can check directly that:

if a_{0} ≡ 1, 2, 10 (mod 11) then a_{3}≡ 0 (mod 11),
if a_{0} ≡ 3, 9  (mod 11) then a_{1}≡ 0 (mod 11),
if a_{0} ≡ 4, 8  (mod 11) then a_{5}≡ 0 (mod 11),
if a_{0} ≡ 5, 7  (mod 11) then a_{2}≡ 0 (mod 11),
if a_{0} ≡ 6  (mod 11) then a_{4}≡ 0 (mod 11).

This completes the solution.

16. Let x_{i} = (a_{i}, S_{i}) and y_{i} = [a_{i}, S_{i}]. Then x_{i}y_{i} = a_{i}S_{i} (i = 3, 4,…, 1989) and the given relation can be written in the form

a_{i} + S_{i} = x_{i} + \frac{a_{i}S_{i}}{x_{i}} ,

i.e. x_{i}^{2} − (a_{i} + S_{i})x_{i} + a_{i}S_{i} = 0. So if a_{i} | S_{i}, then x_{i} = a_{i} and the equation holds true.

Thus we may take a_{1} = 1, a_{2} = 2 and a_{i} = 2^{i−3} · 3, i ≥ 3, whereupon we have S_{i} = 3 · 2^{i−2}, i = 3, 4,…, 1989.

17. Let x ≤ y ≤ z, n be one solution. It is obvious that z − x ≥ y − x ≥ 0 and z + x > y > 0. Hence (z − x)(z + x) ≥ y(y − x), i.e.

z^{2} ≥ x^{2} + y^{2} − xy = \frac{x^{3} + y^{3}}{x + y} ,

or

x + y ≥ \frac{x^{3} + y^{3}}{z^{2}} .

Then it is easy to see that

z = nx^{2}y^{2} − \frac{x^{3} + y^{3}}{z^{2}} ≥ nx^{2}y^{2} − (x + y) > 0,

except for x = y = 1, n = 1, 2 (in this case there is no solution to the problem). But z^{2} | x^{3} + y^{3}, and from the previous inequality we obtain

x^{3} + y^{3} ≥ z^{2} ≥ (nx^{2}y^{2} − (x + y))^{2}.

Therefore

n^{2}x^{4}y^{4} ≤ x^{3} + y^{3} + 2nx^{2}y^{2}(x + y) − (x + y)^{2}

i.e.

n^{2}x^{4}y^{4} < 2nx^{2}y^{2}(x + y) + x^{3} + y^{3}

or

nxy < 2(\frac{1}{x} + \frac{1}{y} ) + \frac{1}{nx^{3}} + \frac{1}{ny^{3}} .

If x ≥ 2, then y ≥ x ≥ 2 and nxy ≥ 4. But

2(\frac{1}{x} + \frac{1}{y} ) + \frac{1}{nx^{3}} + \frac{1}{ny^{3}} ≤ 2(\frac{1}{2} + \frac{1}{2}) + \frac{1}{8} + \frac{1}{8} < 3,

which is a contradiction. Hence x = 1 and we have

ny < 2 + \frac{2}{y} + \frac{1}{n} + \frac{1}{ny^{3}} .

If y ≥ 4, then ny ≥ 4 and

2 + \frac{2}{y} + \frac{1}{n} + \frac{1}{ny^{3}} < 2 + \frac{2}{4} + 1 + \frac{1}{4} < 4,

which is impossible. Therefore y ≤ 3. Since z^{2} | x^{3} + y^{3}, i.e. z^{2} | 1 + y^{3} and z ≥ y, we have several possibilities

(i) if y = 1, then 1 + y^{3} = 2 and z = 1; (ii) if y = 2, then 1 + y^{3} = 9 and z = 3; (iii) if y = 3, then 1 + y^{3} = 28 and z does not exist.

If x = y = z = 1, then n = 3. If x = 1, y = 2, z = 3, then n = 1.

So all solutions of the problem are

(1, 1, 1, 3) (1, 2, 3, 1) (2, 1, 3, 1) (1, 3, 2, 1)
(3, 1, 2, 1) (3, 2, 1, 1) (2, 3, 1, 1).

18. Let z be a common root of x^{5} − px − 1 and x^{2} − ax + b. If z is rational, since z^{5} − pz − 1 = 0, then z = ±1. Hence p = 0 or p = 2. It is easy to be seen that p = 0 or p = 2 satisfy the condition of the problem.

Suppose z is not rational. Then from

pz + 1 = z^{5} = z(az − b)^{2} = z(a^{2}z^{2} − 2abz + b^{2}) =

= z(a^{2}(az − b) − 2abz + b^{2}) = (a^{3} − 2ab)z^{2} + (b^{2} − a^{2}b)z =

= (a^{3} − 2ab)(az − b) + (b^{2} − a^{2}b)z =
= (a^{4} − 3a^{2}b + b^{2})z + 2ab^{2} − a^{3}b.

we conclude

a^{4} − 3a^{2}b + b^{2} = p
2ab^{2} − a^{3}b = 1.

We multiply the first equation by −2a and add to the second. Then

b = \frac{2a^{5} − 2ap + 1}{5a^{3}},

and substituting this in the second equation, after some computation we get

a^{10} + 3pa^{6} + 11a^{5} − 4p^{2}a^{2} + 4pa − 1 = 0.

Since a is rational and p is an integer, we have a = ±1.

Let a = 1. Then −4p^{2} + 7p + 11 = 0 and p is not an integer.

Let a = −1. Then −4p^{2} − p − 11 = 0, and p is not an integer either. So p = 0 and p = 2 are the only solutions.