IF I N = J N = 1 THEN I AND J CAN BE CONSECUTIVE IFF I N−1 J N−1 =...

2. If i _n = j _n = 1 then i and j can be consecutive iff i n−1 j n−1 = 0 and i n−2 . . . i ₁ and j n−2 . . . j ₁ can be

consecutive.

Hence i and j can be consecutive iff (i + 1, j + 1)-th entry of A _n is 1. Denoting this entry by a _i,j , the sum

S(A ^k−1 _n ) = P 2

−1

i

=0 · · · P 2

−1

i

=0 a _i

_i

a _i

_i

· · · a _i

_i

counts the possible fillings. Therefore F _nk = S(A ^k−1 _n ).

The the obvious statement F _nk = F _kn completes the proof.

11 ^th International Mathematical Competition for University Students

Skopje, 25–26 July 2004

Solutions for problems on Day 1

Problem 1. Let S be an infinite set of real numbers such that |s ₁ + s ₂ + · · · + s _k | < 1 for every finite subset

{s ₁ , s ₂ , . . . , s _k } ⊂ S. Show that S is countable. [20 points]

Solution. Let S _n = S ∩ ( ¹ _n , ∞) for any integer n > 0. It follows from the inequality that |S _n | < n. Similarly, if we

define S −n = S ∩ (−∞, − _n ¹ ), then |S _−n | < n. Any nonzero x ∈ S is an element of some S n or S −n , because there

exists an n such that x > _n ¹ , or x < − ¹ _n . Then S ⊂ {0} ∪ S

(S _n ∪ S −n ), S is a countable union of finite sets, and

n∈N

hence countable.

Problem 2. Let P (x) = x ² − 1. How many distinct real solutions does the following equation have:

P (P (. . . (P

(x)) . . . )) = 0 ? [20 points]

| {z }

2004

(x))...)). As P 1 (x) ≥ −1, for each x ∈ R, it must be that P n+1 (x) = P 1 (P n (x)) ≥

Solution. Put P n (x) = P (P (...(P

n

−1, for each n ∈ N and each x ∈ R. Therefore the equation P n (x) = a, where a < −1 has no real solutions.

Let us prove that the equation P _n (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 ∈ N we prove that it must also hold for n + 1. Since P n+1 (x) = a is equivalent to P 1 (P n (x)) = a, we conclude

that P _n (x) = √

a + 1 or P _n (x) = − √

a + 1. The equation P _n (x) = √

a + 1, as √

a + 1 > 1, has exactly two distinct

real solutions by the inductive hypothesis, while the equation P _n (x) = − √

a + 1 has no real solutions (because

− √

a + 1 < −1). Hence the equation P n+1 (x) = a, has exactly two distinct real solutions.

Let us prove now that the equation P _n (x) = 0 has exactly n + 1 distinct real solutions. Again we use