10th International Mathematical Competition for University Students
Cluj-Napoca, July 2003
Day 1
1. (a) Let a1, a2, . . . be a sequence of real numbers such that a1= 1 and an+1 >3
2anfor all n.
Prove that the sequence an
3
2n−1
has a finite limit or tends to infinity. (10 points)
(b) Prove that for all α > 1 there exists a sequence a1, a2, . . . with the same properties such
that
lim an
3
2n−1=α.
(10 points)
Solution. (a) Let bn=an
3
2n−1. Then an+1 >3
2anis equivalent to bn+1 > bn, thus the sequence
(bn) is strictly increasing. Each increasing sequence has a finite limit or tends to infinity.
(b) For all α > 1 there exists a sequence 1 = b1< b2< . . . which converges to α. Choosing
an=3
2n−1bn, we obtain the required sequence (an).
2. Let a1, a2. . . , a51 be non-zero elements of a field. We simultaneously replace each element with
the sum of the 50 remaining ones. In this way we get a sequence b1. . . , b51. If this new sequence is
a permutation of the original one, what can be the characteristic of the field? (The characteristic
of a field is p, if pis the smallest positive integer such that x+x+. . . +x
|{z }
p
= 0 for any element x
of the field. If there exists no such p, the characteristic is 0.) (20 points)
Solution. Let S=a1+a2+· · · +a51. Then b1+b2+· · · +b51 = 50S. Since b1, b2,· · · , b51 is a
permutation of a1, a2,· · · , a51, we get 50S=S, so 49S= 0. Assume that the characteristic of the
field is not equal to 7. Then 49S= 0 implies that S= 0. Therefore bi=−aifor i= 1,2,· · · ,51.
On the other hand, bi=aϕ(i), where ϕ∈S51.Therefore, if the characteristic is not 2, the sequence
a1, a2,· · · , a51 can be partitioned into pairs {ai, aϕ(i)}of additive inverses. But this is impossible,
since 51 is an odd number. It follows that the characteristic of the field is 7 or 2.
The characteristic can be either 2 or 7. For the case of 7, x1=. . . =x51 = 1 is a possible
choice. For the case of 2, any elements can be chosen such that S= 0, since then bi=−ai=ai.
3. Let Abe an n×nreal matrix such that 3A3=A2+A+I(Iis the identity matrix). Show
that the sequence Akconverges to an idempotent matrix. (A matrix Bis called idempotent if
B2=B.) (20 points)
Solution. The minimal polynomial of Ais a divisor of 3x3−x2−x−1. This polynomial has three
different roots. This implies that Ais diagonalizable: A=C−1DC where Dis a diagonal matrix.
The eigenvalues of the matrices Aand Dare all roots of polynomial 3x3−x2−x−1. One of the
three roots is 1, the remaining two roots have smaller absolute value than 1. Hence, the diagonal
elements of Dk, which are the kth powers of the eigenvalues, tend to either 0 or 1 and the limit
M= lim Dkis idempotent. Then lim Ak=C−1MC is idempotent as well.
4. Determine the set of all pairs (a, b) of positive integers for which the set of positive integers
can be decomposed into two sets Aand Bsuch that a·A=b·B. (20 points)
Solution. Clearly aand bmust be different since Aand Bare disjoint.
1
10th International Mathematical Competition for University Students
Cluj-Napoca, July 2003
Day 2
1. Let Aand Bbe n×nreal matrices such that AB +A+B= 0. Prove that AB =BA.
Solution. Since (A+I)(B+I) = AB +A+B+I=I(Iis the identity matrix), matrices
A+Iand B+Iare inverses of each other. Then (A+I)(B+I) = (B+I)(A+I) and
AB +BA.
2. Evaluate the limit
lim
x→0+ Z2x
x
sinmt
tndt (m, n ∈N).
Solution. We use the fact that sin t
tis decreasing in the interval (0, π) and lim
t→0+0
sin t
t= 1.
For all x∈(0,π
2) and t∈[x, 2x] we have sin 2x
2x < sin t
t<1, thus
sin 2x
2xmZ2x
x
tm
tn<Z2x
x
sinmt
tndt < Z2x
x
tm
tndt,
Z2x
x
tm
tndt =xm−n+1 Z2
1
um−ndu.
The factor sin 2x
2xm
tends to 1. If m−n+ 1 <0, the limit of xm−n+1 is infinity; if
m−n+ 1 >0 then 0. If m−n+ 1 = 0 then xm−n+1 R2
1um−ndu = ln 2. Hence,
lim
x→0+0
2x
Z
x
sinmt
tndt =
0, m ≥n
ln 2, n −m= 1
+∞, n −m > 1.
.
3. Let Abe a closed subset of Rnand let Bbe the set of all those points b∈Rnfor which
there exists exactly one point a0∈Asuch that
|a0−b|= inf
a∈A|a−b|.
Prove that Bis dense in Rn; that is, the closure of Bis Rn.
Solution. Let b0/∈A(otherwise b0∈A⊂B), %= inf
a∈A|a−b0|. The intersection of the ball
of radius %+ 1 with centre b0with set Ais compact and there exists a0∈A:|a0−b0|=%.
1
Denote by Br(a) = {x∈Rn:|x−a| ≤ r}and ∂Br(a) = {x∈Rn:|x−a|=r}the
ball and the sphere of center aand radius r, respectively.
If a0is not the unique nearest point then for any point aon the open line segment (a0, b0)
we have B|a−a0|(a)⊂B%(b0) and ∂B|a−a0|(a)T∂B%(b0) = {a0}, therefore (a0, b0)⊂Band
b0is an accumulation point of set B.
4. Find all positive integers nfor which there exists a family Fof three-element subsets
of S={1,2, . . . , n}satisfying the following two conditions:
(i) for any two different elements a, b ∈S, there exists exactly one A∈ F containing
both a, b;
(ii) if a, b, c, x, y, z are elements of Ssuch that if {a, b, x},{a, c, y},{b, c, z}∈F, then
{x, y, z} ∈ F.
Solution. The condition (i) of the problem allows us to define a (well-defined) operation
∗on the set Sgiven by
a∗b=cif and only if {a, b, c} ∈ F, where a6=b.
We note that this operation is still not defined completely (we need to define a∗a), but
nevertheless let us investigate its features. At first, due to (i), for a6=bthe operation
obviously satisfies the following three conditions:
(a) a6=a∗b6=b;
(b) a∗b=b∗a;
(c) a∗(a∗b) = b.
What does the condition (ii) give? It claims that
(e’) x∗(a∗c) = x∗y=z=b∗c= (x∗a)∗c
for any three different x, a, c, i.e. that the operation is associative if the arguments are
different. Now we can complete the definition of ∗. In order to save associativity for non-
different arguments, i.e. to make b=a∗(a∗b) = (a∗a)∗bhold, we will add to San extra
element, call it 0, and define
(d) a∗a= 0 and a∗0 = 0 ∗a=a.
Now it is easy to check that, for any a, b, c ∈S∪ {0}, (a),(b),(c) and (d), still hold, and
(e) a∗b∗c:= (a∗b)∗c=a∗(b∗c).
We have thus obtained that (S∪ {0},∗) has the structure of a finite Abelian group,
whose elements are all of order two. Since the order of every such group is a power of 2,
we conclude that |S∪ {0}| =n+ 1 = 2mand n= 2m−1 for some integer m≥1.
Given n= 2m−1, according to what we have proven till now, we will construct a family
of three-element subsets of Ssatisfying (i) and (ii). Let us define the operation ∗in the
following manner:
if a=a0+ 2a1+. . . + 2m−1am−1and b=b0+ 2b1+. . . + 2m−1bm−1, where ai, bi
are either 0 or 1, we put a∗b=|a0−b0|+ 2|a1−b1|+. . . + 2m−1|am−1−bm−1|.
2
It is simple to check that this ∗satisfies (a),(b),(c) and (e’). Therefore, if we include in
Fall possible triples a, b, a ∗b, the condition (i) follows from (a),(b) and (c), whereas the
condition (ii) follows from (e’)
The answer is: n= 2m−1.
5. (a) Show that for each function f:Q×Q→Rthere exists a function g:Q→Rsuch
that f(x, y)≤g(x) + g(y) for all x, y ∈Q.
(b) Find a function f:R×R→Rfor which there is no function g:R→Rsuch that
f(x, y)≤g(x) + g(y) for all x, y ∈R.
Solution. a) Let ϕ:Q→Nbe a bijection. Define g(x) = max{|f(s, t)|:s, t ∈Q, ϕ(s)≤
ϕ(x), ϕ(t)≤ϕ(x)}. We have f(x, y)≤max{g(x), g(y)} ≤ g(x) + g(y).
b) We shall show that the function defined by f(x, y) = 1
|x−y|for x6=yand f(x, x) = 0
satisfies the problem. If, by contradiction there exists a function gas above, it results, that
g(y)≥1
|x−y|−f(x) for x, y ∈R, x 6=y; one obtains that for each x∈R,lim
y→xg(y) = ∞.
We show, that there exists no function ghaving an infinite limit at each point of a bounded
and closed interval [a, b].
For each k∈N+denote Ak={x∈[a, b] : |g(x)| ≤ k}.
We have obviously [a, b] = ∪∞
k=1Ak. The set [a, b] is uncountable, so at least one of the
sets Akis infinite (in fact uncountable). This set Akbeing infinite, there exists a sequence
in Akhaving distinct terms. This sequence will contain a convergent subsequence (xn)n∈N
convergent to a point x∈[a, b]. But lim
y→xg(y) = ∞implies that g(xn)→ ∞, a contradiction
because |g(xn)| ≤ k, ∀n∈N.
Second solution for part (b). Let Sbe the set of all sequences of real numbers. The
cardinality of Sis |S|=|R|ℵ0= 2ℵ2
0= 2ℵ0=|R|. Thus, there exists a bijection h:R→S.
Now define the function fin the following way. For any real xand positive integer n,
let f(x, n) be the nth element of sequence h(x). If yis not a positive integer then let
f(x, y) = 0. We prove that this function has the required property.
Let gbe an arbitrary R→Rfunction. We show that there exist real numbers x, y
such that f(x, y)> g(x) + g(y). Consider the sequence (n+g(n))∞
n=1. This sequence is an
element of S, thus (n+g(n))∞
n=1 =h(x) for a certain real x. Then for an arbitrary positive
integer n,f(x, n) is the nth element, f(x, n) = n+g(n). Choosing nsuch that n > g(x),
we obtain f(x, n) = n+g(n)> g(x) + g(n).
6. Let (an)n∈Nbe the sequence defined by
a0= 1, an+1 =1
n+ 1
n
X
k=0
ak
n−k+ 2.
Find the limit
lim
n→∞
n
X
k=0
ak
2k,
3
if it exists.
Solution. Consider the generating function f(x) = P∞
n=0 anxn. By induction 0 < an≤1,
thus this series is absolutely convergent for |x|<1, f(0) = 1 and the function is positive
in the interval [0,1). The goal is to compute f(1
2).
By the recurrence formula,
f0(x) =
∞
X
n=0
(n+ 1)an+1xn=
∞
X
n=0
n
X
k=0
ak
n−k+ 2xn=
=
∞
X
k=0
akxk
∞
X
n=k
xn−k
n−k+ 2 =f(x)
∞
X
m=0
xm
m+ 2.
Then
ln f(x) = ln f(x)−ln f(0) = Zx
0
f0
f=
∞
X
m=0
xm+1
(m+ 1)(m+ 2) =
=
∞
X
m=0 xm+1
(m+ 1) −xm+1
(m+ 2)= 1 + 1−1
x∞
X
m=0
xm+1
(m+ 1) = 1 + 1−1
xln 1
1−x,
ln f1
2= 1 −ln 2,
and thus f(1
2) = e
2.
4