1994 Tournament Of Towns

Part of Tournament Of Towns

Subcontests

(42)

1

prod (1+a_k^2 / a_{k+1}) > = prod (1+a_k)

Prove that for all positive

a_1. a_2, ..., a_n

\left( 1+\frac{a_1^2}{a_2}\right) \left( 1+\frac{a_2^2}{a_3}\right) ...\left( 1+\frac{a_n^2}{a_1}\right) \ge (1+a_1)(1+a_2)...(1+a_n)

holds.
(LD Kurliandchik)

1

TOT 440 1994 Autumn A S6 first digit of 2^n related

c_n

be the first digit of

2^n

(in decimal representation). Prove that the number of different

13

< c_k

...

c_{k+12}>

57

1

TOT 439 1994 Autumn A S5 periodic sequences with coprime periods

The periods of two periodic sequences are coprime (i.e. relatively prime) numbers

m

n

.. What is the maximal length of initial sections of the two sequences which can coincide? (The period

p

a_1

a_2

...

p

a_n = a_{n+p}

n

1

TOT 436 1994 Autumn A S2 divide space into congruent tetrahedra

Show how to divide space into (a) congruent tetrahedra, (b) congruent “equifaced” tetrahedra. (A tetrahedron is called equifaced if all its faces are congruent triangles.)
(NB Vassiliev)

1

TOT 435 1994 Autumn A S1 x^2+px+q = 0

p

q

of the equation

x^2+px+q = 0

are changed and the new ones differ from the old ones by

0.001

or less. Can the greater root of the new equation differ from that of the old one by

1000

1

<XOY =? median AD = AC - AB

AD

ABC

intersects its inscribed circle (with center

O

) at the points

X

Y

. Find the angle

XOY

AC = AB + AD

1

TOT 434 1994 Autumn O S4 numbers in 10x1

1

10

strip is divided into

10

1

1

squares. The numbers

1

2

3

...

10

are placed in the squares in the following way. First the number

1

is placed in an arbitrary square, then

2

is placed in a neighbouring square, then

3

is placed into a free square neighbouring one of the squares occupied earlier, and so on (up to

10

). How many different permutations of

1

2

3

...

10

can one get in this way?
(A Shen)

1

TOT 433 1994 Autumn O S3 a^3+_b^3+c^3+d^3=a+b+c+d=

a, b, c

d

be real numbers such that

a^3+b^3+c^3+d^3=a+b+c+d=0

Prove that the sum of a pair of these numbers is equal to

0

.
(LD Kurliandchik)

1

TOT 432 1994 Autumn O S2 two triangles from 6 edges of tetrahedron

Prove that one can construct two triangles from six edges of an arbitrary tetrahedron.
(VV Proizvolov)

1

TOT 431 1994 Autumn O S1 boys and girls dancing a waltz, senior version

Several boys and girls are dancing a waltz at a ball. Is it possible that each girl can always get to dance the next dance with either a more handsome or more clever boy than for the previous dance, and that each time at least

80\%

of the girls get to dance the next dance with a boy who is more handsome and more clever? (The numbers of boys and girls are equal and all are dancing.)
(AY Belov)

1

TOT 427 1994 Autumn A J4 subsequence from 1,1/2,1/3, ...

From the sequence

1,\frac12, \frac13, ...

can one choose
(a) a subsequence of

100

different numbers, (b) an infinite subsequence
such that each number (beginning from the third) is equal to the difference between the two preceding numbers (

a_k=a_{k-2}-a_{k-1}

)?
(SI Tokarev)

1

max no of curvilinear sides by intersection of N circles

F

is the intersection of

N

circles (they may have different radii). Find the maximal number of curvilinear “sides” which

F

can have. Curvilinear sides of

F

are the arcs (of the given circumferences) that constitute the boundary of

F

. (Their ends are the “vertices” of

F

- the points of intersection of given circumferences that lie on the boundary of

F

1

TOT 429 1994 Autumn A J6 sum a_i^6 = product a_i

The sum of sixth powers of six integers minus

1

is six times greater than the product of these six integers. Prove that one of them is

1

-1

and all others are

0

s.
(LD Kurliandchik)

1

TOT 428 1994 Autumn A J5 2 periodic sequences with periods 7, 13

The periods of two periodic sequences are

7

13

. What is the maximal length of initial sections of the two sequences which can coincide? (The period

p

a_1

a_2

...

p

a_n = a_{n+p}

n

1

equilateral wanted, started with intersection of 2 perp. lines with a circle

Two-mutually perpendicular lines

\ell

m

intersect each other at a point of the circumference of a circle, dividing it into three arcs. A point

M_i

i = 1

2

3

) is taken on each arc so that the tangent line to the circumference at the point

M_i

\ell

m

in two points at the same distance from

M_i

M_i

is the midpoint of the segment between them). Prove that the triangle

M_1M_2M_3

is equilateral.
(Przhevalsky)

1

TOT 425 1994 Autumn A J2 64 b , 64 w, isosceles, righttriangles in 8x8

8

8

square is divided into

64

1

1

squares, and must be covered by

64

64

white, isosceles, right-angled triangles (each square must be covered by two triangles). A covering is said to be “fine” if any two neighbouring triangles (i.e. having a common side) are of different colours. How many different fine coverings are there?
(NB Vassiliev)

1

TOT 424 1994 Autumn A J1 nuts are placed in boxes

Nuts are placed in boxes. The mean value of the number of nuts in a box is

10

, and the mean value of the squares of the numbers of nuts in the boxes is less than

1000

. Prove that at least

10\%

of the boxes are not empty.
(AY Belov)

1

TOT 423 1994 Autumn O J4 20 pupils in the Backwoods school

20

pupils in the Backwoods school. Any two of them have a common grandfather. Prove that there exist

14

pupils all of whom have a common grandfather.
(AV Shapovalov)

1

TOT 422 1994 Autumn O J3 gcd of 5 integers = difference

Find five positive integers such that the greatest common divisor of each pair is equal to the difference between them.
(SI Tokarev)

1

TOT 421 1994 Autumn O J2 constant ratio OA/OB

Two circles, one inside the other, are given in the plane. Construct a point

O

, inside the inner circle, such that if a ray from

O

cuts the circles at

A

B

respectively, then the ratio

OA/OB

is constant.
(Folklore)

1

TOT 420 1994 Autumn O J1 boys and girls dancing waltz at a ball

Several boys and girls are dancing a waltz at a ball. Is it possible that each girl can always get to dance the next dance with a boy who is either more handsome or more clever than for the previous dance, and that each time one of the girls gets to dance the next dance with a boy who is more handsome and more clever? (The numbers of boys and girls are equal and all are dancing.)
(AY Belov)

1

TOT 417 1994 Spring A S5 integer that divides M. after crossing 1 digit

Find the maximal integer

M

with nonzero last digit (in its decimal representation) such that after crossing out one of its digits (not the first one) we can get an integer that divides

M

.
(A Galochkin)

1

TOT 415 1994 Spring A S3 (P(x))^n has pos. coefficients ?

At least one of the coefficients of a polynomial

P(x)

is negative. Can all of the coefficients of all of its powers

(P(x))^n

n > 1

, be positive?
(0 Kryzhanovskij)

1

TOT 414 1994 Spring A S2 sequence of numbers, x-> 1 - |1 - 2x|

Consider a sequence of numbers between

0

1

in which the next number after

x

1 - |1 - 2x|

|x| = x

x \ge 0

|x| = -x

x < 0

.) Prove that
(a) if the first number of the sequence is rational, then the sequence will be periodic (i.e. the terms repeat with a certain cycle length after a certain term in the sequence); (b) if the sequence is periodic, then the first number is rational.
(G Shabat)

1

inequalities in areas by chords of a non convex polygon

Consider an arbitrary “figure”

F

(non convex polygon). A chord of

F

is defined to be a segment which lies entirely within

F

and whose ends are on its boundary.
(a) Does there always exist a chord of

F

that divides its area in half? (b) Prove that for any

F

there exists a chord such that the area of each of the two parts of

F

is not less than

1/3

F

. (c) Can the number

1/3

in (b) be changed to a greater one?
(V Proizvolov)

1

collinearity from 1995 ToT

Consider a convex quadrilateral

ABCD

. Pairs of its opposite sides are continued until they intersect:

BA

CD

P

BC

AD

Q

K

be the intersection point of the exterior bisectors of the angles

A

C

of the quadrilateral,

L

be the intersection point of the exterior bisectors of the angles

B

D

of the quadrilateral, and

M

be the intersection point of the exterior bisectors of the angles

P

Q

(the exterior bisector of an angle

X

is the line passing through X and perpendicular to its ordinary bisector). Prove that the points

K

L

M

lie on a straight line.
(S Markelov)

1

fixed length for AK, common ext. tangent of incircles of ABD, ACD

D

is placed on the side

BC

of the triangle

ABC

. Circles are inscribed in the triangles

ABD

ACD

, their common exterior tangent line (other than

BC

AD

K

. Prove that the length of

AK

does not depend on the position of

D

. (An exterior tangent of two circles is one which is tangent to both circles but does not pass between them.)
(I Sharygin)

1

TOT 413 1994 Spring A S1 x^2 + y^2 + z^2 = x^3 + y^3+z^3

Does there exist an infinite set of triples of integers

x, y, z

(not necessarily positive) such that

x^2 + y^2 + z^2 = x^3 + y^3+z^3?

1

TOT 411 1994 Spring O S2 a_{n+2}x^2 + a_{n+1}x+ a_n = 0

The sequence of positive integers

a_1

a_2

...

is such that for each

n = 1

2

...

the quadratic equation

a_{n+2}x^2 + a_{n+1}x+ a_n = 0

has a real root. Can the sequence consist of (a)

10

terms, (b) an infinite number of terms?
(A Shapovalov)

1

TOT 412 1994 Spring O S3 54 cells of a chocolate bar

A chocolate bar has five lengthwise dents and eight crosswise ones, which can be used to break up the bar into sections (one can get a total of

9 \times 6 = 54

cells). Two players play the following game with such a bar. At each move (the two players move alternatively) one player breaks off a section of width one from the bar along a single dent and eats it, the other player does the same with what’s left of the bar, and so on. When one of the players breaks up a section of width two into two strips of width one, he eats one of the strips and the other player eats the other strip. Prove that the player who has the first move can play so as to eat at least

6

cells more than his opponent (no matter how his opponent plays).
(R Fedorov)

1

3 points coincide, symmetric of antidiametric wrt midpoint is fixed

ABC

is inscribed in a circle. Let

A_1

be the point diametrically opposed to

A

A_0

be the midpoint of the side

BC

A_2

be the point symmetric to

A_1

with respect to

A_0

B_2

C_2

are defined in a similar way starting from

B

C

. Prove that the three points

A_2

B_2

C_2

coincide.
(A Jagubjanz)

1

TOT 409 1994 Spring A J7 1 1x4, 2 1x3, 3 1x2, 4 1x1 in 10x10 grid

10

10

square grid (which we call “the bay”) you are requested to place ten “ships”: one

1

4

1

3

1

2

1

1

ships. The ships may not have common points (even corners) but may touch the “shore” of the bay. Prove that
(a) by placing the ships one after the other arbitrarily but in the order indicated above, it is always possible to complete the process; (b) by placing the ships in reverse order (beginning with the smaller ones), it is possible to reach a situation where the next ship cannot be placed (give an example).
(KN Ignatjev)

1

TOT 406 1994 Spring A J4 numbers in 10x10

Prove that among any

10

entries of the table

0 \,\,\,\, 1 \,\,\,\, 2 \,\,\,\, 3 \,\,\,\, ... \,\,\,\, 9

9 \,\,\,\, 0 \,\,\,\, 1 \,\,\,\, 2 \,\,\,\, ... \,\,\,\, 8

8 \,\,\,\, 9 \,\,\,\, 0 \,\,\,\, 1 \,\,\,\, ... \,\,\,\, 7

1 \,\,\,\, 2 \,\,\,\, 3 \,\,\,\, 4 \,\,\,\, ... \,\,\,\, 0

standing in different rows and different columns, at least two are equal.
(A Savin)

1

lamps at integer points of a line

At each integer point of the numerical line a lamp with a toggle button is placed. If the button is pressed, a lit lamp is turned off, an unlit one is turned on. Initially all the lamps are unlit. A stencil with a finite set of fixed holes at integer distances is chosen. The stencil may be moved along the line as a rigid body, and for any fixed position of the stencil, one may push simultaneously all the buttons accessible through the holes. Prove that for any stencil it is possible to get exactly two lit lamps after several such operations.
(B Ginsburg)

1

TOT 407 1994 Spring A J5 similar pentagon cut off by a convex pentagon

Does there exist a convex pentagon from which a similar pentagon can be cut off by a straight line?
(S Tokarev)

1

TOT 405 1994 Spring A J3 450 members of a parliament give a slap

Each of the 450 members of a parliament gives a slap in the face to exactly one of his colleagues. Prove that after that they can choose a committee consisting of 150 members, none of whom has been slapped in the face by any other member of the committee.
(Folklore)

1

MP= NQ wanted, statring with intersecting circles

Two circles intersect at the points

A

B

. Tangent lines drawn to both of the circles at the point

A

intersect the circles at the points

M

N

BM

BN

intersect the circles once more at the points

P

Q

respectively. Prove that the segments

MP

NQ

are equal.
(I Nagel)

1

TOT 403 1994 Spring A J1 two 3-digit numbers

A schoolgirl forgot to write a multiplication sign between two

3

-digit numbers and wrote them as one number. This

6

-digit result proved to be

3

times greater than the product (obtained by multiplication). Find these numbers.
(A Kovaldzhi,

1

TOT 402 1994 Spring O J4 ten coins in a circle

Ten coins are placed in a circle, showing “heads” (the tails are down). Two moves are allowed: (a) turn over four consecutively placed coins; (b) turn over four coins placed as

XX OXX

X

is one of the coins to be turned over,

O

is not touched). Is it possible to have all ten coins showing “tails” after a finite sequence of such moves?
(A Tolpygo)

1

an unusual way to describe incenter of convex polygon

O

be a point inside a convex polygon

A_1A_2... A_n

\angle OA_1A_n \le \angle OA_1A_2, \angle OA_2A_1 \le \angle OA_2A_3, ..., \angle OA_{n-1}A_{n-2} \le \angle OA_{n-1}A_n, \angle OA_nA_{n-1} \le \angle OA_nA_1

and all of these angles are acute. Prove that

O

is the centre of the circle inscribed in the polygon.
(V Proizvolov)

1

TOT 400 1994 Spring O J2 60 children in a summer camp

60

children participate in a summer camp. Among any

10

of the children there are three or more who live in the same block. Prove that there must be

15

or more children from the same block.
(Folklore)

1

TOT 399 1994 Spring O J1 convex quad construction

Construct a convex quadrilateral given the lengths of all its sides and the length of the segment between the midpoints of its diagonals.
(Folklore)