Baltic Way 2005

Stockholm, November 5, 2005

Problems and solutions

1. Let a0 be a positive integer. Define the sequence an , n ≥ 0, as follows: If

j
an = ∑ ci 10i
i =0

where ci are integers with 0 ≤ ci ≤ 9, then

an+1 = c2005
0 + c2005
1 + · · · + c2005
j .

Is it possible to choose a0 so that all the terms in the sequence are distinct?
Answer: No, the sequence must contain two equal terms.
Solution: It is clear that there exists a smallest positive integer k such that

10k > (k + 1) · 92005 .

We will show that there exists a positive integer N such that an consists of less than k + 1
decimal digits for all n ≥ N. Let ai be a positive integer which consists of exactly j + 1
digits, that is,

10 j ≤ ai < 10 j+1 .

We need to prove two statements:

• ai+1 has less than k + 1 digits if j < k; and
• ai > ai+1 if j ≥ k.
To prove the first statement, notice that

ai+1 ≤ ( j + 1) · 92005 < (k + 1) · 92005 < 10k

and hence ai+1 consists of less than k + 1 digits. To prove the second statement, notice
that ai consists of j + 1 digits, none of which exceeds 9. Hence ai+1 ≤ ( j + 1) · 92005 and
because j ≥ k, we get ai ≥ 10 j > ( j + 1) · 92005 ≥ ai+1 , which proves the second statement.
It is now easy to derive the result from this statement. Assume that a0 consists of k + 1 or
more digits (otherwise we are done, because then it follows inductively that all terms of
the sequence consist of less than k + 1 digits, by the first statement). Then the sequence
starts with a strictly decreasing segment a0 > a1 > a2 > · · · by the second statement, so
for some index N the number a N has less than k + 1 digits. Then, by the first statement,
each number an with n ≥ N consists of at most k digits. By the Pigeonhole Principle,
there are two different indices n, m ≥ N such that an = am .
2. Let α, β and γ be three angles with 0 ≤ α, β, γ < 90◦ and sin α + sin β + sin γ = 1. Show
that
3
tan2 α + tan2 β + tan2 γ ≥ .
8
Solution: Since tan2 x = 1/ cos2 x − 1, the inequality to be proved is equivalent to
1 1 1 27
+ + ≥ .
cos2 α cos2 β cos2 γ 8

1
The AM-HM inequality implies

3 cos2 α + cos2 β + cos2 γ

1 1 1
≤
+ + 3
cos2 α cos2 β cos2 γ

3 − (sin2 α + sin2 β + sin2 γ)

=
3
 sin α + sin β + sin γ 2
≤ 1−
3
8
=
9
and the result follows.
3. Consider the sequence ak defined by a1 = 1, a2 = 12 ,

1 1
a k +2 = a k + a k +1 + for k ≥ 1.
2 4ak ak+1

Prove that
1 1 1 1
+ + +···+ < 4.
a1 a3 a2 a4 a3 a5 a98 a100

Solution: Note that

1 2 2
< − ,
a k a k +2 a k a k +1 a k +1 a k +2

because this inequality is equivalent to the inequality

1
a k +2 > a k + a k +1 ,
2
which is evident for the given sequence. Now we have

1 1 1 1
+ + +···+
a1 a3 a2 a4 a3 a5 a98 a100
2 2 2 2
< − + − +···
a1 a2 a2 a3 a2 a3 a3 a4
2
< = 4.
a1 a2

4. Find three different polynomials P( x ) with real coefficients such that P( x2 + 1) = P( x )2 + 1

for all real x.
Answer: For example, P( x ) = x, P( x ) = x2 + 1 and P( x ) = x4 + 2x2 + 2.
Solution: Let Q( x ) = x2 + 1. Then the equation that P must satisfy can be written
P( Q( x )) = Q( P( x )), and it is clear that this will be satisfied for P( x ) = x, P( x ) = Q( x )
and P( x ) = Q( Q( x )).
Solution 2: For all reals x we have P( x )2 + 1 = P( x2 + 1) = P(− x )2 + 1 and consequently,
( P( x ) + P(− x ))( P( x ) − P(− x )) = 0. Now one of the three cases holds:

(a) If both P( x ) + P(− x ) and P( x ) − P(− x ) are not identically 0, then they are non-
constant polynomials and have a finite numbers of roots, so this case cannot hold.

2
(b) If P( x ) + P(− x ) is identically 0 then obviously, P(0) = 0. Consider the infinite
sequence of integers a0 = 0 and an+1 = a2n + 1. By induction it is easy to see that
P( an ) = an for all non-negative integers n. Also, Q( x ) = x has that property, so
P( x ) − Q( x ) is a polynomial with infinitely many roots, whence P( x ) = x.
(c) If P( x ) − P(− x ) is identically 0 then

P( x ) = x2n + bn−1 x2n−2 + · · · + b1 x2 + b0 ,

for some integer n since P( x ) is even and it is easy to see that the coefficient of
x2n must be 1. Putting n = 1 and n = 2 yield the solutions P( x ) = x2 + 1 and
P( x ) = x4 + 2x2 + 2.

Remark: For n = 3 there is no solution, whereas for n = 4 there is the unique solution
P( x ) = x8 + 6x6 + 8x4 + 8x2 + 5.
5. Let a, b, c be positive real numbers with abc = 1. Prove that

a b c
+ 2 + 2 ≤ 1.
a2 +2 b +2 c +2
Solution: For any positive real x we have x2 + 1 ≥ 2x. Hence

a b c a b c
+ 2 + 2 ≤ + +
a2 +2 b +2 c +2 2a + 1 2b + 1 2c + 1
1 1 1
= + + =: R.
2 + 1/a 2 + 1/b 2 + 1/c
R ≤ 1 is equivalent to

2 + 1b 2 + 1c + 2 + 1a 2 + 1c + 2 + 1a 2 + 1b ≤ 2 + 1a 2 + 1b 2 + 1c

1 1 1 1
and to 4 ≤ ab + ac + bc + abc . By abc = 1 and by the AM-GM inequality
r
1 1 1 3 1 2
+ + ≥3 =3
ab ac bc abc
the last inequality follows. Equality appears exactly when a = b = c = 1.
6. Let K and N be positive integers with 1 ≤ K ≤ N. A deck of N different playing cards is
shuffled by repeating the operation of reversing the order of the K topmost cards and moving these
to the bottom of the deck. Prove that the deck will be back in its initial order after a number of
operations not greater than 4 · N 2 /K2 .
Solution: Let N = q · K + r, 0 ≤ r < K, and let us number the cards 1, 2, . . . , N, starting
from the one at the bottom of the deck. First we find out how the cards 1, 2, . . . K are
moving in the deck.
If i ≤ r then the card i is moving along the cycle

i → K + i → 2K + i → · · · → qK + i → (r + 1 − i ) →
K + (r + 1 − i ) → · · · → qK + (r + 1 − i ),

because N − K < qK + i ≤ N and N − K < qK + (r + 1 − i ) ≤ N. The length of this cycle

is 2q + 2. In the special case of i = r + i − 1, it actually consists of two smaller cycles of
length q + 1.

3
 If r < i ≤ K then the card i is moving along the cycle

i → K + i → 2K + i → · · · → (q − 1)K + i →
K + r + 1 − i → K + (K + r + 1 − i) →
2K + (K + r + 1 − i ) → · · · → (q − 1)K + (K + r + 1 − i ),

because N − K < (q − 1)K + i ≤ N and N − K < (q − 1)K + (K + r + 1 − i ) ≤ N. The

length of this cycle is 2q. In the special case of i = K + r + 1 − i, it actually consists of
two smaller cycles of length q.
Since these cycles cover all the numbers 1, . . . , N, we can say that every card returns
to its initial position after either 2q + 2 or 2q operations. Therefore, all the cards are
simultaneously at their initial position after at most lcm(2q + 2, 2q) = 2 lcm(q + 1, q) =
2q(q + 1) operations. Finally,

N 2
2q(q + 1) ≤ (2q)2 = 4q2 ≤ 4


K ,

which concludes the proof.

7. A rectangular array has n rows and six columns, where n > 2. In each cell there is
written either 0 or 1. All rows in the array are different from each other. For each pair of rows
( x1 , x2 , . . . , x6 ) and (y1 , y2 , . . . , y6 ), the row ( x1 y1 , x2 y2 , . . . , x6 y6 ) can also be found in the
array. Prove that there is a column in which at least half of the entries are zeroes.
Solution: Clearly there must be rows with some zeroes. Consider the case when
there is a row with just one zero; we can assume it is (0, 1, 1, 1, 1, 1). Then for each
row (1, x2 , x3 , x4 , x5 , x6 ) there is also a row (0, x2 , x3 , x4 , x5 , x6 ); the conclusion follows.
Consider the case when there is a row with just two zeroes; we can assume it is
(0, 0, 1, 1, 1, 1). Let nij be the number of rows with first two elements i, j. As in the first
case n00 ≥ n11 . Let n01 ≥ n10 ; the other subcase is analogous. Now there are n00 + n01
zeroes in the first column and n10 + n11 ones in the first column; the conclusion follows.
Consider now the case when each row contains at least three zeroes (except (1, 1, 1, 1, 1, 1),
if such a row exists). Let us prove that it is impossible that each such row contains exactly
three zeroes. Assume the opposite. As n > 2 there are at least two rows with zeroes; they
are different, so their product contains at least four zeroes, a contradiction. So there are
more then 3(n − 1) zeroes in the array; so in some column there are more than (n − 1)/2
zeroes; so there are at least n/2 zeroes.
8. Consider a grid of 25 × 25 unit squares. Draw with a red pen contours of squares of any size
on the grid. What is the minimal number of squares we must draw in order to colour all the lines
of the grid?
Answer: 48 squares.
Solution: Consider a diagonal of the square grid. For any grid vertex A on this diagonal
denote by C the farthest endpoint of this diagonal. Let the square with the diagonal AC
be red. Thus, we have defined the set of 48 red squares (24 for each diagonal). It is clear
that if we draw all these squares, all the lines in the grid will turn red.
In order to show that 48 is the minimum, consider all grid segments of length 1
that have exactly one endpoint on the border of the grid. Every horizontal and every
vertical line that cuts the grid into two parts determines two such segments. So we have
4 · 24 = 96 segments. It is evident that every red square can contain at most two of these
segments.

4
9. A rectangle is divided into 200 × 3 unit squares. Prove that the number of ways of splitting
this rectangle into rectangles of size 1 × 2 is divisible by 3.
Solution: Let us denote the number of ways to split some figure into dominos by a
small picture of this figure with a sign #. For example, # = 2.

Let Nn = # (n rows) and γn = # (n − 2 full rows and one row with two cells).
We are going to find a recurrence relation for the numbers Nn .
Observe that

# =# +# +# = 2# +#

# =# +# =# +#

We can generalize our observations by writing the equalities

Nn = 2γn + Nn−2 ,
2γn−2 = Nn−2 − Nn−4 ,
2γn = 2γn−2 + 2Nn−2 .

If we sum up these equalities we obtain the desired recurrence

Nn = 4Nn−2 − Nn−4 .

It is easy to find that N2 = 3, N4 = 11. Now by the recurrence relation it is trivial to

check that N6k+2 ≡ 0 (mod 3).
10. Let m = 30030 = 2 · 3 · 5 · 7 · 11 · 13 and let M be the set of its positive divisors which have
exactly two prime factors. Determine the minimal integer n with the following property: for any
choice of n numbers from M, there exist three numbers a, b, c among them satisfying a · b · c = m.
Answer: n = 11.
Solution: Taking the 10 divisors without the prime 13 shows that n ≥ 11. Consider the
following partition of the 15 divisors into five groups of three each with the property
that the product of the numbers in every group equals m.

{2 · 3, 5 · 13, 7 · 11}, {2 · 5, 3 · 7, 11 · 13}, {2 · 7, 3 · 13, 5 · 11},

{2 · 11, 3 · 5, 7 · 13}, {2 · 13, 3 · 11, 5 · 7}.

If n = 11, there is a group from which we take all three numbers, that is, their product
equals m.
11. Let the points D and E lie on the sides BC and AC, respectively, of the triangle ABC,
satisfying BD = AE. The line joining the circumcentres of the triangles ADC and BEC meets
the lines AC and BC at K and L, respectively. Prove that KC = LC.
Solution: Assume that the circumcircles of triangles ADC and BEC meet at C and P.
The problem is to show that the line KL makes equal angles with the lines AC and BC.
Since the line joining the circumcentres of triangles ADC and BEC is perpendicular to
the line CP, it suffices to show that CP is the angle-bisector of ∠ ACB.

5
 C

E L

K D

A B
P
Since the points A, P, D, C are concyclic, we obtain ∠EAP = ∠ BDP. Analogously, we
have ∠ AEP = ∠ DBP. These two equalities together with AE = BD imply that triangles
APE and DPB are congruent. This means that the distance from P to AC is equal to the
distance from P to BC, and thus CP is the angle-bisector of ∠ ACB, as desired.
12. Let ABCD be a convex quadrilateral such that BC = AD. Let M and N be the midpoints
of AB and CD, respectively. The lines AD and BC meet the line MN at P and Q, respectively.
Prove that CQ = DP.
Solution: Let A0 , B0 , C 0 , D 0 be the feet of the perpendiculars from A, B, C, D, respectively,
onto the line MN. Then

AA0 = BB0 and CC 0 = DD 0 .

Denote by X, Y the feet of the perpendiculars from C, D onto the lines BB0 , AA0 ,
respectively. We infer from the above equalities that AY = BX. Since also BC = AD, the
right-angled triangles BXC and AYD are congruent. This shows that

∠C 0 CQ = ∠ B0 BQ = ∠ A0 AP = ∠ D 0 DP.

Therefore, since CC 0 = DD 0 , the triangles CC 0 Q and DD 0 P are congruent. Thus CQ =

DP.
P
Q

D D0
C
N
C0

Y A0
A M B
X
B0
√
13. What is the smallest number of circles of radius 2 that are needed to cover a rectangle

(a) of size 6 × 3?
(b) of size 5 × 3?

Answer: (a) Six circles, (b) five circles.

Solution: (a) Consider the four corners and the two midpoints of the sides of length 6.
The distance between any two of these six points is 3 or more, so one circle cannot cover
two of these points, and at least six circles are needed.

6
 On the other hand one circle will cover a 2 × 2 square, and it is easy to see that six
such squares can cover the rectangle.

(b) Consider the four corners and the centre of the rectangle. The 5/3
minimum distance between any two of these points √ is the distance
2
between the centre and one of the corners,
√ which
√ is 34/2. This is
greater than the diameter of the circle ( 34/4 > 32/4), so one circle 1
cannot cover two of these points, and at least five circles are needed. 5/2
Partition the rectangle into three rectangles of size 5/3 × 2 and two rectangles of size
5/2 × √1 as shown on the right. It is easy to check that each has a diagonal of length less
than 2 2, so five circles can cover the five small rectangles and hence the 5 × 3 rectangle.
14. Let the medians of the triangle ABC meet at M. Let D and E be different points on the
line BC such that DC = CE = AB, and let P and Q be points on the segments BD and BE,
respectively, such that 2BP = PD and 2BQ = QE. Determine ∠ PMQ.
Answer: ∠ PMQ = 90◦ .
Solution: Draw the parallelogram ABCA0 , with AA0 k BC. Then M lies on BA0 , and
BM = 13 BA0 . So M is on the homothetic image (centre B, dilation 1/3) of the circle with
centre C and radius AB, which meets BC at D and E. The image meets BC at P and Q.
So ∠ PMQ = 90◦ .
A A0

B P Q D C E
15. Let the lines e and f be perpendicular and intersect each other at O. Let A and B lie on e and
C and D lie on f , such that all the five points A, B, C, D and O are distinct. Let the lines b and
d pass through B and D respectively, perpendicularly to AC; let the lines a and c pass through A
and C respectively, perpendicularly to BD. Let a and b intersect at X and c and d intersect at Y.
Prove that XY passes through O.
Solution: Let A1 be the intersection of a with BD, B1 the intersection of b with AC, C1
the intersection of c with BD and D1 the intersection of d with AC. It follows easily by
the given right angles that the following three sets each are concyclic:

• A, A1 , D, D1 , O lie on a circle w1 with diameter AD.

• B, B1 , C, C1 , O lie on a circle w2 with diameter BC.
• C, C1 , D, D1 lie on a circle w3 with diameter DC.

We see that O lies on the radical axis of w1 and w2 . Also, Y lies on the radical axis of w1
and w3 , and on the radical axis of w2 and w3 , so Y is the radical centre of w1 , w2 and
w3 , so it lies on the radical axis of w1 and w2 . Analogously we prove that X lies on the
radical axis of w1 and w2 .

7
 C
X
b

c w3
B1
w2

D1
A e
B
w1 D C1

A1 f d Y

16. Let p be a prime number and let n be a positive integer. Let q be a positive divisor of
(n + 1) p − n p . Show that q − 1 is divisible by p.
Solution: It is sufficient to show the statement for q prime. We need to prove that

( n + 1) p ≡ n p (mod q) =⇒ q ≡ 1 (mod p).

It is obvious that gcd(n, q) = gcd(n + 1, q) = 1 (as n and n + 1 cannot be divisible by q

simultaneously). Hence there exists a positive integer m such that mn ≡ 1 (mod q). In
fact, m is just the multiplicative inverse of n (mod q). Take s = m(n + 1). It is easy to
see that
s p ≡ 1 (mod q).

Let t be the smallest positive integer which satisfies st ≡ 1 (mod q) (t is the order of
s (mod q)). One can easily prove that t divides p. Indeed, write p = at + b where
0 ≤ b < t. Then

a
1 ≡ s p ≡ s at+b ≡ st · sb ≡ sb (mod q).

By the definition of t, we must have b = 0. Hence t divides p. This means that t = 1 or

t = p. However, t = 1 is easily seen to give a contradiction since then we would have

m ( n + 1) ≡ 1 (mod q) or n+1 ≡ n (mod q).

Therefore t = p, and p is the order of s (mod q). By Fermat’s little theorem,

sq−1 ≡ 1 (mod q).

Since p is the order of s (mod q), we have that p divides q − 1, and we are done.
17. A sequence ( xn ), n ≥ 0, is defined as follows: x0 = a, x1 = 2 and xn = 2xn−1 xn−2 −
xn−1 − xn−2 + 1 for n > 1. Find all integers a such that 2x3n − 1 is a perfect square for all
n ≥ 1.
(2m−1)2 +1
Answer: a = 2 where m is an arbitrary positive integer.

8
Solution: Let yn = 2xn − 1. Then

yn = 2(2xn−1 xn−2 − xn−1 − xn−2 + 1) − 1

= 4xn−1 xn−2 − 2xn−1 − 2xn−2 + 1
= (2xn−1 − 1)(2xn−2 − 1) = yn−1 yn−2

when n > 1. Notice that yn+3 = yn+2 yn+1 = y2n+1 yn . We see that yn+3 is a perfect square
if and only if yn is a perfect square. Hence y3n is a perfect square for all n ≥ 1 exactly
(2m−1)2 +1
when y0 is a perfect square. Since y0 = 2a − 1, the result is obtained when a = 2
for all positive integers m.
18. Let x and y be positive integers and assume that z = 4xy/( x + y) is an odd integer. Prove
that at least one divisor of z can be expressed in the form 4n − 1 where n is a positive integer.
Solution: Let x = 2s x1 and y = 2t y1 where x1 and y1 are odd integers. Without loss of
generality we can assume that s ≥ t. We have

2s + t +2 x 1 y 1 2s +2 x 1 y 1
z= = .
2t (2s − t x 1 + y 1 ) 2s − t x 1 + y 1
If s 6= t, then the denominator is odd and therefore z is even. So we have s = t
and z = 2s+2 x1 y1 /( x1 + y1 ). Let x1 = dx2 , y1 = dy2 with gcd( x2 , y2 ) = 1. So z =
2s+2 dx2 y2 /( x2 + y2 ). As z is odd, it must be that x2 + y2 is divisible by 2s+2 ≥ 4, so
x2 + y2 is divisible by 4. As x2 and y2 are odd integers, one of them, say x2 is congruent
to 3 modulo 4. But gcd( x2 , x2 + y2 ) = 1, so x2 is a divisor of z.
19. Is it possible to find 2005 different positive square numbers such that their sum is also a
square number?
Answer: Yes, it is possible.
Solution: Start with a simple Pythagorian identity such as 32 + 42 = 52 . Multiply it by 52

32 · 52 + 42 · 52 = 52 · 52

and insert the identity for the first

32 · (32 + 42 ) + 42 · 52 = 52 · 52
which gives
32 · 32 + 32 · 42 + 42 · 52 = 52 · 52 .

Multiply again by 52

32 · 32 · 52 + 32 · 42 · 52 + 42 · 52 · 52 = 52 · 52 · 52

and split the first term

32 · 32 · (32 + 42 ) + 32 · 42 · 52 + 42 · 52 · 52 = 52 · 52 · 52

that is

32 · 32 · 32 + 32 · 32 · 42 + 32 · 42 · 52 + 42 · 52 · 52 = 52 · 52 · 52 .

This (multiplying by 52 and splitting the first term) can be repeated as often as needed,
each time increasing the number of terms by one.
Clearly, each term is a square number and the terms are strictly increasing from left
to right.

9
20. Find all positive integers n = p1 p2 · · · pk which divide ( p1 + 1)( p2 + 1) · · · ( pk + 1), where
p1 p2 · · · pk is the factorization of n into prime factors (not necessarily distinct).
Answer: All numbers 2r 3s where r and s are non-negative integers and s ≤ r ≤ 2s.
Solution: Let m = ( p1 + 1)( p2 + 1) · · · ( pk + 1). We may assume that pk is the largest
prime factor. If pk > 3 then pk cannot divide m, because if pk divides m it is a prime factor
of pi + 1 for some i, but if pi = 2 then pi + 1 < pk , and otherwise pi + 1 is an even number
with factors 2 and 12 ( pi + 1) which are both strictly smaller than pk . Thus the only primes
that can divide n are 2 and 3, so we can write n = 2r 3s . Then m = 3r 4s = 22s 3r which is
divisible by n if and only if s ≤ r ≤ 2s.

10