V All-Union Mathematical Olympiad

Kvant 1971, No. 11 p. 35, 36, 38, 39, 40 Tag RWCY

Rough automatic draft, low quality: expect mistakes and awkward wording. It will be replaced by a better translation. Original →

V Weighing mathematical optimization.
V. L. Gutenkhær

From April 15 to April 20, the V Weighing Mathematical Optimization took place in Prgue. But the jury was optimized (chairman Jan Bardzin, deputy chairman Nikolai Vasiliev) began its work on April 13. From these tasks that the jury members brought with them, it was necessary to display the most interesting and original tasks. This time, unlike previous years, the jury decided to give schoolchildren problems that would be close to serious mathematical science, and in the second round they even conducted a small experiment: to offer one more difficult problem, breaking it down into a series of gradually conditioned questions, in the solution of which it would be proposed to advance as far as possible.

The first and second rounds of optimization took place on April 16 and 17 separately for the 8th, 9th and 10th grades.

We place below a list of 23 tasks that were offered to schoolchildren. The average ones are essentially 14 different problems in total. We publish 10 problems in the “Kvant Problem Book” (see «Kvant» No. 10, 11).

TASKS

8th grade (first day)

Prove that there is a value of a number divisible by 2 $^{100}$ , in whose decimal notation only the digits 1 and 2 are involved.
Given a triangle $A_1A_2A_3$ . On its side $A_1A_2$ the points $B_1$ and $D_2$ are taken, on the side $A_2A_3$ - points $B_2$ and $D_3$ , on the side $A_3A_1$ - points $B_3$ and $D_1$ so that if we construct parallelgrams $A_1B_1C_1D_1$ , $A_2B_2C_2D_2$ and $A_3B_3C_3D_3$ , then the lines $A_1C_1$ , $A_2C_2$ and $A_3C_3$ will intersect at one point. Prove that if $A_1B_1=A_2D_2$ and $A_2B_2=A_3D_3$ , then $A_3B_3=A_1D_1$ .
Two people play this game. The first ones write two rows of 10 numbers one below the other so that the following rule is satisfied: if the number $b$ is written under the number $a$ , and the number $d$ is written under the number $c$ , then $a+d=b+c$ . The second player, knowing this rule, wants to determine all the written numbers.

He is allowed to ask the first player a question like “What number is in third place in the first line?” or “What number is in ninth place on the second line?” etc. In what is the smallest number of such questions can the second player find out all the numbers?

See problem M111.

8th grade (second day)

See problem M108.
Prove that from 25 different positive numbers it is possible to choose two numbers such that none of the remaining numbers is equal to either the sum or the difference (between double and small) of the selected numbers.
See problem M109.

9th grade (first day)

See problem M113.
On each side of triangle ABC two points are taken: on AB - points D and E, on BC - points F

and G and on CA are points H and K. It is given that AD=BE, BF=CG and CH=AK. In triangles ADK, BEF and CGH, medians are drawn from vertices A, B and C. Prove that the lines on which these medians lie intersect at one point.
3. See problem M115.
4. See problem M111.
5. See problem M112.

9th grade (second day)

A cube with an edge of length n is divided into $n^3$ unit cups. Let’s select several cups and draw three straight lines parallel to the edges through the center of each of them. What is the smallest number of cups that can be chosen so that a straight line drawn through them will cross out all the cubes?
Solve this problem if:
a) $n=4$ ,
b) $n=10$ ,
b) $n$ — any natural number.
Prove that all straight lines dividing both the area and perimeter of a triangle in half intersect at one point.
See problem M110.

10th grade (first day)

See problem M106.
See problem M107, a.
Projections of the body onto two planes are circles. Prove that these circles have equal radii.
See problem M111.
See problem M114.

10th grade (second day)

A cube with an edge of length n is divided into $n^3$ unit cups. Let’s select several cups and draw three straight lines parallel to the edges through the center of each of them. What is the smallest number of cups that can be chosen so that a straight line drawn through them will cross out all the cubes:
a) Give the answer for small values of n: for n=2, 3, 4.

Try to find the answer with n=10.
b) Solve the general problem. If you were unable to find the answer, prove some inequalities that estimate the number of marked cups from above and below.
d) Note that this problem can be formulated like this.
Consider all possible sets $(x_1, x_2, x_3)$ , where each of the letters $x_1, x_2, x_3$ takes one of n values 1, 2,…, n. What is the smallest number of sets that must be chosen so that for each of the remaining sets of the environment chosen, we find one that differs from it only in one place (by the value of only one of the coordinates $x_1, x_2, x_3$ )? Try to find estimates for a more general problem where sets of not three, but four or a large number of letters are considered.

a) Consider the function $f(x, y)=x^2+xy+y^2$ . Prove that for any point $(x, y)$ there are also integers $(m, n)$ , which

$f(x-m, y-n)=(x-m)^2+$
$+(x-m)(y-n)+(y-n)^2\leq \frac{1}{2}.$

Let us denote by $f(x, y)$ the smallest of the numbers $f(x-m, y-n)$ for all integers m and n. The assertion of problem a) is that the inequality $f(x, y)\leq \frac{1}{2}$ holds for all $(x, y)$ . Prove that the stronger inequality $f(x, y)\leq \frac{1}{3}$ is in fact true. Find all points for which the equality $f(x, y)=\frac{1}{3}$ holds.

b) Consider the function

$f_a(x, y)=x^2+axy+y^2(a\geq 0).$

Find some number C (depending on a) such that all $(x, y)$ satisfy the inequality $|\bar{f}_a(x, y)|\leq C$ . Try to find an accurate estimate.

methods of proof unknown to the jury.

The stumbling block was task No. 4, proposed in all classes. Many problems solved this problem, but at the same time they lost sight of the fact that the arrangement of the circles can be quite exotic: the circles can overlap each other, their centers can be located close to each other, etc. Essentially, in this problem, a figure covered with circles can have an almost arbitrary shape, and you need to come up with a reasoning that works for any such figure. This problem has a very short and red solution. In each class, only one student managed to solve it (the table on page 39 shows how many people solved each problem completely or with minor steps). Other tasks were also repeated in equal classes, but their formulations differed from each other. For example, problem 1 in the ninth grade differed from problem 1 in the eighth grade in that the number $n$ was placed together with the number 100. Problem 7 of the ninth grade differed from task 5a of the eighth grade in that the point at which the lines intersect was not named and, thus, was essentially conditional.

As a more interesting example of development, we will give problems 3 (8th grade) and 5 (9th grade). The first of these problems is simply a special case of the second (for $m=2$ , $n=10$ ), but in the 8th grade formulation it is more clearly highlighted what exactly is required in its solution: (1) indicate the answer (this answer - 11 questions - was found almost

All); (2) prove that it is possible to find out all the numbers in 11 questions (this is very simple); (3) prove that it is impossible to find out the numbers in 10 or fewer questions.

Task 3 (8th grade). Let $a$ and $c$ be some two numbers in the top line, and $b$ and $d$ be the numbers below them:

$\dots a \dots c \dots$
$\dots b \dots d \dots$

The only condition that this number will satisfy is that $a+d=c+b$ . Let’s rewrite this condition as follows: $a-b=c-d$ . It follows that the difference between the number in the top row and the number below it is the same for all columns; Let’s denote this difference by $y$ . The table can be written like this:

$\begin{array}{c c c c c} x_1 & x_2 & \dots & x_9 & x_{10} \\ x_1-y & x_2-y & \dots & x_9-y & x_{10}-y \end{array}$

$x_1, \dots, x_{10}$ , $y$ are arbitrary numbers. This table can be determined in 11 questions. For example, in 10 questions you can find 10 numbers $x_1, \dots, x_{10}$ from the first line, and then, by asking one question “what number comes first in the second line?”, find $y$ .

It is almost very indo that in less than 11 questions it is impossible to find 11 unknowns. However, the jury did not consider this to be very indo and demanded clarification

neniya. The greatest difficulty for the participants was recording their complete and clear solutions to the problems. Writing rows and tables consisting of a large number of elements, and handling them fluently, can very little not be used as a difficulty of this kind.

Task 6 (8th grade). We will prove the statement of the problem by contradiction. Let us assume that either the sum of two numbers out of 25 or their difference is contained among the remaining numbers.

Let’s arrange these numbers in ascending order:

$a_1 < a_2 < \dots < a_{24} < a_{25}.$

Consider most of the numbers $a_{25}$ paired with any of the other numbers. Obviously, the sum of such numbers is not contained among the given numbers, since

$a_{25} + a_i > a_{25} \quad (i=1, 2, \dots, 24).$

Therefore, the differences of these numbers

$a_{25} - a_{24} < a_{25} - a_{23} < \dots < a_{25} - a_1$

must be contained among the given numbers. The only possible option:

$a_{25} - a_{24} = a_1, a_{25} - a_{23} = a_2, \dots, a_{25} - a_1 = a_{24}$

or, what is the same,

$a_{24} + a_1 = a_{23} + a_2 = \dots = a_{13} + a_{12} = a_{25}.$

Number of participants who solved each problem

| 8th grade | Task No. | Day I | | | II day | | | | |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| | Decided | 1 | 2 | 3 | 4 | | 5 | 6 | 7 | 8 |
| | | 30 | 7 | 22 | 1 | | | 42 | 15 | 13 |
| 9th grade | Task No. | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 |
| | Decided | 56 | 31 | 0 | | 1 | 6 | 9 | 1 | 16 |
| 10th grade | Task No. | 1 | 2 | 3 | | 4 | 5 | 6* | 7* | 8* |
| | Decided | 26 | 43 | 65 | | 1 | 5 | 32 | 1 | 18 |

The various results obtained by participants on these tasks do not fit neatly into the framework of the formulated questions; the number of schoolchildren, the most complete and accurate results obtained, examples constructed, etc. are indicated.

Now consider the number $a_{24}$ in pala with any of the first twenty-three numbers. The pair of numbers $a_1$ and $a_{24}$ is fine because $a_{24}+a_1=a_{25}$ . Sums of numbers

$a_{24}+a_2,\dots,a_{24}+a_{23}$

are not included among these numbers, since

$a_{24}+a_i>a_{24}+a_1=a_{25},$

( $i=2,3,\dots,23$ ).

Therefore, the differences of these numbers must be contained among the given numbers. Let’s write them in ascending order:

$a_{24}-a_{23}<a_{24}-a_{22}<\dots<a_{24}-a_2.$

From the equality $a_{23}+a_2=a_{25}$ it follows that $a_{24}-a_2<a_{23}$ and therefore the only possible option is:

$a_{24}-a_{23}=a_1, \quad a_{24}-a_{22}=a_2, \dots, a_{24}-a_{12}=a_{12}, \dots, a_{24}-a_2=a_{22}.$

But in this case, the difference $a_{24}-a_{12}$ is not contained among the remaining numbers, and the sum $a_{24}+a_{12}$ is not contained among the given numbers at all. We got a contradiction. Thus, the statement of the problem is proven.

The problem turns out to be true for $n$ numbers, where $n \geq 4$ . The proof can be verified in a similar way, and for even $n$ we can obtain a contradiction at the very first step of our reasoning deniens. Try to write down this proof yourself.

What was unexpected for the jury was the comparatively easy theoretic problem 3 (grade 10). The task turned out to be feasible for only one third of tenth graders. This indicates, perhaps, that the spatial understanding of the majority of Olympiad participants is insufficiently developed.

Task 3 (grade 10). Here we are talking about a general orthogonal projection. The definition of the projection of a body onto a given plane is contained in the school textbook. We will need to determine the projection of the body onto a straight line.

The projection of a point onto a given line is called onto a given line, then its projection will be this point itself.

The projection of a body onto a given line is called onto a given line, then its projection will be this point itself.

Let $P$ be a plane and $l$ a line lying on $P$ . From the theorem on three redistributions it follows that the projection of any point onto the line $l$ can be obtained by successively projecting this point onto the plane $P$ and projecting the resulting point onto the line.

According to the conditions of the problem, the projection of a body onto two planes is a circle. Let us assume that these planes intersect along the straight line $l$ . From the above it follows that the projection of the body onto the straight line $l$ coincides with the projections of each of the circles onto $l$ . From here we conclude that the projections of the circles $l$ coincide with each other.

It is clear that the projection of a circle onto the straight line $l$ lying in its plane is a segment equal to the diameter of the circle. Consequently, these circles have the same diameters and the same radii.

The case when these planes are parallel to each other is very convenient.

We can say that the remaining problems of the first day for the tenth graders, although they were more difficult, all allowed a significant number of solutions than the solution to problem No. 3 given above.

The ninth grade option must be admitted as somewhat overloaded: there was not a single “completely simple” task here. In particular, problem 3 has not been completely solved.

The second round was especially difficult, containing tasks that required lengthy thinking. And since the same as in the tenth grade,