FOURTH INTERNATIONAL COMPETITION
FOR UNIVERSITY STUDENTS IN MATHEMATICS
July 30 – August 4, 1997, Plovdiv, BULGARIA
First day — August 1, 1997
Problems and Solutions
Problem 1.
Let {ε
n
}
∞
n=1
be a sequence of positive real numbers, such that lim
n→∞
ε
n
=
0. Find
lim
n→∞
1
n
n

k=1
ln

k
n
+ ε
n


+ ε
n

≥
1
n
n

k=1
ln

k
n

−→
n→∞
−1.
Given ε > 0 there exist n
0
such that 0 < ε
n
≤ ε for all n ≥ n
0
. Then
1
n
n

k=1
ln

n
+ ε

=

1
0
ln(x + ε)dx
=

1+ε
ε
ln xdx
1
we obtain the result when ε goes to 0 and so
lim
n→∞
1
n
n

k=1
ln

k
n
+ ε
n

= −1.

9
+ a
32
+ ···
b) a
1
+ a
2
+ a
3
+ a
4
+ a
5
+ a
7
+ a
6
+ a
8
+ a
9
+ a
11
+ a
13
+ a
15
+ a
10

such
that |S
n
− S| < ε for n > n
0
. The partial sums of the permuted series have
the form L
2
n−1
+k
= S
2
n−1
+ S
2
n
− S
2
n
−k
, 0 ≤ k < 2
n−1
and for 2
n−1
> n
0
we
have |L
2
n−1

n−2
1
√
2
n
−→
n→∞
∞, so L
3.2
n−2
−→
n→∞
∞.
Problem 3.
Let A and B be real n×n matrices such that A
2
+B
2
=AB. Prove that
if BA − AB is an invertible matrix then n is divisible by 3.
Solution.
Set S = A + ωB, where ω = −
1
2
+ i
√
3
2
. We have
S

where each n
i
is a positive integer satisfying
n
2
i
≤ n
i+1
.
b) Show that α is rational if and only if its infinite product has the
following property:
For some m and all k ≥ m,
n
k+1
= n
2
k
.
Solution.
a) We construct inductively the sequence {n
i
} and the ratios
θ
k
=
α

k
1
(1 +

.
Since
θ
k−1
≤ 1 +
1
n
k
− 1
we have
1 +
1
n
k+1
< θ
k
=
θ
k−1
1 +
1
n
k
≤
1 +
1
n
k
−1
1 +

1
n
k

.
The uniquness of the infinite product will follow from the fact that on
every step n
k
has to be determine by (1).
Indeed, if for some k we have
1 +
1
n
k
≥ θ
k−1
then θ
k
≤ 1, θ
k+1
< 1 and hence {θ
k
} does not converge to 1.
Now observe that for M > 1,
(2)

1 +
1
M


− 1
< θ
k−1
.
Then we get
α
(1 +
1
n
1
)(1 +
1
n
2
) . . .
=
θ
k−1
(1 +
1
n
k
)(1 +
1
n
k+1
) . . .
≥
θ
k−1

m
n
m
− 1
.
Suppose this is not the case, so that for every m,
(3) θ
m−1
<
n
m
n
m
− 1
.
4
For each k we write
θ
k
=
p
k
q
k
as a fraction (not necessarily in lowest terms) where
p
0
= p, q
0
= q

p
k−1
− (n
k
+ 1)q
k−1
− p
k−1
+ q
k−1
= (n
k
− 1)p
k−1
− n
k
q
k−1
and this is negative because
p
k−1
q
k−1
= θ
k−1
<
n
k
n
k

: all y
i
are integers}. Define the (quasi–)norm
in R
n
by x
p
=

n

i=1
|x
i
|
p

1/p
if 0 < p < ∞, and x
∞
= max
i
|x
i
|.
a) Let x ∈ R
n
0
be such that
max

n
0
such that
x
p
> x + y
p
.
5
Solution.
a) For x = 0 the statement is trivial. Let x = 0. Then max
i
x
i
> 0 and
min
i
x
i
< 0. Hence x
∞
< 1. From the hypothesis on x it follows that:
i) If x
j
≤ 0 then max
i
x
i
≤ x
j

i
> 0}, I(−, −) = {i : y
i
< 0, x
i
≤ 0}.
As least one of the last four index sets is not empty. If I(+, +) = Ø or
I(−, −) = Ø then x + y
∞
≥ 1 > x
∞
. If I(+, +) = I(−, −) = Ø then

y
i
= 0 implies I(+, −) = Ø and I(−, +) = Ø. Therefore i) and ii) give
x + y
∞
≥ x
∞
which completes the case p = ∞.
Now let 1 ≤ p < ∞. Then using i) for every j ∈ I(+, −) we get
|x
j
+ y
j
| = y
j
− 1 + x
j

k
|
p
for every k ∈ I(+, −) and j ∈ I(−, +);
|x
j
+ y
j
|
p
≥ |y
j
| + |x
j
|
p
for every j ∈ I(+, +) ∪ I(−, −).
Assume that

j∈I(+,−)
1 ≥

j∈I(−,+)
1. Then
x + y
p
p
− x
p
p

p


+



j∈I(−,+)
|x
j
+ y
j
|
p
−

k∈I(+,−)
|x
k
|
p


≥

j∈I(+,+)∪I(−,−)
|y
j
| +


1 = 2

j∈I(+,−)
(y
j
− 1) + 2

j∈I(+,+)
y
j
≥ 0.
The case

j∈I(+,−)
1 ≤

j∈I(−,+)
1 is similar. This proves the statement.
b) Fix p ∈ (0, 1) and a rational t ∈ (
1
2
, 1). Choose a pair of positive
integers m and l such that mt = l(1 −t) and set n = m + l. Let
x
i
= t, i = 1, 2, . . . , m; x
i
= t − 1, i = m + 1, m + 2, . . . , n;
y
i

) + (1 −t)
p
− (m −1 + t)
p
,
which is possitive for m big enough.
Problem 6. Suppose that F is a family of finite subsets of N and for
any two sets A, B ∈ F we have A ∩ B = Ø.
a) Is it true that there is a finite subset Y of N such that for any
A, B ∈ F we have A ∩ B ∩ Y = Ø?
b) Is the statement a) true if we suppose in addition that all of the
members of F have the same size?
Justify your answers.
Solution.
a) No. Consider F = {A
1
, B
1
, . . . , A
n
, B
n
, . . .}, where A
n
= {1, 3, 5, . . . , 2n−
1, 2n}, B
n
= {2, 4, 6, . . . , 2n, 2n + 1}.
b) Yes. We will prove inductively a stronger statement:
Suppose F , G are

0
) = C}.
Then F = ∪
Ø=C⊂A
0
∪B
0
F (C). It is enough to prove that for any pair of non-
empty sets C, D ⊂ A
0
∪B
0
the families F (C) and G(D) satisfy the statement.
Indeed, if we denote by Y
C,D
the corresponding finite set, then the
finite set ∪
C,D⊂A
0
∪B
0
Y
C,D
will satisfy the statement for F and G. The proof
for F (C) and G(D).
If C ∩D = Ø, it is trivial.
If C ∩ D = Ø, then any two sets A ∈ F (C), B ∈ G(D) must meet
outside A
0
∪ B