MathDB

1

ASU 251 All Soviet Union MO 1977 P(Q(x))=Q(P(x))

Let us consider one variable polynomials with the senior coefficient equal to one. We shall say that two polynomials

P(x)

and

Q(x)

commute, if

P(Q(x))=Q(P(x))

(i.e. we obtain the same polynomial, having collected the similar terms).
a) For every a find all

Q

such that the

Q

degree is not greater than three, and

Q

commutes with

(x^2 - a)

.
b) Let

P

be a square polynomial, and

k

is a natural number. Prove that there is not more than one commuting with

P

k

-degree polynomial.
c) Find the

4

-degree and

8

-degree polynomials commuting with the given square polynomial

P

.
d)

R

and

Q

commute with the same square polynomial

P

. Prove that

Q

and

R

commute.
e) Prove that there exists a sequence

P_2, P_3, ... , P_n, ...

(

P_k

is

k

-degree polynomial), such that

P_2(x) = x^2 - 2

, and all the polynomials in this infinite sequence pairwise commute.

250

1

ASU 250 All Soviet Union MO 1977 scales and weights, in n-letter word

Given scales and a set of

n

different weights. We take weights in turn and add them on one of the scales sides. Let us denote "

L

" the scales state with the left side down, and "

R

" -- with the right side down.
a) Prove that you can arrange the weights in such an order, that we shall obtain the sequence

LRLRLRLR...

of the scales states. (That means that the state of the scales will be changed after putting every new weight.)
b) Prove that for every

n

-letter word containing

R

's and

L

's only you can arrange the weights in such an order, that the sequence of the scales states will be described by that word.

248

1

ASU 248 All Soviet Union MO 1977 (x_1+...+x_n)=(y_1+...+y_m)<mn

Given natural numbers

x_1,x_2,...,x_n,y_1,y_2,...,y_m

. The following condition is valid:

(x_1+x_2+...+x_n)=(y_1+y_2+...+y_m)<mn \,\,\,\, (*)

Prove that it is possible to delete some terms from (*) (not all and at least one) and to obtain another valid condition.

247

1

ASU 247 All Soviet Union MO 1977 unique node inside a 100x100 square

Given a square

100\times 100

on the sheet of cross-lined paper. There are several broken lines drawn inside the square. Their links consist of the small squares sides. They are neither pairwise- nor self-intersecting (have no common points). Their ends are on the big square boarder, and all the other vertices are in the big square interior. Prove that there exists (in addition to four big square angles) a node (corresponding to the cross-lining family, inside the big square or on its side) that does not belong to any broken line.

246

1

ASU 246 All Soviet Union MO 1977 1000 and 1000 boxes all numbered

There are

1000

tickets with the numbers

000, 001, ... , 999

, and

100

boxes with the numbers

00, 01, ... , 99

. You may put a ticket in a box, if you can obtain the box number from the ticket number by deleting one digit. Prove that:
a) You can put all the tickets in

50

boxes;
b)

40

boxes is not enough for that;
c) it is impossible to use less than

50

boxes.
d) Consider

10000

4

-digit tickets, and you are allowed to delete two digits. Prove that

34

boxes is enough for storing all the tickets.
e) What is the minimal used boxes set in the case of

k

-digit tickets?

249

1

ASU 249 All Soviet Union MO 1977 1000 squares with parallel sides

Given

1000

squares on the plane with their sides parallel to the coordinate axes. Let

M

be the set of those squares centres. Prove that you can mark some squares in such a way, that every point of

M

will be contained not less than in one and not more than in four marked squares

244

1

ASU 244 All Soviet Union MO 1977 2 perfect squares create a fine number

Let us call "fine" the

2n

-digit number if it is exact square itself and the two numbers represented by its first

n

digits (first digit may not be zero) and last

n

digits (first digit may be zero, but it may not be zero itself) are exact squares also.
a) Find all two- and four-digit fine numbers.
b) Is there any six-digit fine number?
c) Prove that there exists

20

-digit fine number.
d) Prove that there exist at least ten

100

-digit fine numbers.
e) Prove that there exists

30

-digit fine number.

245

1

ASU 245 All Soviet Union MO 1977 sums of subsets of set of positive integers

Given a set of

n

positive numbers. For each its nonempty subset consider the sum of all the subset's numbers. Prove that you can divide those sums onto

n

groups in such a way, that the least sum in every group is not less than a half of the greatest sum in the same group.

243

1

ASU 243 All Soviet Union MO 1977 7 elves around a table, each with cup

Seven elves are sitting at a round table. Each elf has a cup. Some cups are filled with some milk. Each elf in turn and clockwise divides all his milk between six other cups. After the seventh has done this, every cup was containing the initial amount of milk. How much milk did every cup contain, if there was three litres of milk total?

242

1

ASU 242 All Soviet Union MO 1977 game x^{10} + ?x^9 + ?x^8 + ... + ?x + 1

The polynomial

x^{10} + ?x^9 + ?x^8 + ... + ?x + 1

is written on the blackboard. Two players substitute (real) numbers instead of one of the question marks in turn. (

9

turns total.) The first wins if the polynomial will have no real roots. Who wins?

241

1

ASU 241 All Soviet Union MO 1976 convex polyhedron can be inscribed in sphere

Every vertex of a convex polyhedron belongs to three edges. It is possible to circumscribe a circle around all its faces. Prove that the polyhedron can be inscribed in a sphere.

237

1

ASU 237 All Soviet Union MO 1977 2 triangles inscribed in same circle

a) Given a circle with two inscribed triangles

T_1

and

T_2

. The vertices of

T_1

are the midpoints of the arcs with the ends in the vertices of

T_2

. Consider a hexagon -- the intersection of

T_1

and

T_2

. Prove that its main diagonals are parallel to

T_1

sides and are intersecting in one point.
b) The segment, that connects the midpoints of the arcs

AB

and

AC

of the circle circumscribed around the

ABC

triangle, intersects

[AB]

and

[AC]

sides in

D

and

K

points. Prove that the points

A,D,K

and

O

-- the centre of the circle -- are the vertices of a diamond.

240

1

ASU 240 All Soviet Union MO 1977 2 tourists to all cities, cheapest ticket

There are direct routes from every city of a certain country to every other city. The prices are known in advance. Two tourists (they do not necessary start from one city) have decided to visit all the cities, using only direct travel lines. The first always chooses the cheapest ticket to the city, he has never been before (if there are several -- he chooses arbitrary destination among the cheapests). The second -- the most expensive (they do not return to the first city). Prove that the first will spend not more money for the tickets, than the second.

238

1

ASU 238 All Soviet Union MO 1977 b/w checkers around a circle

Several black and white checkers (tokens?) are standing along the circumference. Two men remove checkers in turn. The first removes all the black ones that had at least one white neighbour, and the second -- all the white ones that had at least one black neighbour. They stop when all the checkers are of the same colour.
a) Let there be

40

checkers initially. Is it possible that after two moves of each man there will remain only one (checker)?
b) Let there be

1000

checkers initially. What is the minimal possible number of moves to reach the position when there will remain only one (checker)?

239

1

ASU 239 All Soviet Union MO 1977 b_n=a_{n+1}-a_n/2 ->0 => a_n ->0

Given infinite sequence

a_n

. It is known that the limit of

b_n=a_{n+1}-a_n/2

equals zero. Prove that the limit of

a_n

equals zero.

236

1

ASU 236 All Soviet Union MO 1977 numbers assigned to points, line sums 0

Given several points, not all lying on one straight line. Some number is assigned to every point. It is known, that if a straight line contains two or more points, than the sum of the assigned to those points equals zero. Prove that all the numbers equal to zero.

235

1

ASU 235 All Soviet Union MO 1977 polygon without self-intersections

Given a closed broken line without self-intersections in a plane. Not a triple of its vertices belongs to one straight line. Let us call "special" a couple of line's segments if the one's extension intersects another. Prove that there is even number of special pairs.

1977 All Soviet Union Mathematical Olympiad

Subcontests

ASU 251 All Soviet Union MO 1977 P(Q(x))=Q(P(x))

ASU 250 All Soviet Union MO 1977 scales and weights, in n-letter word

ASU 248 All Soviet Union MO 1977 (x_1+...+x_n)=(y_1+...+y_m)<mn

ASU 247 All Soviet Union MO 1977 unique node inside a 100x100 square

ASU 246 All Soviet Union MO 1977 1000 and 1000 boxes all numbered

ASU 249 All Soviet Union MO 1977 1000 squares with parallel sides

ASU 244 All Soviet Union MO 1977 2 perfect squares create a fine number

ASU 245 All Soviet Union MO 1977 sums of subsets of set of positive integers

ASU 243 All Soviet Union MO 1977 7 elves around a table, each with cup

ASU 242 All Soviet Union MO 1977 game x^{10} + ?x^9 + ?x^8 + ... + ?x + 1

ASU 241 All Soviet Union MO 1976 convex polyhedron can be inscribed in sphere

ASU 237 All Soviet Union MO 1977 2 triangles inscribed in same circle

ASU 240 All Soviet Union MO 1977 2 tourists to all cities, cheapest ticket

ASU 238 All Soviet Union MO 1977 b/w checkers around a circle

ASU 239 All Soviet Union MO 1977 b_n=a_{n+1}-a_n/2 ->0 => a_n ->0

ASU 236 All Soviet Union MO 1977 numbers assigned to points, line sums 0

ASU 235 All Soviet Union MO 1977 polygon without self-intersections

1977 All Soviet Union Mathematical Olympiad

Subcontests

ASU 251 All Soviet Union MO 1977 P(Q(x))=Q(P(x))

ASU 250 All Soviet Union MO 1977 scales and weights, in n-letter word

ASU 248 All Soviet Union MO 1977 (x_1+...+x_n)=(y_1+...+y_m)&lt;mn

ASU 247 All Soviet Union MO 1977 unique node inside a 100x100 square

ASU 246 All Soviet Union MO 1977 1000 and 1000 boxes all numbered

ASU 249 All Soviet Union MO 1977 1000 squares with parallel sides

ASU 244 All Soviet Union MO 1977 2 perfect squares create a fine number

ASU 245 All Soviet Union MO 1977 sums of subsets of set of positive integers

ASU 243 All Soviet Union MO 1977 7 elves around a table, each with cup

ASU 242 All Soviet Union MO 1977 game x^{10} + ?x^9 + ?x^8 + ... + ?x + 1

ASU 241 All Soviet Union MO 1976 convex polyhedron can be inscribed in sphere

ASU 237 All Soviet Union MO 1977 2 triangles inscribed in same circle

ASU 240 All Soviet Union MO 1977 2 tourists to all cities, cheapest ticket

ASU 238 All Soviet Union MO 1977 b/w checkers around a circle

ASU 239 All Soviet Union MO 1977 b_n=a_{n+1}-a_n/2 -&gt;0 =&gt; a_n -&gt;0

ASU 236 All Soviet Union MO 1977 numbers assigned to points, line sums 0

ASU 235 All Soviet Union MO 1977 polygon without self-intersections

ASU 248 All Soviet Union MO 1977 (x_1+...+x_n)=(y_1+...+y_m)<mn

ASU 239 All Soviet Union MO 1977 b_n=a_{n+1}-a_n/2 ->0 => a_n ->0