Balt92 05 PDF
Balt92 05 PDF
Balt92 05 PDF
14. There is a finite number of towns in a country. They are connected by one direction roads. It is
known that, for any two towns, one of them can be reached from another one. Prove that there
is a town such that all remaining towns can be reached from it.
15. Noah has 8 species of animals to fit into 4 cages of the ark. He plans to put species in each cage.
It turns out that, for each species, there are at most 3 other species with which it cannot share
the accomodation. Prove that there is a way to assign the animals to their cages so that each
species shares with compatible species.
16. All faces of a convex polyhedron are parallelograms. Can the polyhedron have exactly 1992 faces?
17. Quadrangle ABCD is inscribed in a circle with radius 1 in such a way that the diagonal AC is a
diameter of the circle, while the other diagonal BD is as long as AB. The diagonals intesect at
P . It is known that the length of P C is 2/5. How long is the side CD ?
18. Show that in a non-obtuse triangle the perimenter of the triangle is always greater than two times
the diameter of the circumcircle.
19. Let C be a circle in plane. Let C1 and C2 be nonintersecting circles touching C internally at
points A and B respectively. Let t be a common tangent of C1 and C2 touching them at points
D and E respectively, such that both C1 and C2 are on the same side of t. Let F be the point of
intersection of AD and BE. Show that F lies on C.
20. Let a ≤ b ≤ c be the sides of a right triangle, and let 2p be its perimeter. Show that
p(p − c) = (p − a)(p − b) = S ,
where S is the area of the triangle.
“Baltic Way – 92” mathematical team contest
4. There is no such sexagon. The sum of any six consecutive positive integers is odd. On the
other hand, the sum of squares of lengths of the sexagon’s sides is equal to the sum of squares
of their projections onto the two axes. But the sum of squares of the projections has the same
parity as the sum of the projections themselves, the latter being obviously even.
2
5. Use the identity a2 + b2 + (a + b)2 = 2 a4 + b4 + (a + b)4 .
6. Note that
100 3
Y k −1 1 · 2 · (1002 + 100 + 1) 2
3
= 2
> .
k +1 100 · 101 · (1 + 1 + 1) 3
k=2
9. Consider the derivative f ′ (x) = 3x2 + 2ax + b . Since b < 0 , it has two real roots x1 and
x2 . Since f (x) → ±∞ as x → ±∞ , it is sufficient to check that f (x1 ) and f (x2 ) have
different signs, i.e., f (x1 )f (x2 ) < 0 . Dividing f (x) by f ′ (x) and using the equality ab = 9c
2 2 b
we find that the remainder is equal to x( b − a2 ) . Now, as x1 x2 = < 0 we have
3 9 3
2 2
f (x1 )f (x2 ) = x1 x2 ( b − a2 )2 < 0 .
3 9
10. Let p(x) = ax4 + bx3 + cx2 + dx + e with a 6= 0 . From (i) – (iii) we get b = d = 0 , a > 0
and e = 1 . From (iv) it follows that p′ (x) = 4ax3 + 2cx has at least two
r different real roots.
′ −c
Since a > 0 , then c < 0 and p (x) has three roots x = 0 , x = ± . The minimum
r r 2a
−c −c
points mentioned in (iv) must be x = ± , so 2 = 2 and c = −2a . Finally, by (ii)
2a 2a
we have p(x) = a(x2 − 1)2 + 1 − a > 0 for all x , which implies 0 < a 6 1 . It is easy to check
that every such polynomial satisfies the conditions (i) – (iv) .
1
11. By condition (iii) we have f (1) = 1 . Applying condition (iii) to each of (i) and (ii) gives
1
two new conditions (i′ ) and (ii′ ) taking care of q > 2 and 6 q < 1 respectively. Now,
2
a a
for any rational number 6= 1 we can use (i) , (i′ ) , (ii) or (ii′ ) to express f in terms
b b
a′
of f ′ where a′ + b′ < a + b . The recursion therefore finishes in a finite number of steps,
b
when we can use f (1) = 1 . Thus we have established that such a function f exists, and it is
uniquely defined by the given conditions.
Remark. Initially it was also required to determine all fixed points of the function f , i.e.,
all solutions q of the equation f (q) = q , but the Jury of the contest decided to simplify the
problem. We present here a solution for the complete one. First note that if q is a fixed point,
1 1 q
then so is . By (i) , if 0 < q < is a fixed point, then f = q − 1 < 0 which is
q 2 1 − 2q
1 a
impossible, so there are no fixed points 0 < q < or q > 2 . Now, for a fixed point 1 6 6 2
2 b
a a−b b
(ii) easily gives us that −1 = and are fixed points too. It is easy to see that
b b a−b
b b
16 6 2 (the latter holds because is a fixed point). As this new fixed point has
a−b a−b
a
the sum of its numerator and denominator strictly less than we can continue in this manner
b
until, in a finite number of steps, we arrive to the fixed point 1 . By reversing the process, any
a
fixed point q > 1 can be constructed by repeatedly using the condition that if > 1 is a
b
a+b
fixed point then so is , starting with a = b = 1 . It is now an easy exercise to see that
a
Fn+1
these fixed points have the form where {Fn }n∈N is the sequence of Fibonacci numbers.
Fn
12. We show that L = 1 is the only possible value. Assume L > 1 , then there exists a number
ϕ(n)
N such that for any n > N we have > 1 and thus ϕ(n) > n + 1 > N + 1 . But then
n
ϕ cannot be bijective, since the numbers 1, 2, . . . , N − 1 cannot be bijectively mapped onto
1, 2, . . . , N .
ϕ−1 (n)
i.e. lim > 1 , which is a contradiction since ϕ−1 is also bijective.
n→∞ n
1
This can easily be done by induction using the fact that a + > 2 for any a > 0 .
a
14. Consider the town A from which a maximum number of towns can be reached. Suppose there
is a town B which cannot be reached from A . Then A can be reached from B and so one
can reach more towns from B than from A , a contradiction.
15. Start assigning the species to cages in an arbitrary order. Since for each species there are at
most three species incompatible with it, we can easily add it in one of the four cages.
2
Remark. Initially the problem was posed as follows: “. . . He plans to put two species in each
cage . . . ”. Because of a misprint the word “two” disappeared, and the problem became actually
trivial. Let us give a solution to the original problem. Start with the distribution obtained
above. If in some cage A there are more than three species, then there is also a cage B with
at most one species and this species is compatible with at least one species in cage A which
we can then transfer to cage B . Thus we may assume that there are at most three species in
each cage. If there are two cages with 3 species then we can obviously transfer one of these 6
species to one of the remaining two cages. Now, assume the four cages contain 1 , 2 , 2 and
3 species respectively. If the species in the first cage is compatible with one in the fourth cage
then transfer that species to the first cage, and we are done. Otherwise, for an arbitrary species
X in the fourth cage there exists a species compatible with it in either the second or the third
cage. Transfer the other species from that cage to the first cage, and then X to that cage.
16. No, it cannot. Let us call a series of faces F1 , F2 , . . . , Fk a ring if the pairs (F1 , F2 ) , (F2 , F3 ) ,
. . . , (Fk−1 , Fk ) , (Fk , F1 ) each have a common edge and all these common edges are parallel.
It is not difficult to see that any two rings have exactly two common faces and, conversely, each
face belongs to exactly two rings. Therefore, if there are n rings then the total number of faces
must be 2Cn2 = n(n − 1) . But there is no positive integer n such that n(n − 1) = 1992 .
π π
17. Denote 6 ACD = 2α (see Fig. 1). Then 6 CAD = −2α , 6 ABD = 2α ,
−α and 6 ADB =
2 2
|DP | 2
6 CDB = α . The sine theorem applied to triangles DCP and DAP yields =
sin 2α 5 sin α
|DP | 8 2 sin 2α 8 cos 2α
and π = π . Combining these equalities we have =
5 sin α 5 cos α
sin − 2α 5 sin −α
2 2
1
which gives 4 sin α cos2 α = 8 cos 2α sin α and cos 2α + 1 = 4 cos 2α . So we get cos 2α =
3
2
and |CD| = 2 cos 2α = .
3
18. Let K, L, M be the midpoints of the sides AB, BC, AC of a non-obtuse triangle ABC (see
Fig. 2). Note that the centre O of the circumcircle is inside the triangle KLM (or at one of
its vertices if ABC is a right-angled triangle). Therefore |AK|+|KL|+|LC| > |AO|+|OC| and
hence |AB|+|AC|+|BC| > 2 · (|AO|+|OC|) = 2d , where d is the diameter of the circumcircle.
B B
B Ap
p
C1 C2
K L
p p
A C D t E
P O
D C pp
A M C F1 F2
Figure 8 Figure 9 Figure 10
19. Let F1 be the second intersection point of the line AD and the circle C (see Fig. 3). Consider
the homothety with centre A which maps D onto F1 . This homothety maps the circle C1
onto C and the tangent line t of C1 onto the tangent line of the circle C at F1 . Let us do
the same with the circle C2 and the line BE : let F2 be their intersection point and consider
the homothety with centre B , mapping E onto F2 , C2 onto C and t onto the tangent of
C at point F2 . Since the tangents of C at F1 and F2 are both parallel to t , they must
coincide as well as the points F1 and F2 .
20. By straightforward computation, we find:
1 ab
p(p − c) = (a + b)2 − c2 = =S,
4 2
1 ab
(p − a)(p − b) = c2 − (a − b)2 = =S.
4 2
3
1
11. An equilateral triangle is divided into n2 congruent equilateral triangles. A spider stands at one
of the vertices, a fly at another. Alternately each of them moves to a neighbouring vertex. Prove
that the spider can always catch the fly.
12. There are 13 cities in a certain kingdom. Between some pairs of the cities a two-way direct bus,
train or plane connections are established. What is the least possible number of connections to
be established in order that choosing any two means of transportation one can go from any city
to any other without using the third kind of vehicle?
2
13. An equilateral triangle ABC is divided into 100 congruent equilateral triangles. What is the
greatest number of vertices of small triangles that can be chosen so that no two of them lie on a
line that is parallel to any of the sides of the triangle ABC.
14. A square is divided into 16 equal squares, obtaining the set of 25 different vertices. What is the
least number of vertices one must remove from this set, so that no 4 points of the remaining set
are the vertices of any square with sides parallel to the sides of the initial square?
15. On each face of two dice some positive integer is written. The two dice are thrown and the
numbers on the top face are added. Determine whether one can select the integers on the faces
so that the possible sums are 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, all equally likely?
16. Two circles, both with the same radius r, are placed in the plane without intersecting each other.
A line in the plane intersects the first circle at the points A, B and the other at points C, D, so
that |AB| = |BC| = |CD| = 14 cm. Another line intersects the circles at E, F , respectively G,
H so that |EF | = |F G| = |GH| = 6 cm. Find the radius r.
17. Let’s consider three pairwise non-parallel straight constant lines in the plane. Three points
are moving along these lines with different nonzero velocities, one on each line (we consider the
movement to have taken place for infinite time and continue infinitely in the future). Is it possible
to determine these straight lines, the velocities of each moving point and their positions at some
“zero” moment in such a way that the points never were, are or will be collinear?
18. In the triangle ABC, |AB| = 15, |BC| = 12, |AC| = 13. Let the median AM and bisector
BK intersect at point O, where M ∈ BC, K ∈ AC. Let OL ⊥ AB, L ∈ AB. Prove that
6 OLK = 6 OLM .
19. A convex quadrangle ABCD is inscribed in a circle with center O. The angles AOB, BOC, COD
and DOA, taken in some order, are of the same size as the angles of the quadrangle ABCD.
Prove that ABCD is a square.
20. Let Q be a unit cube. We say that a tetrahedron is good if all its edges are equal and all of its
vertices lie on the boundary of Q. Find all possible volumes of good tetrahedra.
“Baltic Way – 93” mathematical team contest
4. Denote
v s v s
u u
u 25 625 u 25 625 √
q
p= t + −n + t − − n = 25 + 2 n ,
2 4 2 4
p2 − 25 2
then n = and obviously p is an odd number not less than 5 . If p > 9 then
2
625
n> and the initial expression would be undefined. The two remaining values p = 5 and
4
p = 7 give n = 0 and n = 144 respectively.
and note that one of the two even numbers n − 1 and n + 1 is divisible by 4 .
f (x) x2 x f (x)
6. Denote h(x) = , then we have g(x) = = and g(f (x)) = = x which
x f (x) h(x) h(f (x))
f (x)
yields h(f (x)) = = h(x) . Using induction we easily get h(f (k) (x)) = h(x) for any
x
natural number k where f (k) (x) denotes f (f (. . . f (x) . . .)) . Now
| {z }
k
f (k+1) (x) = f (f (k) (x)) = f (k) (x)·h(f (k) (x)) = f (k) (x)·h(x)
f (k+1) (x)
and = h(x) for any natural number k . Thus,
f (k) (x)
f (k) (3) 2 4
and = (h(3))k ∈ , for all k . This is only possible if h(3) = 1 and thus
3 3 3
f (3) = g(3) = 3 .
1
20 − y
7. From the second and third equation we find z = 2x and x = . Substituting these
3
x
40 − 2y x
into the first equation yields = y 2 . As x 6= 0 (otherwise we have 00 in the
3
40 − 2y
first equation which is usually considered undefined) we have y 2 = ± (the ‘−’ case
3
40 − 2y
occurring only if x is even). The equation y 2 = − has no integer solutions; from
3
40 − 2y 10
y2 = we get y = −4 , x = 8 , z = 16 (the other solution y = is not an integer).
3 3
8. Denote by I and D the sets of all positive integers with strictly increasing (respectively,
decreasing) sequence of digits. Let D0 , D1 , D2 and D3 be the subsets of D consisting of
all numbers starting with 9 , not starting with 9 , ending in 0 and not ending in 0 , respectively.
Let S(A) denote the sum of all numbers belonging to a set A . All numbers in I are obtained
from the number 123456789 by deleting some of its digits. Thus, for any k = 0, 1, . . . , 9 there
are C9k k-digit numbers in I (here we consider 0 a 0-digit number). Every k-digit number
a ∈ I can be associated with a unique number b0 ∈ D0 , b1 ∈ D1 and b3 ∈ D3 such that
a + b0 = 999 . . . 9 = 10k+1 − 1 ;
a + b1 = 99 . . . 9 = 10k − 1 ;
10
a + b3 = 111 . . . 10 = (10k − 1) .
9
Hence we have
9
X
S(I) + S(D0 ) = C9k (10k+1 − 1) = 10 · 119 − 29 ;
k=0
9
X
S(I) + S(D1 ) = C9k (10k − 1) = 119 − 29 ;
k=0
10
S(I) + S(D3 ) = (119 − 29 ) .
9
Noting that S(D0 ) + S(D1 ) = S(D2 ) + S(D3 ) = S(D) and S(D2 ) = 10S(D3 ) we obtain the
system of equations
10 10
2S(I) + S(D) = 11 − 2
1 10
S(I) + S(D) = (119 − 29 )
11 9
which yields
80 35 10
S(I) + S(D) = · 1110 − ·2 .
81 81
This sum contains all one-digit numbers twice, so the final answer is
80 35 10
· 1110 − · 2 − 45 = 25617208995 .
81 81
9. Adding all four equations we get x + y + z + t = 0 . On the other hand, the numbers x, y, z, t
are simultanously positive, negative or equal to zero. Thus, x = y = z = t = 0 is the only
solution.
2
10. Let m be such index that |a′m − b′m | = max |a′i − b′i | = c . Without loss of generality we
16i6n
may assume a′m > b′m . Consider the numbers a′m , a′m+1 , . . . , a′n and b′1 , b′2 , . . . , b′m — as there
are n + 1 numbers altogether and only n places in the initial sequence there must exist an
index j such that we have aj among a′m , a′m+1 , . . . , a′n and bj among b′1 , b′2 , . . . , b′m . Now, as
bj 6 b′m < a′m 6 aj we have |aj − bj | > |a′m − b′m | = c and max |ai − bi | > c = max |a′i − b′i | .
16i6n 16i6n
11. Assume the big triangle lie on one of its sides, then a suitable strategy for the spider will be as
follows:
1) First, move to the lower left vertex of the big triangle;
2) Then, as long as the fly is higher than the spider, move upwards along the left side of the
big triangle;
3) After reaching the horizontal line where the fly is, retain this situation while moving to
the right (more precisely: move “right”, “right-up” or “right-down” depending on the last
move of the fly).
12. An example for 18 connections is shown on Fig. 1 (where single, double and dashed lines
denote the three different kinds of transportation). On the other hand, a graph with 13
vertices can be connected if it has at least 12 edges, so the total number of connections for
any two kinds of vehicle is at least 12 . Thus, twice the total number of all connections is at
least 12 + 12 + 12 = 36 .
c
c c
c c
t
c c c t
t
t
c c t
t
c c t
c
Figure 11 Figure 12
13. An example for 7 vertices is shown on Fig. 2. Now assume we have chosen 8 vertices sat-
isfying the conditions of the problem. Let the height of each small triangle be equal to 1
and denote by ai , bi , ci the distance of the i-th point from the three sides of the big tri-
angle. For any i = 1, 2, . . . , 8 we then have ai , bi , ci > 0 and ai + bi + ci = 10 . Thus,
(a1 + a2 + . . . + a8 ) + (b1 + b2 + . . . + b8 ) + (c1 + c2 + . . . + c8 ) = 80 . On the other hand, each
of the sums in the brackets is not less than 0 + 1 + . . . + 7 = 28 , but 3 · 28 = 84 > 80 , a
contradiction.
14. Remark: The proposed solution to this problem claimed that it is enough to remove 7 vertices
but the example to demonstrate this appeared to be incorrect. Below we show that removing
6 vertices is not sufficient but removing 8 vertices is. It seems that removing 7 vertices is
not sufficient but we currently know no potential way to prove this, apart from a tedious case
study.
The example on Fig. 3a demonstrates that it suffices to remove 8 vertices to “destroy” all
squares. Assume now that we have managed to do that by removing only 6 vertices. Denote
the horizontal and vertical lines by A , B , . . . , E and 1 , 2 , . . . , 5 respectively. Obviously,
one of the removed vertices must be a vertex of the big square — let this be vertex A1 . Then,
in order to “destroy” all the squares shown on Fig. 3b–e we have to remove vertices B2 , C3 ,
D4 , D2 and B4 . Thus we have removed 6 vertices without having any choice but a square
shown on Fig. 3f is still left intact.
1 2 3 4 5
A b b b b b b
B b b b r b b b r b b
C b b r b b b
D b b r r b b b
E
a b c d e f
Figure 13
3
15. We can write 1, 2, 3, 4, 5, 6 on the sides of one die and 1, 1, 1, 7, 7, 7 on the sides of the
other. Then each of the 12 possible sums appears in exactly 3 cases.
16. First, note that the centres O1 and O2 of the two circles lie on different sides of the line EH —
otherwise we have r < 12 and AB cannot be equal to 14 . Let P be the intersection point of
EH and O1 O2 (see Fig. 4). Points A and D lie on the same side of the line O1 O2 (otherwise
the three lines AD , EH and O1 O2 would intersect in P and |AB| = |BC| = |CD| ,
|EF | = |F G| = |GH| would imply |BC| = |F G| , a contradiction). It is easy to see that
|O1 O2 | = 2 · |O1 P | = |AC| = 28 cm. Let h = |O1 T | be the height of triangle O1 EP , then we
have h2 = 142 − 62 = 160 from triangle O1 T P and r2 = h2 + 32 = 169 from triangle O1 T F .
Thus, r = 13 cm.
A
q
B
qq
C
q
D
q
r
E ·q T
F q q+P q
r
q
qG
O1 O2 r
qH
J
J
^
Figure 14 Figure 15
17. Yes, it is. First, place the three points at the vertices of an equilateral triangle at the “zero”
moment and let them move with equal velocities along the straight lines determined by the
sides of the triangle as shown on Fig. 5. Then, at any moment in the past or future, the points
are located at the vertices of some equilateral triangle, and thus cannot be collinear. Finally,
to make the velocities of the points also differ, take any non-zero constant vector such that its
projections to the three lines have different lengths and add it to each of the velocity vectors.
This is equivalent to making the whole picture “drift” across the plane with constant velocity,
so the non-collinearity of our points is preserved (in fact, they are still located at the vertices
of an equilateral triangle at any given moment).
|AP | |AK|
18. Let the line OC intersect AB in point P . As AM is a median, we have =
|P B| |KC|
(this obviously holds if |AB| = |AC| and the equality is preserved under uniform compres-
sion of the plane along BK ). Applying the sine theorem to the triangles ABK and BCK
|AP | |AK| |AB| 5
we obtain = = = (see Fig. 6). As |AP | + |P B| = |AB| = 15
|P B| |KC| |BC| 4
25 20
then we have |AP | = and |P B| = . Thus |AC|2 − |BC|2 = 25 = |AP |2 − |BP |2
3 3
and |AC|2 − |AP |2 = |BC|2 − |BP |2 . Applying now the cosine theorem to the triangles
AP C and BP C we get cos 6 AP C = cos 6 BP C , i.e. P = L . As above, we can use a
compression of the plane to show that KP k BC and therefore 6 OP K = 6 OCB . As
|BM | = |M C| and 6 BP C = 90◦ we have 6 OCB = 6 OP M . Combining these equalities, we
get 6 OLK = 6 OP K = 6 OCB = 6 OP M = 6 OLM .
B B B
P
O M ·· O
A C
O C
A
·
A K C D D
Figure 16 Figure 17 Figure 18
4
a) At least one of the diagonals of ABCD is a diameter — say, 6 AOB + 6 BOC = 180◦ . Then
6 ABC = 6 CDA = 90◦ and at least two of the angles AOB , BOC , COD and DOA must be
90◦ : say, 6 AOB = 6 BOC = 90◦ . Now, 6 COD = 6 DAB and 6 DOA = 6 BCD (see Fig. 7).
1
Using the fact that 6 DOA = 6 DCA = 6 BCD − 45◦ we have 6 BCD = 6 DAB = 90◦ .
2
20. Clearly, the volume of a regular tetrahedron contained in a sphere reaches its maximum value
if and only if all four vertices of the tetrahedron lie on the surface of the sphere. Therefore, a
“good” tetrahedron with maximum volume must have its vertices at the vertices of the cube (for
proof, inscribe the cube in a sphere). There are exactly two such tetrahedra, their volume being
1 1
equal to 1 − 4 · = . On the other hand, one can find arbitrarily small “good” tetrahedra
6 3
by applying homothety to the maximal tetrahedron, with the centre of the homothety in one
of its vertices.
5
1
2. Let a1 , a2 , . . . , a9 be any non-negative numbers such that a1 = a9 = 0 and at least one of the
numbers is non-zero. Prove that for some i, 2 ≤ i ≤ 8, the inequality ai−1 + ai+1 < 2ai holds.
Will the statement remain true if we change the number 2 in the last inequality to 1.9 ?
5. Let p(x) be a polynomial with integer coefficients such that both equations p(x) = 1 and p(x) = 3
have integer solutions. Can the equation p(x) = 2 have two different integer solutions ?
6. Prove that any irreducible fraction p/q, where p and q are positive integers and q is odd, is equal
n
to a fraction k for some positive integers n and k.
2 −1
7. Let p > 2 be a prime number and
1 1 1 m
1+3
+ 3 + ... + 3
= ,
2 3 (p − 1) n
where m and n are relatively prime. Show that m is a multiple of p.
8. Show that for any integer a ≥ 5 there exist integers b and c, c ≥ b ≥ a, such that a, b, c are the
lengths of the sides of a right-angled triangle.
9. Find all pairs of positive integers (a, b) such that 2a + 3b is the square of an integer.
10. How many positive integers satisfy the following three conditions:
a) All digits of the number are from the set {1, 2, 3, 4, 5};
b) The absolute value of the difference between any two consecutive digits is 1;
c) The integer has 1994 digits ?
11. Let N S and EW be two perpendicular diameters of a circle C. A line ` touches C at point
S. Let A and B be two points on C, symmetric with respect to the diameter EW . Denote
the intersection points of ` with the lines N A and N B by A0 and B 0 , respectively. Show that
|SA0 | · |SB 0 | = |SN |2 .
12. The inscribed circle of the triangle A1 A2 A3 touches the sides A2 A3 , A3 A1 , A1 A2 at points S1 ,
S2 , S3 , respectively. Let O1 , O2 , O3 be the centres of the inscribed circles of triangles A1 S2 S3 ,
A2 S3 S1 , A3 S1 S2 , respectively. Prove that the straight lines O1 S1 , O2 S2 , O3 S3 intersect at one
point.
13. Find the smallest number a such that a square of side a can contain five disks of radius 1, so that
no two of the disks have a common interior point.
2
14. Let α, β, γ be the angles of a triangle opposite to its sides with lengths a, b, c respectively. Prove
the inequality
1 1 1 1 1 1 a b c
a· + +b· + +c· + ≥2· + + .
β γ γ α α β α β γ
15. Does there exist a triangle such that the lengths of all its sides and altitudes are integers and its
perimeter is equal to 1995 ?
A Hedgehog
16. The Wonder Island is inhabited by Hedgehogs. Each Hedgehog consists 1
of three segments of unit length having a common endpoint, with all
three angles between them equal to 120◦ (see Figure). Given that all 120◦ 120◦
Hedgehogs are lying flat on the island and no two of them touch each 1 ""
" b
b 1
120◦ bb
other, prove that there is a finite number of Hedgehogs on Wonder Island. "
"
b
17. In a certain kingdom, the king has decided to build 25 new towns on 13 uninhabited islands so
that on each island there will be at least one town. Direct ferry connections will be established
between any pair of new towns which are on different islands. Determine the least possible
number of these connections.
18. There are n lines (n > 2) given in the plane. No two of the lines are parallel and no three of them
intersect at one point. Every point of intersection of these lines is labelled with a natural number
between 1 and n − 1. Prove that, if and only if n is even, it is possible to assign the labels in
such a way that every line has all the numbers from 1 to n − 1 at its points of intersection with
the other n − 1 lines.
19. The Wonder Island Intelligence Service has 16 spies in Tartu. Each of them watches on some
of his colleagues. It is known that if spy A watches on spy B, then B does not watch on A.
Moreover, any 10 spies can numbered in such a way that the first spy watches on the second, the
second watches on the third, . . . , the tenth watches on the first. Prove that any 11 spies can also
be numbered is a similar manner.
20. An equilateral triangle is divided into 9 000 000 congruent equilateral triangles by lines parallel
to its sides. Each vertex of the small triangles is coloured in one of three colours. Prove that
there exist three points of the same colour being the vertices of a triangle with its sides parallel
to the lines of the original triangle.
“Baltic Way – 94” mathematical team contest
1. Note that
(x ◦ y) ◦ z = x + y + z − xy − yz − xz + xyz =
= (x − 1)(y − 1)(z − 1) + 1 .
Hence
(x ◦ y) ◦ z + (y ◦ z) ◦ x + (z ◦ x) ◦ y =
= 3 (x − 1)(y − 1)(z − 1) + 1 .
2. a) Suppose we have the opposite inequality ai−1 + ai+1 > 2ai for all
i = 2, . . . , 8 . Let ak = max ai , then we have ak−1 = ak+1 = ak ,
16i69
ak−2 = ak−1 = ak , etc. Finally we get a1 = ak , a contradiction.
b) Suppose now ai−1 +ai+1 > 1.9ai , i.e. ai+1 > 1.9ai −ai−1 for all i = 2, . . . , 8
and let ak = max ai . We can multiply all numbers a1 , . . . , a9 by the same
16i69
positive constant without changing the situation in any way, so we assume
ak = 1 . Then we have ak−1 + ak+1 > 1.9 and hence 0.9 6 ak−1 , ak+1 6 1 .
Moreover, at least one of the numbers ak−1 , ak+1 must be greater or equal than
0.95 — let us assume ak+1 > 0.95 . Now, we consider two subcases:
b1) k > 5 . Then we have
1 > ak+1 > 0.95 > 0 ;
1 > ak+2 > 1.9ak+1 − ak > 1.9 · 0.95 − 1 = 0.805 > 0 ;
ak+3 > 1.9ak+2 − ak+1 > 1.9 · 0.805 − 1 = 0.5295 > 0 ;
ak+4 > 1.9ak+3 − ak+2 > 1.9 · 0.5295 − 1 = 0.00605 > 0 .
So in any case we have a9 > 0 , a contradiction.
b2) k 6 4 . In this case we obtain
1 > ak−1 > 0.9 > 0 ;
ak−2 > 1.9ak−1 − ak > 1.9 · 0.9 − 1 = 0.71 > 0 ;
ak−3 > 1.9ak−2 − ak−1 > 1.9 · 0.71 − 1 = 0.349 > 0 .
and hence a1 > 0 , contrary to the condition of the problem.
1
3. The expression is well-defined only for |x|, |y| 6 1 and we can assume that
π
x, y > 0 . Let x = cos α and y = cos β for some 0 6 α, β 6 . This reduces
2
the expression to
cos α cos β + cos α sin β + cos β sin α − sin α sin β =
√ π
= cos(α + β) + sin(α + β) = 2 · sin(α + β + )
4
√ π π
which does not exceed 2 . The equality holds when α + β + = , for
4 2
√
π 2
example when α = and β = 0 , i.e. x = and y = 1 .
4 2
√
Answer: the largest value of the expression is 2 .
5. Observe first that if a and b are two different integers then p(a) − p(b) is
divisible by a − b . Suppose now that p(a) = 1 and p(b) = 3 for some integers
a and b . If we have p(c) = 2 for some integer c then c − b = ±1 and
c − a = ±1 , hence there can be at most one such integer c .
2
Answer: No, it cannot.
6. Since the number of congruence classes modulo q is finite, there exist two non-
negative integers i and j with i > j which satisfy 2i ≡ 2j (mod q) . Hence,
q divides the number 2i − 2j = 2j (2i−j − 1) . Since q is odd, q has to divide
2i−j − 1 . Now it suffices to multiply the numerator and denominator of the
p 2i−j − 1
fraction by .
q q
7. The sum has an even number of terms; they can be joined in pairs in such a
way that the sum is the sum of the terms
1 1 p3 − 3p2 k + 3pk 2
+ = .
k 3 (p − k)3 k 3 (p − k)3
The sum of all terms of this type has a denominator in which every prime factor
is less than p while the numerator has p as a factor.
8. We first show this for odd numbers a = 2i+1 > 3 . Put c = 2k+1 and b = 2k .
Then c2 − b2 = (2k + 1)2 − (2k)2 = 4k + 1 = a2 . Now a = 2i + 1 and thus
a2 = 4i2 + 4i + 1 and k = i2 + i . Furthermore, c > b = 2i2 + 2i > 2i + 1 = a .
Since any multiple of a Pythagorean triple (i.e. a triple of integers (x, y, z)
such that x2 + y 2 = z 2 ) is also a Pythagorean triple we see that the statement
is also true for all even numbers which have an odd factor. Hence only the
powers of 2 remain. But for 8 we have the triple 8, 15, 17 and hence all
higher powers of 2 are also minimum values of such a triple.
3
10. Consider all positive integers with 2n digits satisfying conditions (a) and (b)
of the problem. Let the number of such integers beginning with 1 , 2 , 3 , 4
and 5 be an , bn , cn , dn and en , respectively. Then, for n = 1 we have
a1 = 1 (integer 12 ), b1 = 2 (integers 21 and 23 ), c1 = 2 (integers 32 and
34 ), d1 = 2 (integers 43 and 45 ) and e1 = 1 (integer 54 ). Observe that
c 1 = a 1 + e1 .
Suppose now that n > 1 , i.e. the integers have at least four digits. If an integer
begins with the digit 1 then the second digit is 2 while the third can be 1 or
3 . This gives the relation
Similarly, if the first digit is 5 , then the second is 4 while the third can be 3
or 5 . This implies
If the integer begins with 23 then the third digit is 2 or 4 . If the integer
begins with 21 then the third digit is 2 . From this we can conclude that
If the integer begins with 32 then the third digit must be 1 or 3 and if it
begins with 34 the third digit is 3 or 5 . Hence
From (1), (2) and (5) it follows that cn = an + en , which is true for all
n = 1, 2, 3, . . . . On the other hand, adding the relations (1) – (5) results
in
Thus the number of integers satisfying conditions (a) and (b) increases three
times when we increase the number of digits by 2 . Since the number of such
integers with two digits is 8 and 1994 = 2 + 2 · 996 , the number of integers
satisfying all three conditions is 8 · 3996 .
4
Answer: the number of such integers is 8 · 3996 .
11. We have 6 N AS = 6 N BS = 90◦ (see Fig. 1). Thus, the triangles N A′ S and
N SA are similar. Also, the triangles B ′ N S and SN B are similar and the
triangles N SA and SN B are congruent. Hence, the triangles N A′ S and
SA′ SN
B ′ N S are similar which implies = and SA′ · SB ′ = SN 2 .
SN SB ′
N
A
W E
B
l
S B′ A′
Figure 1
12. We shall prove that the lines S1 O1 , S2 O2 , S3 O3 are the bisectors of the
angles of the triangle S1 S2 S3 . Let O and r be the centre and radius of the
inscribed circle C of the triangle A1 A2 A3 . Further, let P1 and H1 be the
points where the inscribed circle of the triangle A1 S2 S3 (with the centre O1
and radius r1 ) touches its sides A1 S2 and S2 S3 , respectively (see Fig. 2). To
show that S1 O1 is the bisector of the angle 6 S3 S1 S2 it is sufficient to prove
that O1 lies on the circumference of circle C , for in this case the arcs O1 S2
and O1 S3 will obviously be equal. To prove this, first note that as A1 S2 S3
is an isosceles triangle the point H1 , as well as O1 , lies on the straight line
A1 O . Now, it suffices to show that |OH1 | = r − r1 . Indeed, we have
r − r1 r1 |O1 P1 | |P1 A1 | |S2 A1 | − |P1 A1 |
= 1− =1− =1− = =
r r |OS2 | |S2 A1 | |S2 A1 |
|S2 P1 | |S2 H1 | |OH1 | |OH1 |
= = = = .
|S2 A1 | |S2 A1 | |OS2 | r
5
A2
S3
S1
O
r H1
r r
O1
A1 P1 S2 A3
Figure 2
13. Let P QRS be a square which has the property described in the problem.
Clearly, a > 2 . Let P ′ Q′ R′ S ′ be the square inside P QRS whose sides are at
distance 1 from the sides of P QRS , and, consequently, are of length a − 2 .
Since all the five disks are inside P QRS , their centers are inside P ′ Q′ R′ S ′ .
a
Divide P ′ Q′ R′ S ′ into four qongruent squares of sidelength − 1 . By the
2
pigeonhole principle, at least two of the five centers are in the same small square.
√ a
!
Their distance, then, is at most 2 − 1 . Since the distance has to be at
2
√ √
least 2, we have a > 2 + 2 2 . On the other hand, if a = 2 + 2 2 , we can
place the five disks in such a way that one is centered at the center of P QRS
and the other four have centers at P ′ , Q′ , R′ , and S ′ .
14. Clearly, the inequality a > b implies α > β and similarly a < b implies
α < β , hence (a − b)(α − β) > 0 and aα + bβ > aβ + bα . Dividing the last
equality by αβ we get
a b a b
+ > + . (1)
β α α β
Similarly we get
a c a c
+ > + (2)
γ α α γ
and
b c b c
+ > + . (3)
γ β β γ
6
15. Consider a triangle ABC with all its sides and heights having integer lengths.
From the cosine theorem we conclude that cos 6 A , cos 6 B and cos 6 C are
rational numbers. Let AH be one of the heights of the triangle ABC , with
the point H lying on the straight line determined by the side BC . Then
|BH| and |CH| must be rational and hence integer (consider the Pythagorean
theorem for the triangles ABH and ACH ). Now, if |BH| and |CH| have
different parity then |AB| and |AC| also have different parity and |BC| is
odd. If |BH| and |CH| have the same parity then |AB| and |AC| also
have the same parity and |BC| is even. In both cases the perimeter of triangle
ABC is an even number and hence cannot be equal to 1995 .
Remark. In the solution we only used the fact that all three sides and one
height of the triangle ABC are integers.
16. It suffices to prove that if the distance between the centres of two Hedge-
hogs is less than 0.2 then these Hedgehogs intersect. To show this, consider
two Hedgehogs with their centres at points O and M respectively such that
|OM | < 0.2 . Let A, B, C be the endpoints of the needles of the first Hedgehog
(see Fig. 3) and draw a straight line l parallel to AC through the point M .
√ 0.2
As |AC| = 3 implies |KL| 6 · |AC| < 1 and the second Hedgehog has at
0.5
least one of its needles pointing inside the triangle OKL , this needle intersects
the first Hedgehog.
Remark: If the Hedgehogs can move their needles so that the angles between
them can take any positive value then there can be an infinite number of Hedge-
hogs on the Wonder Island.
1 K
l
qM
O L
1 1
B C
Figure 3
17. Let a1 , . . . , a13 be the numbers of towns on each island. Suppose there exist
numbers i and j such that ai > aj > 1 and consider an arbitrary town A
on the j -th island. The number of ferry connections from town A is equal to
25−aj . On the other hand, if we “move” town A to the i-th island then there
will be 25 − (ai + 1) connections from town A while no other connections will
be affected by this move. Hence, the smallest number of connections will be
7
achieved if there are 13 towns on one island and one town on each of the other
12 · 11
12 islands. In this case there will be 13 · 12 + = 222 connections.
2
18. Suppose we have assigned the labels in the required manner. When a point has
label 1 then there can be no more occurrences of label 1 on the two lines that
intersect at that point. Therefore, the number of intersection points labelled
n
with 1 has to be exactly , i.e. n must be even. Now, let n be an even
2
number and denote the n lines by l1 , l2 , . . . , ln First write the lines li in the
following table:
l3 l4 . . . ln/2+1
l1 l2
ln ln−1 . . . ln/2+2
l2 l3 . . . ln/2
l1 ln
ln−1 ln−2 . . . ln/2+1
ln l2 . . . ln/2−1
l1 ln−1
ln−2 ln−3 . . . ln/2
etc.
According to these tables, we can join the lines in pairs in n − 1 different ways
— l1 with the line next to it and every other line with the line directly above
or under it. Now we can assign the label i to all the intersection points of the
pairs of lines shown in the i-th table.
19. We call two spies A and B neutral to each other if neither A watches on B
nor B watches on A .
Denote the spies A1 , A2 , . . . , A16 . Let ai , bi and ci denote the number of
spies that watch on Ai , the number of that are watched by Ai and the number
of spies neutral to Ai , respectively. Clearly, we have
ai + bi + ci = 15
ai + c i 6 8
bi + c i 6 8
8
for any i = 1, . . . , 16 (if any of the last two inequalities does not hold then there
exist 10 spies who cannot be numbered in the required manner). Combining
the relations above we find ci 6 1 . Hence, for any spy, the number of his
neutral collegues is 0 or 1 .
Now suppose there is a group of 11 spies that cannot be numbered as re-
quired. Let B be an arbitrary spy in this group. Number the other 10 spies
as C1 , C2 , . . . , C10 so that C1 watches on C2 , . . . , C10 watches on C1 .
Suppose there is no spy neutral to B among C1 , . . . , C10 . Then, if C1
watches on B then B cannot watch on C2 as otherwise C1 , B, C2 , . . . , C10
would form a 11-cycle. So C2 watches on B , etc. As some of the spies
C1 , C2 , . . . , C10 must watch on B we get all of them watching on B , a con-
tradiction. Therefore, each of the 11 spies must have exactly one spy neutral
to him among the other 10 — but this is impossible.
20. Consider the side AB of the big triangle ABC as “horizontal” and suppose
the statement of the problem does not hold. The side AB contains 3001
vertices A = A0 , A1 , . . . , A3000 = B of 3 colours. Hence, there are at least
1001 vertices of one colour, e.g. red. For any two red vertices Ak and An
there exists a unique vertex Bkn such that the triangle Bkn Ak An is equilateral.
That vertice Bkn cannot be red. For different pairs (k, n) the corresponding
2
vertices Bkn are different, so we have at least C1001 > 500000 vertices of type
Bkn that cannot be red. As all these vertices are situated on 3000 horisontal
lines, there exists a line L which contains more than 160 vertices of type Bkn ,
each of them coloured in one of the two remaining colours. Hence there exist
at least 81 vertices of the same colour, e.g. blue, on line L . For every two
blue vertices Bkn and Bml on line L there exists a unique vertex Cknml such
that:
1) Cknml lies above the line L ;
2) The triangle Cknml Bkn Bml is equilateral;
3) Cknml = Bpq where p = min(k, m) and q = max(n, l) .
9
1
1. Find all triples (x, y, z) of positive integers satisfying the system of equations
(
x2 = 2(y + z)
x6 = y 6 + z 6 + 31(y 2 + z 2 ) .
2. Let a and k be positive integers such that a2 + k divides (a − 1)a(a + 1). Prove that k ≥ a.
3. The positive integers a, b, c are pairwise relatively prime, a and c are odd and the numbers satisfy
the equation a2 + b2 = c2 . Prove that b + c is a square of an integer.
4. John is older than Mary. He notices that if he switches the two digits of his age (an integer),
he gets Mary’s age. Moreover, the difference between the squares of their ages is a square of an
integer. How old are Mary and John?
5. Let a < b < c be three positive integers. Prove that among any 2c consecutive positive integers
there exist three different numbers x, y, z such that abc divides xyz.
8. The real numbers a, b and c satisfy the inequalities |a| ≥ |b + c|, |b| ≥ |c + a| and |c| ≥ |a + b| .
Prove that a + b + c = 0.
9. Prove that
1995 1994 1993 2 1 1 3 1995
− + − ··· − + = + + ··· + .
2 3 4 1995 1996 999 1000 1996
10. Find all real-valued functions f defined on the set of all non-zero real numbers such that:
(i) f (1) = 1,
1 1 1
(ii) f x+y
=f x
+f y
for all non-zero x, y, x + y,
(iii) (x + y) · f (x + y) = xy · f (x) · f (y) for all non-zero x, y, x + y.
11. In how many ways can the set of integers {1, 2, . . . , 1995} be partitioned into three nonempty
sets so that none of these sets contains any pair of consecutive integers?
12. Assume we have 95 boxes and 19 balls distributed in these boxes in an arbitrary manner. We
take 6 new balls at a time and place them in 6 of the boxes, one ball in each of the six. Can we,
by repeating this process a suitable number of times, achieve a situation in which each of the 95
boxes contains an equal number of balls?
13. Consider the following two person game. A number of pebbles are situated on the table. Two
players make their moves alternately. A move consists of taking off the table x pebbles where x
is the square of any positive integer. The player who is unable to make a move loses. Prove that
there are infinitely many initial situations in which the second player can win no matter how his
opponent plays.
2
14. There are n fleas on an infinite sheet of triangulated paper. Initially the fleas are in different
small triangles, all of which are inside some equilateral triangle consisting of n2 small triangles.
Once a second each flea jumps from its original triangle to one of the three small triangles having
a common vertex but no common side with it. For which natural numbers n does there exist an
initial configuration such that after a finite number of jumps all the n fleas can meet in a single
small triangle?
15. A polygon with 2n + 1 vertices is given. Show that it is possible to assign numbers 1, 2, . . . , 4n + 2
to the vertices and midpoints of the sides of the polygon so that for each side the sum of the
three numbers assigned to it is the same.
16. In the triangle ABC, let ` be the bisector of the external angle at C. The line through the
midpoint O of AB parallel to ` meets AC at E. Determine |CE|, if |AC| = 7 and |CB| = 4.
17. Prove that there exists a number α such that for any triangle ABC the inequality
max(hA , hB , hC ) ≤ α · min(mA , mB , mC )
holds, where hA , hB , hC denote the lengths of the altitudes and mA , mB , mC denote the lengths
of the medians. Find the smallest possible value of α.
18. Let M be the midpoint of the side AC of a triangle ABC and let H be the footpoint of the
altitude from B. Let P and Q be orthogonal projections of A and C on the bisector of the angle
B. Prove that the four points H, P , M and Q lie on the same circle.
20. Prove that if both coordinates of every vertex of a convex pentagon are integers then the area of
this pentagon is not less than 25 .
1
1. Let α be the angle between two lines containing the diagonals of a regular 1996-gon, and let
β 6= 0 be another such angle. Prove that α/β is a rational number.
2. In the figure below, you see three half-circles. The circle C is tangent to two of the half-circles
and to the line P Q perpendicular to the diameter AB. The area of the shaded region is 39π, and
the area of the circle C is 9π. Find the length of the diameter AB.
Q
........................................................
............. . ........... ....... ... ...............
........... ................... ....... ........................
.................................. ....... ................ ..........
..
...
....................................................... .......... ........................ ....................................
.... . . . . . . . . . . . . . . . . . . . . . . . . . . . ...... .......
........................................... ....... ................... .....
.............................................. ....... .............. ......
.
............ .......................................................... .......... ..................
. ..........
...........
............... ........................................................... ........... ............ C .
.
..
................. .......................................................... .......... ...........
. ...................
.
............... ....................................... ....... ....... ...... .....
. .. . . .
..
.
..................................................................................................... ........... .......... ....................
.
...................... ................. ....... .........
............. ....... ......... ................
.. . . . . . ...
... ............... ....... ....... ........... ............... ...
.... ........... ...... . . . . .... ... ................. ....
...... ....... ............ ................ ................................... ...........
.................. .......... .................... ....
..
.
....... ........................................................................ .......
..
.......... .... ................ ........ ........ . .........
.......... .... ......................
.......................
..............
...... . ..
....... ................... ............
......... .
.............. . .......
.......
....... ........... .......
...... .......... .......
...... .......... ....
... .......... ......
..... ...
... . .
................................................................................................................................................................................................................................................................
A P B
3. Let ABCD be a unit square and let P and Q be points in the plane such that Q is the circumcentre
of triangle BP C and D be the circumcentre of triangle P QA. Find all possible values of the
length of segment P Q.
4. ABCD is a trapezium (AD k BC). P is the point on the line AB such that 6 CP D is maximal.
Q is the point on the line CD such that 6 BQA is maximal. Given that P lies on the segment
AB, prove that 6 CP D = 6 BQA.
5. Let ABCD be a cyclic convex quadrilateral and let ra , rb , rc , rd be the radii of the circles inscribed
in the triangles BCD, ACD, ABD, ABC, respectively. Prove that ra + rc = rb + rd .
6. Let a, b, c, d be positive integers such that ab = cd. Prove that a + b + c + d is not a prime.
8. Consider the sequence: x1 = 19, x2 = 95, xn+2 = lcm (xn+1 , xn ) + xn , for n > 1, where lcm (a, b)
means the least common multiple of a and b. Find the greatest common divisor of x1995 and
x1996 .
9. Let n and k be integers, 1 ≤ k < n. Find an integer b and a set A of n integers satisfying the
following conditions:
(i ) No product of k − 1 distinct elements of A is divisible by b.
(ii) Every product of k distinct elements of A is divisible by b.
(iii ) For all distinct a, a0 in A, a does not divide a0 .
10. Denote by d(n) the number of distinct positive divisors of a positive integer n (including 1 and
n). Let a > 1 and n > 0 be integers such that an + 1 is a prime. Prove that d(an − 1) ≥ n.
2
11. Real numbers x1 , x2 , . . . , x1996 have the following property: For any polynomial W of degree 2 at
least three of the numbers W (x1 ), W (x2 ), . . .
. , W (x1996 ) are equal. Prove that at least three of the numbers x1 , x2 , . . . ,
x1996 are equal.
12. Let S be a set of integers containing the numbers 0 and 1996. Suppose further that any integer
root of any non-zero polynomial with coefficients in S also belongs to S. Prove that −2 belongs
to S.
13. Consider the functions f defined on the set of integers such that
f (x) = f (x2 + x + 1) ,
for all integer x. Find (a) all even functions, (b) all odd functions of this kind.
14. The graph of the function f (x) = xn + an−1 xn−1 + . . . + a1 x + a0 (where n > 1) intersects the line
y = b at the points B1 , B2 , . . . , Bn (from left to right), and the line y = c (c 6= b) at the points
C1 , C2 , . . . , Cn (from left to right). Let P be a point on the line y = c, to the right to the point
Cn . Find the sum
cot(6 B1 C1 P ) + . . . + cot(6 Bn Cn P ) .
16. On an infinite checkerboard two players alternately mark one unmarked cell. One of them uses
×, the other ◦. The first who fills a 2 × 2 square with his symbols wins. Can the player who
starts always win ?
17. Using each of the eight digits 1, 3, 4, 5, 6, 7, 8 and 9 exactly once, a three-digit number A, two
two-digit numbers B and C, B < C, and a one digit number D are formed. The numbers are
such that A + D = B + C = 143. In how many ways can this be done ?
18. The jury of an olympiad has 30 members in the beginning. Each member of the jury thinks
that some of his colleagues are competent, while all the others are not, and these opinions do
not change. At the beginning of every session a voting takes place, and those members who are
not competent in the opinion of more than one half of the voters are excluded from the jury for
the rest of the olympiad. Prove that after at most 15 sessions there will be no more exclusions.
(Note that nobody votes about his own competence.)
19. Four heaps contain 38, 45, 61 and 70 matches respectively. Two players take turn choosing any
two of the heaps and take some non-zero number of matches from one heap and some non-zero
number of matches from the other heap. The player who cannot make a move, loses. Which one
of the players has a winning strategy ?
20. Is it possible to partition all positive integers into disjoint sets A and B such that
(i ) no three numbers of A for an arithmetic progression,
(ii) no infinite non-constant arithmetic progression can be formed by numbers of B ?
Baltic Way 1997
Problems
1. Determine all functions f from the real numbers to the real numbers, dif-
ferent from the zero function, such that f (x)f (y) = f (x − y) for all real
numbers x and y .
1
(x1 − a)2 + · · · + (xn − a)2 6 (|x1 − a| + · · · + |xn − a|)2 .
2
where a is a fixed odd positive integer. Prove that the sequence is periodic
from a certain step.
6. Find all triples (a, b, c) of non-negative integers satisfying a > b > c and
1·a3 + 9·b2 + 9·c + 7 = 1997 .
1
8. If we add 1996 and 1997 , we first add the unit digits 6 and 7 . Obtaining
13 , we write down 3 and “carry” 1 to the next column. Thus we make a
carry. Continuing, we see that we are to make three carries in total:
1 1 1
1996
+ 1997
3993
Does there exist a positive integer k such that adding 1996 · k to 1997 · k
no carry arises during the whole calculation?
B1 B2 B3 B4 B5
r r r r r
r r r r r r r r r r
A1A2A3A4A5A6
2
The point F lies outside the line. Let G be the circumcentre of trian-
gle ADF and H be the circumcentre of triangle BEF . Show that lines GH
and F C are perpendicular.
A B C D E
14. In the triangle ABC , |AC|2 is the arithmetic mean of |BC|2 and |AB|2 .
Show that cot2 B > cot A cot C .
15. In the acute triangle ABC , the bisectors of 6 A , 6 B and 6 C intersect the
circumcircle again in A1 , B1 and C1 , respectively. Let M be the point
of intersection of AB and B1 C1 , and let N be the point of intersection of
BC and A1 B1 . Prove that M N passes through the incentre of triangle
ABC .
16. On a 5 × 5 chessboard, two players play the following game. The first
player places a knight on some square. Then the players alternately move
the knight according to the rules of chess, starting with the second player.
It is not allowed to move the knight to a square that has been visited
previously. The player who cannot move loses. Which of the two players
has a winning strategy?
17. A rectangle can be divided into n equal squares. The same rectangle can
also be divided into n + 76 equal squares. Find all possible values of n .
18. a) Prove the existence of two infinite sets A and B , not necessarily disjoint,
of non-negative integers such that each non-negative integer n is uniquely
representable in the form n = a + b with a ∈ A , b ∈ B .
b) Prove that for each such pair (A, B) , either A or B contains only mul-
tiples of some integer k > 1 .
19. In a forest each of n animals (n > 3) lives in its own cave, and there is
exactly one separate path between any two of these caves. Before the elec-
tion for King of the Forest some of the animals make an election campaign.
Each campaign-making animal visits each of the other caves exactly once,
3
uses only the paths for moving from cave to cave, never turns from one path
to another between the caves and returns to its own cave in the end of its
campaign. It is also known that no path between two caves is used by more
than one campaign-making animal.
a) Prove that for any prime n , the maximum possible number of
n−1
campaign-making animals is ;
2
b) Find the maximum number of campaign-making animals for n = 9 .
20. Twelve cards lie in a row. The cards are of three kinds: with both sides
white, both sides black, or with a white and a black side. Initially, nine
of the twelve cards have a black side up. The cards 1–6 are turned, and
subsequently four of the twelve cards have a black side up. Now cards 4–9
are turned, and six cards have a black side up. Finally, the cards 1–3 and
10–12 are turned, after which five cards have a black side up. How many
cards of each kind are there?
Solutions
2. Let ` be the least index such that a` > a1 . Since 2a` − a1 is a positive
integer larger than a1 , it occurs in the given sequence beyond a` . In other
words, there exists an index m > ` such that am = 2a` −a1 . This completes
the proof.
Remarks. The problem was proposed in the slightly more general form
where the first term of the arithmetic progression has an arbitary index.
The remarks below refer to this version. The problem committee felt that
no essential new aspects would arise from the generalization.
1. A generalization of this problem is to ask about an existence of an
s -term arithmetic subsequence of the sequence (an ) (such a subsequence
4
always exists for s = 3 , as shown above). It turns out that for s = 5 such
a subsequence may not exist. The proof can be found in [1]. The same
problem for s = 4 is still open!
2. The present problem ( s = 3 ) and the above solution is also taken from [1].
xn+1 = xn + a + 2 = a(n+1) + b + 2 .
5
1
un is odd we have un+1 = a + un < 2un and un+2 = un+1 < un . Hence
2
the iteration results in un 6 a in a finite number of steps. Thus for any
non-negative integer m , some non-negative integer n > m satisfies un 6 a ,
and there must be an infinite set of such integers n .
Since the set of natural numbers not exceeding a is finite and such values
arise in the sequence (un ) an infinite number of times, there exist non-
negative integers m and n with n > m such that un = um . Starting from
um the sequence is then periodic with a period dividing n − m .
6
b−a−1997 are of different parity and hence P (b) = (b−a)(b−a−1997)R(b)
is even. Since Q(1998) = 2000 then the constant term in the expansion of
Q(x) is even (otherwise Q(x) would be odd for any even integer x ), and
Q(c) is even for any even integer c . Hence Q(P (b)) is also even and cannot
be equal to 1 .
8. Answer : yes.
The key to the proof is noting that if we add two positive integers and the
result is an integer consisting only of digits 9 then the process of addition
must have gone without any carries. Therefore it is enough to prove that
there exists an integer k such that 3993k is of the form 999...9 .
Consider the first 3994 positive integers consisting only of digits 9 :
By the pigeonhole principle some two of these give the same remainder upon
division by 3993 , so their difference
|99 {z
. . . 9} |00 {z
. . . 0} = 99 . . . 9} · 10r
| {z
n r n
Remarks.
1. The existence of an integer 10` − 1 consisting only of digits 9 and divis-
ible by 3993 may also be demonstrated quite elegantly by means of Euler’s
Theorem. The numbers 10 and 3993 are coprime, so 10ϕ(3993) − 1 is divis-
ible by 3993 . Thus we may take ` = ϕ(3993) .
2. By a computer search it can be found that the smallest integer k satis-
fying the condition of the problem is k = 162 . Then 1996 · 162 = 323352 ;
1997 · 162 = 323514 and
3 2 3 3 5 2
+ 3 2 3 5 1 4
6 4 6 8 6 6
9. Answer : yes.
For any two given worlds, Gandalf can move between them either in both
7
directions or none. Hence, it suffices to show that Gandalf can move to the
world 1 from any given world n . For that, it is sufficient for him to be able
to move from any world n > 1 to some world m such that m < n . We
consider three possible cases:
a) If n = 3k + 1 , then Gandalf can move directly from the world n to the
world k < n .
b) If n = 3k + 2 , then Gandalf can move from the world n to the
world 2n = 6k + 4 = 3 · (2k + 1) + 1 and further to the world 2k + 1 < n .
c) If n = 3k then Gandalf can move from the world n to the world
3n + 1 = 9k + 1 , further from there to the worlds 2 · (9k + 1) = 18k + 2 ,
2 · (18k + 2) = 36k + 4 = 3 · (12k + 1) + 1 , 12k + 1 , 4k and finally to the
world 2k < n .
10. Among the first 40 numbers in the sequence, four are divisible by 10 and
at least one of these has its second digit from the right less than or equal
to 6 . Let this number be x and let y be its sum of digits. Then the
numbers x, x + 1, x + 2, . . . , x + 39 all belong to the sequence, and each
of y, y + 1, . . . , y + 12 appears at least once among their sums of decimal
digits. One of these is divisible by 13 .
Remark : there exist 78 consecutive natural numbers, none of which has its
sum of digits divisible by 13 — e.g. 859999999961 through 860000000038 .
B1 B2 B3 B4 B5
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10
s s s s s s s s s s
s s s s s s s s s s
A1 A2 A3 A4 A5 A6
Figure 2
11. Answer : π − α .
Let C1 , C2 , C3 , . . . be points on the upper line such that |Ci Ci+1 | = 1 and
Bi = C2i for each i = 1, 2, . . . (see Figure 2). Then for any i = 1, 2, . . . we
have
8
Hence
6 A1 B1 A2 + 6 A2 B2 A3 + 6 A3 B3 A4 + . . . =
= 6 C2 A 2 C3 + 6 C3 A 2 C4 + 6 C4 A 2 C5 + . . . = π − α .
12. Depending on the radii of the circles, the distance between their centres
and the choice of the line through P we have several possible arrangements
of the points A, B, P and Y, Z, Q . We shall show that in each case the
triangles AXY and BXZ are congruent, whence |Y X| = |XZ| .
(a) Point P lies within segment AB and point Q lies within segment Y Z
(see Figure 3). Then
6 AY X = 6 AY Q = π − 6 AP Q = 6 BP Q = 6 BZQ = 6 BZX .
Figure 3 Figure 4
(c) Point P lies outside of segment AB and point Q lies outside of seg-
ment Y Z (see Figure 5). Then
6 AY X = π − 6 AY Q = 6 AP Q = 6 BP Q = 6 BZQ = 6 BZX .
(d) Point P lies within segment AB and point Q lies outside of seg-
ment Y Z . This case is similar to (b): exchange the roles of points
P and Q , A and Y , B and Z .
9
PSfrag replacements
C2
C1 P
X Z
A
Q Y B
Figure 5
H0 r
Gr0
O
r
r
G r
A B C H D E
Figure 6
10
replacements
A
B
X 3a
and |HC|2 = R22 + 4a2 − 4aR2 cos β . Together with cos α = and
Y 2R1
Z 3a
Pcos β = this yields |GC|2 − |HC|2 = R12 − R22 . Since |GF | = R1 and
2R2
Q
|HF | = R2 , we also have |GF |2 − |HF |2 = R12 − R22 .
C1
C2
F F
G
G
H H
α β
A B C D E A B C D E
Figure 7 Figure 8
Another solution. We shall use the following fact that can easily be de-
rived from the properties of the power of a point: Let a line s intersect
two circles at points K, L and M, N , respectively, and let these circles in-
tersect each other at P and Q . A point X on the line s lies also on the
line P Q (i.e. is the intersection point of the lines s and P Q ) if and only
if |KX| · |LX| = |M X| · |N X| .
The line AE intersects the circumcircles of triangles ADF and BEF
at A, D and B, E , respectively. Since point C lies on line AE and
|AC| · |DC| = |BC| · |EC| , then line CF passes through the second inter-
section point of these circles (see Figure 8) and hence is perpendicular to
the segment GH connecting the centres of these circles.
11
cos C (a2 + b2 − c2 ) · R
cot C = = ,
sin C abc
A1
I
M N
Q
P
A C
B1
Figure 9
15. Let I be the incenter of triangle ABC (the intersection point of the angle
bisectors AA1 , BB1 and CC1 ), and let B1 C1 intersect the side AC and
the angle bisector AA1 at P and Q , respectively (see Figure 9). Then
1 _ _ 1 ³ 1 _ 1 _ 1 _´
6 AQC1 = (AC1 + A1 B1 ) = · AB + BC + CA = 90◦ .
2 2 2 2 2
Since 6 AC1 B1 = 6 B1 C1 C (as their supporting arcs are of equal size), then
C1 B1 is the bisector of angle AC1 I . Moreover, since AI and C1 B1 are
perpendicular, then C1 B1 is also the bisector of angle AM I . Similarly we
can show that B1 C1 bisects the angles AB1 I ja AP I . Hence the diago-
nals of the quadrangle AM IP are perpendicular and bisect its angles, i.e.
12
AM IP is a rhombus and M I is parrallel to AC . Similarly we can prove
that N I is parallel to AC , i.e. points M , I and N are collinear, q.e.d.
X 12 8 3 11 7 1 7 12 23 18 1
5 3 11 1 7 8 22 17 8 13 24
12 8 6 10 4 6 2 11 6 25 2 19
2 5 9 7 1 4 9 16 21 4 9 14
9 6 2 4 10 5 3 5 10 15 20 3
Alternative solution. If the first player places the knight on the square
marked by 1 on Figure 11, then the second player will have two possible
moves which are symmetric to each other relative to a diagonal of the board.
Suppose w.l.o.g. that he makes a move to the square marked by 2 , then the
first player can make his move to the square marked by 3 . At this point,
the second player can only make a move to the square marked by 4 , and
the first player can make his next move to the square marked by 5 ; then
the second player can only make a move to the square marked by 6 , etc.,
until the first player will make a move to the square marked by 9 . Now
the second player will again have two possible moves, but since these two
squares are symmetric relative to a diagonal of the board (and the set of
squares already used is symmetric to that diagonal as well) we can assume
w.l.o.g. that he makes a move to the square marked by 10 . Now the first
player can make his moves until the end of the game so that the second
player will have no choice for his subsequent moves (these moves will be to
the squares marked by 11 through 25 , in this order). We see that the first
13
player will be the one to make the last move, and hence the winner.
18. a) Let A be the set of non-negative integers whose only non-zero decimal
digits are in even positions counted from the right, and B the set of non-
negative integers whose only non-zero decimal digits are in odd positions
counted from the right. It is obvious that A and B have the required
property.
b) Since the only possible representation of 0 is 0 + 0 , we have 0 ∈ A ∩ B .
The only possible representations of 1 are 1 + 0 and 0 + 1 . Hence 1 must
belong to at least one of the sets A and B . Let 1 ∈ A , and let k be the
smallest positive integer such that k 6∈ A . Then k > 1 . If any number b
with 0 < b < k belonged to B , it would have the two representations b + 0
and 0 + b . Hence no such number belongs to B . Also, in k = a + b with
a ∈ A and b ∈ B the number b cannot be 0 since then a = k , contradicting
the assumption that k 6∈ A . Hence b = k , and k ∈ B .
Consider the decomposition of A into the union A1 ∪A2 ∪· · · of its maximal
subsets A1 , A2 , . . . of consecutive numbers, where each element of A1 is
less than each element of A2 etc. In particular, A1 = {0, 1, . . . , k − 1} .
By our assumption the set of all non-negative integers is the union of non-
intersecting sets An + b = {a + b | a ∈ An } with n ∈ N and b ∈ B , each of
these consisting of some number of consecutive integers. We will show that
each subset An has exactly k elements. Indeed, suppose m is the smallest
index for which the number l of elements in Am is different from k , then
l < k since Am + 0 and Am + k do not overlap. Denoting by c the smallest
element of Am , we have c + k − 1 6∈ A , so c + k − 1 = a + b with a ∈ A
14
and 0 6= b ∈ B . Hence, b > k and a < c . Suppose a ∈ An , then n < m
and the subset An has k elements. But then An + b overlaps with either
Am + 0 or Am + k , a contradiction.
Hence, the set of non-negative integers is the union of non-intersecting sets
An + b with n ∈ N and b ∈ B , each of which consists of k consecutive
integers. The smallest element of each of these subsets is a multiple of k .
Since each integer b ∈ B is the smallest element of A1 + b , it follows that
each b ∈ B is a multiple of k .
19. Answer : b) 4 .
a) As each campaign-making animal uses exactly n paths and the total
n(n − 1)
number of paths is , the number of campaign-making animals
2
n−1
cannot exceed . Labeling the caves by integers 0, 1, 2, . . . , n−1 , we
2
n−1
can construct non-intersecting campaign routes as follows:
2
0 → 1 → 2 → 3 → ... → n → 0
0 → 2 → 4 → 6 → . . . → n−1 → 0
0 → 3 → 6 → 9 → . . . → n−2 → 0
···············
n−1 n+1
0→ → n−1 → . . . → →0
2 2
n−1
(As each of these cyclic routes passes through any cave, the
2
campaign-making animals can be chosen arbitrarily).
b) As noted above, the number of campaign-making animals cannot exceed
9−1
= 4 . The 4 non-intersecting campaign routes can be constructed as
2
follows:
0→1→2→8→3→7→4→6→5→0
0→2→3→1→4→8→5→7→6→0
0→3→4→2→5→1→6→8→7→0
0→4→5→3→6→2→7→1→8→0
15
Remark. In fact it can be proved that the maximal number of non-
intersecting Hamiltonian cycles in a complete graph ¹ on nº vertices (that
n−1
is what the problem actually asks for) is equal to for any inte-
2
ger n . The proof uses a construction similar to the one shown in part b) of
the above solution.
20. Answer : there are 9 cards with one black and one white side and 3 cards
with both sides white.
Divide the cards into four types according to the table below.
When the cards 1–6 were turned, the number of cards with a black side up
decreased by 5. Hence among the cards 1–6 there are five of type A and
one of type C or D . The result of all three moves is that cards 7–12 have
been turned over, hence among these cards there must be four of type A ,
and the combination of the other two must be one of the following:
(a) one of type A and one of type B ;
(b) one of type C and one of type D ;
(c) both of type C ;
(d) both of type D .
Hence the unknown card among the cards 1–6 cannot be of type D , since
this would make too many cards having a black side up initially. For the
same reason, the alternatives (a), (b) and (d) are impossible. Hence there
were nine cards of type A and three cards of type C .
16
(c) there are 6 black and 6 white sides among b1 , b2 , b3 , a4 , a5 , a6 , b7 ,
b8 , b9 , a10 , a11 , a12 ;
(d) there are 5 black and 7 white sides among a1 , a2 , a3 , a4 , a5 , a6 , b7 ,
b8 , b9 , b10 , b11 , b12 .
Cases (b) and (d) together enumerate each of the sides ai and bi exactly
once — hence there are 9 black and 15 white sides altogether. Therefore,
all existing black sides are enumerated in (a), implying that we have 9 cards
with one black and one white side, and the remaining 3 cards have both
sides white.
17
Baltic Way 1998
Problems
f (x, x) = x ,
f (x, y) = f (y, x) ,
(x + y)f (x, y) = yf (x, x+y) .
5. Let a be an odd digit and b an even digit. Prove that for every positive
integer n there exists a positive integer, divisible by 2n , whose decimal
representation contains no digits other than a and b .
7. Let R be the set of all real numbers. Find all functions f : R → R satisfying
for all x, y ∈ R the equation
1
8. Let Pk (x) = 1 + x + x2 + · · · + xk−1 . Show that
n µ ¶ ³1 + x´
X n
Pk (x) = 2n−1 Pn
k 2
k=1
14. Given a triangle ABC with |AB| < |AC| . The line passing through B and
parallel to AC meets the external bisector of angle BAC at D . The line
passing through C and parallel to AB meets this bisector at E . Point F
lies on the side AC and satisfies the equality |F C| = |AB| . Prove that
|DF | = |F E| .
2
15. Given an acute triangle ABC . Point D is the foot of the perpendicular
from A to BC . Point E lies on the segment AD and satisfies the equation
|AE| |CD|
= .
|ED| |DB|
Point F is the foot of the perpendicular from D to BE . Prove that
6 AF C = 90◦ .
17. Let n and k be positive integers. There are nk objects (of the same size)
and k boxes, each of which can hold n objects. Each object is coloured
in one of k different colours. Show that the objects can be packed in the
boxes so that each box holds objects of at most two colours.
18. Determine all positive integers n for which there exists a set S with the
following properties:
(i) S consists of n positive integers, all smaller than 2n−1 ;
(ii) for any two distinct subsets A and B of S , the sum of the elements
of A is different from the sum of the elements of B .
19. Consider a ping-pong match between two teams, each consisting of 1000
players. Each player played against each player of the other team exactly
once (there are no draws in ping-pong). Prove that there exist ten players,
all from the same team, such that every member of the other team has lost
his game against at least one of those ten players.
Solutions
3
We first show that there is at most one such function f . Let z > 2 be
an integer. Knowing the values f (x, y) for all x, y with 0 < x, y < z , we
compute f (x, z) for 0 < x < z using the third equation (with y = z − x );
then from the first two equations we get the values f (z, y) for 0 < y 6 z .
Hence, if f exists then it is unique.
Experimenting a little, we can guess that f (x, y) is the least common multi-
ple of x and y . It remains to verify that the least-common-multiple function
satisfies the given equations. The first two are clear, and for the third one:
xy x(x + y)
(x + y) · lcm (x, y) = (x + y) · =y· =
gcd(x, y) gcd(x, x + y)
= y · lcm (x, x + y) .
c2 = a2 + ab + b2 . (1)
4
1 or −1 modulo 5 ; so 4c2 − 3a2 ≡ ±2 (mod 5) and it cannot be equal to
(a + 2b)2 . This completes the proof.
Remark. A yet stronger claim is true: If a and b are coprime, then every
prime divisor p > 3 of a2 + ab + b2 is of the form p = 6k + 1 . (Hence
every prime divisor of c in an irreducible quasi-Pythagorean triple (a, b, c)
has such a form.)
This stronger claim can be proved by observing that p does not divide a
and the number g = (a + 2b)a(p−3)/2 is an integer whose square satisfies
5
Let n be fixed. We prove that if 1 6 k 6 n , then we can find a positive
integer mk < 5k such that the last k digits of mk 2n are all a or b . Clearly,
for k = 1 we can find m1 with 1 6 m1 6 4 such that m1 2n ends with
b
the digit b . (This corresponds to solving the congruence m1 2n−1 ≡
2
modulo 5 .) If n = 1 , we are done. Hence let n > 2 .
Assume that for a certain k with 1 6 k < n we have found the integer mk .
Let c be the (k+1) -st digit from the right of mk 2n (i.e., the coefficient
of 10k in its decimal representation). Consider the number 5k 2n : it ends
with precisely k zeros, and the last non-zero digit is even; call it d . For
any r , the corresponding digit of the number mk 2n + r5k 2n will be c + rd
modulo 10 . By a suitable choice of r 6 4 we can make this digit be either
a or b , according to whether c is odd or even. (As before, this corresponds
d a−c d b−c
to solving one of the congruences r · ≡ or r · ≡ modulo 5 .)
2 2 2 2
Now, let mk+1 = mk + r5k . The last k+1 digits of mk+1 2n are all a or b .
As mk+1 < 5k +4·5k = 5k+1 , we see that mk+1 has the required properties.
This process can be continued until we obtain a number mn such that the
last n digits of N = mn 2n are a or b . Since mn < 5n , the number N has
at most n digits, all of which are a or b .
6
6. The polynomial Q(x) = P (x) − P (−x), of degree at most 5 , has roots at
−b , −a , 0 , a and b ; these are five distinct numbers. Moreover, Q0 (0) = 0 ,
showing that Q has a multiple root at 0 . Thus Q must be the constant 0 ,
i.e. P (x) = P (−x) for all x .
8. Let A and B be the left- and right-hand side of the claimed formula,
respectively. Since
(1 − x)Pk (x) = 1 − xk ,
we get
n µ ¶ n µ ¶
X n X n
(1 − x) · A = (1 − xk ) = (1 − xk ) = 2n − (1 + x)n
k k
k=1 k=0
and
µ ¶ µ ¶
1+x n−1 1+x
(1 − x) · B = 2 1 − ·2 Pn =
2 2
µ µ ¶n ¶
1+x
= 2n 1 − = 2n − (1 + x)n .
2
Thus A = B for all real numbers x 6= 1 . Since both A and B are polyno-
mials, they coincide also for x = 1 .
7
strictly convex on (0, ∞) . Consequently,
q µ ¶
1 tan α + tan β
= 1 + tan2 γ = f (tan γ) = f <
cos γ 2
µ ¶
f (tan α) + f (tan β) 1 1 1 1
< = + = ,
2 2 cos α cos β cos δ
Remark. The use of calculus can be avoided. We only need the midpoint-
convexity of f , i.e., the inequality
s
1 1p 1p
1 + (u + v)2 < 1 + u2 + 1 + v2
4 2 2
Alternative solution. Draw a unit segment OP in the plane and take points
A and B on the same side of line OP so that 6 P OA = 6 P OB = 90◦ ,
6 OP A = α and 6 OP B = β (see Figure 1). Then we have |OA| = tan α ,
1 1
|OB| = tan β , |P A| = and |P B| = .
cos α cos β
β P
N α
B C
A O
Q
Figure 1
8
Let C be the midpoint of the segment AB . By hypothesis, we have
tan α + tan β 1
|OC| = = tan γ , hence 6 OP C = γ and |P C| = .
2 cos γ
Let Q be the point symmetric to P with respect to C . The quadrilateral
1
P AQB is a parallelogram, and therefore |AQ| = |P B| = . Eventu-
cos β
ally,
2 1 1 2
= + = |P A| + |AQ| > |P Q| = 2 · |P C| = ,
cos δ cos α cos β cos γ
and hence δ > γ .
α+β α−β
Another solution. Set x = and y = , then α = x+y , β = x−y
2 2
and
1
cos α cos β = (cos 2x + cos 2y) =
2
1 1 (3)
= (1 − 2 sin2 x) + (2 cos2 y − 1) = cos2 y − sin2 x .
2 2
By the conditions of the problem,
1 ³ sin α sin β ´ 1 sin(α + β) sin x cos x
tan γ = + = · =
2 cos α cos β 2 cos α cos β cos α cos β
and
1 1³ 1 1 ´ 1 cos α + cos β cos x cos y
= + = · = .
cos δ 2 cos α cos β 2 cos α cos β cos α cos β
9
10. For simplicity, take the length of the circle to be 2n(n − 1) rather than
2π . The vertices of the (n−1) -gon A0 A1 . . . An−2 divide it into n−1 arcs
of length 2n . By the pigeonhole principle, some two of the vertices of the
n -gon B0 B1 . . . Bn−1 lie in the same arc. Assume w.l.o.g. that B0 and B1
lie in the arc A0 A1 , with B0 closer to A0 and B1 closer to A1 , and that
|A0 B0 | 6 |B1 A1 | .
Consider the circle as the segment [0, 2n(n−1)] of the real line, with both of
its endpoints identified with the vertex A0 and the numbers 2n, 4n, 6n, . . .
identified accordingly with the vertices A1 , A2 , A3 , . . . .
For k = 0, 1, . . . , n−1 , let xk be the “coordinate” of the vertex Bk of the
n -gon. Each arc Bk Bk+1 has length 2(n − 1) . By the choice of labelling,
we have
0 6 x0 < x1 = x0 + 2(n − 1) 6 2n
Note that here x0 appears half of the times with a plus sign and half of the
times with a minus sign. Thus, eventually, all terms x0 cancel out, and the
value of S does not depend on anything but n .
10
11. Answer: equality holds if a = b or the angle opposite to c is equal to 90 ◦ .
Denote the angles opposite to the sides a , b , c by A , B , C , respectively.
By the law of sines we have a = 2R sin A , b = 2R sin B , c = 2R sin C .
Hence, the given inequality is equivalent to each of the following:
Equality requires that sin A = λ cos B and sin B = λ cos A for a certain
real number λ , implying that λ is positive and A , B are acute angles.
From these two equations we conclude that sin 2A = sin 2B . This means
that either 2A = 2B or 2A + 2B = π ; in other words, a = b or C = 90◦ .
In each of these two cases the inequality indeed turns into equality.
C
PSfrag replacements
O a
A c M B
Figure 2
11
known formula
A B
Figure 3
12
which is equivalent to the equality we have to prove.
Sfrag replacements
Alternative
A solution. Let 6 BAD = α and 6 CAD = β . By the conditions
◦
of the
B problem, α + β = 90 (hence sin β = cos α ), 6 BDA = 2α and
6 CDA = 2β . By the law of sines,
C
O
|AD| sin 3α
M = = 3 − 4 sin2 α
|BD| sin α
a
and b
c
|AD|
A = sin 3β = 3 − 4 sin2 β = 3 − 4 cos2 α .
|CD|
B sin β
C
Adding
O these two equalities we get the claimed one.
D C1
E C2
D
E C
A B
F
Figure 4
13. Let C1 and C2 be the circumcircles of triangles AED and BCD , respec-
tively. Let DP meet C2 for the second time at F (see Figure 4). Since
6 ADE = 6 BDC , the ratio of the lengths of the segments EA and BC
is equal to the ratio of the radii of C1 and C2 . Thus the homothety with
centre P that takes AE to CB , also transforms C1 onto C2 . The same
homothety transforms the arc DE of C1 onto the arc F B of C2 . Therefore
6 EAD = 6 BDF = 6 BDP . The second equality is proved similarly.
14. Since the lines BD and AC are parallel and since AD is the external
bisector of 6 BAC , we have 6 BAD = 6 BDA ; denote their common size
by α (see Figure 5). Also 6 CAE = 6 CEA = α , implying |AB| = |BD|
and |AC| = |CE| . Let B 0 , C 0 , F 0 be the feet of the perpendiculars from
13
E
C0 α
0
F
A
B0 α
D α
α
F
B C
Figure 5
A P
F E
B D C
Figure 6
14
the points B , E , P are collinear. Therefore 6 DF P = 90◦ , and so F
lies on the circumcircle of the rectangle ADCP with diameter AC ; hence
6 AF C = 90◦ .
Alternative solution. Colour the squares of the board black and white in
the following pattern. In the first (top) row, let the two leftmost squares
be black, the next two be white, the next two black, the next two white,
and so on (at the right end there remains a single black square). In the
second row, let the colouring be reciprocal to that of the first row (two
white squares, two black squares, and so on). If the rows are labelled by 1
through 13 , let all the odd-indexed rows be coloured as the first row, and
all the even-indexed ones as the second row (see Figure 7).
Note that there are more black squares than white squares in the board.
Each 4 × 1 tile, no matter how placed, covers two black squares and two
white squares. Thus if a tiling leaves a single square uncovered, this square
must be black. But the central square of the board is white. Hence such a
tiling is impossible.
Another solution. Colour the squares in four colours as follows: colour all
squares in the 1-st column green, all squares in the 2-nd column black, all
squares in the 3-rd column white, all squares in the 4-th column red, all
squares in the 5-th column green, all squares in the 6-th column black etc.,
leaving only the central square uncoloured (see Figure 8). Altogether we
have 3 · 13 = 39 black squares and 3 · 13 − 1 = 38 white squares. Since
15
each 4 × 1 tile covers either one square of each colour or all four squares
of the same colour, then the difference of the numbers of black and white
squares must be divisible by 4 . Since 39 − 38 = 1 is not divisible by 4 , the
required tiling does not exist.
G BWR G BWR G BWR G
Figure 7 Figure 8
19. We start with the following observation: In a match between two teams (not
necessarily of equal sizes), there exists in one of the teams a player who won
his games with at least half of the members of the other team.
16
Indeed: suppose there is no such player. If the teams consist of m and
n
n members then the players of the first team jointly won less than m ·
2
n
games, and the players of the second team jointly won less than m ·
2
games — this is a contradiction since the total number of games played is
mn , and in each game there must have been a winner.
Returning to the original problem (with two equal teams of size 1000 ),
choose a player who won his games with at least half of the members of
the other team — such a player exists, according to the observation above,
and we shall call his team “first” and the other team “second” in the sequel.
Mark this player with a white hat and remove from further consideration
all those players of the second team who lost their games to him. Applying
the same observation to the first team (complete) and the second team
truncated as explained above, we again find a player (in the first or in the
second team) who won with at least half of the other team members. Mark
him with a white hat, too, and remove the players who lost to him from
further consideration.
We repeat this procedure until there are no players left in one of the teams;
say, in team Y . This means that the white-hatted players of team X
constitute a group with the required property (every member of team Y
has lost his game to at least one player from that group). Each time when a
player of team X was receiving a white hat, the size of team Y was reduced
at least by half; and since initially the size was a number less than 210 , this
could not happen more than ten times.
Hence the white-hatted group from team X consists of not more than ten
players. If there are fewer than ten, round the group up to ten with any
players.
20. Answer: 1 .
Let 1 6 g < h < i < j 6 n be fixed integers. Consider all n -digit numbers
a = a1 a2 . . . an with all digits non-zero, such that ag = 1 , ah = 9 , ai = 9 ,
aj = 8 and this quadruple 1998 is the leftmost one in a ; that is,
al 6= 1 if l < g ;
al 6= 9 if g < l < h ;
al 6= 9 if h < l < i ;
al 6= 8 if i < l < j .
17
There are kghij (n) = 8g−1 · 8h−g−1 · 8i−h−1 · 8j−i−1 · 9n−j such numbers a .
Obviously, kghij (n) ≡ 1 (mod 8) for g = 1 , h = 2 , i = 3 , j = 4 , and
kghij (n) ≡ 0 (mod 8) in all other cases. Since k(n) is obtained by sum-
ming up the values of kghij (n) over all possible choicecs of g, h, i, j , the
remainder we are looking for is 1 .
18
Baltic Way 1999
Problems
2. Determine all positive integers n with the property that the third root of
n is obtained by removing the last three decimal digits of n .
a1 a2 + a2 a3 + · · · + an−1 an + an a1 6 0
Show that there exist x0 and y0 such that f (x, y) 6 f (x0 , y0 ) for all positive
x and y , and find f (x0 , y0 ) .
5. The point (a, b) lies on the circle x2 + y 2 = 1 . The tangent to the circle
at this point meets the parabola y = x2 + 1 at exactly one point. Find all
such points (a, b) .
6. What is the least number of moves it takes a knight to get from one corner
of an n × n chessboard, where n > 4 , to the diagonally opposite corner?
1
square and visit all squares exactly once in such a way that all moves except
the first are made into squares adjacent to an even number of squares already
visited?
8. We are given 1999 coins. No two coins have the same weight. A machine
is provided which allows us with one operation to determine, for any three
coins, which one has the middle weight. Prove that the coin that is the
1000 -th by weight can be determined using no more than 1 000 000 op-
erations and that this is the only coin whose position by weight can be
determined using this machine.
9. A cube with edge length 3 is divided into 27 unit cubes. The numbers
1, 2, . . . , 27 are distributed arbitrarily over the unit cubes, with one number
in each cube. We form the 27 possible row sums (there are nine such sums
of three integers for each of the three directions parallel to the edges of the
cube). At most how many of the 27 row sums can be odd?
10. Can the points of a disc of radius 1 (including its circumference) be parti-
tioned into three subsets in such a way that no subset contains two points
separated by distance 1 ?
11. Prove that for any four points in the plane, no three of which are collinear,
there exists a circle such that three of the four points are on the circum-
ference and the fourth point is either on the circumference or inside the
circle.
12. In a triangle ABC it is given that 2|AB| = |AC| + |BC| . Prove that the
incentre of ABC , the circumcentre of ABC , and the midpoints of AC and
BC are concyclic.
13. The bisectors of the angles A and B of the triangle ABC meet the
sides BC and CA at the points D and E , respectively. Assuming that
|AE| + |BD| = |AB| , determine the size of angle C .
14. Let ABC be an isosceles triangle with |AB| = |AC| . Points D and E lie
on the sides AB and AC , respectively. The line passing through B and
parallel to AC meets the line DE at F . The line passing through C and
parallel to AB meets the line DE at G . Prove that
[DBCG] |AD|
= ,
[F BCE] |AE|
2
where [P QRS] denotes the area of the quadrilateral P QRS .
15. Let ABC be a triangle with 6 C = 60◦ and |AC| < |BC| . The point D
lies on the side BC and satisfies |BD| = |AC| . The side AC is extended
to the point E where |AC| = |CE| . Prove that |AB| = |DE| .
16. Find the smallest positive integer k which is representable in the form
k = 19n − 5m for some positive integers m and n .
17. Does there exist a finite sequence of integers c1 , . . . , cn such that all the
numbers a + c1 , . . . , a + cn are primes for more than one but not infinitely
many different integers a ?
18. Let m be a positive integer such that m ≡ 2 (mod 4) . Show that there
exists at most one factorization
q m = ab where a and b are positive integers
√
satisfying 0 < a − b < 5 + 4 4m + 1 .
19. Prove that there exist infinitely many even positive integers k such that for
every prime p the number p2 + k is composite.
20. Let a , b , c and d be prime numbers such that a > 3b > 6c > 12d and
a2 − b2 + c2 − d2 = 1749 . Determine all possible values of a2 + b2 + c2 + d2 .
Solutions
√
3
√
3
1. Answer: a = b = c = 2 − 1 , d = 5 2 − 1 .
Substituting A = a + 1 , B = b + 1 , C = c + 1 , D = d + 1 , we obtain
ABC = 2 (1)
BCD = 10 (2)
CDA = 10 (3)
DAB = 10 (4)
Multiplying (1), (2), (3) gives C 3 (ABD)2 = 200 , which together with (4)
implies C 3 = 2 . Similarly we find
√ A3 = B 3 = 2√and D 3 = 250 . Therefore
3 3
the only solution is a = b = c = 2 − 1 , d = 5 2 − 1 .
3
If n = m3 is a solution, then m satisfies 1000m 6 m3 < 1000(m + 1) .
From the first inequality, we get m2 > 1000 , or m > 32 . By the second
inequality, we then have
m+1 33 1000
m2 < 1000 · 6 1000 · = 1000 + 6 1032 ,
m 32 32
3. Answer: n = 3 and n = 4 .
For n = 3 we have
a1 a2 + a2 a3 + a3 a4 + a4 a1 = (a1 + a3 )(a2 + a4 ) 6
(a1 + a2 + a3 + a4 )2
6 =0.
4
a1 a2 + a2 a3 + . . . + an−1 an + an a1 = 2 + 2 − 1 = 3 > 0 .
³ 1 1 ´ 1
4. Answer: the maximum value is f √ , √ = √ .
2 2 2
y
We shall make use of the inequality x2 + y 2 > 2xy . If x 6 , then
x2 + y 2
y y 1
x6 6 = ,
x2 + y 2 2xy 2x
1 1
implying x 6 √ , and the equality holds if and only if x = y = √ .
2 2
4
1
If x > √ , then
2
y y 1 1
6 = <√ .
x2 +y 2 2xy 2x 2
y 1
Hence always at least one of x and does not exceed √ . Conse-
+yx2 2
2
1 1
quently f (x, y) 6 √ , with an equality if and only if x = y = √ .
2 2
³ 2√ 6 √
1´ ³2 6 1´
5. Answer: (−1, 0) , (1, 0) , (0, 1) , − ,− , ,− .
5 5 5 5
D2 = k 2 − 4(1 − l) = k 2 + 4l − 4 = 0 .
5
From the system of equations
½ 2
l − k2 = 1
k 2 + 4l − 4 = 0
replacements
Figure 1
For n = 4 , n = 5 and n = 6 the sequences of moves are easily found that
take the knight from square (1, 1) to square (n, n) in 2 , 4 and 4 moves,
6
respectively (see Figure 1). In particular, the knight may get from square
(k, k) to square (k + 3, k + 3) in 2 moves. Hence, by simple induction, for
any n the knight can get from square (1, 1) to square (n, n) in a number
n+1
of moves equal to twice the integer part of , which is the minimal
3
possible number of moves.
8. It is possible to find the 1000 -th coin (i.e. the medium one among the 1999
coins). First we exclude the lightest and heaviest coin — for this we use
1997 weighings, putting the medium-weighted coin aside each time. Next
we exclude the 2 -nd and 1998 -th coins using 1995 weighings, etc. In total
we need
7
weighings can be written in a table like this:
Suppose we make a decision “ ak is the k -th coin” based on this table. Now
let us exchange labels of the lightest and the heaviest coins, of the 2 -nd and
1998 -th (by weight) coins etc. It is easy to see that, after this relabeling,
each step in the procedure above gives the same result as before — but if
ak was previously the k -th coin by weight, then now it is the (2000−k) -th
coin, so the procedure yields a wrong coin which gives us the contradiction.
9. Answer: 24 .
Since each unit cube contributes to exactly three of the row sums, then the
total of all the 27 row sums is 3 · (1 + 2 + . . . + 27) = 3 · 14 · 27 , which is
even. Hence there must be an even number of odd row sums.
+ + + + − − + + − + + − − − −
− + + − + + − − −
+ − + + − + − + −
(a) (b) I II III
Figure 2 Figure 3
We shall prove that if one of the three levels of the cube (in any given
direction) contains an even row sum, then there is another even row sum
within that same level — hence there cannot be 26 odd row sums. Indeed,
if this even row sum is formed by three even numbers (case (a) on Figure 2,
where + denotes an even number and − denotes an odd number), then
in order not to have even column sums (i.e. row sums in the perpendicular
direction), we must have another even number in each of the three columns.
But then the two remaining rows contain three even and three odd numbers,
and hence their row sums cannot both be odd. Consider now the other case
when the even row sum is formed by one even number and two odd numbers
(case (b) on Figure 2). In order not to have even column sums, the column
8
containing the even number must contain another even number and an odd
number, and each of the other two columns must have two numbers of the
same parity. Hence the two other row sums have different parity, and one
of them must be even.
It remains to notice that we can achieve 24 odd row sums (see Figure 3,
where the three levels of the cube are shown).
P
5 A2 P 3
O
A1
P6 A3 P2
P1
Figure 4
11. Consider a circle containing all these four points in its interior. First, de-
crease its radius until at least one of these points (say, A ) will be on the
circle. If the other three points are still in the interior of the circle, then
rotate the circle around A (with its radius unchanged) until at least one of
the other three points (say, B ) will also be on the circle. The centre of the
circle now lies on the perpendicular bisector of the segment AB — moving
9
n=4
n=5
n=6
P1
P2
the
P3 centre along that perpendicular bisector (and changing its radius at the
P4 time, so that points A and B remain on the circle) we arrive at a
same
situation
P5 where at least one of the remaining two points will also be on the
circle
P6 (see Figure 5).
A1
)(
'()'
O D
A
&% D A
O
C
B B
Figure 6 Figure 7
Assume now that the quadrangle ABCD (where A, B, C, D are the four
points) is convex. Then it has a pair of opposite angles, the sum of which
is at least 180◦ — assume these are at vertices B and D (see Figure 7).
We shall prove that point D lies either in the interior of the circumcircle
of triangle ABC or on that circle. Indeed, let the ray drawn from the
10
g replacements
n= 4
circumcentre O of triangle ABC through point D intersect the circumcircle
n=in5D0 : since 6 B + 6 D0 = 180◦ and 6 B + 6 D > 180◦ , then D cannot lie
n= in6the exterior of the circumcircle.
P1
12. LetP2 N be the midpoint of BC and M the midpoint of AC . Let O
be
P3 the circumcentre of ABC and I its incentre (see Figure 8). Since
6 PCM O = 6 CN O = 90◦ , the points C , N , O and M are concyclic (re-
4
gardless
P5 of whether O lies inside the triangle ABC ). We now have to
show
P6 that the points C , N , I and M are also concyclic, i.e I lies on
the
A1 same circle as C , N , O and M . It will be sufficient to show that
6 AN CM + 6 N IM = 180◦ in the quadrilateral CN IM . Since
2
A3
|AC| + |BC|
O|AB| = = |AM | + |BN | ,
2
A
we B can choose a point D on the side AB such that |AD| = |AM | and
C = |BN | . Then triangle AIM is congruent to triangle AID , and
|BD|
D
similarly triangle BIN is congruent to triangle BID . Therefore
O
◦
A6 N CM + 6 N IM = 6 N CM + (360 − 26 AID − 26 BID) =
B = 6 BCA + 360◦ − 26 AIB =
C ³ 6 BAC 6 ABC ´
= 6 BCA + 360◦ − 2 · 180◦ − − =
D 2 2
0
D = 6 BCA + 6 ABC + 6 CAB = 180◦ .
O
C C
e~1 e~2
G
M N M N
H
O I O
I
A B A K B
Figure 8 Figure 9
11
centre, and let G , H and K be the points where the incircle touches
the sides BC , AC and AB of the triangle, respectively. Also, let N be
the midpoint of BC and M the midpoint of AC (see Figure 9). Since
6 CM O = 6 CN O = 90◦ , points M and N lie on the circle with diam-
eter OC . We will show that point I also lies on that circle. Indeed, we
have
|AC| + |BC|
|AH| + |BG| = |AK| + |BK| = |AB| = = |AM | + |BN | ,
2
implying |DG| = |EH| . Hence the triangles DIG ja EIH are congruent,
12
M
N
K
H
G
I
and
e~1
e~26 DIE = 6 GIH = 180◦ − 6 C .
O
C C
D G
E E D
I H I
A F B A K B
Figure 10 Figure 11
On the other hand,
6 A+6 B
6 DIE = 6 AIB = 180◦ − .
2
Hence
6 A+6 B 6 C
6 C= = 90◦ − ,
2 2
which gives 6 C = 60◦ .
14. The quadrilaterals DBCG and F BCE are trapeziums. The area of a
trapezium is equal to half the sum of the lengths of the parallel sides multi-
plied by the distance between them. But the distance between the parallel
sides is the same for both of these trapeziums, since the distance from B
to AC is equal to the distance from C to AB . It therefore suffices to show
that
|BD| + |CG| |AD|
=
|CE| + |BF | |AE|
(see Figure 12). Now, since the triangles BDF , ADE and CGE are
similar, we have
|BD| |CG| |AD|
= = ,
|BF | |CE| |AE|
13
D
E
F
K
H
G
which implies the required equality.
I
F0
G G
C
C
E E
A A M
D D
B B
G0
F F
Figure 12 Figure 13
and
15. Consider a point F on BC such that |CF | = |BD| (see Figure 14). Since
6 ACF = 60◦ , triangle ACF is equilateral. Therefore |AF | = |AC| = |CE|
14
I
A
B
C
D
and 6 AFEB = 6 ECD = 120◦ . Moreover, |BF | = |CD| . This implies that
trianglesFAF B and ECD are congruent, and |AB| = |DE| .
G
F0 E
G0
M
C
60◦
F D
A B
Figure 14
16. Answer: 14 .
Assume that there are integers n, m such that k = 19n − 5m is a positive
integer smaller than 191 − 51 = 14 . For obvious reasons, n and m must be
positive.
Case 1: Assume that n is even. Then the last digit of k is 6 . Consequently,
we have 19n − 5m = 6 . Considering this equation modulo 3 implies that m
15
must be even as well. With n = 2n0 and m = 2m0 the above equation can
be restated as (19n + 5m )(19n − 5m ) = 6 which evidently has no solution
0 0 0 0
in positive integers.
Case 2: Assume that n is odd. Then the last digit of k is 4 . Consequently,
we have 19n − 5m = 4 . On the other hand, the remainder of 19n − 5m
modulo 3 is never 1 , a contradiction.
17. Answer: yes.
Let n = 5 and consider the integers 0, 2, 8, 14, 26 . Adding a = 3 or a = 5
to all of these integers we get primes. Since the numbers 0 , 2 , 8 , 14 and
26 have pairwise different remainders modulo 5 then for any integer a the
numbers a + 0 , a + 2 , a + 8 , a + 14 and a + 26 have also pairwise different
remainders modulo 5 ; therefore one of them is divisible by 5 . Hence if the
numbers a + 0 , a + 2 , a + 8 , a + 14 and a + 26 are all primes then one of
them must be equal to 5 , which is only true for a = 3 and a = 5 .
√
18. Squaring the second inequality gives (a − b)2 < 5 + 4 4m + 1 . Since
m = ab , we have
√ √
(a + b)2 < 5 + 4 4m + 1 + 4m = ( 4m + 1 + 2)2 ,
implying
√
a+b< 4m + 1 + 2 .
Since a > b , different factorizations m = ab will give different values for
the sum a + b ( ab = m, a + b = k, a > b has at most one solution in (a, b) ).
Since m ≡ 2 (mod 4) , we see that a and b must have different parity, and
a + b must be odd. Also note that
√ √
a + b > 2 ab = 4m .
Since 4m cannot be a square we have
√
a + b > 4m + 1 .
√ √
Since a + b is odd and the interval [ 4m + 1, 4m + 1 + 2 ) contains ex-
actly one odd integer, then there can be at most
q one pair (a, b) such that
√ √
a + b < 4m + 1 + 2 , or equivalently a − b < 5 + 4 4m + 1 .
19. Note that the square of any prime p 6= 3 is congruent to 1 modulo 3 . Hence
the numbers k = 6m + 2 will have the required property for any p = 6 3 , as
16
p2 + k will be divisible by 3 and hence composite.
In order to have 32 +k also composite, we look for such values of m for which
k = 6m + 2 is congruent to 1 modulo 5 — then 32 + k will be divisible
by 5 and hence composite. Taking m = 5t + 4 , we have k = 30t + 26 ,
which is congruent to 2 modulo 3 and congruent to 1 modulo 5 . Hence
p2 + (30t + 26) is composite for any positive integer t and prime p .
b
implying b 6 13 . From 4 < c < we now have c = 5 and b must be either
2
11 or 13 . It remains to check that 1749 + 22 − 52 + 132 = 1897 is not a
square of an integer, and 1749 + 22 − 52 + 112 = 1849 = 432 . Hence b = 11 ,
a = 43 and
17
“Baltic Way – 90” mathematical team contest
Problems
1. Integers 1, 2, . . . , n are written (in some order) on the circumference of a circle. What is the
smallest possible sum of moduli of the differences of neighbouring numbers?
n
...
4 10 14
3 6 9 13
2 3 5 8 12
1 1 2 4 7 11
1 2 3 4 5 ... m
Devise a polynomial p(m, n) of two variables m, n such that for any positive integers m and
n the number written in the square with coordinates (m, n) will be equal to p(m, n) .
an + c
an+1 = , n = 0, 1, . . . .
1 − an c
Is it possible that the first 1990 terms a0 , a1 , . . . , a1989 are all positive but a1990 < 0 ?
n
X ai aj
> 0.
i,j=1
i + j−1
5. Let ∗ denote an operation, assigning a real number a ∗ b to each pair of real numbers (a, b)
(e.g. a ∗ b = a + b2 − 17 ). Devise an equation which is true (for all possible values of variables)
provided the operation ∗ is commutative or associative and which can be false otherwise.
6. Let ABCD be a quadrangle, |AD| = |BC| , 6 A + 6 B = 120◦ and let P be a point exterior
to the quadrangle such that P and A lie at opposite sides of the line DC and the triangle
DP C is equilateral. Prove that the triangle AP B is also equilateral.
7. The midpoint of each side of a convex pentagon is connected by a segment with the intersection
point of the medians of the triangle formed by the remaining three vertices of the pentagon.
Prove that all five such segments intersect at one point.
8. Let P be a point on the circumcircle of a triangle ABC . It is known that the basepoints of
the perpendiculars drawn from P onto the lines AB, BC , and CA lie on one straight line
(called a Simpson line). Prove that the Simpson lines of two diametrically opposite points P1
and P2 are perpendicular.
9. Two equal triangles are inscribed into an ellipse. Are they necessarily symmetrical with respect
either to the axes or to the centre of the ellipse?
1
10. A segment AB of unit length is marked on the straight line t . The segment is then moved on
the plane so that it remains parallel to t at all times, the traces of the points A and B do
not intersect and finally the segment returns onto t . How far can the point A now be from
its initial position?
11. Prove that the modulus of an integer root of a polynomial with integer coefficients cannot
exceed the maximum of the moduli of the coefficients.
12. Let m and n be positive integers. Prove that 25m + 3n is divisible by 83 if and only if
3m + 7n is divisible by 83 .
13. Prove that the equation x2 − 7y 2 = 1 has infinitely many solutions in natural numbers.
14. Do there exist 1990 relatively prime numbers such that all possible sums of two or more of
these numbers are composite numbers?
is a cube of an integer.
16. A closed polygonal line is drawn on squared paper so that its links lie on the lines of the paper
(the sides of the squares are equal to 1 ). The lengths of all links are odd numbers. Prove that
the number of links is divisible by 4 .
17. In two piles there are 72 and 30 sweets respectively. Two students take, one after another,
some sweets from one of the piles. Each time the number of sweets taken from a pile must be
an integer multiple of the number of sweets in the other pile. Is it the beginner of the game or
his adversary who can always assure taking the last sweet from one of the piles?
18. Positive integers 1, 2, . . . , 100, 101 are written in the cells of a 101 × 101 square grid so that
each number is repeated 101 times. Prove that there exists either a column or a row containing
at least 11 different numbers.
19. What is the largest possible number of subsets of the set { 1, 2, . . . , 2n + 1 } so that the
intersection of any two subsets consists of one or several consecutive integers?
20. A creative task: propose an original competition problem together with its solution.
2
“Baltic Way – 90” mathematical team contest
|1−a2 |+|a2 −a3 |+. . .+|ak −n|+|n−ak+1 |+. . .+|an −1| >
> |1−a2 +a2 −a3 +. . .+ak −n|+|n−ak+1 +. . .+an −1| =
= |1 − n| + |n − 1| = 2n − 2 .
This minimum is achieved if the numbers are written around the circle in increasing order.
2. Since the square with the coordinates (m, n) is n-th on the (n+m−1)-th diagonal, it contains
the number
n+m−2
X (n + m − 1)(n + m − 2)
P (m, n) = i +n= +n.
i=1
2
3. Obviously we can find angles 0 < α, β < 90◦ such that tan α > 0 , tan (α + β) > 0 , . . . ,
tan (α+1989β) > 0 but tan (α+1990β) < 0 . Now it suffices to note that if we take a0 = tan α
and c = tan β then an = tan (α + nβ) .
n
X
4. Consider the polynomial P (x) = a1 + a2 x + . . . + an xn−1 , then P 2 (x) = ak al xk+l−2 and
k,l=1
Z 1 n
X ak al
P 2 (x) = .
0 k+l−1
k,l=1
1
P B
l P
C1
·
D h O
C · ·
C B1 A
A B
9. No, not necessarily (see Fig. 3 where the two ellipses are equal).
10. The point A can move to any distance from its initial position — see Fig. 4 and note that we
can make the height h arbitrarily small.
A B
t t
h
Figure 4
11. For a polynomial P (x) = an xn + . . . + a1 x + a0 with integer coefficients let k be the smallest
index such that ak 6= 0 , i.e. in fact P (x) = an xn + . . . + ak xk . If c is an integer root of P (x)
then P (x) = (x − c) · Q(x) where Q(x) = bn−1 xn−1 + . . . + bk xk is a polynomial with integer
coefficients, an = bn−1 and ak = −bk · c . Since ak 6= 0 we have bk 6= 0 and |c| 6 |ak | .
12. Use the equality 2 · (25x + 3y) + 11 · (3x + 7y) = 83x + 83y .
13. For any solution (m, n) of the equation we have m2 − 7n2 = 1 and
1 = (m2 − 7n2 )2 = (m2 + 7n2 )2 − 7 · (2mn)2 , hence (m2 + 7n2 , 2mn) is also a solu-
tion. Therefore it is sufficient to note that the equation x2 − 7y 2 = 1 has at least one solution,
e.g. x = 8 , y = 3 .
14. Such numbers do exist. Let M = 1990! and consider the sequence of numbers 1+M , 1+2M ,
1+3M , . . . . For any natural number 2 6 k 6 1990 any sum S of exactly k of these numbers
(not necessarily different) is divisible by k < S and hence a composite number. It remains to
show that we can choose 1990 numbers a1 , . . . , a1990 from this sequence which are relatively
prime. Indeed, let a1 = 1 + M , a2 = 1 + 2M and for a1 , . . . , an already chosen take
an+1 = 1 + a1 · . . . · an · M .
n
15. Assume there exist such natural numbers k and n that 22 + 1 = k 3 . Then k must be
n
an odd number and we have 22 = k 3 − 1 = (k − 1)(k 2 + k + 1) . Hence k − 1 = 2s and
k 2 + k + 1 = 2t where s and t are some natural numbers. Now 22s = (k − 1)2 = k 2 − 2k + 1
and 2t − 22s = 3k , but 2t − 22s is even while 3k is odd, a contradiction.
16. There must be an equal number of horizontal and vertical links, hence it suffices to show that
the number of vertical links is even. Let’s pass the whole polygonal line in a chosen direction
and mark each vertical link as “up” or “down” according to the direction we pass it. As the
sum of lengths of the “up” links is equal to that of the “down” ones and each link is of odd
length then we have an even or odd number of links of both kinds depending on the parity of
the sum of their lengths.
17. Note that one of the players must have a “winning” strategy. Assume it is the player making
the second move who has it, then his strategy will assure taking the last sweet also in the case
when the beginner takes 2 · 30 sweets as his first move. But now, if the beginner takes 1 · 30
sweets then the second player has no choice but to take another 30 sweets from the same pile,
and hence the beginner can use the same strategy to assure taking the last sweet himself. This
contradiction shows that it must be the beginner who has the “winning” strategy.
2
18. Let ak denote the total number of rows and columns containing the number k at least once.
As i · (20 − i) < 101 for any natural number i we have ak > 21 for all k = 1, 2, . . . , 101 .
Hence a1 + . . . + a101 > 21 · 101 = 2121 . On the other hand, assuming any row and column
contains no more than 10 different numbers we have a1 + . . . + a101 6 202 · 10 = 2020 , a
contradiction.
19. Consider any subsets A1 , . . . , As satisfying the condition of the problem and let
Ai = { ai1 , . . . , ai,ki } where ai1 < . . . < ai,ki . Replacing each Ai by
A′i = { ai1 , ai1 + 1, . . . , ai,ki − 1, ai,ki } (i.e. adding to it all “missing” numbers) yields a
collection of different subsets A′1 , . . . , A′s which also satisfies the required condition. Now,
let bi and ci be the smallest and largest elements of the subset A′i respectively, then
min ci > max bi as otherwise some subsets A′k and A′l would not intersect. Hence there
16i6s 16i6s
\
exists an element a ∈ A′i . As the number of subsets of the set { 1, 2, . . . , 2n + 1 } con-
16i6s
taining a and consisting of k consequtive integers does not exceed min (k, 2n + 2 − k) we
have s 6 (n + 1) + 2 · (1 + 2 + . . . + n) = (n + 1)2 . This maximum will be reached if we take
a = n+1.
3
“Baltic Way – 91” mathematical team contest
Problems
1. Find the smallest positive integer n having the property: for any set of n distinct integers
a1 , a2 , . . . , an the product of all differences ai − aj , i < j is divisible by 1991 .
2. Prove that there are no positive integers n and m > 1 such that 1021991 + 1031991 = nm .
3. There are 20 cats priced from $12 to $15 and 20 sacks priced from 10 cents to $1 for sale
(all prices are different). Prove that each of two boys, John and Peter, can buy a cat in a sack
paying the same amount of money.
4. Let p be a polynomial with integer coefficients such that p(−n) < p(n) < n for some integer
n . Prove that p(−n) < −n .
1 1 1 2 2 2 9
+ + > + + > .
a b c a+b b+c c+a a+b+c
6. Let [x] be the integer part of a number x , and {x} = x − [x] . Solve the equation
11. All positive integers from 1 to 1 000 000 are divided into two groups consisting of numbers
with odd or even sums of digits respectively. Which group contains more numbers?
12. The vertices of a convex 1991-gon are enumerated with integers from 1 to 1991 . Each side
and diagonal of the 1991-gon is coloured either red or blue. Prove that, for an arbitrary
renumeration of vertices, one can find integers k and l such that the line connecting vertices
with numbers k and l before the renumeration has the same colour as the line between the
vertices having these numbers after the renumeration.
13. An equilateral triangle is divided into 25 congruent triangles enumerated with numbers from
1 to 25 . Prove that one can find two triangles having a common side and with the difference
of the numbers assigned to them greater than 3 .
1
14. A castle has a number of halls and n doors. Every door leads into another hall or outside.
Every hall has at least two doors. A knight enters the castle. In any hall, he can choose any
door for exit except the one he just used to enter that hall. Find a strategy allowing the knight
to get outside after visiting no more than 2n halls (a hall is counted each time it is entered).
15. In each of the squares of a chessboard an arbitrary integer is written. A king starts to move
on the board. As the king moves, 1 is added to the number in each square it “visits”. Is it
always possible to make the numbers on the chessboard:
a) all even;
b) all divisible by 3 ;
c) all equal?
16. Let two circles C1 and C2 (with radii r1 and r2 ) touch each other externally, and let l be
their common tangent. A third circle C3 (with radius r3 < min(r1 , r2 ) ) is externally tangent
to the two given circles and tangent to the line l . Prove that
1 1 1
√ =√ +√ .
r3 r1 r2
17. Let the coordinate planes have the reflection property. A beam falls onto one of them. How
does the final direction of the beam after reflecting from all three coordinate planes depend on
its initial direction?
1
18. Is it possible to put two tetrahedra of volume without intersection into a sphere with radius
2
1?
19. Let’s expand a little bit three circles, touching each other externally, so that three pairs of
intersection points appear. Denote by A1 , B1 , C1 the three so obtained “external” points
and by A2 , B2 , C2 the corresponding “internal” points. Prove the equality
1
20. Consider two points A(x1 , y1 ) and B(x2 , y2 ) on the graph of the function y =such that
x
0 < x1 < x2 and |AB| = 2 · |OA| ( O is the reference point, i.e. O(0, 0) ). Let C be the
midpoint of the segment AB . Prove that the angle between the x-axis and the ray OA is
equal to three times the angle between x-axis and the ray OC .
2
“Baltic Way – 91” mathematical team contest
2. Factorizing, we get
where 102 + 103 = 205 = 5 · 41 . It suffices to show that the other factor is not divisible by 5 .
Let ak = 102k · 1031990−k , then ak ≡ 4 (mod 5) if k is even and ak ≡ −4 (mod 5) if k is
odd. Thus the whole second factor is congruent to 4 · 1991 ≡ 4 (mod 5) .
3. The number of different possibilities for buying a cat and a sack is 20 · 20 = 400 while the
number of different possible prices is 1600 − 1210 + 1 = 391 . Thus by the pigeonhole principle
there exist two combinations of a cat and a sack costing the same amount of money. Note that
the two cats (and also the two sacks) involved must be different as otherwise the two sacks
(respectively, cats) would have equal prices.
6. Denote f (x) = [x] · {x} , then we have to solve the equation f (x) = 1991x . Obviously,
x = 0 is a solution. For any x > 0 we have 0 6 [x] 6 x and 0 6 {x} < 1 which imply
f (x) < x < 1991x . For x 6 −1 we have 0 > [x] > x − 1 and 0 6 {x} < 1 which imply
f (x) > x − 1 > 1991x . Finally, if −1 < x < 0 , then [x] = −1 , {x} = x − [x] = x + 1 and
1
f (x) = −x − 1 . The only solution of the equation −x − 1 = 1991x is x = − .
1992
π π
7. In an acute-angled triangle we have A + B > , hence sin A > sin − B = cos B and
2 2
sin B > cos A . Using these inequalities we get (1 − sin A)(1 − sin B) < (1 − cos A)(1 − cos B)
and
1
8. At the left-hand side of the equation we have the derivative of the function
f (x) = (x − a)(x − b)(x − c)(x − d)(x − e) which is continuous and has five distinct real
roots.
9. Studying the graphs of the functions aex and x3 it is easy to see that the equation has always
one solution if a 6 0 and can have 0 , 1 or 2 solutions if a > 0 . Moreover, in the case a > 0
the number of solutions can only decrease as a increases and we have exactly one positive
value of a for which the equation has one solution — this is the case when the graphs of aex
and x3 are tangent to each other, i.e. there exists x0 such that aex0 = x30 and aex0 = 3x20 .
27
From these two equations we get x0 = 3 and a = 3 . Summarizing: the equation aex = x3
e
27 27
has one solution for a 6 0 and a = 3 , two solutions for 0 < a < 3 and no solutions for
e e
27
a> 3 .
e
sin 3◦ = sin(18◦ − 15◦ ) = sin 18◦ cos 15◦ + cos 18◦ sin 15◦
30◦
s √ √
◦ 1 − cos 30◦ 6− 2
where sin 15 = sin = = and
2 2 4
√ √
p 6+ 2
cos 15◦ = 1 − sin2 15◦ = . To calculate cos 18◦ and sin 18◦ note that
4
cos(3 · 18◦ ) = sin(2 · 18◦ ) . As cos 3x = cos3 x − 3 cos x sin2 x = cos x(1 − 4 sin2 x) and
sin 2x = 2 sin x cos x we get 1 − 4 sin2 18◦ = 2 sin 18◦ . Solving this quadratic
p equation yields
√ √ √
5−1 − 5−1 10 + 2 5
sin 18◦ = (we discard which is negative) and cos 18◦ = .
4 4 4
11. Among any ten integers a1 . . . an 0 , a1 . . . an 0 , . . . , a1 . . . an 0 there are exactly five numbers
with odd sum of digits and five numbers with even sum of digits. Thus, among the integers
0, 1, . . . , 999 999 we have as many numbers with odd sum of digits as there are numbers with
even sum of digits. After substituting 1 000 000 instead of 0 we shall have more numbers with
odd sum of digits.
12. Assume there exists a renumeration such that for any numbers 1 6 k < l 6 n the segment
connecting vertices numbered k and l before the renumeration has a different colour than the
segment connecting vertices with the same numbers after the renumeration. Thus there has
to be an equal number of red and blue segments, i.e. the total number of segments should be
2
even. However, the number C1991 = 995 · 1991 is odd.
13. Define the distance between two small triangles to be the minimal number of steps one needs
to move from one of the triangles to the other (a step here means transition from one triangle
to another having a common side with it). The maximum distance between two small triangles
is 8 and this maximum is achieved if and only if one of these lies at a corner of the big triangle
and the other lies anywhere at the opposite side of it. Assume now that we have assigned the
numbers 1, . . . , 25 to the small triangles so that the difference of the numbers assigned to any
two adjacent triangles does not exceed 3 . Then the distance between the triangles numbered
1 and 25 ; 1 and 24 ; 2 and 25 ; 2 and 24 must be equal to 8 . However, this is not possible
since it implies that either the numbers 1 and 2 or 24 and 25 should be assigned to the
same “corner” triangle.
14. The knight can use the following strategy: exit from any hall through the door immediately
to the right of the one he used to enter that hall. Then, knowing which door was passed last
and in which direction we can uniquely restore the whole path of the knight up to that point.
Therefore, he will not be able to pass any door twice in the same direction unless he has been
outside the castle in between.
2
15. Figure 1 demonstrates a possible king’s path passing through each square exactly once and
finally returning to the initial square. Thus, it suffices to prove part c) as we can always
increase the numbers on all the squares by 1 or 2 if necessary. Moreover, note that for any
given square it is possible to modify the path shown on Fig. 1 in such a way that this particular
square will be passed twice while any other square will still be passed exactly once. Repeating
this procedure a suitable number of times for each square we can make all the numbers on the
chessboard equal to each other.
16. Let P1 , P2 , P3 be the perpendicular projections of O1 , O2 , O3 to the line l and let Q be the
perpendicular projection of O3 to the line P1 O1 (see Fig. 2). Then |QO3 |2 = |O1 O3 |2 −|QO1 |2
and |P1 P3 |2 = (r1 + r3 )2 − (r1 − r3 )2 = 4r1 r3 . Similarly we get |P1 P2 |2 = 4r1 r2 and
√ √ √
|P2 P3 |2 = 4r2 r3 . Since |P1 P2 | = |P1 P3 | + |P2 P3 | we have r1 r2 = r1 r3 + r2 r3 which
clearly implies the required equality.
y
O2 q 6
O1 q O3 A
· q C
· · · B
j
P1 P3 P2 l -
O x
Figure 5 Figure 6 Figure 7
17. Let the velocity vector of the plane be ~v = (α, β, γ) . Reflection from each of the coordinate
planes changes the sign of exactly one of the coordinates α , β and γ , thus the final direction
will be opposite to the initial one.
18. No, it is not. Any tetrahedron that does not contain the centre of the sphere as an internal
point has a height drawn to one of its faces less or equal than the radius of the sphere, i.e. 1 .
As each of the faces of the√tetrahedron is contained in a circle with radius not greater than 1 ,
3 3
its area cannot exceed . Thus, the volume of such a tetrahedron must be less or equal
4
√ √
1 3 3 3 1
than ·1· = < .
3 4 4 2
19. First, note that the three straight lines A1 A2 , B1 B2 and C1 C2 intersect in a single point O .
Indeed, each of the lines is the locus of points from which the tangents to two of the circles are
of equal length (it is easy to check that this locus has the form of a straight line and obviously it
contains the two intersection points of the circles). Now, we have |OA1 | · |OA2 | = |OB1 | · |OB2 |
(as both of these products are equal to |OT |2 where OT is a tangent line to the circle contain-
|OA1 | |OB1 |
ing A1 , A2 , B1 , B2 and T is the corresponding point of tangency). Hence =
|OB2 | |OA2 |
|A1 B2 | |OA1 |
which implies that the triangles OA1 B2 and OB1 A2 are similar and = . Sim-
|A2 B1 | |OB1 |
|B1 C2 | |OB1 | |C1 A2 | |OC1 |
ilarly we get = and = . It remains to multiply these three
|B2 C1 | |OC1 | |C2 A1 | |OA1 |
equalities.
1 1 x + x
1 2 1 1
20. We have A x1 , , B x2 , and C , + . Computing the coordinates of
x1 x2 2 2x1 2x2
−→ −−→
~v = |OC| · AC + |AC| · OC we find that the vector ~v — and hence also the bisector of the angle
6 OCA — is parallel to the x-axis. Since |OA| = |AC| this yields 6 AOC = 6 ACO = 2· 6 COx
(see Fig. 3) and 6 AOx = 6 AOC + 6 COx = 3 · 6 COx .
3
Baltic Way 2000
Problems
1. Let K be a point inside the triangle ABC . Let M and N be points such
that M and K are on opposite sides of the line AB , and N and K are on
opposite sides of the line BC . Assume that
6 M AB = 6 M BA = 6 N BC = 6 N CB = 6 KAC = 6 KCA .
3. Given a triangle ABC with 6 A = 90◦ and |AB| 6= |AC| . The points
D , E , F lie on the sides BC , CA , AB , respectively, in such a way that
AF DE is a square. Prove that the line BC , the line F E and the line
tangent at the point A to the circumcircle of the triangle ABC intersect
in one point.
6. Fredek runs a private hotel. He claims that whenever n > 3 guests visit
the hotel, it is possible to select two guests who have equally many acquain-
tances among the other guests, and who also have a common acquaintance
or a common unknown among the guests. For which values of n is Fredek
right?
1
(Acquaintance is a symmetric relation.)
10. Two positive integers are written on the blackboard. Initially, one of them
is 2000 and the other is smaller than 2000 . If the arithmetic mean m of
the two numbers on the blackboard is an integer, the following operation is
allowed: one of the two numbers is erased and replaced by m . Prove that
this operation cannot be performed more than ten times. Give an example
where the operation can be performed ten times.
2
12405 ). Prove that
1 1 1
+ + ··· + <3.
x1 x2 xn
14. Find all positive integers n such that n is equal to 100 times the number
of positive divisors of n .
15. Let n be a positive integer not divisible by 2 or 3 . Prove that for all
integers k , the number (k + 1)n − k n − 1 is divisible by k 2 + k + 1 .
18. Determine all positive real numbers x and y satisfying the equation
1 1 √ p
x+y+ + + 4 = 2 · ( 2x + 1 + 2y + 1) .
x y
1
19. Let t > be a real number and n a positive integer. Prove that
2
3
Solutions
1. Denote 6 M AB = 6 M BA = · · · = α . Then
6 M AK = α + (6 BAC − α) = 6 BAC ,
|AM | 1 |AK| 1
= and = (see Figure 1). Hence the tri-
|AB| 2 cos α |AC| 2 cos α
|BC|
angles M AK and BAC are similar, implying |M K| = . Since
2 cos α
|BC|
|BN | = , we have |M K| = |BN | . Similarly we can show that
2 cos α
|BM | = |N K| , and the result follows.
C K
C
α α N
N
α P
α K
A α α B
M A M B
Figure 1 Figure 2
2. Choose the point K such that ABKC is a square. Let N be the point of
intersection of AP and BK (see Figure 2). Since the lines AN and CM
are perpendicular, N is the midpoint of BK . Moreover, triangles AM C
and BN A are congruent, which gives
6 AM C = 6 BN A . (1)
4
3. Let BC and F E meet at P (see Figure 3). It suffices to show that the line
AP is tangent to the circumcircle of the triangle ABC .
F
PSfrag replacements
E
B P
D C
Figure 3
4. Since 6 ABC + 6 ACB = 60◦ , the lines BP and CQ are parallel. Let X
and Y be the feet of perpendiculars
√ from A to BP and √ CQ , respectively
3 3
(see Figure 4). Then |AX| = |AB| and |AY | = |AC| . Since the
2 2
points X , A and Y are collinear, we get
√
3
|P Q| > |XY | = (|AB| + |AC|) .
2
A Y
X
P 120◦ L
K
B C
Figure 4
5
5. Answer: 1 : 2 .
a c+a
Denote |BC| = a , |AC| = b , |AB| = c . The condition =
c−a b
implies c2 = a2 + ab and
c a
= .
a+b c
a
Let D be a point on AB such that |BD| = · c (see Figure 5). Then
a+b
|BD| c a |BC|
= = = ,
|BC| a+b c |BA|
so triangles BCD and BAC are similar, implying 6 BCD = 6 BAC . Also,
|AC| |AD| |BC| |AC|
= yields = , and hence by the bisector theorem
|BC| |BD| |BD| |AD|
CD is the bisector of 6 BCA . So the ratio asked for is 1 : 2 .
B
D
c a
A b C
Figure 5
6
guests C , D with the same number of acquaintances in K \ {A, B} . Since
every guest in K \ {A, B} is acquaintance either with A or with B but not
with both, C and D have the same number of acquaintances in K , which
1 1
implies that they both have either n or n − 1 acquaintances in K .
2 2
Finally, choose from K \ {A, B, C, D} two guests E , F with the same num-
ber of acquaintances in K \ {A, B, C, D} (this is possible as n > 6 ). Since
every guest in K \ {A, B, C, D} has exactly two acquaintances in the set
{A, B, C, D} , the guests E and F have the same number of acquaintances
1 1
in K , which means that they both have either n or n − 1 acquaintances
2 2
in K . Thus at least four people among A , B , C , D , E , F have the same
number of acquaintances in K . Select any three of these four guests – then
one of these three is either a common acquaintance or a common unknown
for the other two.
For n = 4 Fredek is not right. The diagram on Figure 6 gives the coun-
terexample (where points indicate guests and lines show acquaintances).
A B
u u
u u
Figure 6
7. Answer: 2000 .
Altering the state from all-OFF to all-ON requires that the state of each
button is changed an odd number of times. This is achieved by touching
each button once. We prove that the desired result cannot be achieved if
some button is never touched. In order to turn this button ON, the total
number of touches of the other buttons in its row and column must be odd.
Hence either the other buttons in its row or in its column — say, in its
row — must be touched an odd number of times altogether. In order to
change the state of each of these (odd number of) buttons an odd number
of times, the total number of touches of all the other buttons on the panel
(i.e. outside of the selected row) must be even. But then we have an even
7
total number of state changes for the (odd number of) other buttons in the
selected column, whereas an odd number is required to alter the state of all
these buttons. Hence the minimal number of touches is 40 · 50 = 2000 .
8. Answer: Fredek returned at least 32 times.
Assume Fredek returned k times, i.e. he was saying good-bye k + 1 times
to his friends. There exists a friend of Fredek, call him X13 , about whom
Fredek forgot k times in a row, starting from the very first time – otherwise
Fredek would have come back less than k times.
Consider the remaining friends of Fredek: X1 , X2 , . . . , X12 . Assume that
Fredek forgot xj times about each friend Xj . Since Fredek forgot a different
number of times about each of his friends, so we can assume w.l.o.g. that
xj > j − 1 for j = 1, 2, . . . , 12 . Since X13 was forgotten by Fredek k times,
and since Fredek forgot about exactly three of his friends each time, we
have
3(k + 1) = x1 + x2 + x3 + . . . + x12 + k >
> 0 + 1 + 2 + 3 + . . . + 11 + k =
= 66 + k .
Therefore 2k > 63 , which gives k > 32 .
It is possible that Fredek returned 32 times, i.e. he was saying good-bye
33 times to his friends. The following table shows this. The i -th column
displays the three friends Fredek forgot while saying good-bye for the i -th
time (i.e. before his i -th return). For simplicity we write j in place of Xj .
13 ... 13 13 13 . . . 13 13 ... 13 13 13 13 13 13 13 13 11
11 ... 11 11 8 . . . 8 7 ... 7 7 4 4 4 4 3 3 3
10
| .{z
.. 10} 9 9| .{z
.. 9} 6| .{z
.. 6} 5 5 5 5 5 2 2 1
10 8 6
8
p
(i ± 1, j ± k) is 1 + k 2 , we have f (i, j) ∈ O for every (i, j) ∈ X . Now,
since f is one-to-one, the number of elements in f (S) is the same as the
number of elements in S . As f (X) ⊂ O , the number of elements in X is
at most the number of elements in O , or m 6 n .
10. Each time the operation is performed, the difference between the two num-
bers on the blackboard will become one half of its previous value (regardless
of which number was erased). The mean value of two integers is an integer if
and only if their difference is an even number. Suppose the initial numbers
were a = 2000 and b . It follows that the operation can be performed n
times if and only if a − b is of the form 2n u . This shows that n 6 10 since
211 > 2000 . Choosing b = 976 so that a − b = 1024 = 210 , the operation
can be performed 10 times.
11. Answer: 128 .
Let d denote the least possible value of a2000 . We shall prove that d = 128 .
Clearly the sequence defined by a1 = 1 and an = 2α1 +α2 +···+αk for
αk
n = pα 1 α2
1 p2 · · · · · p k has the required property. Since 2000 = 24 · 53 ,
4+3
we have a2000 = 2 = 128 and therefore d 6 128 .
Note that in the sequence 1 < 5 < 25 < 125 < 250 < 500 < 1000 < 2000
each term is divisible by the previous one. As a1 > 1 it follows that
a2000 > 2 · a1000 > 22 · a500 > 23 · a250 > . . . > 27 · a1 > 27 = 128 .
9
13. Assume ai = k + di for i = 1, 2, . . . , n . Then k is a multiple of every
i ∈ {1, 2, . . . , n − 1} but not a multiple of n . If n = ab with a, b > 1 and
gcd(a, b) = 1 , then k is divisible by both a and b , but not by n , which is
a contradiction. Hence, n has only one prime factor.
we have
δ(n) n d(m) 1+p.m p.n 1
= · =p· =p· > 2 · = 1,
δ(m) m d(n) 1+p.n 1+p.n 2
hence δ(m) 6 δ(n) . It is also clear that equality holds if and only if p = 2
and p . n = 1 , i.e. m is odd and n = 2m .
For the general case n = ms where s > 1 is an arbitrary positive integer,
represent s as a product of primes. By elementary induction on the num-
ber of factors in the representation we prove δ(m) 6 δ(n) . The equality
can hold only if all factors are equal to 2 and the number m as well as
any intermediate result of multiplying it by these factors is odd, i.e. the
representation of s consists of a single prime 2 , which gives n = 2m . This
proves the lemma.
Now assume that δ(n) = 100 for some n , i.e. n = 100 · d(n) = 22 · 52 · d(n) .
In the following, we estimate the exponents of primes in the canonical rep-
resentation of n , using the fact that 100 is a divisor of n .
25 · 100 3200
(1) Observe that δ(27 · 52 ) = = > 100 . Hence 2 . n 6 6 , since
8·3 24
otherwise 27 · 52 divides n and, by the lemma, δ(n) > 100 .
10
52 · 100 2500
(2) Observe that δ(22 · 54 ) = = > 100 . Hence 5 . n 6 3 , since
3·5 15
2 4
otherwise 2 · 5 divides n and, by the lemma, δ(n) > 100 .
34 · 100 8100
(3) Observe that δ(22 · 52 · 34 ) = = > 100 . Hence 3 . n 6 3 ,
3·3·5 45
since otherwise 22 · 52 · 34 divides n and, by the lemma, δ(n) > 100 .
(4) Take a prime q > 5 and an integer k > 4 . Then
22 · 5 2 · q k 22 · 5 2 · q k 22 · 5 2 · 3 k
δ(22 · 52 · q k ) = = > =
d(22 · 52 · q k ) d(22 · 52 · 3k ) d(22 · 52 · 3k )
= δ(22 · 52 · 3k ) > 100.
11
3 . n ∈ {2, 3} . Now 3 . n = 2 would imply that 33 divides d(n) and n , a
contradiction; on the other hand 3 . n = 3 would imply 3 . d(n) = 2 and
hence 3 . n = 2 , a contradiction.
b
A
C
a 60◦ 60◦ c
Figure 7
16. If |OA| = a , |OB| = b , |OC| = c (see Figure 7), then the inequality follows
from |AC| 6 |AB|+|BC| by applying the cosine theorem to triangles AOB ,
12
BOC and AOC . The same argument holds if the quadrangle OABC is
concave.
√ √ √
1± 2 1∓ 2 1± 2
17. Answer : x = , y = 2, z = , t = 2 or x = 2 , y = ,
√2 2 2
1∓ 2
z = 2, t = .
2
Let A = x + z and B = y + t . Then the system of equations is equivalent
to
A+B = 5
AB = 4
Bxz + Ayt = 3
(Bxz) · (Ayt) = −4 .
The first two of these equations imply {A, B} = {1, 4} and the last two
give {Bxz, Ayt} = {−1, 4} . Once A = x + z , B = y + t , Bxz and Ayt
are known, it is easy to find the corresponding values of x , y , z and t .
The solutions are shown in the following table.
A B Bxz Ayt x, z y, t
√
1± 2
1 4 -1 4 2
2
1 4 4 -1 - -
4 1 -1 4 - -√
1± 2
4 1 4 -1 2
2
√
18. Answer : x = y = 1 + 2.
Note that
√
1 √ x2 + 2x + 1 − 2x 2x + 1 1 √
x + + 2 − 2 2x + 1 = = (x − 2x + 1)2 .
x x x
Hence the original equation can be rewritten as
1³ √ ´2 1 ³ p ´2
x − 2x + 1 + y − 2y + 1 = 0 .
x y
√ p
For x, y > 0 this gives x − 2x + 1 = 0 and y − 2y + 1 . It follows that
√
the only solution is x = y = 1 + 2 .
13
19. Use induction. For n = 1 the inequality reads t2 > (t − 1)2 + (2t − 1) which
is obviously true. To prove the induction step it suffices to show that
1
This easily follows from t2 > (t−1)2 (which is true for t > ) and t2 > 2t−1
2
(which is true for any real t ).
20. Squaring both sides of the given equality and applying x(x + 2) 6 (x + 1) 2
to the numerator of the obtained fraction and cancelling we have
(2n + 1) · (4n + 1) 2
x2n 6 <2+ .
(2n)2 n
(4n + 1)2 1
x2n > >2+ .
2n · 4n n
Hence
1 2
< x2n − 2 <
n n
and
1 √ 2
√ < xn − 2 < √ .
n(xn + 2) n(xn + 2)
√
From the first chain of inequalities we get xn > 2 and xn < 2 . The result
then follows from the second chain of inequalities.
14
Comment. These inequalities can easily be improved. For example, the
inequalities in the solution involving x2n can immediately be replaced by
3 2
< x2n − 2 < .
2n n
15
Baltic Way 2001
Problems
5. Let 2001 given points on a circle be colored either red or green. In one
step all points are recolored simultaneously in the following way: If both
direct neighbors of a point P have the same color as P , then the color of P
remains unchanged, otherwise P obtains the other color. Starting with the
first coloring F1 , we obtain the colorings F2 , F3 , . . . after several recoloring
steps. Prove that there is a number n0 6 1000 such that Fn0 = Fn0 +2 . Is
the assertion also true if 1000 is replaced by 999 ?
1
7. Given a parallelogram ABCD . A circle passing through A meets the line
segments AB , AC and AD at inner points M , K , N , respectively. Prove
that
9. Given a rhombus ABCD , find the locus of the points P lying inside the
rhombus and satisfying 6 AP D + 6 BP C = 180◦ .
10. In a triangle ABC , the bisector of 6 BAC meets the side BC at the point
D . Knowing that |BD| · |CD| = |AD|2 and 6 ADB = 45◦ , determine the
angles of triangle ABC .
11. The real-valued function f is defined for all positive integers. For any
integers a > 1 , b > 1 with d = gcd(a, b) , we have
µ ³ ´ ³ b ´¶
a
f (ab) = f (d) · f +f ,
d d
2
the cards can be divided into two heaps with sums s1 and s2 so that
n s1
6 6 1.
n+1 s2
15. Let a0 , a1 , a2 , . . . be a sequence of positive real numbers satisfying
i · a2i > (i + 1) · ai−1 ai+1 for i = 1, 2, . . . . Furthermore, let x and y
be positive reals, and let bi = xai + yai−1 for i = 1, 2, . . . . Prove that the
inequality i · b2i > (i+1) · bi−1 bi+1 holds for all integers i > 2 .
17. Let n be a positive integer. Prove that at least 2n−1 + n numbers can be
chosen from the set {1, 2, 3, . . . , 2n } such that for any two different chosen
numbers x and y , x + y is not a divisor of x · y .
19. What is the smallest positive odd integer having the same number of positive
divisors as 360 ?
Solutions
1. Answer: 8 .
Denote the problems by A , B , C , D , E , F , G , H , then 8 possible
problem sets are ABC , ADE , AF G , BDG , BF H , CDH , CEF , EGH .
Hence, there could be 8 students.
3
Suppose that some problem (e.g., A ) was given to 4 students. Then each
of these 4 students should receive 2 different “supplementary” problems,
and there should be at least 9 problems — a contradiction. Therefore each
problem was given to at most 3 students, and there were at most 8 · 3 = 24
“awardings” of problems. As each student was “awarded” 3 problems, there
were at most 8 students.
2. Answer: yes.
Let A1 be the set of positive integers whose only non-zero digits may be
the 1 -st, the (n + 1) -st, the (2n + 1) -st etc. from the end; A2 be the set of
positive integers whose only non-zero digits may be the 2 -nd, the (n + 2) -
nd, the (2n + 2) -nd etc. from the end, and so on. The sets A1 , A2 , . . . , An
have the required property.
Remark. This problem is quite similar to problem 18 from Baltic Way 1997.
3. Answer: no.
If this were possible, then 2 · (1 + . . . + 49) = A + B = 2B . But B is even
since it is the sum of even numbers, whereas 1 + . . . + 49 = 25 · 49 is odd.
This is a contradiction.
p
4. The line y = x contains the diagonal of the rectangle with vertices (0, 0) ,
q
(q, 0) , (q, p) and (0, p) and passes through no points with integer coordi-
nates in the interior of that rectangle. For k = 1, 2, . . . , q−1 the summand
j kp k
counts the number of interior points of the rectangle lying below the
q
p
diagonal y = x and having x -coordinate equal to k . Therefore the sum
q
in consideration counts all interior points with integer coordinates below
the diagonal, which is exactly half the number of all points with integer
1
coordinates in the interior of the rectangle, i.e. · (p − 1)(q − 1) .
2
Remark. The integers p and q need not be primes: in the solution we only
used the fact that they are coprime.
5. Answer: no.
Let the points be denoted by 1, 2, . . . , 2001 such that i, j are neighbors if
|i − j| = 1 or {i, j} = {1, 2001} . We say that k points form a monochro-
matic segment of length k if the points are consecutive on the circle and if
4
they all have the same color. For a coloring F let d(F ) be the maximum
length of a monochromatic segment. Note that d(Fn ) > 1 for all n since
2001 is odd. If d(F1 ) = 2001 then all points have the same color, hence
F1 = F2 = F3 = . . . and we can choose n0 = 1 . Thus, let 1 < d(F1 ) < 2001 .
Below we shall prove the following implications:
From (1) and (2) it follows that d(F1000 ) 6 2 , hence by (3) we have
F1000 = F1002 . Moreover, if F1 is the coloring where 1 is colored
red and all other points are colored green, then d(F1 ) = 2000 and
thus d(F1 ) > d(F2 ) > . . . > d(F1000 ) = 2 which shows that, for all
n < 1000, Fn 6= Fn+2 and thus 1000 cannot be replaced by 999 .
It remains to prove (1)–(3). Let (i + 1, . . . , i + k) be a longest monochro-
matic segment for Fn (considering the labels of the points modulo 2001 ).
Then (i + 2, . . . , i + k − 1) is a monochromatic segment for Fn+1 and
thus d(Fn+1 ) > d(Fn ) − 2 . Moreover, if (i + 1, . . . , i + k) is a longest
monochromatic segment for Fn+1 where k > 3 , then (i, . . . , i + k + 1) is a
monochromatic segment for Fn . From this and Fn+1 > 1 the implications
(1) and (2) clearly follow. For proof of (3) note that if d(Fn ) 6 2 then
Fn+1 is obtained from Fn by changing the colour of all points.
D
PSfrag replacements
Q C
E
P
A B
Figure 1
6. The arcs BC and AE are of equal length (see Figure 1). Also, since
5
AB k EC and ED k AC , we have 6 CAB = 6 DEC and the arcs DC
and BC are of equal length. Since P E is tangent to c and |AE| = |DC| ,
then 6 P EA = 6 DBC = 6 QBC . As ABCD is inscribed in c , we have
6 QCB = 180◦ − 6 EAB = 6 P AE . Also, ABCD is an isosceles trapezium,
whence |AE| = |BC| . So the triangles AP E and CQB are congruent, and
|QC| = |P A| . Now P ACQ is a quadrilateral with a pair of opposite sides
equal and parallel. So P ACQ is a parallelogram, and |P Q| = |AC| .
6 AXD = 6 AN K = 180◦ − 6 AM K
(see Figure 2). Triangles N AK and XAD are similar, having two pairs of
|AN | · |AD|
equal angles, hence |AX| =
PSfrag replacements . Since triangles M AK and XCD
|AK|
A |AM | · |CD| |AM | · |AB|
are also B
similar, we have |CX| = = and
|AK| |AK|
C
|AM | D
· |AB|+|AN | · |AD| = (|AX|+|CX|) · |AK| = |AC| · |AK| .
E
Q D C
P
X
K
A M B
Figure 2
|BC| |BC|
and |N X| = |N Y | = . Therefore, |XY | = √ . Moreover, we have
2 2
6
|AX| = |AB| and |DY | = |DC| . Consequently,
|BC|
|AD| 6 |AX| + |XY | + |Y D| = |AB| + √ + |DC| .
2
A D
replacements Y
A X
B
C B N C
D Figure 3
E
9. Q
Answer: the locus of the points P is the union of the diagonals AC and
BD .
P
A Q be a point such that P QCD is a parallelogram (see Figure 4). Then
Let
ABQP is also a parallelogram. From the equality 6 AP D + 6 BP C = 180◦
B
it follows that 6 BQC + 6 BP C = 180◦ , so the points B , Q , C , P lie
C
D
on a common circle. Therefore, 6 P BC = 6 P QC = 6 P DC , and since
M|BC| = |CD| , we obtain that 6 CP B = 6 CP D or 6 CP B + 6 CP D = 180◦ .
N
Hence, the point P lies on the segment AC or on the segment BD .
K
X D C D C
P Q
P Q
A A
B B
Figure 4
7
P
A
B
C
D
6 CDE M = 6 ADB = 45◦ it follows that 6 AEO = 45◦ . Since |AO| = |EO| ,
N
we have 6 AOE = 90◦ and AO k DM .
K 2
From theX equality |BD| · |CD| = |AD| we obtain |AD| = |DE| , which im-
plies that
A |OM | = |M E| . Therefore |BO| = |BE| and also |BO| = |EO| .
Hence the triangle BOE is equilateral. This gives 6 BAE = 30◦ , so
B
6 BAC = 60◦ . Summing up the angles of the triangle ABD we obtain
C
6 ABC = 105◦ and from this 6 ACB = 15◦ .
D
P
Q
A O
D
B M C
Figure 5
1
11. Answer: 0 and .
2
1
Obviously the constant functions f (n) = 0 and f (n) =provide solutions.
2
We show that there are no other solutions. Assume f (2001) 6= 0 . Since
2001 = 3 · 667 and gcd(3, 667) = 1 , then
f (2001) = f (1) · (f (3) + f (667)) ,
and f (1) 6= 0 . Since gcd(2001, 2001) = 2001 then
8
argument starting from f (20012 ) 6= 0 instead of f (2001) shows that
1
f (20012 ) = 2f (1) − . So
2
1 ³ 1´
2f (1) − = 2f (1) 2f (1) − .
2 2
1 1
Since 2f (1) − = f (2001) 6= 0 , we have f (1) = , which implies
2 2
1 1
f (2001) = 2f (1) − = .
2 2
12. By Hölder’s inequality,
n
X n
X n
µX n
¶3/5 µX ¶2/5
3 5/3
a = (ai · a2i ) 6 ai · 2 5/2
(ai ) .
i=1 i=1 i=1 i=1
n
X
Let S = ai , then (4) is equivalent to
i=1
n ³ n
X ai ´5/3 X ai
61= ,
i=1
S i=1
S
ai 5 ³ a ´5/3 ai
i
which holds since 0 < 6 1 and > 1 yield 6 . So,
S 3 S S
n
X µ n
X ¶ µ X n ¶ 2/5
a3i 6 ai · a5i ,
i=1 i=1 i=1
n
X 3 3
which gives ai > > , since 25 > 52 and hence 2 > 52/5 .
i=1
52/5 2
9
s s √
1 7 1 7+1 7 1
It has a root < α < 1 , because + = > 1 and + < 1 .
2 9 9 3 9 9
nα
We will prove that an 6 M · nα for some M > 0 — since will be
n
arbitrarily small for large enough n , the claim follows from this immediately.
We choose M so that the inequality an 6 M · nα holds for 1 6 n 6 8 ;
since for n > 9 we have 1 < [7n/9] < n and 1 6 [n/9] < n , it follows by
induction that
h 7n iα h n iα
an = a[7n/9] + a[n/9] 6 M · +M · 6
9 9
³ 7n ´α ³ n ´α µ³ ´ ¶
7 α ³ 1 ´α
6 M· +M · = M · nα · + = M · nα .
9 9 9 9
14. Let the numbers be x1 6 x2 6 . . . 6 x2n−1 6 x2n . We will show that the
choice s1 = x1 + x3 + x5 + · · · + x2n−1 and s2 = x2 + x4 + · · · + x2n solves
s1
the problem. Indeed, the inequality 6 1 is obvious and we have
s2
and
10
By (5),
a2i−1 i 1 1 i+1
> =1+ >1+ = ,
ai ai−2 i−1 i−1 i i
which implies
Multiplying (5) and (6), and dividing both sides of the resulting inequality
by iai ai−1 , we get
Adding (i + 1)ai ai−1 to both sides of the last inequality and multiplying
both sides of the resulting inequality by xy gives
16. Answer: 2 .
f (1)
For any prime p we have f (p) = f (1) − f (p) and thus f (p) = .
2
If n is a product of two primes p and q , then f (n) = f (p) − f (q) or
f (n) = f (q) − f (p) , so f (n) = 0 . By the same reasoning we find that if n
is a product of three primes, then there is a prime p such that
³n´ f (1)
f (n) = f − f (p) = −f (p) = − .
p 2
11
(1) If x = 2a−1 and y = 2b−1 , then x+y = (2a−1)+(2b−1) = 2(a+b−1)
is even and does not divide xy = (2a − 1)(2b − 1) which is odd.
(2) If x = 2k and y = 2m where k < m , then x + y = 2k (2m−k + 1) has
an odd divisor greater than 1 and hence does not divide xy = 2a+b .
(3) If x = 2k and y = 2b − 1 , then x + y = 2k + (2b − 1) > (2b − 1) is odd
and hence does not divide xy = 2k (2b − 1) which has 2b − 1 as its largest
odd divisor.
identity
a2 − 22 = (a2 − 22 ) · (a2 + 22
n n n−1 n−1 n−1 n−1
)
we get
. . . · (a2 + 22 ) · (a + 2) · (a − 2) + 2 · 22 .
n
Remark. The transformations allowed in the problem are in fact the ele-
mentary transformations of the determinant
¯ ¯
¯a b¯
¯ ¯
¯c d¯
and the invariant |ad − bc| is the absolute value of the determinant which
is preserved under these transformations.
12
Baltic Way 2002 mathematical team contest
in real numbers.
Answer: a = 1, b = 1, c = 1 .
Solution. Denoting the left hand sides of the given equations as A , B and C , the following equalities
can easily be seen to hold:
−A + B + C = (−a + b + c)3 ,
A − B + C = (a − b + c)3 ,
A + B − C = (a + b − c)3 .
Hence, the system of equations given in the problem is equivalent to the following one:
(−a + b + c)3 = 1
(a − b + c)3 = 1 ,
(a + b − c)3 = 1
which gives
−a + b + c = 1
a−b+c = 1 .
a+b−c = 1
a + b + c + d = −2 ,
ab + ac + ad + bc + bd + cd = 0 .
−2 = a + b + c + d > na + x . (1)
Squaring we get
4 = a 2 + b2 + c 2 + d2
which implies
4 6 n · a 2 + x2 (2)
as the square of the sum of positive numbers is not less than the sum of their squares.
1
Combining inequalities (1) and (2) we obtain
As n 6 3 (if all the numbers are negative, the second condition of the problem cannot be satisfied), we
obtain from the last inequality that
4a2 + 4a > 0 ,
a(a + 1) > 0 .
A + B + C + D = 2. (3)
We also have
ab = (A − 1)(B − 1) = AB − A − B + 1.
Adding 5 similar terms to the last one we get from the second equation
AB + AC + AD + BC + BD + CD − 3(A + B + C + D) + 6 = 0.
AB + AC + AD + BC + BD + CD = 0,
a + b + c + d = −2 (4)
ab + ac + ad + bc + bd + cd = 0. (5)
Suppose that
If all of a, b, c, d were negative, then (5) could not be satisfied, so at most three of them are nega-
tive. If two or less of them were negative, then (6) would imply that the sum of negative numbers,
and hence also the sum a + b + c + d , is greater than 2 · (−1) = −2 , which contradicts (4). So ex-
actly three of a, b, c, d are negative and one is nonnegative. Let d be the nonnegative one. Then
d = −2 − (a + b + c) < −2 − (−1 − 1 − 1) = 1 . Obviously |a|, |b|, |c|, |d| < 1 . Squaring (4) and subtracting
2 times (5), we get
a2 + b2 + c2 + d2 = 4,
but
a contradiction.
2
3. Find all sequences a0 6 a1 6 a2 6 . . . of real numbers such that
am2 +n2 = a2m + a2n
for all integers m, n > 0 .
1
Answer: an ≡ 0 , an ≡ and an = n .
2
Solution. Denoting f (n) = an we have
1
f (2) = f (12 + 12 ) = 2f 2 (1) = ,
2
1
f (8) = f (22 + 22 ) = 2f 2 (2) = ,
2
1 1
etc, implying that f (2i ) = for arbitrarily large natural i and, due to monotonity, f (n) = for every
2 2
natural n .
(2) If f (0) = 0 then by substituting m = 1 , n = 0 into (7) we obtain f (1) = f 2 (1) and hence, f (1) = 0
or f (1) = 1 . This gives two subcases.
(2a) If f (0) = 0 and f (1) = 0 then by the same technique as above we see that f (2 i ) = 0 for arbitrarily
large natural i and, due to monotonity, f (n) = 0 for every natural n .
(2b) If f (0) = 0 and f (1) = 1 then we compute
Now,
f 2 (3) + f 2 (4) = f (25) = f 2 (5) + f 2 (0) = 25 ,
3
4. Let n be a positive integer. Prove that
n µ ¶2
X
2 1
xi (1 − xi ) 6 1−
i=1
n
2
If some xi > then we have
3
µ ¶2
2 2 1
xi (1 − xi ) 6 1 · 1 − = .
3 9
Hence,
n µ ¶2
X 1 124 1
xi (1 − xi ) 6 + = 6 1−
i=1
9 3 9 n
as n > 3 .
5. Find all pairs (a, b) of positive rational numbers such that
√ q
√ √
a+ b= 2+ 3.
4
µ ¶ µ ¶
1 3 3 1
Answer: (a, b) = , or (a, b) = , .
2 2 2 2
√ √ √
so 2 √ab = r + 3 for some rational number r . Squaring both sides of this gives 4ab = r 2 + 3 + 2r 3 ,
so 2r 3 is rational, which implies µ
r = 0 . ¶Hence ab = 3/4
µ and¶substituting this into (8) gives a + b = 2 .
1 3 3 1
Solving for a and b gives (a, b) = , or (a, b) = , .
2 2 2 2
6. The following solitaire game is played on an m×n rectangular board, m, n > 2 , divided into unit squares.
First, a rook is placed on some square. At each move, the rook can be moved an arbitrary number of
squares horizontally or vertically, with the extra condition that each move has to be made in the 90 ◦
clockwise direction compared to the previous one (e.g. after a move to the left, the next one has to be
done upwards, the next one to the right etc). For which values of m and n is it possible that the rook
visits every square of the board exactly once and returns to the first square? (The rook is considered to
visit only those squares it stops on, and not the ones it steps over.)
Answer: m, n ≡ 0 mod 2 .
Solution. First, consider any row that is not the row where the rook starts from. The rook has to visit
all the squares of that row exactly once, and on its tour around the board, every time it visits this row,
exactly two squares get visited. Hence, m must be even; a similar argument for the columns shows that
n must also be even.
It remains to prove that for any even m and n such a tour is possible. We will show it by an induction-
like argument. Labelling the squares with pairs of integers (i, j) , where 1 6 i 6 m and 1 6 j 6 n , we
start moving from the square (m/2 + 1, 1) and first cover all the squares of the top and bottom rows in
the order shown in the figure below, except for the squares (m/2 − 1, n) and (m/2 + 1, n) ; note that we
finish on the square (m/2 − 1, 1) .
3 7 8 4
2 6 10 1 9 5
The next square to visit will be (m/2 − 1, n − 1) and now we will cover the rows numbered 2 and n − 1 ,
except for the two middle squares in row 2 . Continuing in this way we can visit all the squares except
for the two middle squares in every second row (note that here we need the assumption that m and n
are even):
3 7 8 4
15 19 11 20 16 12
23 27 28 24
35 39 31 40 36 32
34 38 37 33
22 26 30 21 29 25
14 18 17 13
2 6 10 1 9 5
5
The rest of the squares can be visited easily:
3 7 47 48 8 4
15 19 11 20 16 12
23 27 43 44 28 24
35 39 31 40 36 32
34 38 42 41 37 33
22 26 30 21 29 25
14 18 46 45 17 13
2 6 10 1 9 5
7. We draw n convex quadrilaterals in the plane. They divide the plane into regions (one of the regions is
infinite). Determine the maximal possible number of these regions.
Answer: The maximal number of regions is 4n2 − 4n + 2 .
Solution. One quadrilateral produces two regions. Suppose we have drawn k quadrilaterals Q 1 , . . . , Qk
and produced ak regions. We draw another quadrilateral Qk+1 and try to evaluate the number of regions
ak+1 now produced. Our task is to make ak+1 as large as possible. Note that in a maximal configuration,
no vertex of any Qi can be located on the edge of another quadrilateral as otherwise we could move this
vertex a little bit to produce an extra region.
Because of this fact and the convexity of the Qj ’s, any one of the four sides of Qk+1 meets at most two
sides of any Qj . So the sides of Qk+1 are divided into at most 2k + 1 segments, each of which potentially
grows the number of regions by one (being part of the common boundary of two parts, one of which is
counted in ak ).
But if a side of Qk+1 intersects the boundary of each Qj , 1 6 j 6 k twice, then its endpoints (vertices
of Qk+1 ) are in the region outside of all the Qj -s, and the the segments meeting at such a vertex are
on the boundary of a single new part (recall that it makes no sense to put vertices on edges of another
quadrilaterals). This means that ak+1 − ak 6 4(2k + 1) − 4 = 8k . By considering squares inscribed in a
circle one easily sees that the situation where ak+1 − ak = 8k can be reached.
It remains to determine the expression for the maximal ak . Since the difference ak+1 − ak is lin-
ear in k , ak is a quadratic polynomial in k , and a0 = 2 . So ak = Ak 2 + Bk + 2 . We have
8k = ak+1 − ak = A(2k + 1) + B for all k . This implies A = 4 , B = −4 , and an = 4n2 − 4n + 2 .
such that T is a set of triangles whose vertices are all µ in¶ P , and si is a side of ti but not of any tj ,
n
j 6= i . Furthermore, let C be the collection of all the triangles whose vertices are in P . Note that
3
µ ¶ µ ¶ µ ¶
n n−1 n−1
|C \ T | = − = .
3 2 3
6
Let m be the number of pairs (s, t) such that s ∈ S is a side of t ∈ C \ T . Since every s ∈ S is a side
of exactly n − 3 triangles from C \ T , we have
µ ¶ µ ¶
n−1 n−1
m = |S| · (n − 3) = · (n − 3) = 3 · = 3 · |C \ T | .
2 3
On the other hand, every t ∈ C \ T has at most three sides from S . By the above equality, for every
t ∈ C \ T , all its sides must be in S .
Assume that for p ∈ P there is a side s ∈ S such that p is an endpoint of s . Then p is also a vertex
of each of the n − 3 triangles in C \ T which have s as a side. Consequently, p is an endpoint of n − 2
sides in S . Since every side in S has exactly 2 endpoints, the number of points p ∈ P which occur as a
vertex of some s ∈ S is
µ ¶
2 · |S| 2 n−1
= · =n−1.
n−2 n−2 2
Consequently, there is an x ∈ P which is not an endpoint of any s ∈ S , and hence T must be equal to
Tx .
9. Two magicians show the following trick. The first magician goes out of the room. The second magician
takes a deck of 100 cards labelled by numbers 1, 2, . . . , 100 and asks three spectators to choose in turn
one card each. The second magician sees what card each spectator has taken. Then he adds one more
card from the rest of the deck. Spectators shuffle these 4 cards, call the first magician and give him these
4 cards. The first magician looks at the 4 cards and “guesses” what card was chosen by the first spectator,
what card by the second and what card by the third. Prove that the magicians can perform this trick.
Solution. We will identify ourselves with the second magician. Then we need to choose a card in such a
manner that another magician will be able to understand which of the 4 cards we have chosen and what
information it gives about the order of the other cards. We will reach these two goals independently.
Let a , b , c be remainders of the labels of the spectators’ three cards modulo 5. There are three possible
cases.
1) All the three remainders coincide. Then choose a card with a remainder not equal to the remainder
of spectators’ cards. Denote this remainder d .
Note that we now have 2 different remainders, one of them in 3 copies (this will be used by the first
magician to distinguish betwwen the three cases). To determine which of the cards is chosen by us is
now a simple exercise in division by 5. But we must also encode the ordering of the spectators’ cards.
These cards have a natural ordering by their labels, and they are also ordered by their belonging to
the spectators. Thus, we have to encode a permutation of 3 elements. There are 6 permutations of 3
elements, let us enumerate them somehow. Then, if we want to inform the first magician that spectators
form a permutation number k with respect to the natural ordering, we choose the card number 5k + d .
2) The remainders a , b , c are pairwise different. Then it is clear that exactly one of the following
possibilities takes place:
(the equalities are considered modulo 5). It is not hard to prove it by a case study, but one could also
imagine choosing three vertices of a regular pentagon — these vertices always form an isosceles, but not
an equilateral triangle.
Each of these possibilities has one of the remainders distinguished from the other two remainders (these
distinguished remainders are a , b , c , respectively). Now, choose a card from the rest of the deck
having the distinguished remainder modulo 5. Hence, we have three different remainders, one of them
distinguished by (9) and presented in two copies. Let d be the distinguished remainder and s = 5m + d
be the spectator’s card with this remainder.
Now we have to choose a card r with the remainder d such that the first magician would be able to
understand which of the cards s and r was chosen by us and what permutation of spectators it implies.
This can be done easily: if we want to inform the first magician that spectators form a permutation
number k with respect to the natural ordering, we choose the card number s + 5k (mod 100) .
7
The decoding procedure is easy: if we have two numbers p and q that have the same remainder modulo 5,
calculate p − q (mod 100) and q − p (mod 100) . If p − q (mod 100) > q − p (mod 100) then r = q is our
card and s = p is the spectator’s card. (The case p − q (mod 100) = q − p (mod 100) is impossible since
the sum of these numbers is equal to 100 , and one of them is not greater than 6 · 5 = 30 .)
3) Two remainders (say, a and b ) coincide. Let us choose a card with the remainder d = (a+c)/2 mod 5 .
Then |a − d| = |d − c| mod 5 , so the remainder d is distinguished by (9). Hence we have three different
remainders, one of them distinguished by (9) and one of the non-distinguished remainders presented in
two copies. The first magician will easily determine our card, and the rule to choose the card in order to
enable him also determine the order of spectators is similar to the one in the 1-st case.
Alternative solution. This solution gives a non-constructive proof that the trick is possible. For this,
we need to show there is an injective mapping from the set of ordered triples to the set of unordered
quadruples that additionally respects inclusion.
To prove that the desired mapping exists, let’s consides a bipartite graph such that the set of ordered
triples T and the set of unordered quadruples Q form the two disjoint sets of vertices and there is an
edge between a triple and a quadruple if and only if the triple is a subset of the quadruple.
For each triple t ∈ T , we can add any of the remaining 97 cards to it, and thus we have 97 different
quadruples connected to each triple in the graph. Conversely, for each quadruple q ∈ Q , we can remove
any of the 4 cards from it, and reorder the remaining 3 cards in 3! = 6 different ways, and thus we have
24 different triples connected to each quadruple in the graph.
According to the Hall’s theorem, a bipartite graph G = (T, Q, E) has a perfect matching if and only if
for each subset T 0 ⊆ T the set of neighbours of T 0 , denoted N (T 0 ) , satisfies |N (T 0 )| > |T 0 | .
To prove that this condition holds for our graph, consider any subset T 0 ⊆ T . Because we have 97
quadruples for each triple, and there can be at most 24 copies of each of them in the multiset of neighbours,
97 0
we have |N (T 0 )| > |T | > 4|T 0 | , which is even much more than we need.
24
Thus, the desired mapping is guaranteed to exist.
Another solution. Let the three chosen numbers be (x1 , x2 , x3 ) . At least one of the sets {1, 2, . . . , 24} ,
{25, 26, . . . , 48} , {49, 50, . . . , 72} and {73, 74, . . . , 96} should contain none of x 1 , x2 and x3 , let S be
such set. Next we split S into 6 parts: S = S1 ∪ S2 ∪ . . . ∪ S6 so that 4 first elements of S are in S1 ,
four next in S2 , etc. Now we choose i ∈ {1, 2, . . . , 6} corresponding to the order of numbers x 1 , x2 and
x3 (if x1 < x2 < x3 then i = 1 , if x1 < x3 < x2 then i = 2 , . . . ,if x3 < x2 < x1 then i = 6 ). At last
let j be the number of elements in {x1 , x2 , x3 } that are greater than elements of S (note that any xk ,
k ∈ {1, 2, 3} , is either greater or smaller than all the elements of S ). Now we choose x 4 ∈ Si so that
x1 + x2 + x3 + x4 ≡ j mod 4 and add the card number x4 to those three cards.
Decoding of {a, b, c, d} is straightforward. We first put the numbers into increasing order and then
calculate a+b+c+d mod 4 showing the added card. The added card belongs to some S i ( i ∈ {1, 2, . . . , 6} )
for some S and i shows us the initial ordering of cards.
10. Let N be a positive integer. Two persons play the following game. The first player writes a list of
positive integers not greater than 25, not necessarily different, such that their sum is at least 200. The
second player wins if he can select some of these numbers so that their sum S satisfies the condition
200 − N 6 S 6 200 + N . What is the smallest value of N for which the second player has a winning
strategy?
Answer: N = 11 .
Solution. If N = 11 , then the second player can simply remove numbers from the list, starting with the
smallest number, until the sum of the remaining numbers is less than 212 . If the last number removed
was not 24 or 25 , then the sum of the remaining numbers is at least 212 − 23 = 189 . If the last
number removed was 24 or 25 , then only 24 -s and 25 -s remain, and there must be exactly 8 of them
since their sum must be less than 212 and not less than 212 − 24 = 188 . Hence their sum S satisfies
8 · 24 = 192 6 S 6 8 · 25 = 200 . In any case the second player wins.
On the other hand, if N 6 10 , then the first player can write 25 two times and 23 seven times. Then
the sum of all numbers is 211 , but if at least one number is removed, then the sum of the remaining ones
is at most 188 — so the second player cannot win.
8
11. Let n be a positive integer. Consider n points in the plane such that no three of them are collinear and
no two of the distances between them are equal. One by one, we connect each point to the two points
nearest to it by line segments (if there are already other line segments drawn to this point, we do not
erase these). Prove that there is no point from which line segments will be drawn to more than 11 points.
Solution. Suppose there exists a point A such that A is connected to twelve points. Then there exist
three points B , C and D such that ∠BAC 6 60◦ , ∠BAD 6 60◦ and ∠CAD 6 60◦ .
We can assume that |AD| > |AB| and |AD| > |AC| . By the cosine law we have
since 1 6 2 cos(∠BAD) . Hence |BD| < |AD| . Similarly we get |CD| < |AD| . Hence A and D should
not be connected which is a contradiction.
Comment. It would be interesting to know whether 11 can be achieved or the actual bound is lower.
12. A set S of four distinct points is given in the plane. It is known that for any point X ∈ S the remaining
points can be denoted by Y , Z and W so that
where at least one of the inequalities is strict if all the four points are not on the same line. Hence, adding
the two last inequalities we get
a contradiction.
13. Let ABC be an acute triangle with ∠BAC > ∠BCA , and let D be a point on side AC such that
|AB| = |BD| . Furthermore, let F be a point on the circumcircle of triangle ABC such that line F D
is perpendicular to side BC and points F , B lie on different sides of line AC . Prove that line F B is
perpendicular to side AC .
Solution. Let E be the other point on the circumcircle of triangle ABC such that |AB| = |EB| . Let
D0 be the point of intersection of side AC and the line perpendicular to side BC , passing through E .
Then ∠ECB = ∠BCA and the triangle ECD 0 is isosceles. As ED 0 ⊥ BC , the triangle BED 0 is also
isosceles and |BE| = |BD 0 | implying D = D 0 . Hence, the points E , D , F lie on one line. We now have
9
The required result now follows.
PSfrag replacements E
A D C
14. Let L , M and N be points on sides AC , AB and BC of triangle ABC , respectively, such that BL
is the bisector of angle ABC and segments AN , BL and CM have a common point. Prove that if
∠ALB = ∠M N B then ∠LN M = 90◦ .
Solution. Let P be the intersection point of lines M N and AC . Then ∠P LB = ∠P N B and the
quadrangle P LN B is cyclic. Let ω be its circumcircle. It is sufficient to prove that P L is a diameter
of ω .
Let Q denote the second intersection point of the line AB and ω . Then ∠P QB = ∠P LB and
|P Q| |BL|
= . (12)
|P A| |BA|
We see that the line P L is a bisector of the inscribed angle N P Q . Now in order to prove that P L is
a diameter of ω it is sufficient to check that |P N | = |P Q| .
|P N | |BL|
= . (13)
|P C| |BC|
|AB| |AL|
= . (14)
|BC| |CL|
|P N | |AL| |CP |
= · .
|P Q| |AP | |CL|
We want to prove that the left hand side of this equality equals 1. This follows from the fact that the
quadruple of points (P, A, L, C) is harmonic, as can be proven using standard methods (e.g. considering
the quadrilateral M BN S , where S = M C ∩ AN ).
10
PSfrag replacements
A
B B
C N
D M
E
F
C P
L A
Q
15. A spider and a fly are sitting on a cube. The fly wants to maximize the shortest path to the spider
along the surface of the cube. Is it necessarily best for the fly to be at the point opposite to the spider?
(“Opposite” means “symmetric with respect to the center of the cube”.)
Answer: no.
Solution. Suppose that the side of the cube is 1 and the spider sits at the middle of one of the edges.
Then the shortest path to the middle of the opposite edge has length 2 . However, if the fly goes to a
point on this edge at distance s from the middle, then the length of the shortest path is
s
µ ¶2
p 9 3
min 4 + s2 , + −s .
4 2
√
If 0 < s < (3 − 7)/2 then this expression is greater than 2 .
16. Find all nonnegative integers m such that
¡ ¢2
am = 22m+1 + 1
is divisible by at most two different primes.
Answer: m = 0, 1, 2 are the only solutions.
Solution. Obviously m = 0, 1, 2 are solutions as a0 = 5 , a1 = 65 = 5 · 13 , and a2 = 1025 = 25 · 41 . We
show that these are the only solutions.
Assume that m > 3 and that am contains at most two different prime factors. Clearly, am = 42m+1 + 1
is divisible by 5 , and
¡ ¢ ¡ ¢
am = 22m+1 + 2m+1 + 1 · 22m+1 − 2m+1 + 1 .
The two above factors are relatively prime as they are both odd and their difference is a power of 2 .
Since both factors are larger than 1 , one of them must be a power of 5 . Hence,
2m+1 · (2m ± 1) = 5t − 1 = (5 − 1) · (1 + 5 + · · · + 5t−1 )
for some positive integer t , where ± reads as either plus or minus. For odd t the right hand side is not
divisible by 8 , contradicting m > 3 . Therefore, t must be even and
Clearly, 5t/2 + 1 ≡ 2 ( mod 4) . Consequently, 5t/2 − 1 = 2m · k for some odd k , and 5t/2 + 1 = 2m · k + 2
divides 2(2m ± 1) , i.e.
2m−1 · k + 1 | 2m ± 1 .
This implies k = 1 , finally leading to a contradiction since
2m−1 + 1 < 2m ± 1 < 2(2m−1 + 1)
for m > 3 .
11
17. Show that the sequence
µ ¶ µ ¶ µ ¶
2002 2003 2004
, , ,... ,
2002 2002 2002
considered modulo 2002, is periodic.
Solution. Define
µ ¶
n
xkn =
k
and note that
µ ¶ µ ¶ µ ¶
n+1 n n
xkn+1 − xkn = − = = xnk−1 .
k k k−1
Let m be any positive integer. We will prove by induction on k that the sequence {x kn }∞n=k is periodic
modulo m . For k = 1 it is obvious that xkn = n is periodic modulo m with period m . Therefore it
will suffice to show that the following is true: the sequence {xn } is periodic modulo m if its difference
sequence, dn = xn+1 − xn , is periodic modulo m .
Furthermore, if t then the period of {xn } is equal to ht where h is the smallest positive integer such
that h(xt − x0 ) ≡ 0 modulo m .
Indeed, let t be the period of {dn } and h be the smallest positive integer such that h(xt − x0 ) ≡ 0
modulo m . Then
n+ht−1
X n−1
X t−1
X
xn+ht = x0 + dj = x 0 + dj + h dj =
j=0 j=0 j=0
= xn + h(xt − x0 ) ≡ xn (mod m)
for all n , so the sequence {xn } is in fact periodic modulo m (with a period dividing ht ).
18. Find all integers n > 1 such that any prime divisor of n6 − 1 is a divisor of (n3 − 1)(n2 − 1) .
Solution. Clearly n = 2 is such an integer. We will show that there are no others.
Consider the equality
n6 − 1 = (n2 − n + 1)(n + 1)(n3 − 1) .
The integer n2 − n + 1 = n(n − 1) + 1 clearly has an odd divisor p . Then p | n3 + 1 . Therefore, p does
not divide n3 − 1 and consequently p | n2 − 1 . This implies that p divides (n3 + 1) + (n2 − 1) = n2 (n + 1) .
As p does not divide n , we obtain p | n + 1 . Also, p | (n2 − 1) − (n2 − n + 1) = n − 2 . From p | n + 1
and p | n − 2 it follows that p = 3 , so n2 − n + 1 = 3r for some positive integer r .
The discriminant of the quadratic n2 − n + (1 − 3r ) must be a square of an integer, hence
must be a squareof an integer. Since for r > 2 the number 4 · 3r−1 − 1 is not divisible by 3 , this is
possible only if r = 1 . So n2 − n − 2 = 0 and n = 2 .
19. Let n be a positive integer. Prove that the equation
1 1
x+y+ + = 3n
x y
does not have solutions in positive rational numbers.
p r
Solution. Suppose x = and y = satisfy the given equation, where p, q, r, s are positive integers
q s
and gcd(p, q) = 1 , gcd(r, s) = 1 . We have
p r q s
+ + + = 3n ,
q s p r
12
or
20. Does there exist an infinite non-constant arithmetic progression, each term of which is of the form a b ,
where a and b are positive integers with b > 2 ?
Answer: no.
Solution. For an arithmetic progression a1 , a2 , . . . with difference d the following holds:
1 1 1 1 1 1
Sn = + + ... + = + + ... + >
a1 a2 an+1 a1 a1 + d a1 + nd
µ ¶
1 1 1 1
> + + ... + ,
m 1 2 n+1
a contradiction.
Alternative solution. Let ak = a0 + dk , k = 0, 1, . . . . Choose a prime number p > d and set
k 0 ≡ (p − a0 )d−1 mod p2 . Then ak0 = a0 + k 0 d ≡ p mod p2 and hence, ak0 can not be a power of
a natural number.
√ √
Another solution. There can be at most b nc squares in the set {1, 2, . . . , n} , at most b 3 nc cubes in
the same set, etc. The greatest power that can occur in the set {1, 2, . . . , n} is blog 2 nc and thus there
are no more than
√ √ √
b nc + b 3 nc + . . . + b blog2 nc nc
powers among the numbers 1, 2, . . . , n . Now we can estimate this sum above:
√ √ √ √
b nc + b 3 nc + . . . + b blog2 nc nc 6 b nc(blog2 nc − 1) <
√
< b nc · blog2 nc = o(n).
This means that every arithmetic progression grows faster than the share of powers.
13
Baltic Way 2003
Problems and Solutions
1. Let Q+ be the set of positive rational numbers.
Find all functions f : Q+ → Q+ which for all x ∈ Q+ fulfil
(1) : f ( x1 ) = f (x)
(2) : (1 + x1 )f (x) = f (x + 1)
Solution: Set g(x) = ff (x)(1)
. Function g fulfils (1), (2) and g(1) = 1.
First we prove that if g exists then it is unique. We prove that g is uniquely
defined on x = pq by induction on max(p, q). If max(p, q) = 1 then x = 1
and g(1) = 1. If p = q then x = 1 and g(x) is unique. If p 6= q then we
can assume (according to (1)) that p > q. From (2) we get g( pq ) = (1 +
q
p−q
)g( p−q
q
). The induction assumption and max(p, q) > max(p q, q) ≥ 1
now give that g( pq ) is unique.
Define the function g by g( pq ) = pq where p and q are choosen such that
gcd(p, q) = 1. It is easily seen that g fulfils (1), (2) and g(1) = 1. All
functions fulfilling (1) and (2) are therefore f ( pq ) = apq, where gcd(p, q) = 1
and a ∈ Q+ .
x3 + px + q = 0
3. Let x, y and z be positive real numbers such that xyz = 1. Prove that
r r r
y z x
(1 + x)(1 + y)(1 + z) ≥ 2 1 + 3 + 3 + 3 .
x y z
Solution: Put a = bx, b = cy and c = az. The given inequality then takes
1
the form
r r r !
a b c 2 2 2
3 b 3 c 3 a
1+ 1+ 1+ ≥ 2 1+ + + =
b c a ac ab bc
a+b+c
= 2 1+ √ .
3 3 abc
qed.
Alternative solution: Expanding the left side we obtain
r r r
1 1 1 y z x
x+y+z+ + + ≥2 3
+ 3 + 3 .
x y z x y z
p
As 3 xy ≤ 13 y + x1 + 1 etc, it suffices to prove that
1 1 1 2 1 1 1
x+y+z+ + + ≥ x+y+z+ + + +2,
x y z 3 x y z
1
which follows from a + a
≥ 2.
2
which is equivalent to 0 ≤ (a b)2 + (a c)2 . Hence we have proved that
2a 1 2a b c
≤ + + .
a2 + bc 4 bc ca ab
Analogously we have
2b 1 2b c a
≤ + + ,
b2 + ca 4 ca ab bc
2c 1 2c a b
≤ + +
c2 + ab 4 ab bc ca
and it suffices to sum the above three inequalities.
√
Alternative solution: As a2 + bc ≥ 2a bc etc, it is sufficient to prove
that
1 1 1 a b c
√ +√ +√ ≤ + + ,
bc ac ab bc ca ab
1 1 1
which can be obtained “inserting” a
+ b
+ c
between the left side and the
right side.
√
5. A sequence (an ) is defined as follows: a1 = 2, a2 = 2, and an+1 = an a2n−1
for n ≥ 2. Prove that for every n ≥ 1 we have
√
(1 + a1 )(1 + a2 ) . . . (1 + an ) < (2 + 2)a1 a2 . . . an .
n−2
Solution: First we prove inductively that for n ≥ 1 an = 22 . We have
0
a1 = 22 , a2 = 22 and
−1
3
6. Let n ≥ 2 and d ≥ 1 be integers with d | n, and let x1 , x2 , . . . , xn be
real numbers
such that x1 + x2 + + xn = 0. Prove that there are at
n−1
least d−1 choices of d indices 1 ≤ i1 < i2 < < id ≤ n such that
xi1 + xi2 + + xid ≥ 0.
Solution: Put m := n/d and [n] := {1, 2, . . . , n}, and consider all parti-
tions [n] = A1 ∪A2 ∪ ∪Am of [n] into d-element subsets Ai , i = 1, 2, . . . , m.
The number of such partitions is denoted by t. Clearly, there are exactly
n
d
d-element subsets of [n] each of which occurs in the same number of par-
titions. Hence, every A [n] with |A| = d occurs in exactly s := tm/ nd
partitions. On the otherPhand, every partition contains at least one d-
element set A such that i∈A xi ≥ 0. Consequently,
the n−1
total
number of
n d n
sets with this property is at least t/s = d /m = n d = d−1 .
200 x1 , (200 x 1 ) x1
200 x2 , (200 x 2 ) x2
..
.
200 xk , (200 x k ) xk
Clearly x1 < x2 < < xk < 100 < 200 xk < 200 xk−1 < < 200
x2 < 200 x1 < 200 < (200 x1 )x1 < (200 x2 )x2 < < (200 xk )xk .
So all numbers in these pairs are different and greater than 100. So at most
one from each pair is in the set X. Therefore, there are at least k numbers
greater than 100 and 99 k numbers less than 100 that are not in the set
X, together at least 99 numbers out of 10000 not being in the set X.
8. There are 2003 pieces of candy on a table. Two players alternately make
moves. A move consists of eating one candy or half of the candies on the
table (the “lesser half” if there is an odd number of candies); at least one
candy must be eaten at each move. The loser is the one who eats the last
candy. Which player – the first or the second – has a winning strategy?
4
Solution: Answer: the second.
Let us prove inductively that for 2n pieces of candy the first has a winning
strategy. For n = 1 it is obvious. Suppose it is true for 2n pieces, and let’s
consider 2n + 2 pieces. If for 2n + 1 pieces the second is the winner, then
the first eats 1 piece and becomes the second in the game starting with
2n + 1 pieces. So suppose that for 2n + 1 pieces the first is the winner. His
winning move for 2n + 1 isn’t eating 1 piece (accordingly to the inductive
assumption). So his winning move is to eat n pieces, leaving the second
with n + 1 pieces, when the second must lose. But the first can leave the
second with n+1 pieces from the starting position with 2n+2 pieces, eating
n + 1 pieces; so 2n + 2 is the winning position for the first.
Now if there are 2003 pieces of candy on the table, the first must eat either
1 or 1001 candies, leaving an even number of candies on the table. So the
second player will be the first player in a game with even number of candies
and therefore has a winning strategy.
5
10. A lattice point in the plane is a point whose coordinates are both in-
tegral. The centroid of four points (xi , yi ), i = 1, 2, 3, 4, is the point
3 +x4 y1 +y2 +y3 +y4
( x1 +x2 +x
4
, 4
). Let n be the largest natural number with the
following property: There are n distinct lattice points in the plane such
that the centroid of any four of them is not a lattice point. Prove that
n = 12.
Solution: To prove n ≤ 12, we have to show that there are 12 lattice
points (xi , yi ), i = 1, 2, , . . . , 12, such that no four determine a lattice point
centroid. This is guaranteed if we just choose the points such that xi
0 (mod 4) for i = 1, . . . , 6, xi 1 (mod 4) for i = 7, . . . , 12, yi 0 (mod 4)
for i = 1, 2, 3, 10, 11, 12, yi 1 (mod 4) for i = 4, . . . , 9.
Now let Pi , i = 1, 2, . . . , 13, be lattice points. We have to show that some
four of them determine a lattice point centroid. First observe that, by
the pigeonhole principle, among any five of the points we find two such
that their x-coordinates as well as their y-coordinates have the same parity.
Consequently, among any five of the points there are two whose midpoint is
a lattice point. Iterated application of this observation implies that among
the 13 points in question we find five disjoint pairs of points whose midpoint
is a lattice point. Among these five midpoints we again find two, say M and
M 0 , such that their midpoint C is a lattice point. Finally, if M and M 0 are
the midpoints of Pi Pj and Pk P` , respectively, {i, j, k, `} {1, 2, . . . , 13},
then C is the centroid of Pi , Pj , Pk , P` .
11. Is it possible to select 1000 points in a plane so that at least 6000 distances
between two of them are equal?
Solution: Yes, it is. Let’s start with configuration of 4 points and 5
distances equal to d, like on picture (α):
(α)
Now take (α) and two copies of it obtainable from (α) by parallel shifts
→ → →
along vectors →a and b , |→ a | = | b | = d and ∠(→a , b ) = 60◦ . Vectors →
a
→
and b should be chosen so that no two vertices of (α) and of two copies
coincide. We get 3 4 = 12 points and 3 5 + 12 = 27 distances.
Proceeding in the same way, we get gradually
3 12 = 36 points and 3 27 + 36 = 117 distances;
3 36 = 108 points and 3 117 + 108 = 459 distances;
3 108 = 324 points and 3 459 + 324 = 1701 distances;
3 324 = 972 points and 3 1701 + 972 = 6075 distances.
6
inner point on side CD with ∠M AN = 45◦ . Prove that the circumcenter
of AM N lies on AC.
Solution: Draw a circle ω through M , C, N ; let it intersect AC at O. We
claim that O is the circumsenter of AM N .
Clearly ∠M ON = 180√ ◦
∠M CN = 90◦ . If√the radius of ω is R, then
OM = 2R sin 45◦ = R 2; similarly ON = √ R 2. Therefore OM = ON .
Draw a circle with center O and a radius R 2. As ∠M AN = 21 ∠M ON ,
this circle will pass through A.
B M C
ω
O N
A D
F
G
A P D
7
now the quadrangles AM BN and CM BN we get OE = OF (from Eiler’s
formula a2 +b2 +c2 +d2 = e2 +f 2 +4P Q2 or otherwise). As EF kAC we get
from this that a perpendicular trough O passes through the circumcenter
of EF G, as it is the perpendicular bisector of EF . The same holds for two
other perpendiculars.
B
O N
M
E F
A
G
C
A
D
Q
T
S R
C
B
8
DP BP = AP CP (due to well-known theorem).
16. Find all pairs of positive integers (a, b) such that a b is a prime and ab is
a perfect square.
Solution: Let p be a prime such that a b = p and let ab = k 2 . Insert
a = b + p in the equation ab = k 2 and then do the following:
p p2
(b + p)b = k 2 ⇔ (b + )2 = k 2 ⇔ (2b + p)2 4k 2 = p2 ⇔
2 4
⇔ (2b + p + 2k)(2b + p 2k) = p2 .
17. All the positive divisors of a positive integer n are stored into an array
in increasing order. Mary has to write a program which decides for an
arbitrarily chosen divisor d > 1 whether it is a prime. Let n have k divisors
not greater than d. Mary claims that it suffices to check divisibility of d by
the first dk/2e divisors of n: if a divisor of d greater than 1 is found among
them, then d is composite, otherwise d is prime. Is Mary right?
Solution: Yes, Mary is right.
Let d > 1 be a divisor of n.
Suppose Mary’s program outputs “composite” for d. That means it has
found a divisor of d greater than 1. Since d > 1, the array contains at least
2 divisors of d: 1 and d. Thus Mary’s program does not check divisibility of
9
d by d (the first half gets complete before reaching d) which means that the
divisor found lays strictly between 1 and d. Hence d is composite indeed.
Suppose now d being composite. Let p be its smallest prime divisor; then
d
p
≥ p or, equivalently, d ≥ p2 . As p is a divisor of n, it occurs in the array.
Let a1 , . . . , ak all divisors of n smaller than p. Then pa1 , . . . , pak are less
than p2 and hence less than d. As a1 , . . . , ak are all relatively prime with p,
all the numbers pa1 , . . . , pak divide n. The numbers a1 , . . . , ak , pa1 , . . . , pak
are pairwise different by construction. Thus there are at least 2k+1 divisors
of n not greater than d. So Mary’s program checks divisibility of d by at
least k + 1 smallest divisors of n, among which it finds p, and outputs
“composite”.
18. Every integer is colored with exactly one of the colors blue, green, red,
yellow. Can this be done in such a way that if a, b, c, d are not all 0 and
have the same color, then 3a 2b 6= 2c 3d?
Solution: The answer is yes. A coloring with the required property can be
defined as follows. For an integer k let k ∗ be the integer uniquely defined
by k = 5m k ∗ , where m is a nonnegative integer and 5 6 |k ∗ . Two integers
k1 , k2 receive the same color if and only if k1∗ k2∗ (mod 5).
Assume that 3a 2b = 2c 3d, i.e. 3a 2b 2c + 3d = 0. Dividing both
sides by the largest power of 5 which simultaneously divides a, b, c, d, we
obtain
3 5 A a∗ 2 5 B b∗ 2 5C c∗ + 3 5D d∗ = 0,
5A + 5 B + 5 C + 5 D 0 (mod 5)
10
hence 3ab must be divisible by p and q. But p 6= 3, so p|a or p|b; but p|a + b,
so p|a and p|b: a = pk, b = p` for some integers k, `. Notice that q = 3,
since otherwise, repeating the above argument, we would have q|a, q|b and
a + b > pq). So we have
3p = a + b = p(k + `)
20. Let n be a positive integer such that the sum of all positive divisors of
n (except n) plus the number of these divisors is equal to n. Prove that
n = 2m2 for some integer m.
Solution: Let t1 , t2 , . . . , ts be all potitive odd divisors of n, 2k be the
maximal power of 2 that divides n. Then the full list of divisors of n is the
following:
t1 , . . . , ts , 2t1 , . . . , 2ts , . . . 2k t1 , . . . , 2k ts .
Hence,
The right hand side can be even only if both k and s are odd. In this case
the number n/2k has odd number of divisors and therefore it is equal to a
perfect square.
11
Mathematical Competition Baltic Way 2004
Vilnius University, Faculty of Mathematics and Informatics, 2004 11 07
Problems with Solutions
1. an + a2n ≥ 3n,
p
2. an+1 + n ≤ 2 an · (n + 1)
Solution:
which implies an ≥ n.
(b) The sequence an = n + 1 satisfies all the conditions of the problem.
2 (LAT) Let P (x) be a polynomial with non-negative coefficients. Prove that if P ( x1 )P (x) ≥
1 for x = 1 then the same inequality holds for each positive x.
Solution: For x > 0 we have P (x) > 0. From the given condition we have (P (1))2 ≥ 1.
Further, let’s denote P (x) = a0 xn + a1 xn−1 + · · · + an , then
1 n n−1 1 n 1 n−1
P (x)P = (a0 x + a1 x + · · · + an ) a0 + a1 + · · · + an ≥
x x x
(using the Couchy-Schwarz-Bunyakowski inequality)
2
a0 √ n
r r
a1 p n−1 √ √
≥ a0 x + a1 x + · · · + an an ≥
xn xn−1
≥ (a0 + a1 + · · · + an )2 = (P (1))2 ≥ 1.
3 (NOR) Let p, q, r be positive real numbers and n ∈ N. Show that if pqr = 1, then
1 1 1
+ n + n ≤ 1.
pn + q + 1 q + r + 1 r + pn + 1
n n
Solution: The key idea is to deal with the case n = 3. Put a = pn/3 , b = q n/3 , and
c = rn/3 , therefore abc = (pqr)n/3 = 1 and
1 1 1
+ n + n =
pn
+ q + 1 p + r + 1 r + pn + 1
n n
1 1 1
= 3 + 3 + 3 .
a + b + 1 b + c + 1 c + a3 + 1
3 3
Now
1 1
= =
a3 3
+b +1 (a + b)(a − ab + b2 ) + 1
2
1 1
= 2
≤ .
(a + b)((a − b) + ab) + 1 (a + b)ab + 1
Since ab = c−1 ,
1 1 c
≤ = .
a3 3
+b +1 (a + b)ab + 1 a+b+c
Similarly we obtain
1 a 1 b
≤ and ≤ .
b3 3
+c +1 a+b+c c3 3
+a +1 a+b+c
Hence
1 1 1
+ 3 + 3 ≤
3 a3
+ b + 1 b + c + 1 c + a3 + 1
3
c a b
≤ + + =1
a+b+c a+b+c a+b+c
And we are at home.
4 (LAT) Let x1 , x2 , . . . , xn be real numbers with arithmetic mean X. Prove that there is
a positive integer K such that the arithmetic mean of each of the lists {x1 , x2 , . . . , xK },
{x2 , x3 , . . . , xK }, {x3 , . . . , xK }, . . . , {xK−1 , xK }, {xK } is not greater than X.
Solution: Consider n bottles, each of volume 1 liter. Suppose they are filled with spirits
of concentrations x1 , x2 , . . . , xn (the measurement with spirits can be correspondingly
chosen). The arithmetic mean of any set of xi − s is a concentration of corresponding
mixture.
|x1 | |x2 | |x3 | |xn |
··· .
B1 B2 B3 Bn
Suppose the contrary to what must be proved. It means: for each bottle BK such a bottle
Bl , l ≤ K, can be found that the concentration of a mixture of bottles Bl , Bl+1 , . . . , BK
exceeds X.
Find such a Bl1 for Bn ; Bl2 for Bl1 −1 ; . . . ; Blm ≡ B1 for Blm −1 . Consider the "segments"
B1 . . . Blm−1 −1 Blm−1 . . . Blm−2 −1 . . . Bl1 . . . Bn .
In each of the segments the concentration of a mixture is greater than X; therefore the
concentration of a mixture from all bottles is greater than X; a contradiction.
5 (DEN) Determine the range of the following function defined for integer k,
f (k) = (k)3 + (2k)5 + (3k)7 − 6k ,
where (k)2n+1 denotes the multiple of 2n + 1 closest to k.
Solution: For odd n we have
n−1 n−1
(k)n = k + − k+ mod n ,
2 2
where m mod n denotes the principal remainder. Hence we get
f (k) = 6 − (k + 1) mod 3 − (2k + 2) mod 5 − (3k + 3) mod 7 ,
The condition that the principal remainders take the values a, b and c, respectively, may
be written
k + 1 ≡ a mod 3 , 2k + 2 ≡ b mod 5 , 3k + 3 ≡ c mod 7 ,
or
k ≡ a − 1 mod 3 , k ≡ −2b − 1 mod 5 , k ≡ −2c − 1 mod 7 .
By the Chinese Remainder Theorem, these congruences have a solution for any set of
a, b and c. Hence f (k) takes all the integer values between 6 − 2 − 4 − 6 = −6 and
6 − 0 − 0 − 0 = 6.
6 (SWE) A positive integer is written on each of the six faces of a cube. For each vertex of
the cube we compute the product of the numbers on the three adjacent faces. The sum of
these products is 1001. What is the sum of the six numbers on the faces?
Solution: Let the numbers on the faces be a1 , a2 , b1 , b2 , c1 , c2 , placed in such a way that
a1 and a2 are on opposite faces etc. Then the sum of the eight products is equal to (a1 +
a2 )(b1 + b2 )(c1 + c2 ) = 1001 = 7 · 11 · 13. Hence the sum of the numbers on the faces is
a1 + a2 + b1 + b2 + c1 + c2 = 7 + 11 + 13 = 31.
7 (EST) Find all sets X consisting of at least two positive integers such that for every pair
m, n ∈ X, where n > m, there exists k ∈ X such that n = mk 2 .
Solution: Answer: All the sets {m, m3 }, where m > 1.
Let X be a set satisfying the condition of the problem and let m and n, where n > m, be
the two smallest elements in the set X. There has to exist a k ∈ X so that n = mk 2 , but
as m ≤ k ≤ n, either k = n or k = m. The first case gives m = n = 1, a contradiction;
the second case implies n = m3 with m > 1.
Suppose there exists the third smallest element q ∈ X. Then there also exists k0 ∈ X,
such that q = mk02 . We have q > k0 ≥ m, but k0 = m would imply q = n, thus k0 = n =
m3 and q = m7 . Now for n and q there has to exist k1 ∈ X such that q = nk12 , which gives
k1 = m2 . Since m2 ∈ / X, we have a contradiction.
Thus we see that the only elements that the set X can contain, are m and m3 for some
m > 1. One can easily verify that all such sets X = {m, m3 } satisfy the conditions of the
problem.
8 (NOR) Let f (x) be a non-constant polynomial with integer coefficients. Prove that there
is an integer n such that f (n) has at least 2004 distinct prime factors.
Solution: Suppose the contrary. Choose an integer n0 so that f (n0 ) has the highest num-
ber of prime factors. By translating the polynomial we may assume
n0 = 0. Setting k = f (0), we have f (wk 2 ) ≡ k mod k 2 , or f (wk 2 ) = ak 2 +k = (ak +1)k.
Since gcd(ak + 1, k) = 1 and k alone achieves the highest number of prime factors of f ,
we must have ak + 1 = ±1. This cannot happen for every w since f is non-constant, so
we have a contradiction.
Alternative solution: Let S = {p|p is prime and divides f (n) for some n ∈ Z}. If |S| ≥
2004, choose primes p1 , p2 , ..., p2004 and integers a1 , a2 , ..., a2004 so that f (ai ) ≡ 0 mod pi .
By the Chinese Remainder Theorem, there is an x so that x ≡ ai mod pi for all i. This x
satisfies p1 , p2 , ..., p2004 |f (x). Otherwise,
Qr if |S| < 2004, let A = {m|(p|m ⇒ p ∈ S)}∪{0}.
ei
m ∈ A can be written m = ± i=1 pi with r = |S| < 2004, 0 ≤ ei ≤ logpi m ≤ log2 m ⇒
|A∩[−N, N ]| ≤ 2(log N √ +1)2003 +1. Let d be the degree of f , then there is an c > 0 so that
d
|f (Z) ∩ [−N, N ]| ≥ c N , which grows asymptotically faster than 2(log N + 1)2003 + 1
and thus contradicts the assumption that |S| < 2004.
9 (EST) A set S of n−1 natural numbers is given (n ≥ 3). There exist at least two elements
in this set whose difference is not divisible by n. Prove that it is possible to choose a non-
empty subset of S so that the sum of its elements is divisible by n.
Solution: Suppose to the contrary that there exists a set X = {a1 , a2 , . . . , an−1 } violating
the statement of the problem, and let an−2 6≡ an−1 mod n. Denote Si = a1 + a2 + . . . + ai ,
i = 1, . . . , n − 1. The conditions of the problem imply that all the numbers Si must give
different remainders when divided by n. Indeed, if for some j < k we had Sj ≡ Sk mod n,
then aj+1 +aj+2 +. . .+ak ≡ Sk −Sj ≡ 0 mod n. Consider now the sum S 0 = Sn−3 +an−1 .
We see that S 0 can not be congruent to any of the sums Si (for i 6= n − 2 the above
argument works and for i = n − 2 we use the assumption an−2 6≡ an−1 mod n). Thus we
have n sums that give pairwise different remainders when divided by n, consequently one
of them has to give the remainder 0, a contradiction.
10 (LAT) Is there an infinite sequence of prime numbers p1 , p2 , . . . , pn , pn+1 , . . . such that
|pn+1 − 2pn | = 1 for each n ∈ N?
Solution: Answer. No, there is no such sequence.
Suppose the contrary. Clearly p3 > 3. We have two possibilities:
a) p3 ≡ 1(mod 3). Then obligatory p4 = 2p3 − 1 (otherwise p4 ≡ 0(mod 3), so p4 ≡
1(mod 3). Analogously p5 = 2p4 − 1, p6 = 2p5 − 1 etc. By an easy induction we have
pn+1 − 1 = 2n−2 (p3 − 1), n = 3; 4; 5; . . . .
If we set n = p3 + 1 we have pp3 +2 − 1 = 2p3 −1 (p3 − 1), from which
pp3 +2 ≡ 1 + 1 · (p3 − 1) = p3 ≡ 0
mod p3 mod p3
– a contradiction.
b) p3 ≡ 2(mod 3) is treated analogously.
12 (LAT) There are 2n different numbers in a row. By one move we can interchange any two
numbers or interchange any 3 numbers cyclically (choose a, b, c and place a instead of b,
b instead of c, and c instead of a). What is the minimal number of moves that is always
sufficient to arrange the numbers in increasing order?
Solution: If number y occupies the place where x should be at the end, we draw an arrow
x → y. Clearly at the beginning all numbers are arranged in several cycles: (a loop),
•
y
• • (binary cycle),
y
•
% &
• •
...
-
.
•
(at least 3 numbers; "long"cycle). Our aim is to obtain 2n loops.
Clearly each binary cycle can be rearranged into 2 loops by one move. If there is a long
cycle with a fragment . . . • −→ • −→ • . . . , interchange a, b, c cyclically; at least 2 loops
a b c
• •
a and b appear. Go on if necessary. By each move the number of loops increase by 2,
so at most n moves are needed.
Comment. The problem can be made considerably more difficult by asking for minimal
number of moves that is always enough. By examining all possible cases how the inter-
changed numbers can be distributed among disjoint cycles we easily see that the number
of disjoint cycles increases by at most 2 per one move. So, if there is one cycle at the
beginning, we can not get 2n loops in less than n moves.
13 (FIN) The 25 member states of the European Union set up a committee with the follow-
ing rules: 1) the committee should meet daily; 2) at each meeting, at least one member
state should be represented; 3) at any two different meetings, a different set of member
states should be represented; and 4) at the nth meeting, for every k < n, the set of states
represented should include at least one state that was represented at the k th meeting. For
how many days can the committee have its meetings?
Solution: If one member is always represented, rules 2 and 4 will be fulfilled. There are
224 different subsets of the remaining 24 members. So there can be at least 224 meetings.
Rule 3 forbids complimentary sets in two different meetings. So the maximal number of
meetings cannot exceed 12 · 225 . So the maximal number of meetings for the commission
is exactly 224 = 16777216.
14 (SPB) We say that a pile is a set of four or more nuts. Two persons play the following
game. They start with one pile of n ≥ 4 nuts. During a move a player takes one of the
piles that they have and split it into two nonempty sets (these sets are not necessarily
piles, they can contain arbitrary number of nuts). If the player cannot move, he loses. For
which values of n does the first player have a winning strategy?
Solution: Answer: First player wins.
More over, if the pile in the beginning of the game contains 4k, 4k + 1, 4k + 2 nuts, then
the first player wins, and if the pile contains 4k + 3 (k ≥ 1) nuts, then the second player
wins.
The set of 1, 2 or 3 piles we will call a degenerate pile.
We will prove the answer by induction on k together with the useful fact that in the
position consisting of two piles of 4t + 1 and 4s + 1 nuts (where s + t ≤ k; s, t ≥ 1) the
second player wins. We omit here the base of induction.
So let us prove the step of induction. Assume that we know the answer for piles with at
most 4k − 1 nuts and the useful fact for s + t ≤ k nuts, and prove the answer for piles
with 4k, 4k + 1, 4k + 2, 4k + 3 nuts and the useful fact for s + t ≤ k + 1 nuts.
1. If the pile contains 4k, 4k + 1 or 4k + 2 nuts, then the first player wins: he “cuts off” 1,
2 or 3 nuts, obtain a pile of 4k − 1 nuts and therefore wins by induction hypothesis.
2. Let the pile contain 4k + 3 nuts. The first player can split it in two different ways:
(4` + 1; 4m + 2) or (4`; 4m + 3). In the first case the second player wins directly if one
of the piles is degenerate (i.e. contains at most 3 nuts) due to the previous paragraph.
Otherwise, he removes one nut from the second pile and wins due to the useful fact. In
the second case he removes one nut from the first pile and wins because in the position
(4` − 1, 4m + 3) he can use in both piles the winning strategy of the second player. (The
case of degenerate piles here is trivial.)
3. Now prove that in the position (4t + 1; 4s + 1) where s + t = k + 1, the second
player wins. Due to the symmetry we can think that the first player splits the second
pile. As in the previous paragraph we have two possible moves: (4t + 1; 4u; 4v + 1) and
(4t + 1; 4u + 2; 4v + 3).
3a) Consider a case (4t + 1; 4u; 4v + 1). If u = 1, the second player moves 4u = 4 → (2; 2)
and wins by the useful fact because actually he has obtained a position (4t + 1; 4v + 1).
Otherwise he moves 4u → (1; 4u−1) and wins because he has winning strategies in both
positions (4t + 1; 4v + 1) and 4u − 1.
3b) Consider a case (4t + 1; 4u + 2; 4v + 3). If u = 0, the second player moves 4v +
3 → (2; 4v + 1) and wins by the useful fact because actually he has obtained a position
(4t + 1; 4v + 1). Otherwise he moves 4u + 2 → (1; 4u + 1) and wins because he has
winning strategies in both positions (4t + 1; 4u + 1) and 4v + 3.
15 (SWE) A circle is divided into 13 segments, numbered consecutively from 1 to 13. Five
fleas called A, B, C, D and E are sitting in the segments 1, 2, 3, 4 and 5. A flea is allowed
to jump to an empty segment five positions away in either direction around the circle.
Only one flea jumps at the same time, and two fleas cannot be in the same segment. After
some jumps, the fleas are back in the segments 1,2,3,4,5, but possibly in some other order
than they started. Which orders are possible?
Solution: Write the numbers from 1 to 13 in the order 1, 6, 11, 3, 8, 13, 5, 10, 2, 7, 12,
4, 9. Then each time a flea jumps it moves between two adjacent numbers or between the
first and the last in this row. Since a flea can never move past another flea, the possible
permutations are
1 3 5 2 4
A C E B D
D A C E B
B D A C E
E B D A C
C E B D A
or equivalently
1 2 3 4 5
A B C D E
D E A B C
B C D E A
E A B C D
C D E A B
16 (DEN) Through a point P exterior to a given circle pass a secant and a tangent to the
circle. The secant intersects the circle at A and B, and the tangent touches the circle at
C on the same side of the diameter through P as A and B. The projection of C on the
diameter is Q. Prove that QC bisects ∠AQB.
Solution: Denoting the center of the circle by O, we have OQ × OP = OA2 = OB 2 .
Hence 4OAQ ∼ 4OP A and 4OBQ ∼ 4OP B. Since 4AOB is isosceles, we have
∠OAP + ∠OBP = 180◦ , and therefore
∠AQP + ∠BQP = ∠AOP + ∠OAQ + ∠BOP + ∠OBQ
= ∠AOP + ∠OP A + ∠BOP + ∠OP B
= 180◦ − ∠OAP + 180◦ − ∠OBP = 180◦ .
Thus QC, being perpendicular to QP , bisects ∠AQB.
17 (SWE) Consider a rectangle with side lengths 3 and 4, and pick an arbitrary inner point
on each side. Let x, y, z and u denote the side lengths of the quadrilateral spanned by
these points. Prove that 25 ≤ x2 + y 2 + z 2 + u2 ≤ 50.
Solution: Let a, b, c, and d be the distances of the chosen points from the midpoints of
the sides of the rectangle (with a and c on the sides of length 3). Then
2 2 2 2
2 2 2 2 3 3 3 3
x +y +z +u = +a + −a + +c + −c +
2 2 2 2
+ (2 + b)2 + (2 − b)2 + (2 + d)2 + (2 − d)2 =
2
3
=4· + 4 · 22 + 2(a2 + b2 + c2 + d2 ) =
2
= 25 + 2(a2 + b2 + c2 + d2 ).
Since 0 ≤ a2 ≤ (3/2)2 , 0 ≤ c2 ≤ (3/2)2 , 0 ≤ b2 ≤ 22 and 0 ≤ d2 ≤ 22 the desired
inequalities follow.
18 (LAT) A ray emanating from the vertex A of the triangle ABC intersects the side BC at
1 1 4
X and the circumcircle of ABC at Y . Prove that AX + XY ≥ BC .
Solution: From the geometric mean – harmonic mean inequality we have
1 1 2
+ ≥√ . (1)
AX XY AX · XY
As BC and AY are chords intersecting at X we have AX · XY = BX · XC. Therefore
(1) transforms into
1 1 2
+ ≥√ . (2)
AX XY BX · XC
√
After all, BX · XC ≤ BX+XC
2
= BC2
. So from (2) we obtain what is needed.
19 (SPB) D is the midpoint of the side BC of the given triangle ABC. M is a point on the
side BC such that ∠BAM = ∠DAC. L is the second intersection point of the circum-
circle of the triangle CAM with the side AB. K is the second intersection point of the
circumcircle of the triangle BAM with the side AC. Prove that KL k BC.
Solution: It is sufficient to prove that CK : LB = AC : AB.
The triangles ABC and M KC are similar because they have common angle C and ∠CM K =
180◦ − ∠BM K = ∠KAB (the latter equality is due to the observation that ∠BM K and
∠KAB are the opposite angles in the inscribed quadrilateral AKM B).
By the analogous reasons the triangles ABC and M BL are similar. Therefore the trian-
gles M KC and M BL are also similar and we have
AM sin KAM BD sin BDA
CK KM sin AKM sin KAM sin DAB AB AC
= = =
AM sin M AB (2)
= = CD sin CDA
= .
LB BM (1) sin M BA
sin M AB (3) sin DAC (4) AC
AB
(1) is due to sinus theorem for triangles AKM and ABM ; (2) is due to the equality
∠AKM = 180◦ − ∠M BA in the inscribed quadrilateral AKM B; (3) is due to the defini-
tion of the point M ; (4) is due to sinus theorem for triangles ACD and ABD;
20 (LAT) Three circular arcs w1 , w2 , w3 with common endpoints A and B are on the same
side of the line AB; w2 lies between w1 and w3 . Two rays emanating from B intersect
M1 M2
these arcs at M1 , M2 , M3 and K1 , K2 , K3 , respectively. Prove that M 2 M3
=K1 K2
K2 K3
.
Solution:
From inscribed angles we have ∠AK1 B = ∠AM1 B, ∠AK2 B = ∠AM2 B. From this it
follows that 4AK1 K2 ∼ 4AM1 M2 , so
K1 K2 AK2
= . (1)
M1 M2 AM2
Similarly 4AK2 K3 ∼ 4AM2 M3 , so
K2 K3 AK2
= . (2)
M2 M3 AM2
K1 K2 K2 K3
From (1) and (2) we get M1 M2
= M2 M3
, from which desired property follows.
Comment. A Thaler theorem for circles, isn’t it?
1
ak+2 = ak + ak+1 +
1 f~ k ≥ 1.
2 4ak ak+1
® ¢Uy
1 1 1 1
+ + + + < 4.
a1 a3 a2 a4 a3 a5 a98 a100
¯ °9U¦q|m¢¦m¡±²| m¥w
y
P (x) 4¡|³|y²´q|Zr|{Uy f~y²y x
P (x2 + 1) = P (x)2 + 1
µm
@ a, b, c F~¡|g)|y;U¥ |44g abc = 1 ® |¶¢Uy
a b c
+ + ≤ 1.
a 2 + 2 b2 + 2 c 2 + 2
·U
@ K yU¦ N cZgw~||)4g 1 ≤ K ≤ N {¸¹¦Rº» N ¦R¡±²|0m
m|¦U¢
0R¼c¦
||gmemF~ r|y³y9||gUmF~|¦my K |m¥w½y¦myr¦³¥w¶m8|m ¢|e|m yZ|¥¾y!|m
¦mº ® |¶~0|U)mw¦mº4g ~|ºg¿g|¢mg
yN¦R)b)³m¥ )yY~|g~UWmy) ~WU
2 2
4 N /K
À ¸$||yUm
y³y|| U~ n {yr¦Á·Âm¥wU £ 4m| n > 2 ¤ ÁÁW|m|»
{4|gZÁ¡|mlÃ
~{»¸/0gÄ| m³ {¦Rg±²|~8f~¥ÅÄm»°m~~|3½B»|¶ (x , x , x , x , x , x ) U¦
|mF|¶ (x y , x y , x y , x y , x y , x y ) cy )fmU¦,, 1
|m203 4 ® 56¢|U
|m|)
4wm¥w,,4m
ly4Z4Uyg9!mF~|4)Æ|~
(y1 , y2 , y3 , y4 , y5 , y6 ) 1 1 2 2 3 3 4 4 5 5 6 6
ÇU¬B~U¦Rw~
¦³ 25 25 mU¡¢UYÈ|¶É4¡|w|¦,~|mNUyN ÆF,|m0|
¦;
Ê rUF¥em¥cyHm¥ y |~ry|/B)¥r½W¦R¶ªgl¦Rc4y²|mFgm! mF~
¦U§
ËU¸É||mÈ4¦R¦m¦³g 200 3 mmg|Uy| ® ÈUym)m¥ 4y9/ /y9m¡meU||m
~|w||m/yNZÆ 1 2 ¦R
«m
Ãm
@ m = 30030 = 2 3 5 7 11 13 U¦qg M WU¢/HgB~gȦmg
Z~|Y4m
|³UÈÌm~ ¨FU¥w
~|¢W|¥wgUme¥em¥cy9~| n 4gÍ|mf~g¶4m{m| /f¢ |U
n U¥ f|¥
M£
mFÌRZ«em¥ a, b, c ¥wm8|m¥[|
Z m a b c = m
~
@@UY~| D yU¦ E gYFmB¦m BC U¦ AC £ || £ y|mO|
ym~g ABC £ |
Z m BD = AE
Î U)gmϽmmem0m¥c~|/y!|m)|m ADC U¦ BEC ¥w|U)m AC U¦ BC K yU¦
L£
||g ® ¢Uy KC = LC
¶¨R
@ ABCD ¢~ÌU¦R|yyU|U BC = AD
H M yU¦ N /|m¥w
¦R~ y AB yU¦ CD £
| Î mFgm AD U¦ BC ¥w4|mFgm M N P U¦ Q £ | ® |È|U CQ = DP
«m Ê r U0Z¥cyZ4m¥ |g/9|~¦RU √2 |UW¢U¦R¦{|c¶4e|m
³y gÆ §
63
³y gÆ §
53
¯
@¢Ue¥e¦RUÈOU||m ABC ¥eFy M 0
@ D U¦ E e¦Rg±²|~)~g|¢Í|megm BC U|
|U DC = CE = AB £ yr¦ P U¦ Q 8~g|ÈÍme~¥w~ BD U¦ BE £ Z|g £ U|U
2BP = P D
U¦
2BQ = QE
OW|¥wgU ∠P M Q
¶µR
@4UFgm e yU¦ f F|U¦R
U4U¦³~|4~|,mW H O
@ A yU¦ B gF~ e U¦ C U¦ D
f £ UUy¢g@ |m0r~| A £ B £ C £ D yU¦ H y|¦RZU¢
HÈm8gm b yU¦ d r|4U~m
U¦ Z|g £ U¦R
m
y| | AC g0mqm a U¦ c r|)m|m~ A U¦ C |r|g £
B
U¦RD
m
y| BD ³
H yU¦ gy yr¦ U¦ ~|Zy ® e|U U~
|m|m~ H a b X c d Y XY
We shall show that there exists a positive integer N such that an consists of less than k + 1
decimal digits, ∀n ≥ N . Let ai be a positive integer which consists of exactly j + 1 digits,
that is,
10j ≤ ai < 10j+1 .
We need to prove two statements:
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 ≥ 10j > (j + 1) 92005 ≥ ai+1 (j ≥ k),
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 rst
statement). It is obviously possible to construct a strictly decreasing sequence a 0 > a1 >
> aN of positive integers such that aN has less than k + 1 digits (where N is the rst
index having this property). By an easy induction, it follows that none of the numbers in
{aN , aN +1 , . . .} consists of more than k digits. This set contains in nitely many numbers
but none of these numbers exceeds 10k . By the Pigeonhole Principle, two elements of this set
must be equal, and we are done.
1
3. Note that
1 2 2
< ,
ak ak+2 ak ak+1 ak+1 ak+2
because this inequality is equivalent to the inequality
1
ak+2 > ak + ak+1 ,
2
which is evident for the given sequence. Now we have
1 1 1 1 2 2 2 2 2
+ + + + < + + < = 4.
a1 a3 a2 a4 a3 a5 a98 a100 a1 a2 a2 a3 a2 a3 a3 a4 a1 a2
(a) P (x)+P ( x) 6 0 and P (x) P ( x) 6 0. Then (P (x)+P ( x)) as well as (P (x) P ( x))
are both non-constant polynomials and have a nite numbers of roots only, i.e. this case
cannot hold.
(b) P (x) + P ( x) 0. Obviously, P (0) = 0. Consider the in nite 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, i.e. P (x) Q(x) is a polynomial
with in nitely many roots, i.e. P (x) x.
(c) P (x) P ( x) 0. Then
P (x) = x2n + bn 1x
2n 2
+ . . . + b 1 x2 + b0 ,
for some integer n since P (x) is even and it is easy to see that the coe cient of x 2n must
be 1. 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.
Alternative 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 satis ed for P (x) = x,
P (x) = Q(x) and P (x) = Q(Q(x)).
R ≤ 1 is equivalent to
1 1 1 1 1 1 1 1 1
2+ 2+ + 2+ 2+ + 2+ 2+ ≤ 2+ 2+ 2+
b c a c a b a b c
1 1 1 1
and to 4 ≤ ab + ac + bc + abc . By abc = 1 and by the AM-GM inequality
s 2
1 1 1 3 1
+ + ≥3 =3
ab ac bc abc
2
6. 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 nd 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, . . . , (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),
7. 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 zeros; we can assume it is (0, 0, 1, 1, 1, 1). Let nij be the number of rows
with rst two elements i, j. As in the rst case n00 ≥ n11 . Let n01 ≥ n10 ; the other subcase
is analogous. Now there are n00 + n01 zeros in the rst column and n10 + n11 ones in the
rst column; the conclusion follows. Consider now the case when each row contains at least 3
zeros (except (1, 1, 1, 1, 1, 1), if such a row exists). Let’s prove it is impossible that each such
row contains exactly 3 zeroes. Assume the opposite. As n > 2 there are at least 2 rows with
zeros; they are di erent, so their product contains at least 4 zeros, a contradiction. So there
are more then 3(n 1) zeros in the array; so in some column there are more than (n 1)/2
zeros; so there are at least n/2 zeros.
8. Answer: 48 squares.
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 de ned 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 2 of these segments.
9. Let us denote the number of ways to split some gure onto dominos by a small picture of this
gure with a sign #. For example, # = 2.
Let Nn =# (n rows);
n =# (n 2 full rows and 1 row with 2 cells). We are going
to nd a recurrent relation for the numbers Nn .
3
Observe that
# = # + # + # = 2# + # ,
# = # +# =# +# .
Nn = 2
n + Nn 2 ,
2
n 2 = Nn 2 Nn , 4
2
n = 2
n 2 + 2Nn 2.
Nn = 4Nn 2 Nn 4 .
{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, then there is a group from which we take all three numbers, i.e. their product
equals m.
11. 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 circumcenters of triangles ADC and BEC is perpendicular to the line CP , it su ces to
show that CP is the angle-bisector of ∠ACB.
E L
D
K
A B
P
4
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 AP E
and DP B 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.
D0
D
N C
0
C
Y A0
A M B
X
B0
∠C 0 CQ = ∠B 0 BQ = ∠A0 AP = ∠D 0 DP .
5/2
Partition the rectangle into 3 rectangles of size 5/3 2 and two rectangles of size√5/2 1 as
shown above. It is easy to check that each has a diagonal of length less than 2 2, so ve
circles can cover the ve small rectangles and hence the 5 3 rectangle.
5
14. Answer: ∠P M Q = 90 .
1
Draw the parallelogram ABCA0 , with AA0 k BC. Then M lies on BA0 , and BM = BA0 . So
3
M is on the homothetic image (center B, dilation 1/3) of the circle with center C and radius
AB, which meets BC at D and E. The image meets BC at P and Q. So ∠P M Q = 90 .
15. 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:
16. It is su cient to show the statement for q prime. We need to prove that
It is obvious that (n, q) = (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
sp 1 (mod q).
Let t be the smallest positive integer which satis es 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 sp sat+b st sb sb (mod q).
Since p is the order of s (mod q), we have that p divides q 1, and we are done.
(2m 1)2 +1
17. Answer: a = 2 where m is an arbitrary positive integer.
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 =
2
yn+1 yn . We see that yn+3 is a perfect square i yn is a perfect square. Hence y3n is a perfect
square for all n ≥ 1 exactly when y0 is a perfect square. Since y0 = 2a 1, the result is
2
obtained when a = (2m 21) +1 for all positive integers m.
18. Let x = 2s x1 and y = 2t y1 where x1 and y1 are odd integers, contrary to assumption. Without
loss of generality we can assume that s ≥ t. We have
2s+t+2 2s+2 x1 y1
z= = s t .
2t (2s t x
1 + y1 ) 2 x1 + y 1
6
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 (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 (x2 , x2 + y2 ) = 1,
so x2 is a divisor of z.
19. Answer: Yes, it is possible.
Start with a simple Pythagorian identity:
32 + 4 2 = 5 2 .
Multiply it with 52
32 5 2 + 4 2 5 2 = 5 2 5 2
and insert the identity for the rst
32 (32 + 42 ) + 42 52 = 52 52
which gives
32 3 2 + 3 2 4 2 + 4 2 5 2 = 5 2 5 2 .
Multiply again with 52
32 3 2 5 2 + 3 2 4 2 5 2 + 4 2 5 2 5 2 = 5 2 5 2 5 2
32 32 (32 + 42 ) + 32 42 52 + 42 52 52 = 52 52 52
that is
32 3 2 3 2 + 3 2 3 2 4 2 + 3 2 4 2 5 2 + 4 2 5 2 5 2 = 5 2 5 2 5 2 .
This (multiplying with 52 and splitting the rst 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.
20. Answer: All numbers 2r 3s where r and s are non-negative integers and s ≤ r ≤ 2s.
Let m = (p1 + 1)(p2 + 1) (pk + 1). Can 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 21 (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.