13
th
International Mathematics Competition for University Students
Odessa, July 20-26, 2006
First Day
Problem 1. Let f : R → R be a real function. Prove or disprove each of the following statements.
(a) If f is continuous and range(f) = R then f is monotonic.
(b) If f is monotonic and range(f) = R then f is continuous.
(c) If f is monotonic and f is continuous then range(f) = R.
(20 points)
Solution. (a) False. Consider function f(x) = x
3
− x. It is continuous, range(f) = R but, for example,
f(0) = 0, f (
1
2
) = −
3
8
and f(1) = 0, therefore f (0) > f(
1
2
), f(
1
2
) < f(1) and f is not monotonic.
(b) True. Assume first that f is non-decreasing. For an arbitrary number a, the limits lim
a−
f and
lim
a+


x
2
− x is divisible by 10
k

and s (k) = |S
k
| , k ≥ 1. Let x =
a
k+1
a
k
. . . a
1
be the decimal writing of an integer x ∈ S
k+1
, k ≥ 1. Then obviously y = a
k
. . . a
1
∈ S
k
. Now,
let y = a
k
. . . a
1
∈ S
k

10
2k
. Since y
2
− y = 10
k
z for an iteger z, it follows that
x
2
−x is divisible by 10
k+1
if and only if z +a
k+1
(2y − 1) ≡ 0 (mod 10). Since y ≡ 3 (mod 10) is obviously
impossible, the congruence has exactly one solution. Hence we obtain a one-to-one correspondence between
the sets S
k+1
and S
k
for every k ≥ 1. Therefore s (2006) = s (1) = 3, because S
1
= {1, 5, 6} .
Solution 2. Since x
2
− x = x(x − 1) and the numbers x and x − 1 are relatively prime, one of them must
be divisible by 2
2006
and one of them (may be the same) must be divisible by 5
2006
. Therefore, x must

with integer entries such that A = B
1
· . . . · B
k
and det B
i
= b
i
for all i = 1, . . . , k.
(20 points)
Solution. By induction, it is enough to consider the case m = 2. Furthermore, we can multiply A with
any integral matrix with determinant 1 from the right or from the left, without changing the problem.
Hence we can assume A to be upper triangular.
1
13
th
International Mathematics Competition for University Students
Odessa, July 20-26, 2006
Second Day
Problem 1. Let V be a convex polygon with n vertices.
(a) Prove that if n is divisible by 3 then V can be triangulated (i.e. dissected into non-overlapping
triangles whose vertices are vertices of V ) so that each vertex of V is the vertex of an odd number
of triangles.
(b) Prove that if n is not divisible by 3 then V can be triangulated so that there are exactly two
vertices that are the vertices of an even number of the triangles.
(20 points)
Solution. Apply induction on n. For the initial cases n = 3, 4, 5, chose the triangulations shown in
the Figure to prove the statement.
oddodd odd even even even
odd even odd

k+2
and P
1
P
k+2
P
k+3
. This way we
introduce two new triangles at vertices P
1
and P
k
so parity is preserved. The vertices P
k+1
, P
k+2
and
P
k+3
share an odd number of triangles. Therefore, the number of vertices shared by even number of
triangles remains the same as in polygon P
1
P
2
. . . P
k
.
P
1
P

f(x) − f(y) = x − y implies f (x) − x = f(y) − y, which says that f(x) = x + c for some constant c.
Similarly, the case of a decreasing function f leads to f (x) = −x + c for some constant c.
Problem 3. Compare tan(sin x) and sin(tan x) for all x ∈ (0,
π
2
).
(20 points)
Solution. Let f(x) = tan(sin x) − sin(tan x). Then
f

(x) =
cos x
cos
2
(sin x)
−
cos(tan x)
cos
2
x
=
cos
3
x − cos(tan x) · cos
2
(sin x)
cos
2
x · cos
2


1
cos
2
x
+ 2 cos x

≥
3

1
cos
2
x
· cos x · cos x = 1. This
proves that cos
3
x−cos(tan x)·cos
2
(sin x) > 0, so f

(x) > 0, so f increases on the interval [0, arctan
π
2
].
To end the proof it is enough to notice that (recall that 4 + π
2
< 16)
tan


2
, . . . , v
n+1
∈ R
n
be such that the Euclidean
norm |v
i
− v
j
| is rational for every 0 ≤ i, j ≤ n + 1. Prove that v
1
, . . . , v
n+1
are linearly dependent
over the rationals.
(20 points)
Solution. By passing to a subspace we can assume that v
1
, . . . , v
n
are linearly independent over the
reals. Then there exist λ
1
, . . . , λ
n
∈ R satisfying
v
n+1
=

, v
j
 is rational for all i, j. Define A to be the rational n × n-matrix A
ij
= v
i
, v
j
,
w ∈ Q
n
to be the vector w
i
= v
i
, v
n+1
, and λ ∈ R
n
to be the vector (λ
i
)
i
. Then,
v
i
, v
n+1
 =
n

y
3
− ny + mn = 0.
Let two roots be u and v; the third one must be w = −(u + v) since the sum is 0. The roots must
also satisfy
uv + uw + vw = −(u
2
+ uv + v
2
) = −n, i.e. u
2
+ uv + v
2
= n
and
uvw = −uv(u + v) = mn.
So we need some integer pairs (u, v) such that uv(u + v) is divisible by u
2
+ uv + v
2
. Look for such
pairs in the form u = kp, v = kq. Then
u
2
+ uv + v
2
= k
2
(p
2

, m = p
2
q + pq
2
,
and the three roots are
x
1
= p
3
, x
2
= q
3
, x
3
= −(p + q)
3
.
Problem 6. Let A
i
, B
i
, S
i
(i = 1, 2, 3) be invertible real 2 × 2 matrices such that
(1) not all A
i
have a common real eigenvector;
(2) A

−1
B
i
S for all i = 1, 2, 3.
(20 points)
Solution. We note that the problem is trivial if A
j
= λI for some j, so suppose this is not the case.
Consider then first the situation where some A
j
, say A
3
, has two distinct real eigenvalues. We may
assume that A
3
= B
3
=

λ
µ

by conjugating both sides. Let A
2
= (
a b
c d
) and B
2
=

2
B
3
) = a

λ + d

µ.
Hence a = a

and d = d

and so also bc = b

c

. Now we cannot have c = 0 or b = 0, for then (1, 0)

or
(0, 1)

would be a common eigenvector of all A
j
. The matrix S = (
c

c
) conjugates A
2
= S

j
have a common eigenvector over C. Even if they do, say A
j
v = λ
j
v,
by taking the conjugate square root it follows that A
j
’s can be simultaneously diagonalized. If
A
2
= (
a
d
) and B
2
=

a

b

c

d


, it follows as above that a = a

, d = d

may be conjugated to some T
−1
S
0
T =

x 0
y 0

, with (x, y)

= (0, 0)

, and it follows that all A
j
have a common eigenvector T (0, 1)

, a contradiction.
We are left with the case when no A
j
has distinct eigenvalues; then these eigenvalues by necessity
are real. By conjugation and division by scalars we may assume that A
3
= (
1 b
1
) and b = 0. By further
conjugation by upper-triangular matrices (which preserves the shape of A
3
up to the value of b) we can

2
= Tr
2
A
1
= 4 det A
1
= −4/u. Comparing these two it follows that b = −2v.
What we have done is simultaneously reduced all A
j
to matrices whose all entries depend on u and
v (= − det A
2
and Tr A
2
, respectively) only, but these themselves are invariant under similarity. So
B
j
’s can be simultaneously reduced to the very same matrices.
4