Mathlinks Contest

MathLinks Contest
First Round 24.02.2003 - 10.03.2003
1. In a country there are n major cities, n ≥ 4, connected by railroads, such that each city
is directly connected to each other city. Each railroad company in that country has but
only one train, which connects a series of cities, at least two, such that the train doesn’t
pass through the same city twice in one shift. The companies divided the market such that
any two cities are directly1 connected only by one company. Prove that among any n+1
companies, there are two which have no common train station or there are two cities that
are connected by two trains belonging to two of these n+1 companies.
2. Prove that for all positive integers a, b, c the following inequality holds:
a+b b+c c+a a b c
+ + ≤ + +
a+c b+a c+b b c a
3. Let x0 = 1 and x1 = 2003 and define the sequence (xn )n≥0 by:
x2n + 1
xn+1 = ∀n≥1
xn−1
Prove that for every n ≥ 2 the denominator of the fraction xn , when xn is expressed in
lowest terms is a power of 2003.
Good Luck in solving these problems!
TeX (c) 2003 Valentin Vornicu
1
directly connected means that they are connected by a railroad, without no other station between them
MathLinks Contest
First Round 24.02.2003 - 10.03.2003
Solutions
1. In a country there are n major cities, n ≥ 4, connected by railroads, such that each city is
directly connected to each other city. Each railroad company in that country has but only one train,
which connects a series of cities, at least two, such that the train doesn’t pass through the same
city twice in one shift. The companies divided the market such that any two cities are directly1
connected only by one company. Prove that among any n+1 companies, there are two which have
no common train station or there are two cities that are connected by two trains belonging to two
of these n + 1 companies.
Solution 1 (Andrei Stefanescu). The problem can be reformulated like this: in a partition
of a complet graph with n vertices with more than n + 1 chains there are two chains that have no
common vertex or two chains that have at least two common edges.
Suppose that any 2 chains from the n + 1 chosen have exactly one common vertex. Observe
that we have n(n + 1)/2 intersections of chains and n vertices, thus there are more than [(n + 1)/2]
chains passing through one vertex (1)(more than implies that there are at least [(n + 1)/2] + 1 =
[(n − 1)/2] + 2.)
For any chain of length > 1, (composed of more than 1 edge), and 3 vertices of the chain i, j, k,
the edges ij, jk and ik don’t belong to other chains. But for every vertex there are n − 1 adiacent
edges. Thus there are at most [(n − 1)/2] chains of length > 1 that pass thorough that vertex, thus
from (1) there are at least two chains of length 1 that pass through that vertex.
Let i be that vertex and ij, ik the chains of length 1 that pass through i. Now any chain that
will pass through j will pass through k (it cannot intersect ik in i), thus through j there cannot be
more than one chain passing.
Any 2 chains that pass through i do not intersect, and through i there can be at most n − 3
other chains different from ij and ik. Now because any chain has to intersect the chain ij (any
chain must pass through i or j) and through j there is only one chain passing besides ij we have
that n + 1 ≤ (n − 3) + 2 + 1 = n contradiction.
Solution 2 (Andrei Negut). Suppose that as above any two companies have exactly a
common station. We construct a matrix A with n+1 lines and n columns such that at the intersection
of the line i and the column j lies 1 if the station j is on the line of the company i and 0 if otherwise.
Observe that two different lines have just one single 1 in common (by common we understand being
on the same column). Below is an example of two such lines in this matrix:
1 0 0 0 1 1 1 0
0 0 1 1 1 0 0 0
In the example on the 5th column lies the ”common 1” of these two lines. Observe that the line can
have more ”common 0-s”. Also observe that each line has at least two of 1-s, because each company
connects at least two cities. Now comes the nice and ingenious part of Andrei’s solution:
Compute A · At . The result will be a n + 1 times n + 1 matrix. Let’s see how does this product’s
entries look like: the element found on the line i and column i will be the result of the sum of
products between the elements of the line i in A and the column i in At which is exactly the same
line i in A, thus the product will represent the number of 1-s in the line i. All the other elements
of A · At will be the sum of the products of the elements of 2 different lines of A, thus it will be 1,
because any two lines have one single 1 in common. Thus the product will look like this:
 
a1 1 1 ... 1
 1 a2 1 ... ... 
A · At = 
 
 1 1 a3 ... ... 
 ... ... ... ... 1 
1 ... ... 1 an+1
where ai represents the number of 1-s in each line, thus ai ≥ 2.

1 directly connected means that they are connected by a railroad, without no other station between them
1
We want to prove that:

a1 1 1 ... 1

1 a2 1 ... ...

1 1 a3 ... ... >0

... ... ... ... 1

1 ... ... 1 an+1
by induction after n, for any ai ≥ 2. For n = 2 the result is obvious. Suppose that we have the
result true for some n, and let’s prove it for n + 1. We have:

a1 1 1 ...
1 a1 − 1 1 1 ... 1
a2 1 1 ... 1

1 a2 1 ...
... 1 − a2 a2 1 ... ...
1 a3 1 ... ...

1 1 a3 ...
... = 0 1 a3 ... ... = (a1 − 1) 1 1 a4 ... ... +

... ... ... ... 1 0 ... ... ... 1 ... ... ... ... 1

1 ... ... 1 an+1 0 ... ... 1 an+1 1 ... ... 1 an+1

1 1 1 ... 1

1 a3 1 ... ...

+(a2 − 1) 1 1 a4 ... ... .

... ... ... ... 1

1 ... ... 1 an+1
By induction the first determinant is positive, thus all we must prove in order to complete our lemma
is that the second determinant is also positive. Let’s compute some more:

1 1 1 ... 1 0 1 1 ... 1

1 a3 1 ... ... 1 − a3 a3 1 ... ...

(a2 − 1) 1 1 a4 ... ... = (a2 − 1) 0 1 a4 ... ... =
... ... ... ... 1 ... ... ... ... 1

1 ... ... 1 an+1 0 ... ... 1 an+1

1 1 1 ... 1

1 a4 1 ... ...
= . . . = (a2 − 1)(a3 − 1) · · · (an − 1) 1 1

= (a2 − 1)(a3 − 1) 1 1 a5 ... ... 1 an+1
>0

... ... ... ... 1

1 ... ... 1 an+1
Thus the determinant of A · At is positive, thus non-zero. In this way we have proved that the
rang of A · At is n + 1. But it is well-known that rang(AB) ≤rang(A), thus rang(AAt ) ≤rang(A),
therefore rang(A) ≥ n + 1, which is impossible because A has only n columns, and we are done.
Comment: This is an incredible solution, which proves that combinatorics can be found in all
the parts of mathematics, and also shows Andrei’s good command of superior algebra.
Solution 3 (Claudiu Raicu and Valentin Vornicu). This is my original solution, found
by Claudiu in the contest. From now on |M | will symbolize the number of elements of the set M .
Suppose like everyone else has that the conclusion in the problem is false. Then there are n + 1
companies such that any two have exactly a common station on their lines. Let’s denote by X the
set of the cities and for i = 1, ..., n + 1 we denote by Ai the set of cities in which the company i has
stations. From the supposition we have that |Ai ∩ Aj | = 1. Also we have that |Ai | ≥ 2, since any
company connects at least two cities. For any x ∈ X we denote with d(x) the number of sets Ai in
which x appears (if we consider the graph, this would be the degree of the vertex x relative to the
n + 1 chains we have chosen).
Suppose that there is x ∈ X such that d(x) = n + 1, thus for all i-s the sets Ai − {x} are
non-intersecting distinct subsets. But |X| = n, thus the last affirmation is false, therefore we might
say that there is an i between 1 and n + 1 such that x 6∈ Ai .
Also if there is an i such that Ai = X, then take a j 6= i and because |Ai ∩ Aj | = 1 it follows
that |Aj | = 1, which is obviously false.
Take now a pair of the form (x, Ai ) such that x 6∈ Ai . Existence of such a pair has been proven
above. If d(x) ≤ 2 then obviously |Ai | ≥ d(x), otherwise if d(x) ≥ 3 for any two sets Aj and Ak
which contain x we have Ai ∩ Aj 6= Ai ∩ Ak (we cannot have {α = Ai ∩ Aj = Ai ∩ Ak because that
would mean that {x, α} ⊂ Aj ∩ Ak false) thus |Ai | ≥ d(x).
2
The latter takes us to n + 1 − d(x) > n − |Ai | > 0 which takes us to:
n n
|Ai | d(x) X |Ai | X d(x)
> ⇒ > (1)
n − |Ai | n + 1 − d(x) n − |Ai | n + 1 − d(x)
i=1, x6∈Ai i=1, x6∈Ai
But for each Ai there are n − |Ai | elements x 6∈ Ai thus:

n n+1 n+1
X |Ai | X |Ai | X
= (n − |Ai |) = |Ai | (2)
n − |Ai | n − |Ai |
i=1, x6∈Ai i=1 i=1
Also we have that for all x ∈ X there are n + 1 − d(x) sets Ai for which x 6∈ Ai , therefore:
n
X d(x) X d(x) X
= (n + 1 − d(x)) = d(x) (3)
n + 1 − d(x) n + 1 − d(x)
i=1, x6∈Ai x∈X x∈X
Finally we observe that

n+1
X X
|Ai | = d(x) (4)
i=1 x∈X
Out of (1), (2), (3) and (4) we obtain a serious contradiction, which is exactly what we wanted.
2. Prove that for all positive integers a, b, c the following inequality holds:
a+b b+c c+a a b c
+ + ≤ + +
a+c b+a c+b b c a
Comment: Due to a typing error, the inequality had to be proved only for positive integers. It
seemed that this hasn’t eased up the problem. The following solutions work for positive reals too.
Solution 1 (Siutz). The inequality is equivalent with:
b c a
1+ a 1+ b 1+ c a b c
⇔ c + a + b
≤ + +
1+ a 1+ b 1+ c
b c a
b a b c c b c a a
⇔ 1+ 1+ 1+ + 1+ 1+ 1+ + 1+ 1+ 1+
a b c a b c a b c
c a b a b c
≤ 1+ 1+ 1+ + +
a b c b c a
b a b c c b c a a
⇔ 1+ 1+ 1+ + 1+ 1+ 1+ + 1+ 1+ 1+
a b c a b c a b c
c a ba c a bb c a b c
≤ 1+ 1+ 1+ + 1+ 1+ 1+ + 1+ 1+ 1+
a b c b a b c c a b c a
b a b c c b c a a
⇔ 1+ 1+ 1+ + 1+ 1+ 1+ + 1+ 1+ 1+
a b c a b c a b c
c a a a b b a b c c c b
≤ 1+ 1+ + + + 1+ 1+ + 1+ + 1+
a b b c c a b c a a b c
b a b c c b a c a
⇔ 1− 1+ 1+ + 1− 1+ 1+ + 1− 1+ 1+ ≤0
c b c a a c b a b
3
b2 a c2 b a2 c
⇔ 1− 2 1+ + 1− 2 1+ + 1− 2 1+ ≤0
c b a c b a
b2 a ab c2 b bc a2 c ca
⇔1− + − + 1 − + − + 1 − + − 2 ≤0
c2 b c2 a2 c a2 b2 a b
b2 c2 a2 ab bc ca a b c
⇔ 2
+ 2
+ 2
+ 2 + 2 + 2 ≥3+ + +
c a b c a b b c a
By Cauchy Schwarz and AM-GM Inequality,

r
b2 c2 a2 1 a b c 2 1 a b c 3 abc a b c
2
+ 2 + 2 ≥ ( + + ) ≥ ( + + )3 = + +
c a b 3 b c a 3 b c a bca b c a
By AM-GM Inequality, r
ab bc ca 3 ab bc ca
2
+ 2 + 2 ≥3 =3
c a b c2 a2 b2
Comment: This solution doesn’t have any cases and doesn’t use any inequalities between a,b,c.
Although long it is very easy to follow and understand. Good job Siutz!
Solution 2 (Andrei Negut). Let S be the sum of a, b, c. Then our inequality is equivalent
with:
Xa X b+c Xa XS−a X a S−a X S(a − b)
≥ ⇔ ≥ ⇔ ( − )≥0⇔ ≥0⇔
b c+a b S−b b S−b b(S − b)
X a X b X a X a
− ≥0⇔ − ≥0⇔
b(S − b) b(S − b) b(S − b) a(S − a)
X a X a(a − b)(S − a − b)
(aS − a2 − bS − b2 ) ≥ 0 ⇔ ≥0⇔
ab(S − a)(S − b) ab(S − a)(S − b)
X a(a − b)cc(S − c) X X
≥0⇔ a2 c2 S + abc3 ≥ abc2 S + a2 c3 ⇔
abc(S − a)(S − b)(S − c)
X X X X X
a2 c2 (S − c) + abc3 ≥ abcS a⇔ a2 c2 (a + b) + abc3 ≥ abcS 2 ⇔
X X X
a3 c2 + a2 c2 b + abc3 ≥ abc(a + b + c)2 ⇔
X
a3 c2 ≥ abc[(a + b + c)2 − a2 − b2 − c2 − ab − bc − ca] = abc(ab + bc + ca) ⇔
a3 c2 + b3 a2 + c3 b2 ≥ a2 b2 c + b2 c2 a + a2 c2 b (1)
At this point the Andrei solved (1) using rearrangement inequality: suppose that a ≥ b ≥ c because
the inequality is cyclic, then we have that a2 b2 ≥ c2 a2 ≥ b2 c2 which leads us to:
aa2 c2 + bb2 a2 + cc2 b2 ≥ a2 b2 c + b2 c2 a + a2 c2 b
4
The same follows if a ≤ b ≤ c. All the other cases are obtained from these ones by cyclic permuta-
tions.
I thought of a different approach of (1) multiply both sides by 5, and then apply the generalized
AM-GM. I leave this as an exercise.
Comment: My initial solution was more straight-forward, I just multiplied the inequality with
the product of all the denominators, and got a polynomial expression, which lead me finally to (1)(af-
ter some boring computations of course).
3. Let x0 = 1 and x1 = 2003 and define the sequence (xn )n≥0 by:
x2n + 1
xn+1 = ∀n≥1
xn−1
Prove that for every n ≥ 2 the denominator of the fraction xn , when xn is expressed in lowest
terms is a power of 2003.
Solution 1 (Valentin Vornicu and Siutz). Let p = 2003. Firstly, claim
p2 + 2
an+1 = an − an−1
p
for positive integer n ≥ 1.
When n = 1,
a21 + 1 p2 + 2
a2 = = p2 + 1 = a1 − a0
a0 p
Assume
p2 + 2
ak+1 = ak − ak−1
p
for some positive integer k ≥ 1.
When n = k + 2,
2
p2 +2
a2k+1 + 1 ak+1 ( p p+2 ak − ak−1 ) + 1 p ak+1 ak − ak+1 ak−1 + 1
ak+2 = = =
ak ak ak

p2 +2 p2 +2
− a2k −1+1 ak p ak+1 − ak
p ak+1 ak p2 + 2
= = = ak+1 − ak
ak ak p
By induction,
p2 + 2
an+1 = an − an−1
p
for positive integer n ≥ 1.
Obviously, if the denominators of an , an−1 are powers of p, the denominator of an+1 is also a power
of p. By induction, it is easy to show the denominator of an is a power of 2003 for n ≥ 2.
Solution 2 (Andrei Stefanescu and Claudiu Raicu). We have x0 = 1, x1 = 2003,

x2 = 20032 + 1, etc.
Let’s denote p2 = 20032 + 1, q2 = 1, p3 = p22 + 1, q3 = 2003 and for n ≥ 3 consider:
p2n + qn2 q2
pn+1 = , qn+1 = n
pn−1 qn−1
We have that x2 = p2 /q2 and x3 = p3 /q3 and moreover xn = pn /qn for all n ≥ 3. It follows easily
that qn = 2003n−2 for all n-s.
We shall prove by induction the following statement: Pn and qn are positive integers, pn−1 | p2n +
qn2 and gcd(pn , 2003) = 1.
5
For n = 3 the proof is obvious. Suppose the affirmation is true for n and let’s prove it for n + 1.
Because pn−1 | p2n + qn2 we have that pn+1 is a positive integer. Suppose that 2003 | pn+1 . Then it
follows that 2003 | p2n + qn2 ⇒ 2003 | pn false.
All we have to prove now is that: pn | p2n+1 + qn+1
2
which is the same with:
p4n + qn4 + 2p2n qn2 2

pn | + qn+1 ⇒ pn | p4n + qn4 + 2p2n qn2 + p2n−1 qn+1
2
p2n−1
because if gcd(pn , pn−1 ) = d > 1 then d | pn−1 | p2n + qn2 ⇒ d | qn2 absurd.
The latter is equivalent with:
2
qn4

qn+1
pn | qn4 (1 + p2n−1 ) ⇒ pn | (p2 2
+ qn−1 )
qn2 qn−1 n−1
2
which is true because of the fact that pn−2 pn = p2n−1 + qn−1

2
, and we are done.
Solution 3 (Andrei Negut). We shall prove the property for any given prime p, not just
bn
for 2003. Let an = pn−1 , where b1 =1 and b2 = p2 . It suffices to prove that the sequence (b)n has
only positive integers term, because after some simplifications of bn with p, the fraction will have
the denominator a power of p.
Let y and z be the solutions of the following second degree equation:
p2
x2 − x +
p4 + 4
which because
4p2 2
1≥ ⇔ p2 − 2 ≥ 0,
p4 +4
has real solutions, thus y, z are reals and also positive. Let y ≥ z.
We will prove by induction that:
p !n−1 p !n−1
p2 + 2 + p4 + 4 p2 + 2 − p 4 + 4
bn = y +z .
2 2
Obviously b1 = y + z = 1 and
p p
p2 + 2 p2 + 2 p4 + 4 p2 + 2 p4 + 4 p
b2 = y +z + (y − z) = + (y − z)2 =
2 2 2 2 2
p p s
p2 + 2 p4 + 4 p p 2
+ 2 p 4+4 4p2
= + (y + z)2 − 4yz = + 1− 4 =
2 2 2 2 p +4
p p
p2 + 2 p4 + 4 (p2 − 2)2
= + p = p2
2 2 p4 + 4
Now if bn−1 and bn have that formula, let’s prove that bn+1 has it too.
b2n
a2 + 1 bn+1 p2n−2 + 1 b2n + p2n−2
an+1 = n ⇒ n = bn−1
⇒ bn+1 = .
an−1 p bn−1
pn−2
We must prove that:

" p !n p !n #  p !n−2 p !n−2 
2 2 2 2
p +2+ p4 +4 4
p +2− p +4 p + 2 + p4 + 4 p +2− p4 +4
y +z y +z =
2 2 2 2
6
 p !n−1 p !n−1 2
p2 + 2 + p 4 + 4 p 2 + 2 − p4 + 4  + p2n−2 ⇔
= y +z
2 2
√ 2n−2 √ 2n−2 √ n √ n−2

2 p2 +2+ p4 +4 2 p2 +2− p4 +4 p2 +2+ p4 +4 p2 +2− p4 +4
y 2 +z 2 + yz 2 2
√ n−2 √ n √ 2n−2 √ 2n−2
p2 +2+ p4 +4 p2 +2− p4 +4 p2 +2+ p4 +4 p2 +2− p4 +4
+yz 2 2 = y2 2 + z2 2 +
√ n−1 √ n−1
p2 +2+ p4 +4 p2 +2− p4 +4
+2yz 2 2 + p2n−2 ⇔
 √ 2 √ 2 
p2 +2+ p4 +4 p2 +2+− p4 +4
√ n−2 √ n−2 + − 
p2 +2+ p4 +4 p2 +2− p4 +4  2 2
yz  √ √  = p2n−2
2 2  p2 +2+ p4 +4 p2 +2− p4 +4 
2 2 2
√ √ 2
2n−4 p2 +2+ p4 +4 p2 +2− p4 +4
⇔ yzp 2 − 2 = p2n−2 ⇔ yz(p4 + 4) = p2 .
The last relationship is true from the way y and z were defined. Let’s denote by
p ! p !
p2 + 2 + p 4 + 4 p2 + 2 − p 4 + 4
α= and β =
2 2
Obviously α+β = p2 +2 and αβ = p2 . Thus α and β are the roots of the equation: x2 −x(p2 +2)+p2 =
0
⇒ α2 = α(p2 + 2) − p2 ⇒ yαn+1 = yαn (p2 + 2) − p2 yαn−1
⇒ β 2 = β(p2 + 2) − p2 ⇒ zβ n+1 = zβ n (p2 + 2) − p2 zβ n−1 .

Summing up we get:
bn+2 = bn+1 (p2 + 2) − bn p2 .
But b1 and b2 are integers, then by induction all bn -s are integers and we are done.
Comment: No comment.
7
MathLinks Contest
Second Round 10.03.2003 - 23.03.2003
1. Let A be a finite set of positive integers. Prove that there exists a finite set B of positive
integers such that A ⊂ B and Y X
x= x2 .
x∈B x∈B
2. In a triangle ∆ABC, ∠B = 2∠C. Let P and Q be points on the perpendicular bisector

of segment BC such that rays AP and AQ trisect ∠A. Prove that P Q is smaller than AB
if and only if ∠B is obtuse.
3. Prove that in any acute triangle with sides a, b, c circumscribed in a circle of radius R
the following inequality holds: √
2 Rp 1
< <
4 2aR + bc 2
where p represents the semi-perimeter of the triangle.

MathLinks Contest
Third Round 23.03.2003 - 06.04.2003
1. A pack of 2003 circus flees are deployed by their circus trainer, named Gogu, on a suf-
ficiently large table, in such a way that they are not all lying on the same line. He now
wants to get his Ph.D. in fleas training, so Gogu has thought the fleas the following trick:
we chooses two fleas and tells one of them to jump over the other one, such that any flea
jumps as far as twice the initial distance between him and the flea over which he is jumping.
The Ph.D. circus committee has but only one task to Gogu: he has to make the his flees
gather around on the table such that every flea represents a vertex of a convex polygon.
Can Gogu get his Ph.D., no matter of how the fleas were deployed?
2. Let a be a non-zero integer, and n ≥ 3 another integer. Prove that the following
polynomial is irreducible in the ring of integer polynomials (i.e. it cannot be written as a
product of two non-constant integer polynomials):
f (x) = xn + axn−1 + axn−2 + . . . + ax − 1
3. Let (Ai )i≥1 be sequence of sets of two integer numbers, such that no integer is contained
in more than one Ai and for every Ai the sum of its elements is i. Prove that there are
infinitely many values of k for which one of the elements of Ak is greater than 13k/7.

MathLinks Contest
Fourth Round 07.04.2003 - 20.04.2003
1. Given are 4004 distinct points, which lie in the interior of a convex polygon of area 1.
1
Prove that there exists a convex polygon of area , included in the given polygon, such
2003
that it does not contain any of the given points in its interior.
2. Let f be a polynomial with real coefficients such that for each positive integer n the
equation f (x) = n has at least one rational solution. Find f .
3. Find the triangle of the least area which can cover any triangle with sides not exceeding 1.

MathLinks Contest
Fifth Round 27.04.2003 - 04.05.2003
1. In a triangle ABC, ∠B = 70◦ , ∠C = 50◦ . A point M is taken on the side AB such

that ∠M CB = 40◦ , and a point N is taken on the side AC such that ∠N BC = 50◦ . Find
∠N M C.
2. Let m be the greatest number such that for any set of complex numbers having the sum
of all modulus of all the elements 1, there exists a subset having the modulus of the sum of
the elements in the subset greater than m. Prove that
1 1
≤m≤ .
4 2
(Optional Task for 3p) Find a smaller value for the RHS.
3. Prove that if the positive reals a, b, c have sum 1 then the following inequality holds
5 5 5
1
(ab) + (bc) + (ca) 4 < .
4 4
4

MathLinks Contest
Sixth Round 06.05.2003 - 18.05.2003
1. Let a, m be two positive integers, a 6= 10k , for all non-negative integers k and d1 , d2 , . . . , dm
random decimal 1 digits with d1 > 0. Prove that there exists some positive integer n for
which the representation in the decimal base of the number an begins with the digits
d1 , d2 , . . . , dm in this order.
2. Given is a triangle ABC and on its sides the triangles ABM , BCN and CAP are build
such that ∠AM B = 150◦ , AM = M B, ∠CAP = ∠CBN = 30◦ , ∠ACP = ∠BCN = 45◦ .
Prove that the triangle M N P is an equilateral triangle.
3. Consider (fn )n≥0 the Fibonacci sequence, defined by f0 = 0, f1 = 1, fn+1 = fn + fn−1

for all positive integers n. Solve the following equation in positive integers
nfn fn+1 = (fn+2 − 1)2 .
1
lesser or equal with 9
MathLinks Contest
Seventh Round 18.05.2003 - 1.06.2003
1. Prove that for every positive numbers x, y, z the following inequality holds:
p p p
4x2 + 4x(y + z) + (y − z)2 < 4y 2 + 4y(z + x) + (z − x)2 + 4z 2 + 4z(x + y) + (x − y)2 .
2. Consider the circles ω, ω1 , ω2 , where ω1 , ω2 pass through the center O of ω. The circle
ω cuts ω1 at A, E and ω2 at C, D. The circles ω1 and ω2 intersect at O and M . If AD
cuts CE at B and if M N ⊥ BO, (N ∈ BO) prove that 2M N 2 ≤ BM · M O.
3. For a set S, let |S| denote the number of elements in S. Let A be a set of positive integers
with |A| = 2001. Prove that there exists a set B such that all of the following conditions
are fulfilled:
a) B ⊆ A;
b) |B| ≥ 668;
c) for any x, y ∈ B we have x + y 6∈ B.

2nd MathLinks Contest
Round 1
September 1 - September 14, 2003
1. Let x, y, z be positive numbers such that

1 1 1
xyz ≤ 2 and + + < k, for some real k ≥ 2.
x2 y 2 z 2
Find all values of k such that the conditions above imply that there exist a triangle
having the side-lengths x, y, z.
2. We call a permutation σ of the first n positive integers friendly if and only if the
following conditions are fulfilled:
(1) σ(k + 1) ∈ {2σ(k), 2σ(k) − 1, 2σ(k) − n, 2σ(k) − n − 1}, ∀k ∈ {1, 2, . . . , n − 1}
(2) σ(1) ∈ {2σ(n), 2σ(n) − 1, 2σ(n) − n, 2σ(n) − n − 1}.
Find all positive integers n for which there exists such a friendly permutation of the
first n positive integers.
3. Given are on a line three points A, B, C such that AB = 1 and BC = x. Consider

the circles Ωa , Ωb and Ωc which are tangent to the given line at the points A, B, C
respectively, and such that Ωb is tangent externally with both Ωa and Ωc in points
M, N respectively. Find all values of the radius of the circle Ωb for which the triangle
BM N is isosceles.
Good luck in solving these problems.

Tex Compiling (c) Valentin Vornicu 2003
Round 1
Solutions and comments
1. Let x, y, z be positive numbers such that

1 1 1
xyz ≤ 2 and 2
+ 2 + 2 < k, for some real k ≥ 2.
x y z
Find all values of k such that the conditions above imply that there exist a triangle
having the side-lengths x, y, z.
Solution 1: (Claude, Octavian Ganea, Valentin Vornicu) We observe that
setting x = y = 1, z = 2 we have xyz = 2 and
1 1 1 9
+ 2 + 2 = . As 1,1,2 are not the side-lengths of a triangle it follows that
x2 y z 4
9 3 9
k ≤ . We shall prove that every k ∈ √ 3
, is a solution, and using the condition
4 4 4
9
k ≥ 2 in the hypothesis, we will conclude the final solution as 2, .
4
For that let us suppose that x, y, z are chosen randomly such that x ≤ y ≤ z and
1 1 1 9
xyz ≤ 2 and 2
+ 2+ 2 < .
x y z 4
If a triangle having side-lengths x, y, z does not exist, then z ≥ x+y. Let us denote by
s = x + y and p = xy. Then z ≥ s and zp ≤ 2. It follows that sp ≤ 2 and furthermore
1 p
from ≤ we deduce that
z 2
1 1 p2 9 p2 x2 + y 2 9
+ + < ⇔ + < ⇔
x2 y 2 4 4 4 p2 4
p2 s2 − 2p 9
+ 2
< ⇔ p4 + 4s2 − 8p < 9p2 ⇔ p4 − 9p2 − 8p + 4s2 < 0.
4 p 4
Using AM-GM we obtain that s2 ≥ 4p thus p4 − 9p2 + 8p < 0 which means that
p3 − 9p + 8 < 0 or better yet (p − 1)(p2 + p − 8) < 0.
If p ≤ 1, because p > 0, it follows that p2 + p ≤ 2 < 8 therefore (p − 1)(p2 + p − 8) ≥ 0,
contradiction. We must have p > 1 and because ps ≤ 2 we obtain that s < 2. But
4 > s2 ≥ 4p > 4, which is absurd. The supposition we made was false, and x, y, z are
the side-lengths of a triangle.
To prove that the hole interval is a solution, we must be sure that we can find 3
1 1 1
positive reals such that xyz ≤ 2 and 2 + 2 + 2 ≤ k, so we take the easiest way
x y z
√3 1 1 1 3
setting x = y = z = 2, and we see that 2 + 2 + 2 = √ 3
< 2.
x y z 2
3
Comment. The argument k ≥ 2 appeared from a mistake of mine, thinking that √ 3
4
is smaller than 2. When I realized the mistake :-) it was too late to change anything.
In fact it should have been k ≥ 1.
Solution 2: (Grobber) The following lemma is well known: a, b, c are the side-
lengths of a triangle if and only if E = (a2 + b2 + c2 )2 − 2(a4 + b4 + c4 ) > 0. For
reference go to http://www.mathlinks.ro/phpBB/viewtopic.php?t=281.
9
If k > it means that the triplet (1, 1, 2) verifies the inequalities, these cannot be
4
9 1 1 1 9
the side-lengths of a triangle. So k ≤ . Consider xyz ≤ 2, 2 + 2 + 2 < k ≤ .
4 x y z 4
1 1 1 1 1 1
Let us denote by a = , b = , c = . It suffices to prove that , , are the
x y z a b c
side-lengths of a triangle, which is equivalent (multiplying with abc) that ab, bc, ca
are the side-lengths of a triangle, which by the lemma above means
(a2 b2 + b2 c2 + c2 a2 )2 > 2(a4 b4 + b4 c4 + c4 a4 ) (1)
Now let us denote a2 = t, b2 = u, c2 = v. Then (1) can be rewritten as (tu+uv+vt)2 >

2(t2 u2 + u2 v 2 + v 2 t2 ) which is the same as 2tuv(t + u + v) > t2 u2 + u2 v 2 + v 2 t2 .
So the new problem is this: given t, u, v positive reals such that tuv ≥ 1 and t+u+v <≤
9
prove that 2tuv(t + u + v) > t2 u2 + u2 v 2 + v 2 t2 . We look at this as a second degree
4
equation in t. Then we must prove that (u − v)2 t2 − 2uv(u + v)t + u2 v 2 < 0. The
solutions of this equation are, after completing the calculations
uv uv
t1 = √ √ and t2 = √ √ .
( u + v)2 ( u − v)2
We have to prove that t is in the interval (t1 , t2 ). We know that

1 9
≤ t < − (u + v) (2)
4uv 4
1 uv
For the first inequality we must prove that > √ √ . From (2) we get
4uv ( u + v)2
1
4u + 4v + < 9, and by applying AM-GM we get uv < 1. Therefore
uv
1 uv 4u2 v 2
> √ √ 2 ⇔ √ √ <1
4uv ( u + v) ( u + v)2
but since uv < 1 we have
√
4u2 v 2 4 uv
√ √ < √ √ ≤1
( u + v)2 ( u + v)2
so we have proved that t > t1 .
9
We now have to prove t < t2 . We know that t < − (u + v) so it would be enough
4
to prove that
9 uv
− (u + v) ≤ √ √ .
4 ( u − v)2
uv
We can, without any restrictions, assume that t ≤ u ≤ v. Then √ √ >v≥t
( u − v)2
and we are done with t < t2 .
inthe first solution, there are numbers x, y, z to fulfill the conditions for all k ∈
As
9
2, .
4
2. We call a permutation σ of the first n positive integers friendly if and only if the
following conditions are fulfilled:
(1) σ(k + 1) ∈ {2σ(k), 2σ(k) − 1, 2σ(k) − n, 2σ(k) − n − 1}, ∀k ∈ {1, 2, . . . , n − 1}
(2) σ(1) ∈ {2σ(n), 2σ(n) − 1, 2σ(n) − n, 2σ(n) − n − 1}.
Find all positive integers n for which there exists such a friendly permutation of the
first n positive integers.
Modified by Valentin Vornicu, from C6/2002 IMO ShortList
Solution: (Octavian Ganea, Toumaf) It is easy to see that 1 and 2 are good
numbers. Suppose now that n ≥ 3 and let us consider the first case, that in which
n is odd. Let n = 2k + 1, and let i be such that σ(i) = n. Then σ(i + 1) ∈
{2n, 2n−1, n, n−1}, so σ(i+1) = n−1. But n = σ(i) ∈ {2σ(i−1), 2σ(i−1)−1, 2σ(i−
1)−n, 2σ(i−1)−n−1} and as n is odd, it follows that n ∈ {2σ(i−1)−1, 2σ(i−1)−n}.
If 2σ(i − 1) − n = n ⇒ σ(i − 1) = n, contradiction.
n+1
We thus have σ(i − 1) = . Consider j ≤ n such that σ(j) = 1. Then
2
1 ∈ {2σ(j − 1), 2σ(j − 1) − 1, 2σ(j − 1) − n, 2σ(j − 1) − n − 1} and obviously
1 ∈ {2σ(j − 1) − 1, 2σ(j − 1) − n}, for which it results that either 1 = 2σ(j − 1) − 1,
n+1
which is obviously a contradiction, or 1 = 2σ(j − 1) − n ⇒ σ(j − 1) = = σ(i − 1)
2
which means that i − 1 = j − 1 and i = j contradiction. Therefore n must necessarily
be even.
Now, we will prove that for n even there exists a friendly permutation of the first n
integers.
We define a (friendly) ring to be an ordered sequence of distinct integers between 1
and n such that the rule defining friendly permutations is satisfied.
By definition, the successor of an integer m is either 2m or 2m − 1 (mod. n). We can
see easily that an integer only has two possible antecedent: if m is even they are m/2
or (m + n)/2; if m is odd they are (m + 1)/2 or (m + 1 + n)/2.
First we construct a family of rings containing all integers between 1 and n exactly
once.
Start with 1 and choose its successor to be one of the possible two integers satisfying
the “friendly rule”. Call it p. Continue and choose a successor to p. Continue this
construction but never pick up a number which is already in the ring, except the first
value we started from, that is 1. Eventually, we must return back to 1. The first ring
is now constructed. To make the second ring, pick up any integer which is left out
(not in the first ring) and use the same process as before. In this fashion, we end up
with a partition of the set of integers into several distinct rings.
To prove that the construction above is really possible, we observe that, by contra-
diction, if we had (during the construction of a ring) a number q with no possible
successor to choose, then it would mean that 2q and 2q − 1 already have antecedents
different from q. But each of them can only have q + n/2 as an antecedent (other
than q). This is impossible because two distinct numbers must have two distinct
antecedents.
It remains to put together the rings to generate a friendly permutation.
We first note that every number has an antecedent which is smaller than itself. An
even number 2b has the antecedent b (with b < 2b), while an odd number 2b − 1 has
the antecedent b (with b < 2b − 1).
Choose the ring containing 1. Search for the smallest number r not already within
this ring. It belongs to another ring which we want to connect to the first ring. Cut
the second ring just before r. The number r has two possible antecedents, one of them
m (the smallest) belongs to the first ring (because all numbers smaller than r belong
the first ring), the other M (the largest) is precisely its antecedent within the second
ring. We build up a new ring by squeezing the second ring within the first one, just
between m and its successor, which we call r0 . So we get
...(first ring)..., m, r, ...(second ring), M, r0 , ...(first ring)...
By the “friendly” definition we see that r0 is indeed a possible successor of M . The

process is continued by adding more and rings until we exhaust the set of rings and
we end up with a friendly permutation.
Comment. This problem is a modification of the C6/2002 IMO ShortList - at the
moment of submittal I didn’t knew that fact because that problem (C6) has appeared
in another source as well, and thought that I have a simple solution to the problem.
I was wrong, but it was too late to change it. As it turned out the problem is more
difficult than C6 (but not with much). Fortunately Kalva Website didn’t present to
the closing hour of round 1 a solution to this problem, so it will be still validated.
3. Given are on a line three points A, B, C such that AB = 1 and BC = x. Consider

the circles Ωa , Ωb and Ωc which are tangent to the given line at the points A, B, C
respectively, and such that Ωb is tangent externally with both Ωa and Ωc in points
M, N respectively. Find all values of the radius of the circle Ωb for which the triangle
BM N is isosceles.
Solution: (Andrei Neguţ) Let d be the line on which the three points lie. As the
enounce does not states, we have to consider the orderings on the line d of the points
A, B, C.
First case: B lies between A and C. Let us denote by b the radius of the circle Ωb ,
and let us consider the inversion of pole B and power 1, such that d is mapped into
1
itself, as A into itself, C is mapped into C 0 such that BC 0 = , Ωb maps into d0 , a
x
1
line parallel with d, at which distance of this, and Ωa and Ωc remain circles, Ω0a
2b
and Ω0c , tangent in A, respectively C 0 at d, and at d0 because d0 is the mapping of Ωb .
Also M is mapped into M 0 and N into N 0 as shown below.
Before the inversion, if the triangle BM N would have been isosceles, that is
BM = BN , BM = M N , or BN = M N . These relations become respectively:
1 1 1 MN0 1 MN0
= , = or = , which are equivalent with
BM00 BN0 0 BM 0
0 BM
0 0
0 · BN 0
0
BN0 0 0 BM 0 · BN 0
BM = BN , BN = M N , or BM = M N . Let us compute these values:
r r
1 1 1 1
M 0 N 0 = A0 C 0 = 1 + , BM 0 = 1 + 2 , BN 0 = + .
x 4b x2 4b2
The three conditions become:
r
0 0 0 1 1 2 1 1 x2 x
BM = M N ⇔ 1+ = 1 + 2 ⇔ + 2 = 2 ⇔ 4b2 = ⇔b= √
x 4b x x 4b 2x + 1 2 2x + 1
r r
0 0 0 1 1 1 2 1 2 x 1 x
BN = M N ⇔ 1 + = 2
+ 2 ⇔ + 1 = 2 ⇔ 4b = ⇔b=
x x 4b x 4b x+2 2 x+2
1 1 1
BM 0 = BN 0 ⇔ 1 + = 2 + 2 ⇔ x = 1.
4b2 x 4b
Therefore, in the case of which x = 1, the triangle BM N is isosceles for any value
1
of b, and for b = √ is equilateral, and for x 6= 1, we have a triangle isosceles for
2 3 r
1 x 1 x
b∈ · √ , · .
2 2 2x + 1 2 x+2
For the second case, we consider the order B, C, A (or B, A, C depending if the
following expression is positive x − 1 or not) making the same inversion we have the
mapping shown below
The
same
conditions for an isosceles triangle, but a length is different: M 0 N 0 =
1 − 1 . Therefore the three conditions become:

x
r
x2

0 0 0 1 1 1 2 1 x
BM = M N ⇔ 1 − = 1 + 2 ⇔ 2 − = 2 ⇔ 4b2 =

⇔b= √
x 4b x x 4b 1 − 2x 2 1 − 2x
r r
0 0 0
1 1 1 2 1 2 x 1 x
BN = M N ⇔ 1 − =
2
+ 2 ⇔ 1− = 2 ⇔ 4b = ⇔b=
x x 4b x 4b x−2 2 x−2
1 1 1
BM 0 = BN 0 ⇔ 1 + 2
= 2 + 2 ⇔ x = 1.
4b x 4b
1 x 1
Thus if x < , the only solution is b = √ , if ≤ x < 1 we do not have any
2 2 1 − 2x 2
solutions, if x = 1 all positive values are good values for b but the triangle BM N
r if 1 < x ≤ 2 we do not have any solutions, and finally if
becomes a line segment,
1 x
x > 2 we have b = .
2 x−2
Solution 2: (Toumaf, Grobber) First, we concentrate our attention on the points
B, C, and N . Let us denote by B 0 and C 0 the centers of the circles Ωb and Ωc
respectively. We now have a figure with the points B 0 , B, C, C 0 , N . Observe that the
points B 0 , N, C 0 are aligned. Call H the foot of the perpendicular line to the side BC
containing also N . Let us denote by b the radius of the circle Ωb and let c be the
radius of Ωc . By Pythagora’s theorem we obtain
x2
(b − c)2 + x2 = (b + c)2 ⇒ c = .
4b
b BH
By Thales theorem we get that = , but HC = x − BH, thus
c HC
4b2 x
BH = .
4b2 + x2
Now, the triangle B 0 BN is isosceles, so its angle at B is equal to its angle at N . Call
it β. We then obtain that the angle ∠N BH = π/2 − β, the angle ∠BN H = β.
Similarly, if we call γ the measure of the angle ∠C 0 N C, we get that ∠CN H = γ. So
we have 2β + 2γ = π.
With these properties we conclude that the angle ∠BN C is a right angle. We can
now use the cosine of the angle ∠N BC. It is equal simultaneously to
BN BH 2bx
cos(∠N BC) = = ⇒ BN = √ .
x BN 4b2 + x2
2b
Exactly the same argument shows that BM = √ .
4b2 + 1
It remains to express that the triangle M BN is isosceles. If x = 1 then the figure is
completely symmetric and the triangle BM N is always isosceles. For x 6= 1 we can
see that the distance BM is different from BN . There are three cases:
1) the points A, B, C are ordered in this way on the line;
2) the points A, C, B are ordered in this way on the line;
3) the points C, A, B are ordered in this way on the line.
We concentrate on the first case. The half-angle ∠M B 0 B is given by
∠M B 0 B

MB 0 −1 M B
= sin ⇒ ∠M B B = 2 sin .
2b 2 2b

−1 N B
0
Similarly, ∠N B B = 2 sin ⇒ ∠M B 0 N = 2π − ∠M B 0 B − ∠N B 0 B and
2b
∠M B 0 N

M N = 2b sin . We obtain
2

−1 M B −1 N B
M N = 2b sin π − sin − sin and since cos(sin−1 α) = 1−α2
2b 2b
r r
N B2 M B2
⇒ MN = MB 1 − + N B 1 − .
4b2 4b2
We use the expressions for M B and N B:
r r r r
4b2 x2 4b2 x2 1 4b2 (x + 1)
MN = 1 − + 1 − ⇒ M N = √ √
4b2 + 1 4b2 + x2 4b2 + x2 4b2 + 1 4b2 + 1 4b2 + x2
r
1 x
Either M N = M B which is equivalent to b = , or M N = M B which is
2 x+2
x
equivalent to b = √ .
2 1 + 2x
Now, for ther case where the points A, C, B are ordered on the line we obtain x > 2
1 x 1 x
and b = or else x < and b = √ .
2 x−2 2 2 1 − 2x
Finally, the third case gives the same conditions again.
General Comment. These problems have subtle enounces, and many of the contestants
lost points because they did not interpreted/evaluated the statement of the problem
carefully. This happens a lot at the IMO, and I hope to prevent that in the future.
Although I have made slight mistakes in the appreciation of the problem’s difficulties,
everything turned out all right after all. Sorry once again, and hope that the next
rounds will be less computational :-) and a lot more tricky.
Tex (c) Valentin Vornicu 2003

Round 2
1. Given are six reals a, b, c, x, y, z such that
(a + b + c)(x + y + z) = 3 and (a2 + b2 + c2 )(x2 + y 2 + z 2 ) = 4.
Prove that ax + by + cz ≥ 0.
2. Let {an }n≥0 be a sequence of rational numbers given by a0 = a1 = a2 = a3 = 1 and

for all n ≥ 4 we have an−4 an = an−3 an−1 + a2n−2 .
Prove that all the terms of the sequence are integers.
3. Prove that if two triangles are inscribed in the same circle, then their incircles are not
strictly contained one into each other.

Round 2
1. Given are six reals a, b, c, x, y, z such that
(a + b + c)(x + y + z) = 3 and (a2 + b2 + c2 )(x2 + y 2 + z 2 ) = 4.
Prove that ax + by + cz ≥ 0.
Solution 1: (Iandrei) It is clear that a2 + b2 + c2 6= 0 and x2 + y 2 + z 2 6= 0 since
their product is non-zero. We consider the number:
s
a2 + b2 + c2
α= 4 2 6= 0
x + y2 + z2
Also, let us consider the following numbers:

a b c
a1 = , a2 = , c1 = , x1 = xα, y1 = yα, z1 = zα
α α α
The following relationships hold:
(a1 + b1 + c1 )(x1 + y1 + z1 ) = (a + b + c)(x + y + z) = 3,
(a21 + b21 + c21 )(x21 + y12 + z12 ) = (a2 + b2 + c2 )(x2 + y 2 + z 2 ) = 4,

a1 x1 + b1 y1 + c1 z1 = ax + by + cz
Moreover, the new numbers have extra properties:

a2 + b2 + c2 p 2
a21 + b21 + c21 = = (a + b2 + c2 )(x2 + y 2 + z 2 ) = 2 (1)
α2
p
x21 + y12 + z12 = (x2 + y 2 + z 2 )α2 = (a2 + b2 + c2 )(x2 + y 2 + z 2 ) = 2 (2)
Therefore, it is enough to prove that a1 x1 + b1 y1 + c1 z1 ≥ 0, or, using (1) and (2),
(a1 + x1 )2 + (b1 + y1 )2 + (c1 + z1 )2 ≥ 4.
Applying the Cauchy inequality we obtain

1
(a1 + x1 )2 + (b1 + y1 )2 + (c1 + z1 )2 ≥ (a1 + b1 + c1 + x1 + y1 + z1 )2 (3)
3
And by AM-GM for a1 + b1 + c1 and x1 + y1 + z1 we get
1 4 4
(a1 + b1 + c1 + x1 + y1 + z1 )2 ≥ (a1 + b1 + c1 )(x1 + y1 + z1 ) = · 3 = 4. (4)
3 3 3
From (3) and (4) the conclusion follows and we are done.
Comment. The only pure algebric solution received turns out to the be the most simple
and elegant solution of this problem. Well done, Andrei!
Solution 2: (Andrei Neguţ) Let us consider the vectors − →xi = OXi , −
→
v = OA,
where X1 = (x, y, z), X2 = (y, z, x) and X3 = (z, x, y), and the point A = (a, b, c) in
the 3D space. The conditions are translated as
|−
→
xi ||−
→
v | = 2, ∀ i ∈ {1, 2, 3} (1)
3 3
3
3 = (a + b + c)(x + y + z) = −
→1 · −
→
v +−
→2 · −
→
v +−
→3 · −
→
X X
x x x v =2 cos αi ⇒ cos αi = (2)
2
i=1 i=1
where we have denoted by αi the angle between the vectors − →xi and −→v.
We are required to prove that ax + by + cz ≥ 0, that is −→1 · −
x →
v ≥ 0, which means that
π π
α1 ≤ . Suppose for the sake of contradiction that α1 > .
2 2
We observe that for all i 6
= j we have →
−xi · →
−
xj = xy + yz + zx, and as
→
−
p
2 2 2
| xi | = x + y + z , ∀i ∈ {1, 2, 3}, we deduce that the angles between the three
vectors − →
xi are equal, say with θ. Let us reach a contradiction, by proving the next
general lemma:
Lemma. Given are three vectors − →yi have equal angles between them, and have the
same modulus; prove that if a fourth vector − →
y is chosen such that the angles between
3
π X
him and one of the three vectors is greater than , then the sum cos βi is less than
2
i=1
3
2 , where βi denotes the angle between the vectors −→
y and −→
yi .
Proof. We can suppose WLOG that all the vectors have modulus 1, since we only care
about angles. Also we can suppose WLOG that Y1 = (0, 0, 1), and that
Y2 = (m, n, cos θ), where θ is the angle between the first three vectors. Also by choos-
ing Y3 = (m0 , n0 , cos θ), we obtain that m2 + n2 = m02 + n02 = sin2 θ, because they all
have modulus 1, and cos θ = mm0 + nn0 + cos2 θ, that is cos θ − cos2 θ = mm0 + nn0
(this follows from the fact that − →
y2 · −
→
y3 = cos θ).
Let us now consider the defining coordinates of − →
y being (m1 , n1 , p1 ), where p1 must
3
necessarily be negative. It suffices to prove that cos β2 +cos β3 < , because cos β1 < 0.
2
−
→ →
− →
− 3
The latter is equivalent with ( y2 + y3 ) · y < .
2
π
Now if θ > , then by Cauchy-Schwartz we have
2
−
→
y2 · −
→
y +−
→
y3 · −
→
y = m1 (m + m0 ) + n1 (n + n0 ) + 2p1 cos θ ≤
q
≤ (m21 + n21 + p21 )(m2 + n2 + m02 + n02 + 2mm0 + 2nn0 + 4 cos2 θ) =
p √ √ 3
= 1 − cos2 θ + 1 − cos2 θ + 2 cos θ − 2 cos2 θ + 4 cos2 θ ≤ 2 + 2 cos θ < 2 < .
2
π
So we can consider θ ≤ . Then also by Cauchy-Schwartz we have
2
−
→y2 · −
→
y +−→
y3 · −
→
y = m1 (m + m0 ) + n1 (n + n0 ) + 2p1 cos θ ≤
q
≤ (m21 + n21 )(m2 + n2 + m02 + n02 + 2mm0 + 2nn0 ) + 2p1 cos θ ≤
p
≤ 1 − cos2 θ + 1 − cos2 θ + 2 cos θ − 2 cos2 θ + 2p1 cos θ ≤
2
p p 3
≤ 2(1 + cos θ − 2 cos2 θ) + 2p1 cos θ < 2(1 + cos θ − 2 cos2 θ) ≤ ,
2
2 2 2 2 2
where we have used that m1 + n1 + p1 = 1, so m1 + n1 < 1, and the fact that p1 < 0.
In both cases we have reached a contradiction, and thus our supposition was false,
and the lemma is proved, hence the problem is solved.
Comment. This is the first idea that came into my mind when I saw the problem. I
must mention that similar solutions, based on the same vectorial approach, we given
by Smooken and Toumaf.
2. Let {an }n≥0 be a sequence of rational numbers given by a0 = a1 = a2 = a3 = 1 and

for all n ≥ 4 we have an−4 an = an−3 an−1 + a2n−2 .
Prove that all the terms of the sequence are integers.
Solution: (Toumaf) We assume that all terms ak are integers up to k = n some
some n ≥ 7. Obviously the first seven terms are integers, with a4 = 2, a5 = 3, and
a6 = 7.
We first establish that an−1 and an are relatively prime. By contradiction, suppose
that λ is a common prime factor. Using the recurrence relationship we see that an−2
is divisible by λ. By induction we can also deduce that all previous terms ak are
divisible by λ, which is impossible because (for instance) a0 = 1.
We then establish that an−2 and an are relatively prime. The same argument shows
that an−1 an−3 is divisible by λ, so either an−1 or an−3 is divisible by λ, in each case
we have two consecutive terms divisible by λ and this is impossible by the previous
observation.
We finally establish that an−3 and an are relatively prime. It is exactly the same proof
as for the first observation: we get that an−2 is divisible by λ and again we arrive at
two consecutive terms divisible by λ.
We now want to prove that an+1 is an integer, knowing that all previous terms are
integers. In view of the definition of an+1
an+1 an−3 = an an−2 + a2n−1
we must prove that an an−2 + a2n−1 is divisible by an−3 . We can multiply this quantity
by an−4 a2n−5 an−6 because by the facts above it is relatively prime with an−3 . We now
have to prove that
X = an−4 a2n−5 an−6 an an−2 + an−4 a2n−5 an−6 a2n−1
is divisible by an−3 . We find that
X = (an−4 an )(an−6 an−2 )a2n−5 + (an−5 an−1 )2 (an−4 an−6 )
therefore
X = (an−3 an−1 +a2n−2 )(an−5 an−3 +a2n−4 )a2n−5 +(an−4 an−2 +a2n−3 )2 (an−3 an−7 −a2n−5 )
thus modulo an−3 :
X ≡ (a2n−2 )(a2n−4 )a2n−5 + (an−4 an−2 )2 (−a2n−5 ) ≡ 0.
We deduce that an+1 is an integer.
3
Comment. All the other 4 solutions received were based on the same principles, but
none was as clear, and easy to follow up as this one. The other 4 that gave good
solutions were: Claude, Andrei Negut, Iandrei and Bugz Podder.
3. Prove that if two triangles are inscribed in the same circle, then their incircles are not
strictly contained one into each other.
Solution 1: (Bugz Podder, Iandrei, Octavian Ganea, Sebadollahi, Andrei
Neguţ) Let ∆1 and ∆2 be two triangles inscribed in the same circle C(O, R), having
incircles C1 (I1 , r1 ) and C2 (I2 , r2 ) such that C2 is strictly contained in C1 . Since OI12 =
R2 − 2Rr1 < R2 and OI22 = R2 − 2Rr2 < R2 (this is one of Euler’s known theorems),
it follows that I1 and I2 are inside C.
Because the two circles are contained one into the other we must have I1 I2 < |r1 − r2 |
(triangle inequality). However, again from the triangle inequality in the triangle OI1 I2
(possibly degenerate) we have
p p
I1 I2 ≥ |OI1 − OI2 | = | R2 − 2Rr1 − R2 − 2Rr2 | =
2R|r1 − r2 | 2R|r1 − r2 |
=√ √ > = |r1 − r2 |
R2 2
− 2Rr1 + R − 2Rr2 R+R
We have obviously reached a contradiction and from here it follows that C2 cannot be
strictly contained in C1 .
Last updated at February 22, 2004.

4
Round 3
September 29 - Octomber 12, 2003
1. Determine all values of a ∈ R such that there exists a function f : [0, 1] → R fulfilling
the following inequality for all x 6= y:
|f (x) − f (y)| ≥ a.
2. Let ABC be a triangle with altitudes AD, BE, CF . Choose the points A1 , B1 , C1
on the lines AD, BE, CF respectively, such that
AA1 BB1 CC1
= = = k.
AD BE CF
Find all values of k such that the triangle A1 B1 C1 is similar to the triangle ABC for
all triangles ABC.
3. Prove that for every positive integer m there exists a positive integer N such that
S(2n ) > m for every positive integer n > N , where by S(x) we denote the sum of
digits of a positive integer x.

Round 3
September 29 - October 12, 2003
1. Determine all values of a ∈ R such that there exists a function f : [0, 1] → R fulfilling
the following inequality for all x 6= y:
|f (x) − f (y)| ≥ a.
Solution: First of all observe that all values a ≤ 0 are solutions since any function
satisfies the property with a ≤ 0.
Secondly, we shall prove that no value a > 0 is solution to the problem. By contra-
diction, suppose that there would exist a value a > 0 and a function f such that for
all x 6= y
|f (x) − f (y)| ≥ a.
By replacing f by f /a we can assume without loss of generality that a = 1.
Let
Y = f (R) = {f (x); x ∈ R}.
By our assumption on f , we can see that any two elements f (x) and f (y) in Y are
separated by at least 1. (Thus f is injective.)
Consider the set g(Y ) where g(y) denotes the greatest integer less than or equal to y
(“integer part”). We can see that the mapping g : Y → g(Y ) is one-to-one because
any two numbers in Y are separated by at least 1 and therefore have distinct integer
parts. But g(Y ) is a subset of the set Z of integers thus Y must be at most countable.
Since f is injective, it would be an injection from the real numbers R to the integers
Z, which is impossible.
Comment. All the contestants gave solutions based on the idea that [0, 1] is not a
countable set. This problem was proposed by Dan Radu.
2. Let ABC be a triangle with altitudes AD, BE, CF . Choose the points A1 , B1 , C1
on the lines AD, BE, CF respectively, such that
AA1 BB1 CC1
= = = k.
AD BE CF
Find all values of the positive real k such that the triangle A1 B1 C1 is similar to the
triangle ABC for all triangles ABC.
Solution 1: (Valentin Vornicu) Let ABC be a right isosceles triangle in A with
AB = AC = 1. We have E = F = A. We apply Thales’ theorem which gives
(BC) k (B1 C1 ), and so (AD) ⊥ (B1 C1 ), intersecting in H.
The triangle A1 B1 C1 , which is similar to ABC has a right angle. It cannot be in C1 or
in B1 because then (A1 C1 ) or (A1 B1 ) would be parallel to (AD), which is impossible.
k
By construction, AC1 = AB1 = 1 − k and AA1 = √ . AB1 A1 C1 is a square (because
2
k
k 6= 0) of side length equal to 1 − k and diagonal length of √ , which implies that
2
√ k
2(1 − k) = √ ,
2
2
which gives us the only possible value of k, which is k = .
3
2
Let us now prove that k = is a good value. One can easily see (!) that the lines
3
parallel with BC, CA, AB respectively, passing through centroid G of the triangle
ABC, intersect the altitudes in A0 , B 0 and C 0 respectively, because the G cuts the
median lines in the same ratio. Therefore A0 , B 0 , C 0 each lie on the circle with diameter
GH, so in particular
∠A0 B 0 C 0 = π − ∠C 0 HA0 = π − ∠F HD = ∠DBF = ∠ABC.
In the same way the the other two angles are equal, so the triangle ABC ∼ A0 B 0 C 0 .
2
Solution 2: (Andreis) In the same manner as above we see that k = is the only
3
possible positive solution.
2
To prove (again) the fact that k = is a good value, we shall use this time complex
3
numbers. We shall use small letters as affixes of the points denoted by capital letters.
Consider O the origin of the complex plane, where O is the circumcircle of the triangle
a + b + c − abc
ABC, such that |a| = |b| = |c| = 1. It is easy to check that d = , thus
2
bc
a+b+c− a +a
a0 = and the same with the other points b0 , c0 .
3
Then the similarity of the triangles ABC and A0 B 0 C 0 is given by the constant ratios
|b1 − a1 | |b − a|
of the side lengths. We shall only prove that = , as the other ratio
|c1 − a1 | |c − a|
equality is obvious. We have
2 2

b − a + c b − a |ab + bc + ca|

|b1 − a1 | |b − a| ba |b − a| |ab| |b|
= ⇔ 2 2
= ⇔ = = 1,
|c1 − a1 | |c − a| |c − |ab + bc + ca| |c|
c − a + b c − a a|

ac |ac|
and we are done.

2
Comment. The reasoning for the fact that k = is the only possible value, has been
3
made by Toumaf. Unfortunately, he tried to prove that this is yet not a good value.
Almost all the contestants gave really long and computational solutions, when a much
more simpler argument was available (see the ! mark). This problem was proposed in
Vietnam Olympiad.
2
3. Prove that for every positive integer m there exists a positive integer N such that
S(2n ) > m for every positive integer n > N , where by S(x) we denote the sum of
digits of a positive integer x.
Solution 1: (Claude) We have to prove that lim S(2n ) = ∞. Suppose that the
n→∞
affirmation is not true, and as the sequence {S(2n )}n is a sequence composed of pos-
itive integers, it will contain a constant sub-sequence; thus there exists an increasing
sequence {nk }k≥1 and m ∈ N such that S(2nk ) = m, ∀ k ≥ 1. It follows that 2nk
contains at most m non-zero digits in his decimal representation, and if we write it as
K1 O1 K2 . . . Kp , where Ki are groups of non-zero digits and Oi -s are groups composed
only of zeros, then we have that p ≤ m, and Ki contains at most m digits.
Let f : N → N, f (n) = blog2 10n c + 1 be a function. Also consider m1 = m, p1 =
f (m1 ). For i ≥ 2 take mi = pi−1 + m and pi = f (mi ). Obviously
m1 < p1 < m2 < p2 < · · · and so on.
Further on we have that lim 2nk = ∞, thus we can choose k0 such that
k→∞
N (2nk0 ) > mm , where N (x) represents the number of digits of x in decimal rep-
resentation. Let 2nk0 = K1 O1 K2 ...Kp be the decimal representation of 2nk0 (with the
notations used above). For a ≤ nk0 , by writing 2nk0 = q · 10a + r, with 0 ≤ r < 10a
we obtain that r 6= 0 and 2a |r ⇒ r ≥ 2a . (2)
Let us denote by o0i the number of zeros in the group Oi and by ki0 the number of
0 0 0
digits in the group Ki . It follows that 2nk0 ≥ 10o1 +k2 +...+kp ⇒ nk0 ≥ o01 + k20 + ... + kp0 .
We also have that kp0 ≤ m = m1 ⇒ Kp < 10m1 .
0 0 0 0
Moreover, 2nk0 = K1 O1 K2 ...Kp−1 · 10op−1 +kp + Kp ⇒ Kp ≥ 2op−1 +kp (from (2))⇒
o0p−1 + kp0 ≤ log2 Kp ≤ log2 10m1 < f (m1 ) = p1 from which it results that
0
kp−1 0
+ o0p−1 + kp0 < kp−1 + p1 ≤ m + p1 = m2 ⇒ Kp−1 Op−1 Kp < 10m2 .
0 0 0 0
But 2nk0 = K1 O1 K2 . . . Kp−2 · 10op−2 +kp−1 +op−1 +kp + Kp−1 Op−1 Kp therefore
0 0 0 0
Kp−1 Op−1 Kp ≥ 2op−2 +kp−1 +op−1 +kp ⇒ o0p−2 + kp−1
0 + o0p−1 + kp0 ≤ log2 Kp−1 Op−1 Kp ≤
m
≤ log2 10 < f (m2 ) = p2 .
2
We finally obtain o01 + k20 + ... + o0p−1 + kp0 ≤ pp−1 and k10 + o01 + k20 + ... + o0p−1 + kp0 ≤
≤ pp−1 + m = mp . So we have seen that p ≤ m ⇒ mp ≤ mm ⇒ N (2nk0 ) ≤ mm
which is a contradiction. Thus the original supposition was false, which means that
lim S(2n ) = ∞.
n→∞
Solution 2: (Andreis) We shall prove that for all positive integers m there exist the
positive integers nm , cm such that the sum of last cm digits of 2x with x ≥ nm ≥ cm
is greater or equal than m.
We shall proceed using induction. For m = 2 the affirmation is obvious, as n2 = 1
cm
and c2 = 1. We have, for an integer s ≥ cm , that 2s+kϕ(5 ) ≡ 2s (mod 10s ), that is
cm

2s 2kϕ(5 ) − 1 ≡ 0 (mod 2cm · 5cm ),
cm )
therefore the last cm digits are the same for 2s and 2s+kϕ(5 , for all positive integers
k.
Let us consider the minimal value of the sum of the last cm digits of the numbers 2nm ,
cm
2nm +1 , . . ., 2nm +ϕ(5 )−1 , which is m, as nm ≥ cm , we have that the last cm digits of
3
2x , x ≥ nm , are the same with the last digits of 2y , with y ∈ {nm , nm + 1, . . . , nm +
ϕ(5cm ) − 1} thus the sum of the last cm digits is greater or equal with m.
Suppose by contradiction that for all positive integers n0m ≥ c0 , with n0m > nm and
c0 > cm . There exists a number x such that the sum of the last c0 digits of x = m,
because otherwise n0m and c0 are good for m + 1. But the last cm digits of 2x are
the same with those of 2y , which have sum m, so we have that x has the form
0 0
a1 . . . ai 00 . . . 0} b1 b2 . . . bcm . But 2x > 10c , we have that 2c | a1 . . . ai 00
| {z . . . 0} and
| {z
| {z }
c0 −cm cm cm
c0
2 | 2xthus 2c
0
c0
| b1 b2 . . . bcm , ∀ ∈ N, which is a contradiction. We have proved the
existence of nm+1 and cm+1 , and we are done.
Comment. This beautiful problem can be generalized to any number d which is not
divisible by 10. This problem is a result of Schinzel.
Last updated at November 2, 2003.

4
Round 4
Octomber 13 - Octomber 26, 2003
1. The real polynomial f ∈ R[X] has an odd degree and it is given that f is co-prime
with g(x) = x2 − x − 1 and
f (x2 − 1) = f (x)f (−x), ∀ x ∈ R.
Prove that f has at least two complex non-real roots.
2. Given is a finite set of points M and an equilateral triangle ∆ in the plane. It is

known that for any subset M 0 ⊂ M , which has no more than 9 points, can be covered
by two translations of the triangle ∆. Prove that the entire set M can be covered by
two translations of ∆.
3. In a country there are 100 cities, some of which are connected by roads. For each four
cities there are at least two roads between them. Also, there is no path that passes
through each city exactly one time. Prove that one can choose two cities among those
100, such that each of the 98 remaining cities would be connected by a road with at
least one of the two chosen cities.

1
Last updated on October 14, 2003.
Round 4
October 13 - October 26, 2003
1. The real polynomial f ∈ R[X] has an odd degree and it is given that f is co-prime
with g(x) = x2 − x − 1 and
f (x2 − 1) = f (x)f (−x), ∀ x ∈ R.
Prove that f has at least two complex non-real roots.

Solution 1: (Andrei Negut) Let us denote σ(x) = x2 − 1. We shall say a poly-
nomial h = (x − a1 )(x − a2 ) · · · (x − aj ) is a cycle if ai+1 = ai , for all i = 1, j, where
aj+1 = a1 .
We shall also use the following lemma:
Lemma. A real polynomial f , having all roots reals, and which is co-prime with g(x)
and fulfilling the relationship
h(x2 − 1) = ±h(x)h(−x) (∗)
can be written as a product of polynomials hi , i = 1, k, where each of the hi is a cycle.

We shall call these cycles hi the components of h.
Proof of lemma. We shall proceed through mathematical induction after n, the degree
of h. The statement is obvious for n = 0 and n = 1. Let us suppose that it is true for
all values 0, 1, . . . , n − 1 and let us prove it for n.
From (*) if x is a root of h then also is σ(x). So, let us consider x0 a root of h, and
the numbers σ (k) (x), for all positive integers k, where σ (k+1) (x) = σ(σ (k) (x)).
Let d = min{k − l : k > l, σ (k) (x) = σ (l) (x)}, and k, l two of the indices for which
this minimal value is taken. This set is obviously not empty, because we cannot have
an infinity of roots of h. Let us denote by ai = σ (l+i−1) (x), i = 1, k − l + 1. All of the
ai -s are different, because of the minimality of d. All of them are also roots of h, and
further more ai+1 = a2i −1, for all i-s. That is why (x−a1 )(x−a2 ) · · · (x−ak−l+1 ) | h(x),
so h(x) = h1 (x)(x − a1 )(x − a2 ) · · · (x − ak−l+1 ). But h1 (x) has only real roots, and it
is also prime with g(x), and replacing the latter equality in (*) we obtain
h1 (x2 − 1)(x2 − 1 − a1 ) · · · (x2 − ak−l+1 − 1) =
= ±h1 (x)h1 (−x)(x − a1 )(−x − a1 ) · · · (x − ak−l+1 )(−x − ak−l+1 ) ⇒

h1 (x2 − 1) = ±h1 (x)h1 (−x) (∗∗)
and by induction h1 (x) is a product of cycles, thus h is a product of cycles, and the
lemma is proved.
Getting back to our original problem, we observe that f has no complex roots. By
applying the lemma, we obtain that f is a product of cycles, so each of its roots will
be part in one of the cycles, that is for each root x0 of f , there exists k such that
σ (k) (x) = x.
Let α > 0 > β > −1 be the roots of g(x). Obviously, since f is prime with g, α and
β are not among f ’s roots.
Now, we have some cases to analyze. First of all, if f has a root x0 > α, then because
σ(x) > x, we would obtain an infinite sequence of different roots of f , which is absurd.
If f would have a root x0 in the interval (0, α), because of the fact that −1 ≤ x2 − 1 =
σ(x0 ) < x0 , we would obtain an infinite sequence of roots. This would not happen if
and only if at some point k we would have σ (k) (x0 ) = β, but then σ (l) (x0 ) = β, for all
l ≥ k, and x0 would not belong to any cycle, in direct contradiction with the lemma
above. This means that f has no positive roots.
Also, if f would have a root x0 < −1, then σ(x0 ) > 0 (!) and thus f would have a
positive root, which cannot be true, as proved above.
We are left with one case, f having all roots in the interval [−1, 0]. We shall prove
that in this case f has an even degree.
Consider a component of f , (x − a1 ) · · · (x − aj ) | f (x). We have, from the definition
of a component, that σ (j) (a1 ) = a1 . Also we observe that if −1 ≤ x < β, then
β < σ(x) ≤ 0, and if β < x ≤ 0 then −1 ≤ σ(x) < β.
Therefore if −1 ≤ a1 < β, we have −1 ≤ σ (2i) (a1 ) < β and β < σ (2i+1) (a1 ) ≤ 0, for
all non-negative integers i. It follows that j is even. So, we have chosen a random
component of f , and proven that its degree is even. As f is a product of such
components it follows that f has an even degree with is a contradiction with the
statement of the problem.
We conclude that f has at least a non-real complex root z, and because f is a real
polynomial, it must also have the conjugate z as a root and we are done.
Solution 2: (Iandrei) We shall argue by contradiction. Assume that f has at most
one complex non-real root. If it had exactly one root α = u + iv(u, v ∈ R, v 6= 0)
then α = u − iv is also a root, so we must have α = α, or equivalently, v = 0, a
contradiction. So if it has at most one complex non-real root, it has none. Thus it
must have all real roots. Let us prove that in this case, f must have even degree.
We notice that if f (x) = (x2 + x)k f1 (x), then :
f1 (x2 − 1) = f1 (x)f1 (−x)
Thus we can assume that f is not divisible by x2 + x. If it is divisible only by x, then

let f (x) = xf1 (x) so :
(x2 − 1)f1 (x2 − 1) = −x2 f1 (x)f1 (−x)
But this means that x2 |f1 (x2 − 1) , or equivalently, x + 1|f1 (x). Thus if x|f (x) then
x2 + x|f (x).
Now let us assume that x + 1|f (x). Let f (x) = (x + 1)f1 (x) so that :
x2 f1 (x2 − 1) = (1 − x2 )f1 (x)f1 (−x)
But this means that 1 − x2 |f1 (x2 − 1), or equivalently, x|f1 (x). So we can assume in
fact that f is coprime with g1 (x) = (x2 + x)(x2 − x − 1).
Let α be a root of f and h(x) = x2 − 1. Notice that h(α) is also a root of f .
2
( √ √ )
1− 5 1+ 5
Consider the smallest root α0 of f . Then clearly α0 ∈
/ , . There are
2 2
three cases :
√
1+ 5
If α0 > , then h(α0 ) > α0 and so we obtain an infinite increasing sequence of
2
roots of f : α0 , h(α0 ), h(h(α0 )), . . . . This is a contradiction so f doesn’t have any
roots in that interval, because instead of α0 we can take any root α (we didn’t use
the minimal property of α0 in this case).
√ √
1− 5 1+ 5
If < α0 < , then h(α0 ) < α0 is a smaller root of f , a contradiction.
2 2
√
1− 5
This means that α0 < . Since f (x)f (−x) has only real roots then so does
2
f (x − 1). Thus if β is a root of f , x2 − 1 − β|f (x2 − 1), so x2 − 1 − β has only real
2
roots. Thus −β − 1 ≤ 0, or β ≥ −1. We have already established that we can assume

that f (x) and g1 (x) are co-prime, so that β > −1. In particular α0 + 1 > 0.
h(h(α0 )) = (α02 − 1)2 − 1 < α0 ⇔ (α0 + 1)2 (α0 − 1)2 < 1 + α0 ⇔
(α0 + 1)(α0 − 1)2 < 1 ⇔ (α02 − 1)(α0 − 1) < 1 ⇔ α03 − α02 − α0 + 1 < 1 ⇔
α0 (α02 − α0 − 1) < 0
" √ √ #
1− 5 1+ 5
The last relationship is true since α0 ∈/ , and α0 < 0. Thus we have
2 2
found a smaller root of f , a contradiction. It follows that f has no real roots except
0 and −1. And since these come in pairs of two, f must be of the form :
f (x) = (x2 + x)k
a contradiction since f must have odd degree. So our original assumption must be
false and f has indeed at least two complex non-real roots.
Solution 3: (Toumaf) If β ∈ R is a non-zero root of f , then β 2 − 1 ∈ R is also a
root of f , as a direct consequence of the hypothesis.
√
1+ 5
If β > ϕ = , then β 2 − 1 > β, and this allows the construction of an infinite
2
sequence of distinct roots of the polynomial f , which brings a contradiction.
If β < −ϕ, then β 2 − 1 > ϕ, and so the previous remark stands and also brings a
" √ √ #
1+ 5 1+ 5
contradiction. Thus all real root of f are in the range − , .
2 2
√ !
1− 5
If β ∈ , 0 , then (β 2 − 1)2 − 1 > β and we remain in the same interval, thus
2
we can again construct an infinite sequence of distinct roots of f .
√ ! √ !
5−1 2
2 1− 5
If β ∈ 0, , then β − 1 − 1 ∈ , 0 , and this brings, by the same
2 2
reasoning, a contradiction.
3
√ ! √ !
√
1− 5 5−1
If β ∈ −1, ∪ , 1 , then β 2 − 1 ∈ 1−2 5 , 0 , and this is impossible,
2 2
as seen before. We have restrained the possible values for the roots of f to the following
domain " √ # " √ #
1+ 5 5+1
− , −1 ∪ {0} ∪ 1, .
2 2
√ ! √ !
1 + 5 1 − 5
Since f is co-prime to g(x) = x2 − x − 1 = x − x− , we get
2 2
√
√ !
1± 5 0 1± 5
that the x = 2 are not roots of f , and thus x = − are not roots of f
2
because x02 − 1 = x.
√
We define the sequence {un }n≥0 by u0 = 0 and un+1 = 1 + un . We have un =
u2n+1 − 1, so if un+1 is a root of f , then un also is a root of f .
Let us suppose that α ∈ (un , un+1 ) is a root of f . Then α2 − 1 ∈ (un−1 , un ), and is
a root of f . By continuing this process, we construct a decreasing sequence of roots,
which after a certain number of steps, falls into the interval (0, 1) = (u0 , u1 ), which is
impossible.
" √ # " √ #
1+ 5 5 + 1
If α ∈ − , −1 − {−ui : i ∈ N}, then α2 − 1 ∈ 1, − {ui : i ∈ N},
2 2
and we find ourselves in the first case again. Therefore the only possible roots of f
are found in the set {ui |i ∈ N} ∪ {−ui |i ∈ N}.
Since f is an odd degree polynomial with real coefficients, we have
l+ = lim f (x) = − lim f (x) = −l− ,
x→+∞ x→−∞
and both limits are equal to ±∞. With the property f (x2 − 1) = f (x)f (−x), by
2
letting x to go to +∞ we obtain l+ = l+ l− = − (l+ ) . Thus we have l+ = −∞ and
l− = +∞, so the leading order coefficient of f is negative.
Then f can be written, for a certain p, and with nk ∈ N,
f (x) = λxn0 (x − u1 )n1 · · · (x − up )np (x + u1 )n−1 · · · (x + up )n−p .
We can, using the statement of the problem, write that
p
Y
f (x2 − 1) = f (x)f (−x) = λ2 (x − ui )ni (−x − ui )ni
i=−p
p
Y p
Y
2 ni 2 n−p +···+np
λ (x − 1 − ui ) = λ (−1) (x − ui )ni +n−i
i=−p i=−p
Yp p
Y
λ (x2 − 1 − ui )ni = −λ2 (x − ui )ni +n−i
i=−p i=−p
p p
Y ni n−i Y
λ x2 − 1 − ui x2 − 1 + ui = −λ2 ((x − ui )(x + ui ))ni +n−i
i=0 i=0
p
Y ni +n−i
= −λ2 x2 − u2i
i=0
4
because n−p + · · · + np , degree of f , is odd. This equality between polynomials assures
us that λ = −1. They are of the same degree, and so this equality implies that the
roots are the same, and of the same order. Let us denote y = x2 , and we obtain
p p
Y Y ni +n−i
− (y − 1 − ui )ni (y − 1 + ui )n−i = −y 2n0
y − u2i .
i=0 i=1
Since u2i = ui−1 + 1, this can also be written

p p
Y Y ni +n−i
(y − 1 − ui )ni (y − 1 + ui )n−i = y 2n0 y − ui−1 − 1
i=0 i=1
p−1
Y
= y 2n0 (y − 1 − ui )ni+1 +n−i−1 .
i=0
By looking at the order of the root 0 = u0 in both polynomials of the previous equality,
we get that n−1 = 2n0 , and in the same manner, the order of the root 1 = u1 gives
2n0 = n1 + n−1 .
By combining these two relations, we get that n1 = 0. And also u1 is not root of f ,
so for all i > 1, ui is not root of f , and neither is −ui because (−ui )2 − 1 = ui−1 .
Therefore f can be written
f (x) = −xn0 (x + 1)n−1 = −xn0 (x + 1)2n0 .
Since the degree of f is odd, we have 3n0 which is odd, and so n0 is odd. We then
use the hypothesis, which gives:
f (x2 − 1) = −(x2 − 1)n0 (x2 − 1 + 1)2n0 = −xn0 (x + 1)2n0 −(−x)n0 (−x + 1)2n0

This relation can be simplified into:
−(x2 − 1)n0 x4n0 = (−1)n0 x2n0 (x2 − 1)2n0

x2n0 = (x2 − 1)n0 .
This is impossible since n0 6= 0.

By contradiction, f cannot have only real roots. Since f is a real polynomial, if z is
a complex root of f , then z̄ is also root of f and we are done.
Comments. I would like to say that the following students also presented good solu-
tions of this problem: Octavian Ganea, Claude, Andreis. Their solutions resemble
much with Solution 2. I have presented 3 solutions here, to observe the same problem
attacked in three different thinking modes: the first solution is rather combinatorial
thinking, the second one (the one I’ve thought about when I made the problem) is pure
algebric thinking, and the third one has a little piece of analysis in it.
However, I have not managed, yet :), to find a geometrical-related approach.
5
2. Given is a finite set of points M and an equilateral triangle ∆ in the plane. It is
known that for any subset M 0 ⊂ M , which has no more than 9 points, can be covered
by two translations of the triangle ∆. Prove that the entire set M can be covered by
two translations of ∆.
Solution: (Andreis, Claude) Let us consider the smallest equilateral triangle
A1 A2 A3 that contains all of M -s point inside or on the boundary, and is homothetical
with ∆. Obviously it contains on each side a point of M . It is possible that one of
the vertices of the triangle ABC is a point of M , but that can only work in our favor.
So let us denote the three points by P1 , P2 and P3 , such that Pi ∈ Ai−1 Ai+1 , where
all indices are taken modulo 3.
For each side Ai−1 Ai+1 we consider a translation ∆i of ∆ which has a side parallel
to it, and the opposite vertex in the opposite vertex of the triangle A1 A2 A3 . Also for
each of these 3 triangles, let us consider the points Qi and Ri such that if we draw
through them parallel lines qi and ri with Ai−1 Ai , and respectively with Ai+1 Ai , every
point of M which lies between the lines qi and Ai−1 Ai , respectively ri and Ai+1 Ai lies
inside ∆i .
Therefore we obtain at most 9 points, which by the statement of the problem can be
covered by two translations of ∆, say T1 and T2 . By the pigeon-hole principle, two of
the Pi -s are covered by the same translation. Suppose WLOG that they are P2 and
P3 , and they are covered by T1 . It is easy to see that the translation T1 has no reason
to exceed the boundaries of A1 A2 A3 so it must also cover A1 , and it also does not
cover anything beyond ∆1 .
Now, P1 , Q1 and R1 must be covered by T2 . Taken any other point of M , not already
covered by T1 . It cannot lie between the lines q1 and A1 A2 , nor between r1 and A1 A3 .
But A2 A3 , r1 and q1 determinate an equilateral triangle, which has on each side a
point of M , so it must be covered entirely by T2 . Thus we have proved that T1 and
T2 cover all of M ’s points, and we are done.
Comments. Similar solutions, based on the same idea, were presented by Andrei Negut,
Toumaf, Octavian Ganea. Difficult problem to write, based on a nice idea, this problem
is the work of V. Dolnikow and R. Karasev, Russia.
3. In a country there are 100 cities, some of which are connected by roads. For each four
cities there are at least two roads between them. Also, there is no path that passes
through each city exactly one time. Prove that one can choose two cities among those
100, such that each of the 98 remaining cities would be connected by a road with at
least one of the two chosen cities.
Before beginning the solutions, I will add that everyone considered the graph G with
100 vertices, with the property that any 4 vertices are connected by at least 2 edges.
Solution 1: (Andrei Negut) As usual he begins with two lemmas:
Lemma 1. If a subset M of our graph is not connected with a certain vertex X then
M is a complete sub-graph, with some disjoint edges missing (disjoint means that they
have no common vertex).
Proof of lemma 1. Suppose that there exists a vertex in M unconnected by two other
vertices in M (that would contradict our statement of the lemma). Then considering
those 3 vertices and X we would obtain a 4-subgraph of G with only one possible edge,
which is a contradiction. Thus the lemma is proved. Further more, we observe that
if |M | is odd, then there exists a vertex A in M connected to all the other vertices in
6
M (because the disjoint edges imply an even number of heads). If |M | is even then
there exists a vertex B in M connected to all vertices in M but one.
Lemma 2. If C is one of the cycles of G with maximal length, then it is composed of
at least 7 vertices.
Proof of lemma 2. Suppose that each cycle in G is composed of at most 6 vertices.
If some vertex X of G is not connected with 7 other vertices, we are done, because,
from lemma 1, those 7 vertices would form a complete graph without 3 edges, from
which we can easily extract a hamiltonian cycle.
Therefore all vertices of G have the degree at least 93. We can easily construct a cycle
of length 7 using the pigeon-hole principle: if some X1 is connected to X2 , . . . , X94 ,
then X2 is connected with at least 87 of these 93 vertices, some X3 of these 87 is
connected with 87-6=81 vertices of those 87, ... , until some X6 is connected some 65
vertices from the original 93, and one of these 65 vertices is connected with X1 , say
X7 . We have obtained a cycle.
Comment. Using Turan’s Theorem we can easily see that we can actually find a
complete graph with 7 vertices in the case deg(x) ≥ 93, for all x ∈ G.
Getting back to our original setback, let us suppose that no two vertices from G which
have the property from the enounce. Let us consider a cycle C of maximum length.
If C would contain all the vertices, we would contradict the hypothesis. This means
that there exists a vertex X which is not found in C.
If X is connected with at least 3 vertices of C, say D, E, F (written counter-clockwise
on the cycle). If any two of the vertices D, E, F would be consecutive in the cycle,
then X could also join the cycle, which would contradict our maximality assumption
over C.
So, let us consider the points D0 , E 0 , F 0 which are consecutive to D, E, F respectively
on C, going counter-clockwise. Obviously X is not connected with either of D0 , E 0 , F 0 .
So the three points will have at least two edges among them. Suppose WLOG that
D0 is connected with both E 0 and F 0 .
It is easy to check that we have obtained a larger cycle, which includes X, following
the path: from D0 to E on C in counter-clockwise way, from E to X, the X to D,
from D to E 0 in clockwise direction, and from E 0 back to D0 , which is a contradiction.
Therefore any X not belonging to C is connected with at most two vertices in C. Let
us denote with B the set of points in G not belonging to C and let us prove that B is
a complete graph.
Suppose that X, Y ∈ B are not connected. As they together connect to at most 4
vertices of C, let us consider A, B ∈ C, two points which are not among those 4, points
which exist in base of the lemma 2. But then we would have 4 points (X, Y, A, B) in
G that can be connected only by one edge AB. Thus our supposition is false, and B
is a complete graph.
7
Now, let us define a function f : B → {0, 1, 2}, given by f (X) equals the number of
vertices in C with which X is connected. We have two major cases:
Case 1: If B has but one element X. If f (X) = 0, then all of the 99 vertices of C
will not be connected with X, and from lemma 1, we infer that, since 99 is odd, there
is a vertex Y ∈ C connected to all vertices in C − {Y }. Choosing X and Y solves our
problem.
If f (X) = 1, then X is connected with Y ∈ C, and considering the other 98 vertices
of C and using lemma 1 again, we obtain that these 98 vertices form a complete sub-
graph, from which some disjoint edges are missing. Let us consider a neighboring
vertex of Y in the cycle C, say Z. If Z is connected with all the other 97 vertices, then
choosing Y and Z solves the problem. Otherwise, there is some point T among those
97 with which Z is not connected. But from T only one edge can be missing from the
complete subgraph formed with the 98 vertices, so besides Z, T is connected with all
the other 96 remaining vertices. Choosing Y and T solves the problem.
Now if f (X) = 2, then X is connected with Y, Z from C, and by lemma 1, there is
a vertex T among the remaining 97 vertices, which is connected with all of the 96
vertices. Obviously choosing X and T solves the problem, and case 1 is over.
Case 2: If B contains more than 2 vertices, let us consider two of them X, Y ∈ B.
They can be connected with at most 4 elements of C. So, for each A, B in C which
are not among those 4 points, A and B must be connected. Otherwise we would have
one edge (XY ) between 4 distinct vertices, which is absurd.
Let M be the set of points from C which is connected with X, and N the set of points
in C − M which is connected with Y . By lemma 1, the set C − M is a complete graph
without some disjoint edges, and C − M − N is a complete graph (proved above). The
last set contains at least 3 vertices (from lemma 2), and at least one of these three, say
Z, is connected with all the vertices from N , because N contains at most 2 elements.
Because Z is also connected with all the points from C − M − N we can choose X and
Z and the problem is solved.
Solution 2: (Iandrei) Let V (G) be the set of vertices of G and E(G) be the set of
edges of G. For x ∈ V (G), let d(x) be the number of elements of the set:
N (x) = {y ∈ V (G)|y 6= x, (xy) ∈ E(G)}.
Let us first start with a lemma:

Lemma. Let k ∈ N and f : {y1 , y2 , . . . , y2k+1 } → {y1 , y2 , . . . , y2k+1 } be an injective,
involutive function. Then f has a fixed point.
Proof of lemma. We prove this by induction on k. For k = 0 it is clear that f (y1 ) = y1
and we are done.
Assume that it is true for k and let us prove it for k + 1. Take an arbitrary element
y and y 0 = f (y). If y = y 0 then we are done. Otherwise, notice that y 0 = f (y) and
consider the set
M = {y1 , y2 , . . . , y2k+3 } − {y, y 0 }.
There is no x ∈ M such that f (x) ∈ / M , or else we would contradict the fact that f
is injective (we would have f (x) = f (y) or f (x) = f (y 0 ), but x ∈
/ {y, y 0 }).
Consider the function f1 : M → M such that f1 (x) = f (x), ∀ x ∈ M . Applying
the induction hypothesis to the function f1 and to the set M we find that there is an
8
x0 ∈ M such that f1 (x0 ) = x0 , or equivalently f (x0 ) = x0 . Thus it is also true for
k + 1.
Getting back to our original problem, let us consider the chain of maximal length and
assume that it is (x1 , x2 , . . . , xk ). We have two main cases:
Case 1: We have an edge between x1 and xk . Then the chain is a cycle (k ≥ 2).
Assume that k ≤ 98. Then there are at least two vertices which are not part of the
chain, call them y and z. For each i, 1 ≤ i ≤ k, (yxi ) ∈
/ E(G) and (zxi ) ∈
/ E(G). If
there was such an i, then we would find a longer chain:
(y, xi , xi+1 , . . . , xk , x1 , . . . , xi−1 ) or (z, xi , xi+1 , . . . , xk , x1 , . . . , xi−1 )
Consider the quadruple {xi , xj , y, z} for some i 6= j. Since
(yxi ), (yxj ), (zxi ), (zxj ) ∈

/ E(G)
it follows that (xi xj ), (yz) ∈ E(G). Moreover, since i and j were arbitrarily chosen,
we have that the vertices x1 , x2 , . . . , xk span a complete subgraph Kk = G1 of the
given graph.
Also since y and z were arbitrarily chosen from the remaining 100 − k vertices, it
follows that they also form a complete K100−k = G2 subgraph. Now take an arbitrary
vertex u ∈ V (G1 ) and v ∈ V (G2 ). They obviously satisfy the required condition.
If k ≥ 99, since we also had k ≤ 99 (there is no chain containing all the vertices by the
hypothesis), we infer that k = 99. Thus our graph is composed of a cycle of length 99
and another vertex y. This vertex y is obviously not connected to any of the xi ’s by
the previous observation.
If there exist i < j such that (xi xj ) ∈/ E(G) then take l such that l ∈ {1, 2, . . . , n} −
{i, j} and consider the quadruple {y, xi , xj , xl }. We have that (xi xj ), (yxi ), (yxj ),
(yxl ) ∈
/ E(G), thus (xi xl ), (xj xl ) ∈ E(G). Thus it easily follows that xi and xj are
each connected to all the remaining 97 vertices in the cycle.
We now prove that there must be u ∈ {1, 2, . . . , 99} such that xu is connected with
all other xi . Assume that it is not true. Then for each i there is a f (i) such that xi is
not connected to xf (i) and is connected to the rest of the vertices forming the cycle.
Also f is well defined because for every i, there is a unique j such that xi xj ∈ / E(G).
Let us notice that f (i) 6= i, for all i. It is obvious that if f (i) = j then f (j) = i.
Assume that f is not injective. Then there are i1 6= i2 such that f (i1 ) = f (i2 ) = j.
But that means f (j) = i1 = i2 , a contradiction.
From the lemma above it follows that f has a fixed point, which is a contradiction
with the definition of f and we are done.
Case 2: If (x1 xk ) ∈
/ E(G). Assume that k ≤ 98. Then take y, z such that they are
not part of the chain. Now, for every vertex u not in the chain, (ux1 ), (uxk ) ∈
/ E(G).
Otherwise there would be a longer chain
(u, x1 , x2 , . . . , xk ) or (u, xk , xk−1 , . . . , x1 ).
Now, consider the quadruple {y, z, x1 , xk }. We have that (x1 xk ), (yx1 ), (yxk ), (zx1 ),
(zxk ) ∈
/ E(G) so there is only at most one edge formed between these 4 vertices, which
is a contradiction. Thus our assumption was false and thus k = 99.
9
Let us denote the remaining vertex with y. We see that it is not possible for y to be
connected with 2 consecutive vertices xi and xi+1 or otherwise there would be a chain
containing all elements of the graph (x1 , x2 , . . . , xi , y, xi+1 , . . . , x99 ).
If a vertex xl ∈ / {x1 , x99 } is not connected to y, then let us consider the quadruple
{y, x1 , x99 , xl }. And since (yx1 ), (yxk ), (x1 xk ), (yxl ) ∈
/ E(G) it follows easily that xl
is connected to both x1 and x99 .
If there is l ∈ {3, 4, . . . , 97} such that yxl ∈ E(G) then by a previous observation,
(yxl−1 ), (yxl+1 ) ∈/ E(G) so x1 and x99 are both connected to both xl−1 and xl . Since
in the quadruple {x1 , xl , x99 , y} there must be at least one more edge, it can only be
either (x1 xl ) or (x99 xl ).
Suppose without loss of generality that it is (x1 xl ). Then the chain
(y, xl , x1 , x2 , . . . , xl−1 , x99 , x98 , . . . , xl+1 )
contains all the vertices of the graph, contradiction.
Let us now study the case (yx2 ) ∈ E(G) and the study of (yx98 ) ∈ E(G) will be
analogous. Then by a previous observation, (yx3 ) ∈
/ E(G) so we infer that (x1 x3 ),
(x99 x3 ) ∈ E(G). Then we have the chain
(y, x2 , x1 , x3 , x4 , . . . , x99 )
which contains all the vertices of the graph, a contradiction.
Because y can neither be connected x1 nor to x99 we infer that for all i, 1 ≤ i ≤ 99,
y is not connected with xi . Also from this it follows that
(x1 xl ), (x99 xl ) ∈ E(G), ∀ 2 ≤ l ≤ 98.
If {xi , xj } 6= {x1 , x99 } and (xi xj ) ∈/ E(G) then let us consider the quadruples
{y, xi , xj , xl }, for l ∈
/ {i, j}. We have that (yxi ), (yxj ), (yxl ), (xi xj ) ∈
/ E(G) so it
follows from here that (xi xl ), (xj xl ) ∈ E(G). So if xi is not connected to all vertices
in the chain,then it is connected to all but one. Let us prove that in this case there is
u such that d(xu ) = 98.
Suppose that there is no such u. Define the function f as in the previous case, (notice
that f (u) exists for every u or otherwise we would be done), and let us prove that it is
also injective in this case. If i1 6= i2 such that f (i1 ) = f (i2 ) = j, then f (j) = i1 = i2 ,
which is a contradiction.
Thus f is injective, in this case also. Notice how we have f (1) = 99 and vice-versa.
Moreover f is an involutive function from a finite set with odd number of elements
to itself, which is injective. From the lemma above it follows again that f has a fixed
point and we have reached a contradiction.
Thus in this case there is u such that xu is connected to all other xi , so if we take y
and xu they form a solution, and the problem is solved.
Comments. The problem was solved by Claude and Octavian Ganea following the
same steps as above, with minor modifications. This beautiful problem was created by
I. Ivanov, Russia.
Last updated at November 23, 2003.

10
Round 5
October 27 - November 9, 2003
1. For which positive integers n ≥ 4 one can find n points in the plane, no three collinear,
such that for each triangle formed with three of the n points which are on the convex
hull, exactly one of the n − 3 remaining points belongs to its interior.
3
2. Let S be the set of positive integers n for which cannot be written as the sum of two
n
1
rational numbers of the form , where k is a positive integer. Prove that S cannot
k
be written as the union of finitely many arithmetic progressions.
3. Let n ≥ 3 and σ ∈ Sn a permutation of the first n positive integers. Prove that the
numbers σ(1), 2σ(2), 3σ(3), . . . , nσ(n) cannot form an arithmetic, nor a geometric
progression.

1
Last updated on November 3, 2003.
Round 5
1. For which positive integers n ≥ 4 one can find n points in the plane, no three collinear,
such that for each triangle formed with three of the n points which are on the convex
hull, exactly one of the n − 3 remaining points belongs to its interior.
Solution 1: (Andrei Negut) Considering a triangulation of the convex hull with
k vertices we find that each of the k − 1 disjoint triangles contains exactly one of the
n points inside, thus n = 2(k − 1), thus n is even.
We begin (as usual) with the following lemma:
Lemma. For all positive integers k ≥ 3 there exists a convex polygon with k vertices
and k−2 points in its interior such that any 3 points are not collinear and any triangle
formed with 3 vertices of the polygon contains at least one of the k − 2 points in its
interior.
Proof of lemma. Let us consider an arbitrary convex polygon with k vertices A1 A2 . . . Ak .
Let us choose a point Bj , for each j = 3, k, inside the intersection of the interiors of
the triangles Aj−1 Aj Aj+1 and Aj A1 A2 . We have obtained k − 2 points, and we shall
prove that these are good for our lemma.
Indeed, consider a random triangle Ar As Ap , with {r, s, p} ⊂ {1, 2, . . . , k}. Since A1
and A2 are connected by a side of the polygon, they can be found between Ar and As ,
or As and Ap , or Ap and Ar (maybe they will coincide with some of them). Suppose
that Ar , A1 , A2 , As lie in this order on the polygon. Then the point Bp lies inside the
triangle Ar As Ap (because it lies inside the triangle A1 A2 Ap also) and the lemma is
proved.
Now back to our problem, let n = 2k, with k ≥ 2. We have shown in the lemma above
that there exists a convex polygon with k + 1 vertices and k − 1 points inside such
that any triangle formed with 3 of the k + 1 points contains at least one of the k − 1
points inside. Let us prove that it can only contain one point exactly.
Suppose there there would be a triangle ∆ with 2 points of those k − 1 inside it. Let
us triangulate the polygon, in such a way that one of the triangles is ∆ (this is always
possible). Each of the remaining k − 2 triangles from the triangulation must have a
point from those k − 1 inside, but then we would need at least k − 2 + 2 = k points,
contradiction, and we are done.
Solution 2: (Andreis) As Andrei Negut showed above, Andreis proves that n must
be even.
We shall prove that each even n ≥ 4 works. We shall prove the previous statement
through induction after k.
For n = 4 take a right angled triangle A1 A2 A3 , with the right angle in A1 and a point
B1 inside, in a circle of radius ε > 0 with center in A2 . Further on consider the square
A1 A2 A4 A3 , and take another point B2 inside the added triangle, in a circle of radius
ε with center in A3 (see the figure). Obviously these 6 point verify the hypothesis.
Let us consider now A5 and A6 such that A4 A3 A5 A6 is an isosceles trapezoid, with
A3 A4 > A5 A6 and points B3 and B4 in the triangles A3 A4 A5 and respectively A4 A5 A6 ,
inside disks of radius ε with centers in A4 and A5 respectively. Notice that the
construction is done in two steps, each time adding two more points.
Therefore we construct inductively a convex polygon with n vertices Ai , having n − 2
points inside Bi . We shall prove that these points fulfill the hypothesis, for a small
enough ε. Suppose by induction that we have proved that this structure works for n,
and let us prove that it also works for n + 1.
All the triangles formed with points from the set {A1 , A2 , . . . , An } are good. Let us
check triangles that contain the newly added An+1 , say An+1 Ai Aj , i < j. It is obvious
that the point Bj−1 lies inside the angle ∠Aj−1 Aj Aj+1 , that means that it also lies
inside ∠Ai Aj An+1 , and for sufficiently small ε, also lies inside the triangle An+1 Ai Aj .
It is easy to check that no other point of Bi -s can lie inside the triangle An+1 Ai Aj .
If i ≤ k < j, then the lines An+1 Ai and Ai Aj cut the interior of the convex polygon
A1 A2 . . . An+1 and leaves outside the triangle An+1 Ai Aj the points Ai+1 , Ai+2 , . . . , Aj−1
(if they exist at all), and of course the corresponding Bk−1 -s are left outside of the
triangle also (being very close to Ak -s). Same reasoning works for k < i and k > j.
Solution 3: (Fedor Bakharev) Let convex hull of the set be a k-gon A1 A2 . . . Ak .
Split this k-gon by diagonals, coming out from A1 on k − 2 triangles. On condition
in each of them lie exactly one point we obtain that n = 2k − 2. Thereby for uneven
n such ensembles of points on planes does not exist.
For even n we will build by induction such ensemble of points on planes, satisfying
condition of the problem. The base of induction for n = 4 is obvious. Let n = 2k − 2
and suppose that for it required ensemble is already built.
Let A1 A2 . . . Ak be the convex hull of this ensemble. The points B1 , B2 , . . . , Bk−2 lie
in its interior. We will choose Ak+1 so that A1 . . . Ak+1 is a convex polygon and Ak+1
lies very close to Ak and also such that we have that Bj , j ≤ k − 2, belongs the
interior of a certain triangle Ap Aq Ak , 1 ≤ p < q ≤ k − 1, if and only if it belongs the
interior of the triangle Ap Aq Ak+1 . If we denote by O the intersection of the diagonals
in the quadrilateral Ak Ak+1 Ap Aq , then that Bj lies inside the triangle Ap OAq , which
means that the triangles of the form Ap Ak Ak+1 do not have a single point from the
set B1 , . . . , Bk−2 inside.
We will add in the interior of A1 . . . Ak+1 a point Bk−1 , lying very close to the middle
point of the segment Ak Ak+1 . Then Bk−1 will fall into all triangles of type Ai Ak Ak+1 ,
but not into triangles of type Ap Aq Ak or Ap Aq Ak+1 .
Therefore we have built the example for n + 2 points are we are done.
Comments. Also elegant solutions, based on induction were presented by Claude,
Octavian Ganea and Iandrei. This problem was proposed at the Kurschak contest in
1998.
2
3
2. Let S be the set of positive integers n for which cannot be written as the sum of two
n
1
rational numbers of the form , where k is a positive integer. Prove that S cannot
k
be written as the union of finitely many arithmetic progressions.
Solution 1: (Fedor Bakharev) If a number n has a prime divisor of the form
3 1
6s − 1, then n ∈/ S. Indeed, if n = m(6s − 1) then in this case = +
m(6s − 1) 2sm
1
.
2sm(6s − 1)
3
Moreover if n is a prime number of the form 6s + 1, then n ∈ S. Indeed, let =
n
1 1 k+l
+ = . One of the numbers k, l is divisible by n. Without loss of generality
k l kl
suppose that k = nt. Then 3tl = nt + l. Consequently t | l.
Let l = tl1 , then 3tl1 = n + l1 . Therefore l1 is a divisor of n, then or l1 = 1, or l1 = n.
In the first case n ≡ −1 (mod 3), one contradicts the choice n, but in the second
case 3t = 2 we have a contradiction. Therefore, there are infinitely many elements in
S.
We will expect that S can be written as the union of finitely many arithmetic pro-
gressions. Progressions with non-zero ratios form a non-empty set, because there are
infinitely many elements in S. Consider such an arithmetic progression and its first
terms: a1 , a2 , . . . , am . Put p = 6d − 1. While gcd(p, d) = 1, then there exists k such
that kp ≡ a1 (mod d). So kp lies in the progression, but does not lie in S thus we
have obtained the required contradiction.
Solution 2: (Iandrei) First let us prove that n is in S if and only if n is either 1
or it has only factors from 3Z + 1 in its decomposition.
If 3 divides n, then there exists m ∈ N such that n = 3m. In this case, we have
3 1 m+1 1 1
= = = +
n m m(m + 1) m(m + 1) m + 1
If there exists a prime number p ∈ 3Z + 2 such that p | n, then there is q ∈ N such

that n = pq. Thus, we have
3 3 3(p + 1) p+1 1 1
= = = p+1 = p+1 + p+1
n pq (p + 1)pq pq 3 q 3 pq 3
It is clear that n = 1 cannot be represented in the given form. If it could, let a and b
be positive integers such that :
3 1 1 1 1
= + ⇒3= + ≤2
n a b a b
which is obviously a contradiction.
Now let us prove that if n has factors only from 3Z + 1, then it cannot be represented
in the given form. Assume the contrary, and let a and b be positive integers such that
3 1 1 3ab
= + ⇒n=
n a b a+b
Let d = gcd(a, b) and a = da1 , b = db1 with gcd(a1 , b1 ) = 1.
3d2 a1 b1
n∈N⇒ ∈ N ⇒ a1 + b1 | 3da1 b1
d(a1 + b1 )
3
But since gcd(a1 , b1 ) = 1 it is easy to see that gcd(a1 + b1 , a1 b1 ) = 1, thus
k(a1 + b1 )
a1 + b1 | 3d ⇒ (∃)k ∈ N, 3d = k(a1 + b1 ) ⇒ d =
3
ka1 (a1 + b1 ) kb1 (a1 + b1 ) 3ab
In this case we have a = ,b = ⇒n= = ka1 b1 .
3 3 a+b
Since a1 and b1 divide n, it follows that a1 + b1 = 2(mod 3) so 3 cannot be a divisor
of a1 + b1 . Also, since k divides n, gcd(k, 3) = 1. Thus d ∈ / Z, a contradiction. This
means that our assumption was false, and consequently, n cannot be written in the
given form.
It is clear that S is infinite since all powers of 7 are in S. Now, let us consider an
arithmetic series with terms in S : let a be its starting term and d be its ratio. Assume
that it is infinite. Since all its terms are in 3Z + 1, it follows that d ∈ 3Z, a ∈ 3Z + 1.
Let p be a prime number p ∈ 3Z + 2 larger than d (it is well-known that an infinite
number of primes of the form 3k + 2 exist) . It is clear that gcd(p, d) = 1. Thus d is
invertible in Zp , or equivalently, (∃)q ∈ N such that dq = 1(mod p). Taking N ∈ N
large enough and working modulo p we find that
X = a + d(pN − qa) = a − dqa = a − a = 0
Thus the number X is a term of the arithmetic series but is not in S (because it is
divisible by p), a contradiction. So any arithmetic series with terms in S has a finite
number of terms. Assume that S can be written as the union of a finite number of
arithmetic series. Using the earlier observation, this means the given series can cover
only a finite number of elements of S. Since we have already established that S is
infinite, we have reached a contradiction.
Comments. The problem is rather simple, but I think it’s quite nice. It was proposed
for IMO in 1982.
3. Let n ≥ 3 and σ ∈ Sn a permutation of the first n positive integers. Prove that the
numbers σ(1), 2σ(2), 3σ(3), . . . , nσ(n) cannot form an arithmetic, nor a geometric
progression.
Solution 1:(Andrei Negut) Let us first prove that we cannot have a constant
sequence. Let a0 , a1 , . . . , an−1 be the terms of the sequence. But σ(1) ≤ n ≤ nσ(n)
so we must have σ(n) = 1, thus σ(n − 1) ≥ 2, which means that (n − 1)σ(n − 1) ≥
2(n − 1) ≥ n + 1 and we are done.
To prove now that {ai }i are not in geometric progression, let us consider that they
p
actually are forming one progression with ratio , with p, q co-prime integers, and
q
p > q ≥ 1 (it cannot be a constant progression as shown above). We have an−1 =
n−1
a0 pqn−1 , thus q n−1 | a0 and pn−1 | an−1 . But an−1 ≤ n2 ⇒ 2n−1 ≤ pn−1 ≤ n2 ⇒ n ≤ 6,
p = 2, and as a0 ≤ n it follows that q = 1, so the ratio would be 2. An easy check for
n = 3, 4, 5, 6 shows that we cannot have a solution.
Suppose that the numbers can form an arithmetical progression, and take them to be
a + kr, where r is the ratio, and a is the smallest number. Obviously r is a positive
integer, and k runs from 0 to n − 1. If r ≥ n + 1, then n2 ≥ a + (n − 1)r ≥ a + n2 − 1 ⇒
a = 1, so σ(1) = 1, and σ(n) = n, r = n+1, but then an−2 = n2 −n−1 > n2 −2n+1 ≥
kσ(k), for all 2 ≤ k ≤ n − 1, contradiction.
Thus r ≤ n, which means that there is a positive integer p, p ≤ n such that σ(p) = r,
which means that some ai is divisible by r, thus a is divisible by r. If r > 2, then let
4
jnk
d= , and consider the 2d numbers 1, r + 1, . . . , (d − 1)r + 1, r − 1, 2r − 1, . . . , dr − 1.
r
All of these numbers are co-prime with r, thus r must divide σ(i) for any i among
those 2d numbers. But σ(i) cannot take more than d values multiples of r (from d’s
definition), contradiction.
Therefore r = 2, which means that all our numbers are smaller than 2n contradiction,
3
because 1σ(1)+2σ(2)+· · ·+nσ(n) ≥ 1·n+2·(n−2)+· · ·+n·1 ≥ n6 be rearrangement
inequality. The case r = 1 is trivial, and we are done.
Solution 2: (Andreis) We have that kσ(k) ∈ [1, n2 ]. Suppose that the numbers
are in arithmetic progression with ratio r.
It r ≥ n + 1, then the largest number is greater than (n − 1)(n + 1) + s ≥ n2 , where
s is the smallest number from the sequence {kσ(k)}k . The only possible situation
would be s = 1, that is kσ(k) = n2 and obviously k = n. The number before has
kσ(k) = n2 − (n + 1) then kσ(k) ≤ (n − 1) · (n − 1) = n2 − 2n + 1, and we would have
n2 − n − 1 ≤ n2 − 2n + 1 ⇔ n ≤ 2, a contradiction.
Therefore r ≤ n. Atunci iσ(i) ≡ jσ(j) (mod r), for all i, j = 1, n, but
rσ(r) ≡ 0 (mod r) thus iσ(i) ≡ 0 (mod r). Suppose that r > 1 then let p | r
n
be a prime divisor of r. If p 6 | i then it follows that p | σ(i). But there are the
p
n
number of multiples of p in the set {1, 2, . . . , n} thus 2 ≥ n ⇒ p = 2, because for
p
n n
p ≥ 3 we have 2 ≤ 2 < n. Also 2 | n.
p p
That means r = 2k . If k > 1 then iσ(i) ≡ 0 (mod 4), and for i = 2 we have 2 | σ(2),
and for all odd i we have 2 | σ(i) so we would get more even numbers than odd numbers
amongst {σ(1), σ(2), . . . , σ(n)} contradiction. Thus k = 1, and r ≤ 2. But for r = 2,
as iσ(i) 6= nσ(n) for all i, it follows that there exists an i for which iσ(i) ≥= 3n, but
then the smallest of them all would have to be larger than 3n − 2(n − 1) = n + 2. But
σ(1) ≤ n, which is a contradiction.
Therefore we can only have r = 1, but because σ(1) 6= nσ(n), we have that the largest
number of the form iσ(i) is at least 2n, and the smallest is at least 2n−(n−1) = n+1,
contradiction made by i = 1.
Let us now prove the second part, supposing at the beginning that there exists a
m
geometric progression with the given numbers, or ratio q = , with m, n positive
n
co-prime integers. Then 3σ(3)nk = mk jσ(j) for some j, k. We can obviously choose
j such that jσ(j) is not divisible by 3, so we must have 3 | m. But then 3n−1 | iσ(i),
where i is chosen such that iσ(i) ≥ jσ(j), for all j. But iσ(i) ≤ n2 ⇒ 3n−1 ≤ n2
which is a contradiction.
Comments. Not a hard problem, but most of the contestants wrote a lot more than it
was required. The author of the problem is Laurenţiu Panaitopol.
Last updated at January 3, 2004.

5
Round 6
November 9 - November 22, 2003

2002!
1. Determine the parity of the positive integer N , where N = .
2001 · 2003
√
2. A triangle ABC is located in a cartesian plane π and has a perimeter of 3 + 2 3.
It is known that the triangle ABC has the property that any triangle in the plane
π, congruent with it, contains inside or on the boundary at least one lattice point
(a point with both coordinates integers). Prove that the triangle ABC is equilateral.
3. At a party there were some couples attending. As they arrive each person gets to talk
with all the other persons which are already in the room. During the party, after all
the guests arrive, groups of persons form, such that no two persons forming a couple
belong to the same group, and for each two persons that do not form a couple, there is
one and only one group to which both belong. Find the number of couples attending
the party, knowing that there are less groups than persons at the party.

1
Round 6

2002!
1. Determine the parity of the positive integer N , where N = .
2001 · 2003
Solution: Because 2003 is a prime number, by Wilson’s theorem one gets:
2002! ≡ −1( mod 2003). But 2001 · 1001 = 2003001 ≡ 1( mod 2003) ⇒
2002!
≡ 2002! · 1001 ≡ −1001( mod 2003).
2001
2002!
Therefore there exists an integer k such that = k · 2003 − 1001.
2001
2002!
is even, therefore k is an odd number ⇒
2001
2002! 1001
=k− ⇒ N = k − 1 ⇒ N is even, and we are done.
2001 · 2003 2003
Comments. Yeah, I know: probably the easiest problem on the contest by now, but
nevertheless it was my last chance of proposing this 2003-year problem in a contest :)
Obviously all the participants of this round solved it correctly, and in the same way as
me.
√
2. A triangle ABC is located in a cartesian plane π and has a perimeter of 3 + 2 3.
It is known that the triangle ABC has the property that any triangle in the plane
π, congruent with it, contains inside or on the boundary at least one lattice point
(a point with both coordinates integers). Prove that the triangle ABC is equilateral.
Solution 1: (Andreis) We observe that
√ r √
p2 3 p p(3p − a − b − c)3 p2 3
S≤ ⇔ p(p − a)(p − b)(p − c) ≤ =
9 27 9
and equality holds if and only if a = b = c, where p is the semi-perimeter of the
triangle.
The inscribed square in the triangle has edge x and lies on the largest side, say a.
(notice that we can always inscribe a square into a triangle - a simple observation of
continuity of inscribed rectangles).
ha − x x 1 1 1 a 1 1 a2 a
We have that = ⇔ + = ⇔ + = ⇔ − + 1 = 0.
ha a ha a x 2S a x 2S x
√
It is easy to check that for the equilateral triangle with perimeter 3 + 2 3 and area
S we have x = 1.
If ABC is not equilateral than its area is smaller than S and let A1 B1 C1 be a triangle
similar to ABC with area S. Obviously if ABC is a good triangle then A1 B1 C1 is a
good one too. Consider a1 to be the largest side of A1 B1 C1 . Then from similarity
x 1
a1 > a. But the function f (x) = + is increasing on [a, ∞) because its derivative
2S x
1 1
is f 0 (x) = − > 0 ⇔ x2 > 2S 2 . But from the inequality proved above, and using
2S x2 √
3 p2 3 9 3 3
the fact that p ≤ a, we observe that 2S < ≤ · a2 · = a2 < a2 ≤ x2 , for
2 9 4 9 4
all x ≥ a.
Then the edge x1 of the inscribed square in A1 B1 C1 is smaller than 1 is equivalent
a1 2
with − a1 + 1 > 0 which is true because f (a1 ) > f (a) = −1.
2S
It is easy now to check that 2x1 > h1 (the altitude corresponding to the largest side),
and thus we can put B1 C1 parallel with the axis (Ox at distance x1 < 1 such that
the inscribed square has no lattice point inside or on the boundary and since h1 < 2,
the triangle A1 B1 C1 has no lattice point inside, which means that and ABC is not a
good triangle too, which is what we wanted to prove.
Solution 2: (Toumaf) Let Ha , Hb , Hc be the foots of the altitudes of the triangle
ABC respectively opposed to A, B, C. Any triangle congruent with ABC which has
the side [BC] on the (Ox axis must contain at least one unit point, so we can easily
see that ABC must contain a square of unit side with its side on [BC].
(AHa − 1)BC
We then have, by Thales’ theorem ≥ 1. By calling S the surface of
AHa
2S
ABC and a the length BC, we get 2S = AHa · BC ≥ AHa + BC = + a. The
a
number a, being a length of a side of a non-degenerated triangle, is strictly positive,
so
a2 − 2Sa + 2S ≤ 0.
p p
We can easily see that a ∈ [S − (S(S − 2)), S + (S(S − 2))] and S ≥ 2. By a
similar argument we get that b and c, the lengths of [AC] and [AB], are in the same
interval.
We know that S, being the surface of ABC, can be expressed in means of a, b and c:
p
S = p(p − a)(p − b)(p − c),
a+b+c 3 √
with p = = + 3 (actually this formula is called Herron’s Forumula).
2 2
For a fixed perimeter, the biggest surface is achieved by the equilateral triangle
(basically the same inequality as in the above solution), with a surface of:
√ √
2 2

3 7 3
Smax = 1+ √ =1+
4 3 12
" √ # " √ #
7 3 3 2
We then have S ∈ 2, 1 + . We obtain that a, b and c are in 1 + ,1 + √ ,
12 2 3
√ 2
but a + b + c = 3 + 2 3, so a = b = c = 1 + √ which means that ABC is equilateral.
3
Comments. This problem was proposed by I. Voronovich at the Belarussian Olympiad
in 1998.
2
3. At a party there were some couples attending. As they arrive each person gets to talk
with all the other persons which are already in the room. During the party, after all
the guests arrive, groups of persons form, such that no two persons forming a couple
belong to the same group, and for each two persons that do not form a couple, there is
one and only one group to which both belong. Find the number of couples attending
the party, knowing that there are less groups than persons at the party.
Solution 2: (Andreis) Let a1 , a2 , ..., a2n the people and ki the number of groups
which ai belongs to, m the number of groups, Ai the groups and si the number
elements. We shall denote the pair element of ai by ai . It is clear that if ai ∈
/ Aj
than ki ≥ sj , if ai ∈
/ Aj and ki ≥ sj − 1 otherwise, and we also have
2n
X m
X
ki = sj (1)
i=1 j=1
We may assume k2n ≤ ki , a2n ∈ A1 , . . . , Ak2n and ai ∈ Ai for i ≤ k2n . It is clear that
n = 1 is as good value, n = 2 is not, so we have to consider only the cases when n ≥ 3.
If k2n = 2 we have (n − 1)(n − 2) + 2 < 2n ⇒ n = 3(if ai ∈ A1 then ai ∈ A2 and it
must meet with all the elements of A2 but ai in another group). We have the groups:
(1, 3, 6), (1, 4, 5), (2, 3, 5), (2, 4, 6).
We can suppose k2n ≥ 3. We have ki ≥ sj for i, j ≤ k2n , i 6= j and ai ∈ / Aj and
ki ≥ sj − 1 if ai ∈ Aj , since ai belongs to exactly one Aj . By adding them we obtain:
k2n
X k2n
X
(k2n − 1) ki ≥ −k2n + (k2n − 1) si
i=1 i=1
or since k2n ≥ 3 and the sums are integers:

k2n
X k2n
X
ki + 1 ≥ si (2)
i=1 i=1
On the other hand k2n ≥ sj , j > k2n or k2n ≥ sj − 1. We may assume m < 2n. Since
ki ≥ k2n by adding we have:
m
X m
X
sj ≤ (m − k2n )k2n + k 2n ≤ kj + k 2n (3)
i=k2n +1 j=k2n +1
By adding (2) and (3) and using ki ≥ 3 we have m = 2n − 1(otherwise:

2n
X m
X
ki > sj
i=1 j=1
contradiction with (1)).

Now we have to improve (3). Let α > k2n , kα 6= k 2n . Since k 2n ≥ 3 there is al
least one set a2n ∈ Aα1 such that none of aα , aα belongs to it, and we can improve
by 1 (3)(kα > sα1 , while k2n was ≥). If k 2n ≥ 4 we can do the same again we can
improve by 2 (3) and by adding (2), (3) we get:
2n
X m
X
ki ≥ 1 + sj
i=1 j=1
3
which is a contradiction. If k 2n = 3 then k2n = 3 and we get s1 , s2 , s3 ≤ 4 and since
we have 2n elements we have that n = 5. Since ai ∈ Aα1 only if ai , ai ∈ {a1 , a2 , a3 }
and sα1 ≥ 3 we have that ai , ai ∈ Aα1 which is a contradiction.
Solution 2: (Fedor Bakharev, Andrei Negut) Let the number of groups be
m and the number of couples be n. Match each person, received to evening party a
vector from Rm in the following way: if it falls into k-th group, that k-th coordinate
of this vector is 1, otherwise it is 0. Let uj , vj be a pair of vectors, corresponding to
j-th couple.
Let us first consider the case in which |uj |2 > 2, |vj |2 > 2 for 1 ≤ j ≤ n. The
hypothesis can be translated into the following 4 relations among the vectors:
1) (uk , vj ) = 1 for k 6= j; 2) (uk , uj ) = 1 for k 6= j;
3) (vk , vj ) = 1 for k 6= j; 4) (uk , vk ) = 0.
where by (·, ·) we have denoted the inner (scalar ) product in Rm .
Since there are 2n > m vectors u1 , . . . , un , v1 , . . . , vn linear dependent, there exist
ai , bi not all simultaneously equal to zero such that
Xn n
X
ai ui + bi vi = 0.
i=1 i=1
X
Multiplying this equality with uj we get that aj |uj |2 = − (ai + bi ), and similarly
i6=j
X
bj |vj |2 = − (ai + bi ). Consequently, aj and bj have the same sign.
i6=j
n
X
2 2
Furthermore, aj (|uj | − 2) + bj (|vj | − 2) = − (ai + bi ).
i=1
Since |uj |2 > 2, |vj |2 > 2, it follows that the sign of aj and of bj is the opposite sign
Xn
of (ai + bi ). This is valid for all j ≤ n, thus aj = bj = 0 for all j which disagrees
i=1
with our supposition.
We have obtained that |u1 |2 ≤ 2. This means that the corresponding person enters
not more, than in two groups. But it must fall into some group with u2 and with v2
and these groups are different (u2 and v2 can not fall into one group). So, in case
n ≥ 2 we surely have that |u1 |2 ≥ 2. It remain to study the case in which |u1 |2 = 2.
In this case, corresponding to person enters in two groups exactly. Without loss of
generality it is possible to consider that this groups are A = {u1 , u2 , . . . , un } and
B = {u1 , v2 , . . . , vn }. But then the couples uj , vi for 2 ≤ j ≤ n, 2 ≤ i ≤ n, i 6= j
belongs into (two by two) different groups, different from A and B. Consequently
m ≥ 2 + (n − 1)(n − 2). Since m < 2n, that get that 2n < n2 − 3n + 4 that is to say
n2 − 5n + 4 < 0. So n =∈ {1, 2, 3}.
It is easy to check that these values of n are solutions. We only give for n = 3 the
groups: A = {u1 , u2 , u3 }, B = {u1 , v2 , v3 }, C = {v1 , u2 , v3 }, D = {v1 , v2 , u3 }.
Comments. Nice and difficult problem. Andrei Negut’s solution used matrices’ product
to give a representation of the relations 1-4 but essentially his solution is the same as
Fedor’s. This problem was on the IMO Shorlist in 1982.

4
Round 7
November 22 - December 5, 2003
1. Fifty students take part in a mathematical competition where a set of 8 problems

is given (same set to each participant). The final result showed that a total of 171
correct solutions were obtained. Prove that there are 3 of the given problems that
have been correctly solved by the same 3 students.
2. Find all positive integers n with the property that n3 − 1 is a perfect square.
3. A convex polygon P can be partitioned into 27 parallelograms. Prove that it can also
be partitioned into 21 parallelograms.

1
Round 7
1. Fifty students take part in a mathematical competition where a set of 8 problems

is given (same set to each participant). The final result showed that a total of 171
correct solutions were obtained. Prove that there are 3 of the given problems that
have been correctly solved by the same 3 students.
Solution 1: (Radu Gologan and Valentin Vornicu) Suppose the students are
1,2, . . . , 50 and the student i solved ni problems, ni ≥ 0, i runs from 1 to 50.
labelled
ni
Then triplets of solved problems by student i are available, where we consider
3
x
= 0 if x ≤ y.
y
By the pigeon-hole principle, in order to have three students with three same solved
problems, it is necessary and sufficient that
50
X ni 8
>2 . (1)
3 3
i=1
To minimize the expression from the left of (1), we shall make use of the following
lemma:
Lemma. For any non-negative integers a, b such that a − b ≥ 2 we have

a b a−1 b+1
+ ≥ + . (2)
3 3 3 3
Proof of lemma. The inequality (2) is equivalent with
a(a − 1)(a − 2) + b(b − 1)(b − 2) ≥ (a − 1)(a − 2)(a − 3) + b(b + 1)(b − 1)
for a ≥ 1 and b ≥ 0. It becomes (a − 1)(a − 2) ≥ b(b − 1) which is obviously true for

a ≥ b + 2. The cases when some of the numbers at the left of (2) are zero ar obvious.
Returning to the original problem, since we need to find the minimum of the sum
50
X
ni , where ni satisfy (1), the lemma implies that we can consider
i=1
n1 = · · · = nr = p + 1 and nr+1 = · · · = n50 = p.

p+1 p
Condition (1) then becomes r + (50 − r) > 112.
3 3
For a minimum value, we are forced to take p = 3, that is 50+3r > 112. The minimum
112 − 50 62
of such an r is the smallest integer greater than = , that is r = 21. In
3 3
that case
n1 + · · · + n50 = 21 · 4 + (50 − 21) · 3 = 171.
and we are done.
Solution 2: (Andreis) We begin with the following
a+b
Lema. Let a, b be two positive integers, a, b > 2, and m = then the following
2
inequality takes place
a b bmc dme
+ ≥ + (1)
3 3 3 3
Proof of lemma. Let a ≥ b, a = m + α, b = m − α, α ≥ 0. Then
a3 − 3 · a2 + 2 · a + b3 − 3 · b2 + 2 · b

a b
+ = =
3 3 6
2 · m3 − 6 · m2 + 4 · m + 2 · α(3 · m − 1)
=
6
1
which is minimal when α is 0 or (if m is even or odd).
2
X50
Let the student i solve ni problems. Using (1) and ni = 171 we have that
i=1
50
X ni 4 3
≥ 21 · + 29 · = 113
3 3 3
i=1

8
By the other hand we have = 56 sets of problems and since 2 · 56 = 112 < 113
3
there are at least 3 students that have solved the same 3 problems.
Solution 3: (Iandrei) Let n1 , n2 , . . . , n50 be the number of problems solved by
student i. The hypothesis tells us that n1 + n2 + . . . + n50 = 171. Call the problems
8
p1 , p2 , . . . , p8 . There are pairs of problems (pi , pj , pk ) with i < j < k. Also, the
3
ni
i − th student successfully solves such pairs of problems. Therefore if we prove
3
that :
n1 n2 n50 8
+ + ··· + ≥2 +1
3 3 3 3
we will be done since there will be a pair of problems solved by at least 3 students,
by the pigeonhole principle (one pair of problems is solved by a single student only
once).
50
X
Given n1 , n2 , . . . , n50 non-negative integers with ni = 171, we have to minimise
i=1
50
X ni
the sum . If there are k numbers equal to 0 and 50 − k non-zero numbers
3
i=1
among n1 , n2 , . . . , n50 ,
then there is at least one non-zero number equal to at least 4.
Otherwise there would be at most 3(50 − k) ≤ 150 < 171 problems solved.
If 2α ≥ 4 is the greatest number among ni then

2α 0 α
+ >2 ⇔ 3α > 0 (1)
3 3 3
2
If 2α + 1 ≥ 5 is the greatest number among ni then :

2α + 1 0 α+1 α
+ > + ⇔ 3α + 3 > 0 (2)
3 3 3 3
In both cases it is clear that we can decrease k and at the same time decrease the sum
(from (1) and (2)), while k > 0. So the sum must be minimal when all the numbers
are non-zero. Now, if there exist ni 6= nj such that ni − nj ≥ 2 then by replacing
ni with n0i = ni − 1 and nj with n0j = nj + 1, let us prove that the new sum will be
smaller :
0 0
ni nj ni nj
+ − − > 0 ⇔ 3(ni − 1)(ni − 2) > 3nj (nj − 1)
3 3 3 3
But ni − 2 ≥ nj ≥ 1 so 3(ni − 1)(ni − 2) ≥ 3(ni − 1)nj , therefore it is enough to prove

that:
3(ni − 1)nj > 3nj (nj − 1) ⇔ ni > nj
which is obviously true.
We now infer that the sum is minimal when k numbers are equal to 3 and the other
50 − k numbers are equal to 4. Let us compute k for which the sum is minimal :
3k + 4(50 − k) = 171 ⇔ 200 − k = 171 ⇔ k = 29
So we have in fact :
50
X ni 3 4 8
≥ 29 · + 21 · = 113 = 2 +1
3 3 3 3
i=1
and we are done by the observation at the beginning.

Comments. Although these three solutions are much alike, I tried to preserve the
wording so that one can see better different types of approaches into a problem which
are based on the same counting idea. This problem is a not-so difficult combinatorics
problem, which was proposed by prof. Radu Gologan and Valentin Vornicu for the
IMO 2003 in Japan.
2. Find all positive integers n with the property that n3 − 1 is a perfect square.
Solution 1: (Valentin Vornicu, Claude) It is easy to check that if n3 − 1 = k 2
then k is even. Indeed let us assume that k = 2r + 1. Then n3 − 1 = 4r2 + 4r + 1 ⇒
n3 = 2(2r2 + 2r + 1) equality that cannot take place.
So k is an even number. Let us consider the equality k 2 + 1 = n3 in the ring Z[i] =
{a + bi : a, b ∈ Z, i2 = −1} (also known as Gauss’ ring). This ring is an euclidian
ring with respect to the norm N (a + bi) = a2 + b2 , thus it is also a GCD ring. In this
ring the elements k + i and k − i are co-prime.
Let us suppose that d | k + i and d | k − i, where d is a non-unit element in Z[i].
Then d | 2i, which means that N (d) | N (2i) = 4, so N (d) ∈ {1, 2, 4}. But d is not
an unit, so N (d) ∈ {2, 4}. On the other hand since d | k + i, we also have that
N (d) | N (k + i) = k 2 + 1, that is k is odd. But that is a contradiction with what we
proved above, so k + i and k − i are indeed co-prime. It follows that each of k + i
and k − i is a product of a unit and a cube in Z[i]. Since the units are {±1, ±i}
3
and each of them is a cube of another, we can say that k ± i is a cube. But since
they are conjugate numbers, the cubes are also conjugate, so k + i = (a + bi)3 and
k − i = (a − bi)3 . Thus we have that 2i = 2i(3a2 b − b3 ) ⇒ b(3a2 − b2 ) = 1 which only
lets us choose b = −1 and a = 0 as integer solutions, and that in turn gives us the
only solution of the equation, namely k = 0 and n = 1.
Solution 2: (Andrei Negut) As usual Andrei begins with a lemma:
Lemma. There are no solutions in positive integers of the following Pell equation:
a2 − 3b2 = 1, with a = 3t + 1, and b = 2q 2 .
Proof of lemma. Suppose that such solutions exist and let us consider the one with
minimal b. We have
3 · 4q 4 = (a − 1)(a + 1) = 3t(3t + 2) ⇒ 4q 4 = t(3t + 2)
But t and 3t + 2 have the same parity, thus they are both even. Let us denote t = 2x
and 3t + 2 = 2y, which means that y = 3x + 1, and x and y are co-prime positive
integers. Furthermore 4xy = 4q 4 ⇒ xy = q 4 , and thus x = m4 , y = n4 . But
y = 3x + 1 ⇒ n4 − 1 = 3m4 . (1)
Now, if m would be odd, then m4 ≡ 1( mod 8), and that would mean
n4 ≡ 4( mod 8) which is impossible. So, m is even, and moreover m4 = x < q 4 ,
because xy = q 4 , and if x = q 4 then y = 1 which is absurd as y = 3x + 1.
Therefore we can say m = 2j and n2 = 3s + 1 because n2 is a perfect square and
n is obviously not divisible by 3 from (1). So, (1) becomes 48j 4 = 3s(3s + 2) ⇒
16j 4 = s(3s + 2). But n2 ≡ 1( mod 4), which means that 4 | s. Same as above, this
means that s = 2x0 and 3s + 2 = 2y 0 , and y 0 = 3x0 + 1 is co-prime with x0 . Thus
4j 4 = x0 y 0 . But 4 | s implies that 2 | x0 , so x0 = 4e4 and y = f 4 , with ef = j. But
y 0 = 3x0 + 1 so this becomes
f 4 = 12e04 + 1 ⇔ (f 2 )2 − 3(2e2 )2 = 1
and this is a Pell equation of the form a2 − 3b2 = 1, and because f 2 is obviously
not divisible by 3, it must be of the form 3k + 1 and all we are left to prove is that
√ m2
2e2 < b. But 2e2 = x0 < 2j 2 = < q 2 < 2q 2 , and also e 6= 0, because otherwise
2
backtracking we would obtain q = 0 and thus b = 0 contradiction. Thus the lemma is
proved.
Getting back to the original problem we have that if n3 − 1 = k 2 , with n, k > 0, then
k 2 = (n − 1)(n2 + n + 1). The numbers n − 1 and n2 + n + 1 can only have 1 or 3 as
common divisors. First let us suppose that they are co-prime. That means that both
of them are perfect squares. But n2 + n + 1 cannot be a square, because it is smaller
than (n + 1)2 and larger than n2 . This means that 3 | n − 1 and 3 | n2 + n + 1.
Then n − 1 = 3p2 and n2 + n + 1 = 3q 2 , thus q 2 = 3p4 + 3p2 + 1. So q is not divisible
by 3.
If q = 3k − 1 then we would obtain p4 + p2 = 3k 2 − 2k, so 4p4 + 4p2 + 1 = 12k 2 − 8k + 1,
thus (2p2 + 1)2 = (2k − 1)(6k − 1). Let s = 2k − 1, thus (2p2 + 1)2 = s(3s + 2). As s
is odd we have that s and 3s + 2 are co-prime, so s = a2 and 3s + 2 = b2 , but that is
a contradiction modulo 3.
4
So only the case q = 3k + 1 remains. We have p4 + p2 = 3k 2 + 2k, therefore
4p4 + 4p2 + 1 = 12k 2 + 8k + 1, so (2p2 + 1)2 = (2k + 1)(6k + 1). Let s = 2k + 1,
so (2p2 + 1)2 = s(3s − 2). As above s is odd, so s and 3s − 2 are co-prime and then
s = a2 and 3s − 2 = b2 , which means that 3a2 = b2 + 2 and ab = 2p2 + 1.
Let r = a + b. We have r2 = a2 + b2 + 2ab = 4a2 − 2 + 2(2p2 + 1) = 4a2 + 4p2 , thus 2 | r,
r
and a, p, form a Pythagorean triplet, and a being odd, a, r and p begin co-prime
2
we have a = x2 − y 2 , p = 2xy and r = 2(x2 + y 2 ), thus b = x2 + 3y 2 . Plugging all
these into ab = 2p2 + 1 we get
x4 − 3y 4 + 2x2 y 2 = 8x2 y 2 + 1 ⇒ (x2 − 3y 2 )2 − 3(2y 2 )2 = 1.
But x2 − 3y 2 is not divisible by 3, because if it would be, then x2 − 3y 2 + 6y 2 = b
would be, but b2 = 3s − 2 so b cannot be divisible by 3. Applying the lemma gives
us the only possible solution y = 0 and x2 = 1, and backtracking the notations we
obtain n = 1 and k = 0 so n = 1 is the only solution of the problem.
Comments. My algebra teacher at university, Mr. Vlådoiu, gave me this problem in
class. I solved it using the properties of Gauss’ ring Z[i]. I tried but I could not come
up with an elementary solution, being always stuck in a Pell-type equation, but I figured
others might have better chances of solving it, not knowing an easy superior algebraic
approach. And Andrei Negut did it, and he has my Congratulations. Apparently this
problem is folklore.
3. A convex polygon P can be partitioned into 27 parallelograms. Prove that it can also
be partitioned into 21 parallelograms.
Solution 1: (Claude) We shall first prove that the polygon P has an even number of
sides and these are two by two parallel and equal in length. Firstly, starting from those
27 parallelograms which make the partition of the polygon we shall build a smoother
partition, one in which any two distinct parallelograms either do not intersect, or have
just a common vertex, or have a common side. In this way, if we take a parallelogram
and a point found strictly inside a side which is a vertex for another parallelogram, we
consider a segment passing through this point which is parallel with other two sides
of the parallelogram on which the point lies. Obviously after only a finite number of
steps we have achieved our smoother partition.
Consider now the new partition on the polygon and two parallelograms within it which
intersect in more than 1 point. Then they must share a side. Let us consider that
one of the parallelograms is resting on a side of the polygon. Obviously there aren’t
any other parallelograms doing that, as they would have to be of exact the same
altitude (otherwise we would have a point inside). We continue to spawn a chain of
parallelograms which share sides, and we shall reach another side of the polygon. This
means that the two sides are parallel and congruent. An argument of angles and using
the convexity of the polygon easily shows us that we cannot have three parallel sides
in P , which means that the polygon has 2k sides.
Let us now consider two pairs of parallel sides of the polygon and let us construct for
each pair a chain of parallelograms as above. It is easy to check that the two chains
must intersect somewhere inside the polygon. They intersect after a parallelogram
which has the sides parallel with the pair of polygon sides chosen. But there are k2

pairs of parallel sides of the polygon, therefore we must have at least k different
2
k
parallelograms inside the polygon. Thus ≤ 27 ⇒ n ≤ 7.
2
5
It is easy now to check that any polygon as above with 2k sides can be partitioned
into exactly k2 parallelograms. For k = 2 it is obvious, as the the polygon is actually

a parallelogram itself. For k ≥ 3 we consider now two neighboring sides and form a
parallelogram. We then take the next side and form another parallelogram until we
have reached the opposite side of the starting one. We have obtained k − 1 paral-
lelograms and a polygon with 2(k − 1) sides, which has parallel pairs of congruent
sides, and which, by induction, can be partitioned into k − 1 parallelograms, and
2
k−1 k
as k − 1 + = we are done.
2 2
Now,
because our polygon has at most 14 sides, it can be partitioned into at most
7
= 21 parallelograms. If it is less we just create more parallelograms by splitting
2
one parallelogram in more parallelograms.
Solution 2: (Andreis) As Claude showed above there are an even number of sides
in the polygon and they can be paired into parallel and congruent sides. Let us
suppose that the polygon is A1 A2 . . . A2k .
For each pair of opposite sizes we have a path of parallelograms with sides parallel
to the given ones
between them. Since any 2 path have a common parallelogram we
k
need at least parallelograms.
2

k
Now we need to prove that is enough. We can take k parallelograms A1 A2 A3 B1 ,
2
B1 A3 A4 B2 , . . . , Bk−2 Ak Ak+1 Ak+2 (we may assume
that k ≥ 3) and for the remaining
k−1
polygon A1 B1 B2 . . . Bk−2 Ak+1 . . . A2·k we need . By induction the affirmation
2
is proven.

8 7
Since 27 < 28 = and 21 = we have that k < 8 and we can construct at
2 2
most 21 parallelograms, and if less, then we can make from one parallelogram two
buy cutting him in half.
Comments. Not an easy problem, but yet challenging and beautiful. It was again
told to us by Mr. Vlådoiu, along with the problem above, its original source being at
this point unknown. I would like to mention Toumaf and Octavian Ganea for their
complete solutions to this final problem.

6
3rd MathLinks Contest
Round 1
February 23 - March 7, 2004
1. Let P be the set of points in the Euclidian plane, and let L be the set of lines in the
same plane. Does there exist an one-to-one mapping (injective function) f : L → P
such that for each ` ∈ L we have f (`) ∈ `?
2. Prove that for all positive reals a, b, c the following double inequality holds:
s √ √ √
a+b+c 3 (a + b)(b + c)(c + a) ab + bc + ca
≥ ≥ .
3 8 3
3. Let a and b be different positive rational numbers such that the there exist an infinity
of positive integers n for which an − bn is an integer. Prove that a and b are also
integers.

Round 2
March 8 - March 21, 2004
1. Find all functions f, g : (0, ∞) → (0, ∞) such that for all x > 0 we have the relations:
x x
f (g(x)) = and g(f (x)) = .
xf (x) − 2 xg(x) − 2
2. Let ABC be a triangle with semiperimeter s and inradius r. The semicircles with
diameters BC, CA, AB are drawn on the outside of the triangle ABC. The circle
tangent to all three semicircles has radius t. Prove that
√ !
s s 3
<t≤ + 1− r.
2 2 2
3. Each point in the Euclidian space is colored with one of n ≥ 2 colors, and each of the
n colors is used. Prove that one can find a triangle such that the color assigned to
the orthocenter is different from all the colors assigned to the vertices of the triangle.

Round 3
March 22 - April 4, 2004
1. Let S be a nonempty set of points of the plane. We say that S determines the distance
d > 0 if there are two points A, B in S such that AB = d.
Assuming that S does not contain 8 collinear points and that it determines not more
than 91 distances, prove that S has less than 2004 elements.
2. Let n be a positive integer and let a1 , a2 , . . . , an , b1 , b2 , . . . , bn , c2 , c3 , . . . , c2n be 4n − 1

positive real numbers such that c2i+j ≥ ai bj , for all 1 ≤ i, j ≤ n. Also let m = max ci .
2≤i≤2n
2
m + c2 + c3 + · · · + c2n a1 + a2 + · · · + an b1 + b2 + · · · + bn

Prove that ≥ .
2n n n
3. An integer z is said to be a friendly integer if |z| is not the square of an integer.
Determine all integers n such that there exists an infinite number of triplets of distinct
friendly integers (a, b, c) such that n = a+b+c and abc is the square of an odd integer.

LaTeX Compiling (c) Valentin Vornicu 2004
Round 4
April 5 - April 18, 2004
1. Find all functions f : (0, +∞) → (0, +∞) which are increasing on [1, +∞) and for all
positive reals a, b, c they fulfill the following relation
f (ab)f (bc)f (ca) = f (a2 b2 c2 ) + f (a2 ) + f (b2 ) + f (c2 ).
2. The sequence {xn }n≥1 is defined by x1 = 7, xn+1 = 2x2n − 1, for all positive integers
n. Prove that for all positive integers n the number xn cannot be divisible by 2003.
3. An integer point of the usual Euclidean 3-dimensional space is a point whose three
coordinates are all integers. A set S of integer points is called a covered set if for all
points A, B in S each integer point in the segment [AB] is also in S.
Determine the maximum number of elements that a covered set can have if it does
not contain 2004 collinear points.

Round 5
April 19 - May 2, 2004
1. Let a, b, c be positive reals. Prove that

√ √ √ √ q
abc( a + b + c) + (a + b + c)2 ≥ 4 3abc(a + b + c).
2. Let k ≥ 1 be an integer and a1 , a2 , . . . , ak , b1 , b2 , . . . , bk rational numbers with the

property that for any irrational numbers xi > 1, i = 1, 2, . . . , k, there exist the
positive integers n1 , n2 , . . . , nk , m1 , m2 , . . . , mk such that
a1 bxn1 1 c + a2 bxn2 2 c + · · · + ak bxnk k c = b1 bxm m2 mk

1 c + b2 bx2 c + · · · + bk bxk c.
1
Prove that ai = bi for all i = 1, 2, . . . , k.
3. We say that a tetrahedron is median if and only if for each vertex the plane that
passes through the midpoints of the edges emerging from the vertex is tangent to the
inscribed sphere. Also a tetrahedron is called regular if all its faces are congruent.
Prove that a tetrahedron is regular if and only if it is median.

LaTeX Compiling (c) Valentin Vornicu 2004
Round 6
May 3 - May 16, 2004
1. For a triangle ABC and a point M inside the triangle we consider the lines AM , BM ,
CM which intersect the sides BC, CA, AB in A1 , B1 , C1 respectively. Take A0 , B 0 , C 0
to be the intersection points between the lines AA1 , BB1 , CC1 and B1 C1 , C1 A1 , A1 B1
respectively.
a) Prove that the lines BC 0 , CB 0 and AA0 intersect in a point A2 ;
b) Define similarly points B2 , C2 . Find the loci of M such that the triangle A1 B1 C1
is similar with the triangle A2 B2 C2 .
2. Let a1 , a2 , . . . , a2004 be integer numbers such that for all positive integers n the number
An = an1 + an2 + · · · + an2004 is a perfect square. What is the minimal number of zeros
within the 2004 numbers?
3. Let n ≥ 3 be an integer. Find the minimal value of the real number kn such that for
all positive numbers x1 , x2 , . . . , xn with product 1, we have
1 1 1
√ +√ + ··· + √ ≤ n − 1.
1 + kn x1 1 + kn x2 1 + kn xn

Round 7
May 26 - June 7, 2004
1. In a soccer championship 2004 teams are subscribed. Because of the extremely large
number of teams the usual rules of the championship are modified as follows:
a) any two teams can play against one each other at most one game;
b) from any 4 teams, 3 of them play against one each other.
How many days are necessary to make such a championship, knowing that each team
can play at most one game per day?
2. Find all functions f : {1, 2, . . . , n, . . .} → Z with the following properties
(i) if a, b are positive integers and a | b, then f (a) ≥ f (b);
(ii) if a, b are positive integers then
f (ab) + f (a2 + b2 ) = f (a) + f (b).
3. On a 2004 × 2004 chessboard we place 2004 white knights1 in the upper row, and 2004
black ones in the lowest row. After a finite number of regular chess moves2 , we get
the opposite situation where the black ones are on the top and the white ones on the
bottom lines.
In a turn we make a move with each of the pieces of a color. If you know that
each square except those on which the knights originally lie, must not be used more
than once in this process, and that after each turn no 2 knights of the same color
can be attacking each other3 , determine the number of ways in which this can be
accomplished.

1
also known as horses
2
the knight can be moved either one square horizontally and two vertically or two squares horizontally
and one vertically, in any direction on both horizontal and vertical lines
3
a knight is attacking another knight, if in one chess move, the first one can be placed on the second
one’s place
4
Last updated on May 26, 2004.
4th MathLinks Contest
Round 1
October 11 - October 24, 2004
1. Let a ≥ 2 be an integer. Find all polynomials f with real coefficients such that
2
A = {an | n ≥ 1, n ∈ Z} ⊂ {f (n) | n ≥ 1, n ∈ Z} = B.
2. Find, with proof, the maximal length of a non-constant arithmetic progression with
all the terms squares of positive integers.
3. Let Ω1 (O1 , r1 ) and Ω2 (O2 , r2 ) be two circles that intersect in two points X, Y . Let
A, C be the points in which the line O1 O2 cuts the circle Ω1 , and let B be the point
in which the circle Ω2 itnersect the interior of the segment AC, and let M be the
intersection of the lines AX and BY .
1
Prove that M is the midpoint of the segment AX if and only if O1 O2 = (r1 + r2 ).
2

For details about the contest, please visit the following

www.mathlinks.ro or e-mail at valentin@mathlinks.ro
Round 2
1. For a positive integer n let σ(n) be the sum of all its positive divisors.
σ(n)
Find all positive integers n such that the number is an integer.
n+1
2. Prove that the six sides of any tetrahedron can be the sides of a convex hexagon.
3. Let m ≥ 2n be two positive integers. Find a closed form for the following expression:
n
X m−k n
E(m, n) = (−1)k .
n k
k=0


Round 3
1. Let {fn }n≥1 be the Fibonacci sequence, defined by f1 = f2 = 1, and for all positive
integers n, fn+2 = fn+1 + fn .
Prove that the following inequality takes place for all positive integers n:
(2n + 2)n

n n n
f1 + f2 + · · · + fn < .
1 2 n n!
2. Determine all functions f : R → R such that f (x) ≥ 0 for all positive reals x, f (0) = 0
and for all reals x, y
f (x + y − xy) = f (x) + f (y) − f (xy).
3. Let ABC be a triangle, and let C be its circumcircle. Let T be the circle tangent
to AB, AC and C internally in the points F, E and D respectively. Let P, Q be the
intersection points between the line EF and the lines DB and DC respectively.
Prove that if DP = DQ then the triangle ABC is isosceles.


Round 4
1. Let N0 be the set of all non-negative integers and let f : N0 × N0 → [0, +∞) be a
function such that f (a, b) = f (b, a) and
f (a, b) = f (a + 1, b) + f (a, b + 1),
for all a, b ∈ N0 . Denote by xn = f (n, 0) for all n ∈ N0 .

Prove that for all n ∈ N0 the following inequality takes place
2n xn ≥ x0 .
2. We say that two triangles T1 and T2 are contained one in each other, and we write
T1 ⊂ T2 , if and only if all the points of the triangle T1 lie on the sides or in the interior
of the triangle T2 .
Let ∆ be a triangle of area S, and let ∆1 ⊂ ∆ be the largest equilateral triangle with
this property, and let ∆ ⊂ ∆2 be the smallest equilateral triangle with this property
(in terms of areas). Let S1 , S2 be the areas of ∆1 , ∆2 respectively.
Prove that S1 S2 = S 2 .
Bonus question1 : Does this statement hold for quadrilaterals (and squares)?
3. Given is a graph G. An empty subgraph of G is a subgraph of G with no edges

between its vertices. An edge of G is called important if and only if the removal of
this edge will increase the size of the maximal empty subgraph.
Suppose that two important edges in G have a common endpoint. Prove there exists
a cycle of odd length in G.


1
worths 3 extra points
Round 5
December 6 - December 19, 2004
1. Let n be a positive integer and let an be the number of ways to write n as a sum of
positive integers, such that any two summands differ by at least 2. Also, let bn be the
number of ways to write n as a sum of positive integers of the form 5k ± 1, k ∈ Z.
an
Prove that is a constant for all positive integers n.
bn
2. Let ABCD be a convex quadrilateral, and let K be a point on side AB such that
∠KDA = ∠BCD. Let L be a point on the diagonal AC such that KL k BC.
Prove that ∠KDB = ∠LDC.
3. The sequence {xn }n is defined as follows: x1 = 0, and for all n ≥ 1
(n + 1)3 xn+1 = 2n2 (2n + 1)xn + 2(3n + 1).
Prove that {xn }n contains infinitely many integer numbers.


Round 6
December 20, 2004 - January 2, 2005
1. Find all positive integers a, b, c, d, such that the following equality takes place for an
infinity of positive integers n
(1a + 2a + · · · + na )b = (1c + 2c + · · · + nc )d .
2. Let P be the set of points in the plane, and let f : P → P be a function such that the
image through f of any triangle is a square (any polygon is considered to be formed
by the reunion of the points on its sides).
Prove that f (P) is a square.
3. If n > 2 is an integer and x1 , . . . , xn are positive reals such that
1 1 1
+ + ··· + =n
x1 x2 xn
then the following inequality takes place
n−1
x22 + · · · + x2n x21 + x23 + · · · + x2n x2 + · · · + x2n−1 x21 + ... + x2n

· ··· 1 ≥ .
n−1 n−1 n−1 n


Round 7
January 3 - January 16, 2005
1. Let a, b, c, d be positive reals such that abcd = 1. Prove that

1 1 1 1
+ + + ≥ 2.
a(b + 1) b(c + 1) c(d + 1) d(a + 1)
2. Let C be the incircle of a triangle ABC. Suppose that there exists a circle passing
through B and C and tangent to C in A0 . Suppose the similar points B 0 , C 0 exist.
Prove that the lines AA0 , BB 0 and CC 0 are concurrent.
3. Let {fn }n≥0 be the Fibonacci sequence, given by f0 = f1 = 1, and for all positive
integers n the recurrence fn+1 = fn + fn−1 .
Let an = fn+1 fn for any non-negative integer n, and let
Pn (X) = X n + an−1 X n−1 + · · · + a1 X + a0 .
Prove that for all positive integers n ≥ 3 the polynomial Pn (X) is irreducible in Z[X].


Round 1
April 11 - April 24, 2005
1. Find all pairs of positive integers x, y such that
x3 − y 3 = 2005(x2 − y 2 ).
2. Find all the integers n ≥ 5 such that the residue of n when divided by each prime
n
number smaller than is odd.
2
3. Let ABC be a triangle and let A0 ∈ BC, B 0 ∈ CA and C 0 ∈ AB be three collinear
points.
a) Prove that each pair of circles of diameters AA0 , BB 0 and CC 0 has the same radical
axis;
b) Prove that the circumcenter of the triangle formed by the intersections of the lines
AA0 , BB 0 and CC 0 lies on the common radical axis found above.

Compiling (c) Valentin Vornicu 2005

Round 2
April 25 - May 8, 2005
1. For what positive integers k there exists a function f : N → N such that for all n ∈ N
we have
f (f (. . . f (n) . . .)) = f (n) + 2 ?
| {z }
k times
2. Suppose that {Dn }n≥1 is an finite sequence of disks in the plane whose total area is
less than 1.
Prove that it is possible to rearrange the disks so that they are disjoint from each
other and all contained inside a disk of area 4.
3. Let a, b, c be positive numbers such that abc ≤ 8. Prove that
1 1 1
2
+ 2 + 2 ≥ 1.
a −a+1 b −b+1 c −c+1


Round 3
May 9 - May 22, 2005
1. Let {xn }n be a sequence of positive rational numbers, such that x1 is a positive integer,
and for all positive integers n

 2(n − 1) xn−1 ,
 if xn−1 ≤ 1
n


xn =
 (n − 1)xn−1 − 1 , if xn−1 > 1.



n
Prove that there exists a constant subsequence of {xn }n .
2. Let 0 < a1 < a2 < · · · < a16 < 122 be 16 integers. Prove that there exist integers
(p, q, r, s), with 1 ≤ p < r ≤ s < q ≤ 16, such that ap + aq = ar + as .
For problem 2, an additional 2 points will be awarded for this problem if you can find
a larger bound than 122 (with proof ).
1 1
3. Let x1 , x2 , . . . , xn be positive numbers such that S = x1 +x2 +· · ·+xn = +· · ·+ .
x1 xn
Prove that
n n
X 1 X 1
≥ .
n − 1 + xi 1 + S − xi
i=1 i=1


Round 4
23 May - 4 June, 2005
1. Let ABC be an acute angled triangle. Let M be the midpoint of BC, and let BE
and CF be the altitudes of the triangle. Let D 6= M be a point on the circumcircle
of the triangle EF M such that DE = DF .
Prove that AD ⊥ BC.
2. Given is a unit cube in space. Find the maximal integer n such that there are n
points, satisfying the following conditions:
(a) All points lie on the surface of the cube;
(b) No face contains all these points;
(c) The n points are the vertices of a polygon.
3. Let a1 , . . . , an be positive reals and let x1 , . . . , xn be real numbers such that

a1 x1 + · · · + an xn = 0. Prove that
X
xi xj |ai − aj | ≤ 0.
1≤i<j≤n
When does the equality take place?


Round 5
June 6 - June 19, 2005
1. Find all real numbers a > 1 such that there exists an integer k ≥ 1 such that the
sequence {xn }n≥1 formed with the first k digits of the number ban c is periodical.
2. Prove or disprove the existence of a function f : S → R such that for all x 6= y ∈ S
1
we have |f (x) − f (y)| ≥ 2 , in each of the cases
x + y2
a) S = R;
b) S = Q.
3. A student wants to make his birthday party special this year. He wants to organize
it such that among any groups of 4 persons at the party there is one that is friends
with exactly another person in the group.
Find the largest number of his friends that he can possibly invite at the party.


Round 6
20 June - 26 June, 2005
1. Let ABC be a triangle and let C be a circle that intersects the sides BC, CA and AB
in the points A1 , A2 , B1 , B2 and C1 , C2 respectively.
Prove that if AA1 , BB1 and CC1 are concurrent lines then AA2 , BB2 and CC2 are
also concurrent lines.
4 1 1 1
2. We say that a positive integer n is nice if cannot be written as + + for any
n x y z
positive integers x, y, z.
Let us denote by an the number of nice numbers smaller than n. Prove that the
n
sequence is not bounded.
an
3. Let x, y, z be three positive numbers such that

1 1 1
(x + y − z) + − = 4.
x y z
Find the minimal value of the expression

4 4 4 1 1 1
E(x, y, z) = (x + y + z ) + + .
x4 y 4 z 4


Round 7
30 June - 7 July, 2005
2n − 1

1. Prove that the numbers , i = 0, 1, . . ., 2n−1 − 1, have pairwise different
i
residues modulo 2n .
2. For any positive integer n, let s(n) be the sum of its digits, written in decimal base.
Prove that for each integer n ≥ 1 there exists a positive integer x such that the fraction
x+k
is not integral, for each integer k with 0 ≤ k ≤ n.
s(x + k)
√ √
3. Given is a square of sides 3 7 × 3 7. Find the minimal positive integer n such that
no matter how we put n unit disks inside the given square, without overlapping, there
exists a line that intersects 4 disks.


Round 1
October 10 - 23, 2005
1. Let a, b, c be positive real numbers such that ab + bc + ca = 1. Prove that
1 + a2 b2 1 + b2 c2 1 + c2 a2 5
2
+ 2
+ 2
≥ .
(a + b) (b + c) (c + a) 2
2. Let ABCD be a rectangle of center O in the plane α, and let V ∈ / α be a point in

space such that V O ⊥ α. Let A0 ∈ (V A), B 0 ∈ (V B), C 0 ∈ (V C), D0 ∈ (V D) be four
points, and let M and N be the midpoints of the segments A0 C 0 and B 0 D0 .
Prove that M N k α if and only if V , A0 , B 0 , C 0 , D0 all lie on a sphere.
3. Introductory part. We call an n-tuple x = (x1 , x2 , . . . , xn ), with xk ∈ R (or respectively

with all xk ∈ Z) a real vector (or respectively an integer vector). The set of all real
vectors (respectively all integer vectors) is usually denoted by Rn (respectively Zn ).
A vector x is null if and only if xk = 0, for all k ∈ {1, 2, . . . , n}. Also let Un be the
set of all real vectors x = (x1 , . . . , xn ) such that x21 + x22 + . . . + x2n = 1.
For two vectors x = (x1 , . . . , xn ), y = (y1 , . . . , yn ) we define the scalar product as the
real number
p x · y = x1 y1 + x2 y2 + · · · + xn yn . We define the norm of the vector x as
||x|| = x21 + x22 + · · · + x2n .
The problem.

k
Let A(k, r) = x ∈ Un | for all z ∈ Zn we have either |x · z| ≥ or z is null .
||z||r
Prove that if r > n − 1 the we can find a positive number k such that A(k, r) is not
empty, and if r < n − 1 we cannot find such a positive number k.


Round 2
1. Solve in positive real numbers the following equation
x−y + y −x = 4 − x − y.
2. Let a1 , . . . , an−1 be n − 1 consecutive positive integers in increasing order such

, a2
n
that k ≡ 0 (mod ak ), for all k ∈ {1, 2, . . . , n − 1}. Find the possible values of a1 .
k
3. Let σ : {1, 2, . . . , n} → {1, 2, . . . , n} be a bijective mapping. Let Sn be the set of all
such mappings and let
dk (σ) = |σ(k) − σ(k + 1)|, for all k ∈ {1, 2, . . . , n}, where σ(n + 1) = σ(1).
Also let d(σ) = min{dk (σ) | 1 ≤ k ≤ n}. Find max d(σ).

σ∈Sn


Round 3
1. For each positive integer n let τ (n) be the sum of divisors of n. Find all positive
integers k for which
τ (kn − 1) ≡ 0 (mod k)
for all positive integers n.
2. Let ABCD be a convex quadrilateral, and the points A1 ∈ (CD), A2 ∈ (BC), C1 ∈

(AB), C2 ∈ (AD). Let M, N be the intersection points between the lines AA2 , CC1
and AA1 , CC2 respectively.
Prove that if three of the quadrilaterals ABCD, A2 BC1 M , AM CN , A1 N C2 D are cir-
cumscriptive (i.e. there exists an incircle tangent to all the sides of the quadrilateral )
then the forth quadrilateral is also circumscriptive.
3. We say that a set of points M in the plane is convex if for any two points A, B ∈ M ,
all the points from the segment (AB) also belong to M .
Let n ≥ 2 be an integer and let F be a family of n disjoint convex sets in the plane.
Prove that
l n there
m exists a line ` in the plane, a set M ∈ F and a subset S ⊂ F with
at least elements such that M is contained in one closed half-plane determined
12
by `, and all the sets N ∈ S are contained in the complementary closed half-plane
determined by `.


Round 4
1. Let F be a family of n subsets of a set K with 5 elements, such that any two subsets
in F have a common element. Find the minimal value of n such that no matter how
we choose F with the properties above, there exists exactly one element of K which
belongs to all the sets in F.
2. Let n be a positive integer. Prove that there exist an infinity of multiples of n which
do not contain the digit “9” in their decimal representation.
3. Let a, b, c be positive real numbers such that abc = 1. Prove that

r r r
a+b b+c c+a
+ + ≥ 3.
b+1 c+1 a+1


Round 5
December 5 - December 18, 2005
1. Find all solutions in integers of the equation
x2 + 22 = y 3 + 33 .
2. Let n ≥ 5 be an integer and let x1 , x2 , . . . , xn be n distinct integer numbers such that

no 3 of them can be in arithmetic progression. Prove that if for all 1 ≤ i, j ≤ n we
have
2|xi − xj | ≤ n(n − 1)
then there exist 4 distinct indices i, j, k, l ∈ {1, 2, . . . , n} such that
xi + xj = xk + xl .
3. Let ABC be a triangle, and let ABB2 A3 , BCC3 B1 and CAA1 C2 be squares con-
structed outside the triangle. Denote with S the area of the triangle ABC and with s
the area of the triangle formed by the intersection of the lines A1 B1 , B2 C2 and C3 A3 .
Prove that √
s ≤ (4 − 2 3)S.


Round 6
December 26, 2005 - January 8, 2006
1. Let p > 1 and let a, b, c, d be positive numbers such that

1 1 1 1
(a + b + c + d) + + + = 16p2 .
a b c d
max{a, b, c, d}
Find all values of the ratio R = (depending on the parameter p).
min{a, b, c, d}
2. A n × n matrix is filled with non-negative real numbers such that on each line and
column the sum of the elements is 1. Prove that one can choose n positive entries
from the matrix, such that each of them lies on a different line and different column.
3. Let C1 , C2 and C3 be three circles, of radii 2, 4 and 6 respectively. It is known that

each of them are tangent exteriorly with the other two circles. Let Ω1 and Ω2 be two
more circles, each of them tangent to all of the 3 circles above, of radius ω1 and ω2
respectively.
Prove that ω1 + ω2 = 2ω1 ω2 .


Round 7
January 9 - January 22, 2006
1. Write the following polynomial as a product of irreducible polynomials in Z[X]
f (X) = X 2005 − 2005X + 2004.
Justify your answer.
2. Let ABCD be a cyclic quadrilateral. Let M, N be the midpoints of the diagonals AC

and BD and let P be the midpoint of M N . Let A0 , B 0 , C 0 , D0 be the intersections of
the rays AP , BP , CP and DP respectively with the circumcircle of the quadrilateral
ABCD.
Find, with proof, the value of the sum
AP BP CP DP
σ= 0
+ 0
+ 0
+ .
PA PB PC P D0
3. A lattice point in the Carthesian plane is a point with both coordinates integers. A
rectangle minor (respectively a square minor ) is a set of lattice points formed by all
the lattice points lying inside or on the boundaries of a rectangle (respectively square)
with vertices lattice points. We assign to each lattice point a real number, such that
the sum of all the numbers in any square minor is less than 1 in absolute value.
Prove that the sum of all the numbers in any rectangle minor is less than 4 in absolute
value.


Round 1
1. Given is an acute triangle ABC and the points A1 , B1 , C1 , that are the feet of its alti-
tudes from A, B, C respectively. A circle passes through A1 and B1 and touches the smaller
arc AB of the circumcircle of ABC in point C2 . Points A2 and B2 are defined analogously.
Prove that the lines A1 A2 , B1 B2 , C1 C2 have a common point, which lies on the Euler line
of ABC.
2. Let a, b, c, d be four distinct positive integers in arithmetic progression. Prove that

abcd is not a perfect square.
3. We are given the finite sets X, A1 , A2 , . . . , An−1 and the functions fi : X → Ai . A

vector (x1 , x2 , . . . , xn ) ∈ X n is called nice, if fi (xi ) = fi (xi+1 ), for each 1, 2, . . . , n − 1. Prove
that the number of nice vectors is at least
|X|n
n−1
.
Q
|Ai |
i=1
1
Round 2
1. Let k be an integer, k ≥ 2, and let p1 , p2 , . . . , pk be positive reals with p1 + p2 + . . . +

pk = 1. Suppose we have a collection (A1,1 , A1,2 , . . . , A1,k ), (A2,1 , A2,2 , . . . , A2,k ), . . .
,(Am,1 , Am,2 , . . . , Am,k ) of k-tuples of finite sets satisfying the following two properties:
(i) for every i and every j 6= j 0 , Ai,j ∩ Ai,j 0 = ∅, and
(ii) for every i 6= i0 there exist j 6= j 0 for which Ai,j ∩ Ai,j 0 = ∅. Prove that
m Y
X k
|Ab,a |
pa ≤ 1.
b=1 a=1
2. For a prime p an a positive integer n, denote by νp (n) the exponent of in the prime
factorization of n!. Given a positive integer d and a finite set {p1 , p2 , . . . , pk } of primes,
show that there are infinitely many positive integers n such that νpi (n) ≡ 0 (mod d), for
all 1 ≤ i ≤ k.
3. Let ABC be a given triangle with the incenter I , and denote by X, Y, Z the inter-
sections of the lines AI, BI, CI with the sides BC, CA and AB, respectively. Consider Ka
the circle tangent simultaneously to the sidelines AB, AC, and internally to the circumcir-
cle C(O) of ABC, and let A0 be the tangency point of Ka with C. Similarly define, B 0 , and C 0 .
Prove that the circumcircles of triangles AXA0 , BY B 0 , and CZC 0 all pass through two
distinct points.
2
Round 3
1. Let p be a prime and let d ∈ {0, 1, . . . , p}. Prove that
Xµ
p−1
2k
¶
≡r (mod p),
k+d
k=0
where r ≡ p − d (mod 3), r ∈ {−1, 0, 1}.
2. Prove that for positive integers x, y, z the number x2 + y 2 + z 2 is not divisible by

3(xy + yz + zx).
3. Find the greatest positive real number k such that the inequality below holds for any
positive real numbers a, b, c:
µ ¶
a b c a b c 3
+ + −3≥k + + − .
b c a b+c c+a a+b 2
3
Round 4
1. Let A, B, C, D, E be five distinct points, such that no three of them lie on the same line.
Prove that
AB + BC + CA + DE < AD + AE + BD + BE + CD + CE.
2. Find the number of finite sequences {a1 , a2 , . . . , a2n+1 }, formed with nonnegative in-
tegers, for which a1 = a2n+1 = 0 and |ak − ak+1 | = 1, for all k ∈ {1, 2, . . . , 2n}.
3. Let a, b, c be positive real numbers such that ab + bc + ca = 3. Prove that

1 1 1 3
+ + ≤ .
1 + a2 (b + c) 1 + b2 (c + a) 1 + c2 (a + b) 1 + 2abc
4
Round 5
1. Find all real polynomials g(x) of degree at most n − 3, n ≥ 3, knowing that all the roots
of the polynomial
n(n − 1) n−2
f (x) = xn + nxn−1 + x + g(x)
2
are real.
2. Let A0 be an arbitrary point on the side BC of a triangle ABC. Denote by TAb , TAc
the circles simultaneously tangent to AA0 , A0 B, Γ and AA0 , A0 C, Γ, respectively, where Γ is
the circumcircle of ABC. Prove that TAb , TAc are congruent if and only if AA0 passes through
the Nagel point of triangle ABC.
(If M, N, P are the points of tangency of the excircles of the triangle ABC with the sides
of the triangle BC, CA and AB respectively, then the Nagel point of the triangle is the in-
tersection point of the lines AM, BN and CP .)
3. If a ≥ b ≥ c ≥ d > 0 such that abcd = 1, then prove that

1 1 1 3
+ + ≥ √ .
1+a 1+b 1+c 1 + 3 abc
5
Round 6
1. Let {xn }n≥1 be a sequences, given by x1 = 1, x2 = 2 and
x2n+1 + 3
xn+2 = .
xn
Prove that x2008 is the sum of two perfect squares.
2. Find all functions f, g : Q → Q such that for all rational numbers x, y we have
f (f (x) + g(y)) = g(f (x)) + y.
3. Let Ω be the circumcircle of triangle ABC. Let D be the point at which the incir-
cle of ABC touches its side BC. Let M be the point on Ω such that the line AM is parallel
to BC. Also, let P be the point at which the circle tangent to the segments AB and AC
and to the circle Ω touches Ω. Prove that the points P, D, M are collinear.
6
Round 7
1. Find all pairs of positive integers a, b such that
b2 + b + 1 ≡ 0 (mod a)
a2 + a + 1 ≡ 0 (mod b).
2. Prove that the set of all the points with both coordinates begin rational numbers can be
written as a reunion of two disjoint sets A and B such that any line that that is parallel
with Ox, and respectively Oy intersects A, and respectively B in a finite number of points.
3. Let n be a positive integer, and let M = {1, 2, . . . , 2n}. Find the minimal positive
integer m , such that no matter how we choose the subsets Ai ⊂ M, 1 ≤ i ≤ m, with the
properties:
(1)|Ai − Aj | ≥ 1, for all i 6= j,
Sm
(2) i=1 Ai = M,
we can always find two subsets Ak and Al such that Ak ∪ Al = M (here |X| represents
the number of elements in the set X.)

Mathlinks Contest

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Mathlinks Contest

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Mathlinks Contest

Uploaded by

Copyright:

Available Formats

MathLinks Contest

First Round 24.02.2003 - 10.03.2003

Good Luck in solving these problems!

TeX (c) 2003 Valentin Vornicu

where ai represents the number of 1-s in each line, thus ai ≥ 2.

But for each Ai there are n − |Ai | elements x 6∈ Ai thus:

Finally we observe that

By Cauchy Schwarz and AM-GM Inequality,

aa2 c2 + bb2 a2 + cc2 b2 ≥ a2 b2 c + b2 c2 a + a2 c2 b

Solution 1 (Valentin Vornicu and Siutz). Let p = 2003. Firstly, claim

Solution 2 (Andrei Stefanescu and Claudiu Raicu). We have x0 = 1, x1 = 2003,

p4n + qn4 + 2p2n qn2 2

which is true because of the fact that pn−2 pn = p2n−1 + qn−1

We must prove that:

 √ 2n−2  √ 2n−2  √ n  √ n−2

⇒ α2 = α(p2 + 2) − p2 ⇒ yαn+1 = yαn (p2 + 2) − p2 yαn−1

⇒ β 2 = β(p2 + 2) − p2 ⇒ zβ n+1 = zβ n (p2 + 2) − p2 zβ n−1 .

TeX (c) 2003 Valentin Vornicu

2. In a triangle ∆ABC, ∠B = 2∠C. Let P and Q be points on the perpendicular bisector

Good Luck in solving these problems!

TeX (c) 2003 Valentin Vornicu

f (x) = xn + axn−1 + axn−2 + . . . + ax − 1

Good Luck in solving these problems!

TeX (c) 2003 Valentin Vornicu

Good Luck in solving these problems!

TeX (c) 2003 Valentin Vornicu

1. In a triangle ABC, ∠B = 70◦ , ∠C = 50◦ . A point M is taken on the side AB such

Good Luck in solving these problems!

TeX (c) 2003 Valentin Vornicu

3. Consider (fn )n≥0 the Fibonacci sequence, defined by f0 = 0, f1 = 1, fn+1 = fn + fn−1

nfn fn+1 = (fn+2 − 1)2 .

Good Luck in solving these problems!

TeX (c) 2003 Valentin Vornicu

Good Luck in solving these problems!

TeX (c) 2003 Valentin Vornicu

1. Let x, y, z be positive numbers such that

(1) σ(k + 1) ∈ {2σ(k), 2σ(k) − 1, 2σ(k) − n, 2σ(k) − n − 1}, ∀k ∈ {1, 2, . . . , n − 1}

(2) σ(1) ∈ {2σ(n), 2σ(n) − 1, 2σ(n) − n, 2σ(n) − n − 1}.

3. Given are on a line three points A, B, C such that AB = 1 and BC = x. Consider

Good luck in solving these problems.

1. Let x, y, z be positive numbers such that

(a2 b2 + b2 c2 + c2 a2 )2 > 2(a4 b4 + b4 c4 + c4 a4 ) (1)

Now let us denote a2 = t, b2 = u, c2 = v. Then (1) can be rewritten as (tu+uv+vt)2 >

We have to prove that t is in the interval (t1 , t2 ). We know that

(1) σ(k + 1) ∈ {2σ(k), 2σ(k) − 1, 2σ(k) − n, 2σ(k) − n − 1}, ∀k ∈ {1, 2, . . . , n − 1}

(2) σ(1) ∈ {2σ(n), 2σ(n) − 1, 2σ(n) − n, 2σ(n) − n − 1}.

...(first ring)..., m, r, ...(second ring), M, r0 , ...(first ring)...

By the “friendly” definition we see that r0 is indeed a possible successor of M . The

3. Given are on a line three points A, B, C such that AB = 1 and BC = x. Consider

Tex (c) Valentin Vornicu 2003

1. Given are six reals a, b, c, x, y, z such that

(a + b + c)(x + y + z) = 3 and (a2 + b2 + c2 )(x2 + y 2 + z 2 ) = 4.

2. Let {an }n≥0 be a sequence of rational numbers given by a0 = a1 = a2 = a3 = 1 and

Good luck in solving these problems.

1. Given are six reals a, b, c, x, y, z such that

(a + b + c)(x + y + z) = 3 and (a2 + b2 + c2 )(x2 + y 2 + z 2 ) = 4.

Also, let us consider the following numbers:

The following relationships hold:

(a1 + b1 + c1 )(x1 + y1 + z1 ) = (a + b + c)(x + y + z) = 3,

√ 2n−2 √ 2n−2 √ n √ n−2