11th International Mathematical Competition for University Students
Skopje, 25–26 July 2004
Solutions for problems on Day 2
1. Let Abe a real 4 ×2 matrix and Bbe a real 2 ×4 matrix such that
AB =
1 0 −1 0
0 1 0 −1
−1 0 1 0
0−1 0 1
.
Find BA. [20 points]
Solution. Let A=A1
A2and B=B1B2where A1, A2, B1, B2are 2 ×2 matrices. Then
1 0 −1 0
0 1 0 −1
−1 0 1 0
0−1 0 1
=A1
A2B1B2=A1B1A1B2
A2B1A2B2
therefore, A1B1=A2B2=I2and A1B2=A2B1=−I2. Then B1=A−1
1,B2=−A−1
1and A2=B−1
2=
−A1. Finally,
BA =B1B2A1
A2=B1A1+B2A2= 2I2=2 0
0 2
2. Let f, g : [a, b]→[0,∞) be continuous and non-decreasing functions such that for each x∈[a, b] we
have Zx
apf(t)dt ≤Zx
apg(t)dt
and Rb
apf(t)dt =Rb
apg(t)dt.
Prove that Rb
ap1 + f(t)dt ≥Rb
ap1 + g(t)dt. [20 points]
Solution. Let F(x) = Rx
apf(t)dt and G(x) = Rx
apg(t)dt. The functions F, G are convex, F(a) = 0 =
G(a) and F(b) = G(b) by the hypothesis. We are supposed to show that
Zb
aq1 + F0(t)2dt ≥Zb
aq1 + G0(t)2dt
i.e. The length ot the graph of Fis ≥the length of the graph of G. This is clear since both functions are
convex, their graphs have common ends and the graph of Fis below the graph of G— the length of the
graph of Fis the least upper bound of the lengths of the graphs of piecewise linear functions whose values
at the points of non-differentiability coincide with the values of F, if a convex polygon P1is contained in
a polygon P2then the perimeter of P1is ≤the perimeter of P2.
3. Let Dbe the closed unit disk in the plane, and let p1, p2, . . . , pnbe fixed points in D. Show that there
exists a point pin Dsuch that the sum of the distances of pto each of p1, p2, . . . , pnis greater than or
equal to 1. [20 points]
Solution. considering as vectors, thoose pto be the unit vector which points into the opposite direction as
n
P
i=1
pi. Then, by the triangle inequality,
n
X
i=1
|p−pi| ≥
np −
n
X
i=1
pi
=n+
n
X
i=1
pi
≥n..
4. For n≥1 let Mbe an n×ncomplex matrix with distinct eigenvalues λ1, λ2, . . . , λk, with multiplicities
m1, m2, . . . , mk, respectively. Consider the linear operator LMdefined by LM(X) = MX +XMT, for any
complex n×nmatrix X. Find its eigenvalues and their multiplicities. (MTdenotes the transpose of M;
that is, if M= (mk,l), then MT= (ml,k).) [20 points]
Solution. We first solve the problem for the special case when the eigenvalues of Mare distinct and all sums
λr+λsare different. Let λrand λsbe two eigenvalues of Mand ~vr,~vseigenvectors associated to them, i.e.
M~vj=λ~vjfor j=r, s. We have M~vr(~vs)T+~vr(~vs)TMT= (M~vr)(~vs)T+~vrM~vsT=λr~vr(~vs)T+λs~vr(~vs)T,
so ~vr(~vs) is an eigenmatrix of LMwith the eigenvalue λr+λs.
Notice that if λr6=λsthen vectors ~u, ~w are linearly independent and matrices ~u(~w)Tand ~w(~u)Tare
linearly independent, too. This implies that the eigenvalue λr+λsis double if r6=s.
The map LMmaps n2–dimensional linear space into itself, so it has at most n2eigenvalues. We already
found n2eigenvalues, so there exists no more and the problem is solved for the special case.
In the general case, matrix Mis a limit of matrices M1, M2, . . . such that each of them belongs to the
special case above. By the continuity of the eigenvalues we obtain that the eigenvalues of LMare
•2λrwith multiplicity m2
r(r= 1, . . . , k);
•λr+λswith multiplicity 2mrms(1 ≤r < s ≤k).
(It can happen that the sums λr+λsare not pairwise different; for those multiple values the multiplicities
should be summed up.)
5. Prove that Z1
0Z1
0
dx dy
x−1+|ln y| − 1≤1.[20 points]
Solution 1. First we use the inequality
x−1−1≥ | ln x|, x ∈(0,1],
which follows from
(x−1−1)
x=1 =|ln x||x=1 = 0,
(x−1−1)0=−1
x2≤ − 1
x=|ln x|0, x ∈(0,1].
Therefore Z1
0Z1
0
dx dy
x−1+|ln y| − 1≤Z1
0Z1
0
dx dy
|ln x|+|ln y|=Z1
0Z1
0
dx dy
|ln(x·y)|.
Substituting y=u/x, we obtain
Z1
0Z1
0
dx dy
|ln(x·y)|=Z1
0Z1
u
dx
xdu
|ln u|=Z1
0
|ln u| · du
|ln u|= 1.
Solution 2. Substituting s=x−1−1 and u=s−ln y,
Z1
0Z1
0
dx dy
x−1+|ln y| − 1=Z∞
0Z∞
s
es−u
(s+ 1)2ududs =Z∞
0Zu
0
es
(s+ 1)2dse−u
udsdu.
Since the function es
(s+1)2is convex,
Zu
0
es
(s+ 1)2ds ≤u
2eu
(u+ 1)2+ 1
so
Z1
0Z1
0
dx dy
x−1+|ln y| − 1≤Z∞
0
u
2eu
(u+ 1)2+ 1e−u
udu =1
2Z∞
0
du
(u+ 1)2+Z∞
0
e−udu= 1.
6. For n≥0 define matrices Anand Bnas follows: A0=B0= (1) and for every n > 0
An=An−1An−1
An−1Bn−1and Bn=An−1An−1
An−10.
Denote the sum of all elements of a matrix Mby S(M). Prove that S(Ak−1
n) = S(An−1
k) for every n, k ≥1.
[20 points]
Solution. The quantity S(Ak−1
n) has a special combinatorical meaning. Consider an n×ktable filled with
0’s and 1’s such that no 2 ×2 contains only 1’s. Denote the number of such fillings by Fnk. The filling of
each row of the table corresponds to some integer ranging from 0 to 2n−1 written in base 2. Fnk equals
to the number of k-tuples of integers such that every two consecutive integers correspond to the filling of
n×2 table without 2 ×2 squares filled with 1’s.
Consider binary expansions of integers iand jinin−1. . . i1and jnjn−1. . . j1. There are two cases:
1. If injn= 0 then iand jcan be consecutive iff in−1. . . i1and jn−1. . . j1can be consequtive.
2. If in=jn= 1 then iand jcan be consecutive iff in−1jn−1= 0 and in−2. . . i1and jn−2. . . j1can be
consecutive.
Hence iand jcan be consecutive iff (i+ 1, j + 1)-th entry of Anis 1. Denoting this entry by ai,j , the sum
S(Ak−1
n) = P2n−1
i1=0 · · · P2n−1
ik=0 ai1i2ai2i3· · · aik−1ikcounts the possible fillings. Therefore Fnk =S(Ak−1
n).
The the obvious statement Fnk =Fkn completes the proof.
11th International Mathematical Competition for University Students
Skopje, 25–26 July 2004
Solutions for problems on Day 1
Problem 1. Let Sbe an infinite set of real numbers such that |s1+s2+··· +sk|<1 for every finite subset
{s1, s2, . . . , sk} ⊂ S. Show that Sis countable. [20 points]
Solution. Let Sn=S∩(1
n,∞) for any integer n > 0. It follows from the inequality that |Sn|< n. Similarly, if we
define S−n=S∩(−∞,−1
n), then |S−n|< n. Any nonzero x∈Sis an element of some Snor S−n, because there
exists an nsuch that x > 1
n, or x < −1
n. Then S⊂ {0}∪ S
n∈N
(Sn∪S−n), Sis a countable union of finite sets, and
hence countable.
Problem 2. Let P(x) = x2−1. How many distinct real solutions does the following equation have:
P(P(. . . (P
|{z }
2004
(x)) . . . )) = 0 ? [20 points]
Solution. Put Pn(x) = P(P(...(P
|{z }
n
(x))...)). As P1(x)≥ −1, for each x∈R, it must be that Pn+1(x) = P1(Pn(x)) ≥
−1, for each n∈Nand each x∈R. Therefore the equation Pn(x) = a, where a < −1 has no real solutions.
Let us prove that the equation Pn(x) = a, where a > 0, has exactly two distinct real solutions. To this end we
use mathematical induction by n. If n= 1 the assertion follows directly. Assuming that the assertion holds for a
n∈Nwe prove that it must also hold for n+ 1. Since Pn+1(x) = ais equivalent to P1(Pn(x)) = a, we conclude
that Pn(x) = √a+ 1 or Pn(x) = −√a+ 1.The equation Pn(x) = √a+ 1, as √a+ 1 >1, has exactly two distinct
real solutions by the inductive hypothesis, while the equation Pn(x) = −√a+ 1 has no real solutions (because
−√a+ 1 <−1).Hence the equation Pn+1(x) = a, has exactly two distinct real solutions.
Let us prove now that the equation Pn(x) = 0 has exactly n+ 1 distinct real solutions. Again we use
mathematical induction. If n= 1 the solutions are x=±1, and if n= 2 the solutions are x= 0 and x=±√2,
so in both cases the number of solutions is equal to n+ 1. Suppose that the assertion holds for some n∈N.
Note that Pn+2(x) = P2(Pn(x)) = P2
n(x)(P2
n(x)−2), so the set of all real solutions of the equation Pn+2 = 0 is
exactly the union of the sets of all real solutions of the equations Pn(x) = 0, Pn(x) = √2 and Pn(x) = −√2.
By the inductive hypothesis the equation Pn(x) = 0 has exactly n+ 1 distinct real solutions, while the equations
Pn(x) = √2 and Pn(x) = −√2 have two and no distinct real solutions, respectively. Hence, the sets above being
pairwise disjoint, the equation Pn+2(x) = 0 has exactly n+ 3 distinct real solutions. Thus we have proved that,
for each n∈N, the equation Pn(x) = 0 has exactly n+ 1 distinct real solutions, so the answer to the question
posed in this problem is 2005.
Problem 3. Let Snbe the set of all sums
n
P
k=1
xk, where n≥2, 0 ≤x1, x2, . . . , xn≤π
2and
n
X
k=1
sin xk= 1 .
a) Show that Snis an interval. [10 points]
b) Let lnbe the length of Sn. Find lim
n→∞ ln.[10 points]
Solution. (a) Equivalently, we consider the set
Y={y= (y1, y2, ..., yn)|0≤y1, y2, ..., yn≤1, y1+y2+... +yn= 1} ⊂ Rn
and the image f(Y) of Yunder
f(y) = arcsin y1+ arcsin y2+... + arcsin yn.
Note that f(Y) = Sn. Since Yis a connected subspace of Rnand fis a continuous function, the image f(Y) is
also connected, and we know that the only connected subspaces of Rare intervals. Thus Snis an interval.
(b) We prove that
narcsin 1
n≤x1+x2+... +xn≤π
2.
Since the graph of sin xis concave down for x∈[0,π
2], the chord joining the points (0,0) and (π
2,1) lies below the
graph. Hence 2x
π≤sin xfor all x∈[0,π
2]
and we can deduce the right-hand side of the claim:
2
π(x1+x2+... +xn)≤sin x1+ sin x2+... + sin xn= 1.
The value 1 can be reached choosing x1=π
2and x2=··· =xn= 0.
The left-hand side follows immediately from Jensen’s inequality, since sin xis concave down for x∈[0,π
2] and
0≤x1+x2+...+xn
n<π
21
n=sin x1+ sin x2+... + sin xn
n≤sin x1+x2+... +xn
n.
Equality holds if x1=··· =xn= arcsin 1
n.
Now we have computed the minimum and maximum of interval Sn; we can conclude that Sn= [narcsin 1
n,π
2].
Thus ln=π
2−narcsin 1
nand
lim
n→∞ ln=π
2−lim
n→∞
arcsin(1/n)
1/n =π
2−1.
Problem 4. Suppose n≥4 and let Mbe a finite set of npoints in R3, no four of which lie in a plane. Assume
that the points can be coloured black or white so that any sphere which intersects Min at least four points has
the property that exactly half of the points in the intersection of Mand the sphere are white. Prove that all of
the points in Mlie on one sphere. [20 points]
Solution. Define f:M→ {−1,1},f(X) = −1, if Xis white
1, if Xis black . The given condition becomes PX∈Sf(X) = 0
for any sphere Swhich passes through at least 4 points of M. For any 3 given points A,B,Cin M, denote by
S(A, B, C) the set of all spheres which pass through A,B,Cand at least one other point of Mand by |S(A, B, C)|
the number of these spheres. Also, denote by Pthe sum PX∈Mf(X).
We have
0 = X
S∈S(A,B,C)X
X∈S
f(X) = (|S(A, B, C)| − 1) (f(A) + f(B) + f(C))+X(1)
since the values of A,B,Cappear |S(A, B, C)|times each and the other values appear only once.
If there are 3 points A,B,Csuch that |S(A, B, C)|= 1, the proof is finished.
If |S(A, B, C)|>1 for any distinct points A,B,Cin M, we will prove at first that P= 0.
Assume that P>0. From (1) it follows that f(A) + f(B) + f(C)<0 and summing by all n
3possible
choices of (A, B, C) we obtain that n
3P<0, which means P<0 (contradicts the starting assumption). The
same reasoning is applied when assuming P<0.
Now, from P= 0 and (1), it follows that f(A) + f(B) + f(C) = 0 for any distinct points A,B,Cin M.
Taking another point D∈M, the following equalities take place
f(A) + f(B) + f(C) = 0
f(A) + f(B) + f(D) = 0
f(A) + f(C) + f(D) = 0
f(B) + f(C) + f(D) = 0
which easily leads to f(A) = f(B) = f(C) = f(D) = 0, which contradicts the definition of f.
Problem 5. Let Xbe a set of 2k−4
k−2+ 1 real numbers, k≥2. Prove that there exists a monotone sequence
{xi}k
i=1 ⊆Xsuch that
|xi+1 −x1| ≥ 2|xi−x1|
for all i= 2, . . . , k−1. [20 points]