Kvant 1970, No. 8 · Pages

8

Problem 6. Prove that the vertices of a polyorganic can be divided into black and white poppies so that no two vertices of a monozoche tsempa are adjacent moeda and molko moeda, when each face of the polyorganic has an even number of sides.

e is also indicated. To prove it, it is enough to take any vertex and declare it white, its neighbors black, etc. It is necessary to prove that no contradictions arise in this case, i.e., that in every closed broken line composed of the edges of a polyorganic there is an even number of links.

Let’s return to the polyorganic $M$ with colored vertices. Since $M$ three faces converge at each vertex, the number of white vertices is equal to the number of black vertices. Let us select some of its black vertices (one, two or all) and cut them off using planes. Each vertex is a segment of one plane, intersecting only those edges that emanate from this vertex, and not containing any vertices $M$. We denote the resulting polyorganic by $M'$. It differs from $M$ in that it has, together with some black vertices, triangular faces. Let us prove that the polyorganic $M'$ is absolutely indescribable.

Let us assume that the polyorganic $M'$ or another polyorganic having the same structure is inscribed in a sphere. Let us select three faces that correspond to those faces of the polyorganic $M$ that converge at one trimmed vertex. These three faces are pairwise adjacent, the vertex of the truncated trihedral angle obviously lies outside the sphere, since the polyorganic is inscribed, therefore the sum of the relative angles for them is less than l. Let us assign to each edge of the polyorganic $M$ a relative angle with the corresponding edge of the polyorganic $M'$. Then the sum of these assigned angles for all white and all unselected black vertices is equal to l, and for selected black vertices it is strictly less than l. As in the proof of Steinitz’s theorem, we write out these equalities and inequalities, multiply the sums corresponding to the white vertices by -1 and add them. The result should be strict inequality. However, on the left side we get zero, or each of the assigned angles is included in the sum once for a white vertex, and once for a black one. On the right side we will also get zero, since the number of white vertices is equal to the number of black ones. The resulting contradiction ($0<0$) proves our statement.

Exactly the same reasoning can be verified if the marked vertices are defined not by one, but by several planes, as long as the faces converging in them remain pairwise adjacent and do not converge at one vertex.

This method can also obtain other sufficient conditions. Now some necessary conditions have become known for a polyorganic to be absolutely indescribable, but in general the problem has not yet been solved.

The relative angle method allows us to solve other interesting problems.

Problem 7. Let three faces converge at each vertex of the polyorganic $M$, and let each face have the same number of sides. Prove that if all but one of the vertices of the polyorganic $M$ lie on the sphere, then the polyorganic $M$ is inscribed.

Indicated and e. Use problem 6. Do not miss this unpleasant possibility: edges emanating from a vertex that does not lie on the sphere touch the sphere.

Similar, but more complex.

Problem 8. Let all the vertices of the polyorganic $M$ be divided into black and white, as described in Problem 5, and the number of black vertices is equal to the number of white ones. Prove that if all but one of the vertices of the polyorganic $M$ lie on the sphere, then the polyorganic $M$ is inscribed.

Thus, if the vertices can be divided into black and white, as described in task 5, then either the polyorganic is absolutely indescribable or satisfies task 8, i.e.

15

First, the entire first row and first two columns are filled. Further filling of the table is carried out according to the following scheme:

| $a_{n-2}$ | $a_{n-1}$ | $a_n$ |
| :— | :— | :— |
| $p_{n-2}$ | $p_{n-1}$ | |

1. column $\left| \frac{p_{n-1}}{q_{n-1}} \right|$ multiplied by $a_n$,

2. add the previous one to the resulting column.

The same scheme is recommended to be used if you need to calculate the value of the entire continued fraction: the last column $\left| \frac{p_s}{q_s} \right|$ will provide a sufficient answer.

Practice filling out the table for the continued fraction [0; 3, 14, 1, 2, 5]

| 0 | 3 | 14 | 1 | 2 | 5 |
| :— | :— | :— | :— | :— | :— |
| 0 | 1 | 14 | 15 | 44 | 235 |
| 1 | 3 | 43 | 46 | 135 | 721 |

4. Difference of adjacent suitable fractions. The step from the $n$th suitable fraction to the next one is represented by the $n$th fraction and is designated $\Delta_n$:

$$\Delta_n = \frac{p_{n+1}}{q_{n+1}} - \frac{p_n}{q_n} = \frac{p_{n+1} q_n - p_n q_{n+1}}{q_n q_{n+1}} = \frac{D_n}{q_n q_{n+1}},$$

where $D_n$ denotes numeric

$$D_n = p_{n+1} q_n - p_n q_{n+1}.$$

Let us lower the indices $y$ $p_{n+1}$ and $q_{n+1}$ according to formulas (3.2):

$$D_n = \left( p_n a_{n+1} + p_{n-1} \right) q_n - p_n \left( q_n a_{n+1} + q_{n-1} \right) = -\left( p_n q_{n-1} - p_{n-1} q_n \right).$$

The expression in parentheses is the same type as (**), but all indices are by one

less. So it represents $D_{n-1}$:

$$D_n = -D_{n-1}.$$

This recurrence relationship allows you to lower the index to zero:

$$D_n = -D_{n-1} = D_{n-2} = -D_{n-3} = \dots = (-1)^n D_0.$$

For complete success, all that remains is to directly calculate $D_0$:

$$D_0 = p_1 q_0 - p_0 q_1 = (a_1 a_0 + 1) \cdot 1 - a_0 a_1 = 1.$$

Hence,

$$D_n = p_{n+1} q_n - p_n q_{n+1} = (-1)^n,$$

(4.1) and by formula (*)

$$\Delta_n = \frac{p_{n+1}}{q_{n+1}} - \frac{p_n}{q_n} = \frac{(-1)^n}{q_n q_{n+1}}.$$

5. Comparing the one with the odd number greater than the neighboring fractions (previous and subsequent). What suitable odd-numbered fraction is smaller than its neighboring fractions.

When applying this formulation to the zero and last suitable fractions, we must take into account that each of them has only one neighboring fraction.

The validity of this property is immediately clear from formula (4.2).

Property 1 means that successive suitable fractions are alternately greater and lesser.

Property 2. Differences between adjacent fractions in abscimal values ​​cancel out (meaning: as the number increases).

Let’s compare:

$$|\Delta_n| = \frac{1}{q_n q_{n+1}},$$

$$|\Delta_{n+1}| = \frac{1}{q_n+1 q_{n+2}}.$$

We have $q_{n+2} > q_n$. This means that the second fraction has a larger denominator, but it itself is smaller:

$$|\Delta_{n+1}| < |\Delta_n|.$$

6. Irreducibility of suitable fractions. All suitable fractions are irreducible.

16

Recall that the numerators and denominators of suitable fractions are formed according to formulas (3.1). Let us assume that the fraction $\frac{p_n}{q_n}$ is reducible, i.e. its numerator and denominator have a common factor $\lambda$, different from one:

$$p_n = \lambda p_n', \quad q_n = \lambda q_n'.$$

Then formula (4.1) gives

$$\lambda (p_{n+1} q_n' - p_n' q_{n+1}) = (-1)^n.$$

We are stuck with an absurd equality: the left side is divisible by $\lambda$, but the right is not. This means that the fraction $\frac{p_n}{q_n}$ is irreducible.

III. Introduction of infinite fractions

7. The meaning of an infinite continued fraction. The principle of nested segments will serve us as a key that will open the meaning of an infinite continued fraction. Let us recall a similar situation: how to extrude an infinite decimal fraction? An infinite decimal fraction can be considered as a shorthand notation of a sequence of nested segments: successive roundings with a deficit give the left ends of these segments, and with an excess - the right ones. What is the meaning of the statement that $\sqrt{2}$ is expressed as an infinite decimal fraction

$$\sqrt{2} = 1,4142...?$$

This means that

$$1 < \sqrt{2} < 2,$$

$$1,4 < \sqrt{2} < 1,5,$$

$$1,41 < \sqrt{2} < 1,42,$$

There is a single number that satisfies all these inequalities at once. This is $\sqrt{2}$.

Having symbolic infinite continued fractions

$$[a_0; a_1, a_2, \dots],$$

it is possible to form an infinite sequence of finite continued fractions

$$a_0, [a_0; a_1], [a_0; a_1, a_2], \dots,$$

$$[a_0; a_1, a_2, \dots, a_n], \dots,$$

(**)

which can be written as suitable fractions

$$\frac{p_0}{q_0}, \frac{p_1}{q_1}, \frac{p_2}{q_2}, \dots, \frac{p_n}{q_n}, \dots$$

(***)

These suitable fractions determine the sequence of nested segments

$$\left[ \frac{p_0}{q_0}, \frac{p_1}{q_1} \right], \left[ \frac{p_2}{q_2}, \frac{p_1}{q_1} \right], \left[ \frac{p_2}{q_2}, \frac{p_3}{q_3} \right],$$

$$\left[ \frac{p_4}{q_4}, \frac{p_3}{q_3} \right], \dots$$

Each next segment is in the previous one (Fig. 4) and their lengths tend to zero (see formulas (4.2)). Therefore, there is a number $\alpha$ that belongs to all segments. It belongs to the value of an infinite continued fraction**).

This definition can be expressed in another way. Here are two options.

1. The value of an infinite continued fraction lies between any two adjacent suitable fractions.

2. The value of a .befinite continued fraction is greater than the doi of a suitable fraction

(*) Marks 0, 1, 2, … on figure 4 read the numbers of suitable fractions.

**) This defines the term “fitting fraction”, it “fits” closer and closer to the point $\alpha$.

17

bi with an even number and less than every suitable fraction with an odd number (all this is clearly visible on figure 5).

It is important to understand that any of these formulations define a singular number.

It is easy to show (do this) that if the irrational number $\alpha$ is decomposed into an integer fraction, then successive suitable fractions are alternately smaller and larger than $\alpha$. It follows that this number $\alpha$ is the value that is now assigned to the infinite whole fraction (the unity of the point belonging to all segments!). Others are allowed to write

$$\alpha = [a_0; a_1, a_2, \dots].$$

It is now clear that each suitable fraction can be considered an approximation of the whole fraction. The larger the number, the more accurate the approximation.

Almost the same thing was said about the approximation of a finite integer fraction by suitable fractions. The only difference is that in the case of an infinite whole fraction, there is no last good fraction, and significant, no good fraction gives the powerful value of the whole fraction.

For infinite integer fractions, the sign of equality is preserved («Kvant», No. 1, p. 22). Let’s formulate it like this:

1. Two infinite integer fractions $[a_0; a_1, a_2, \dots, a_n, \dots]$ and $[b_0; b_1, b_2, \dots, b_n, \dots]$ are equal to each other if and only if their corresponding elements coincide, i.e. $a_n = b_n$ with $n=0, 1, 2, \dots$.

2. An infinite whole fraction cannot be equal to a finite fraction.

8. And the approximation of a suitable fraction and fractions. Does the reader remember when we set out on this long voyage? We are looking for an advantageous way to approximate real numbers (including rational numbers) to rational ones.

What’s happened! Is this a typo? Is it possible to approximate rational numbers by rational numbers?

Can. For example,

$$\frac{6187}{7425} \approx \frac{5}{6}.$$

In this example, we replace a cumbersome rational number with a simpler one.

Once we’ve become familiar with whole fractions, a natural project that comes up is to factor the number $\alpha$ into a whole fraction and count successive suitable fractions as approximations of that number. In other words, truncate the whole fraction, discarding all elements starting from some, and take the remaining truncated fraction as an approximate value of the full whole fraction. This is exactly what we do by truncating the decimal fraction and leaving only the desired number of francs after the decimal point.

In order to accept or reject this project, we need to find out what kind of error we allow by replacing the number $\alpha$ with a suitable fraction, i.e., assuming

$$\alpha \approx \frac{p_n}{q_n}.$$

In all further reasoning it is assumed that the fraction $\frac{p_n}{q_n}$ is not zero and not the last. For $n=0$ the use of whole fractions does not provide anything new compared to the use of decimals, and the case $n=s$ is uninteresting since we get $\alpha=\alpha$ and the error is zero.

19

cutting is $|\Delta_n| = \frac{1}{q_n q_{n+1}}$. The point $\alpha$ may be an interior point of that segment, or may be the same as $\frac{p_{n+1}}{q_{n+1}}$ (if $\alpha$ is rational and $\frac{p_{n+1}}{q_{n+1}}$ is the last matching fraction). Thus,

$$\left| \alpha - \frac{p_n}{q_n} \right| \leqslant |\Delta_n|. \tag{10.1}$$

Let $\frac{p}{q} - \text{какая-нибудь дробь}$, whose denominator is less than $q_n$ and thereby less than $q_{n+1}$:

$$q < q_n < q_{n+1}. \tag{10.2}$$

Since the suitable fractions are irreducible, it follows from inequalities (10.2) that

$$\frac{p}{q} \neq \frac{p_n}{q_n}, \quad \frac{p}{q} \neq \frac{p_{n+1}}{q_{n+1}}.$$

It’s clear that

$$\left| \frac{p}{q} - \frac{p_n}{q_n} \right| = \frac{|pq_n - p_n|}{qq_n} \geqslant \frac{1}{qq_n},$$

$$\left| \frac{p}{q} - \frac{p_{n+1}}{q_{n+1}} \right| = \frac{|pq_{n+1} - p_{n+1}|}{qq_{n+1}} \geqslant \frac{1}{qq_{n+1}}.$$

These inequalities are still successful if we replace $q$ with the greater value of $q_{n+1}$ or $q_n$:

$$\left| \frac{p}{q} - \frac{p_n}{q_n} \right| > \frac{1}{q_{n+1} q_n} = |\Delta_n|,$$

$$\left| \frac{p}{q} - \frac{p_{n+1}}{q_{n+1}} \right| > \frac{1}{q_n q_{n+1}} = |\Delta_n|.$$

The meaning of the last two inequalities is as follows: the fraction $\frac{p}{q}$ is removed from each end of the segment $\left[ \frac{p_n}{q_n}, \frac{p_{n+1}}{q_{n+1}} \right]$ at a distance greater than the length of this segment $|\Delta_n|$. Delaying the segment $|\Delta_n|$ (Fig. 6) from points $\frac{p_n}{q_n}$ and $\frac{p_{n+1}}{q_{n+1}}$ to the left and right, we obtain a forbidden zone $AB$, in which the fraction $\frac{p}{q}$ cannot be located (points $A$ and $B$ are also forbidden). It is now clear that $\frac{p}{q}$ is a worse approximation for the number $\alpha$ than $\frac{p_n}{q_n}$. In fact,

$$\left| \alpha - \frac{p_n}{q_n} \right| \leqslant |\Delta_n|,$$

$$\left| \alpha - \frac{p}{q} \right| > |\Delta_n|.$$

Note that the converse theorem is not true, i.e., there are fractions that do not serve as suitable ones and yet give a better approximation for the number $\alpha$ than any fraction with a smaller value. For example, from the table on page 18 («Kvant», No. 1) it is clear that the approximations of the numbers $19/6$, $\frac{16}{5}$ and $\frac{13}{4}$ have this property. Therefore, the theorem proved does not mean that suitable fractions are better than others for approximating real numbers. But here are two horizontal strong theorems, which we will present without proof.

For a suitable fraction, the benefit coefficient $^*$) $\lambda = \frac{1}{2|q_n \alpha - p_n|}$ is greater than for any other fraction with a smaller value.

Finally, the most surprising thing: the converse theorem is also true, i.e. it has such a large coefficient of profitability $^*$) «Kvant», No. 1, p. 18.

32

SUBSCRIBE TO THE MAGAZINE ANNOUNCED
“QUANT” FOR 1971

«Kvant» is a popular science physics and mathematics journal of the USSR Academy of Sciences and the USSR Academy of Pedagogical Sciences. It is intended primarily for schoolchildren in grades 8–10. Among its readers are many teachers, especially those who teach clubs or elective classes in physics and mathematics, as well as students of pedagogical institutes. Older physics and mathematics lovers also read it with interest.

«Kvant» publishes articles and notes devoted to modern problems of science, as well as many different materials that expand and deepen school courses in physics and mathematics.

It contains a wealth of information for those preparing to enter college.

The regular sections of the magazine - “Quent’s Problem Book”, “Quant’s Laboratory”, “Applicant’s Workshop” - contain many interesting tasks and home experiments.

«Kvant» provides its readers with regular information about new books, about the work of physics and mathematics schools and clubs.

Among our authors are famous Soviet and foreign scientists, young scientists, and teachers. Schoolchildren can also report on their first discoveries, laboratory work or independently constructed devices on the pages of our magazine.

Subscription starts on September 1st. The price of the room is 30 kopecks. The cost of an annual subscription is 3 rubles 60 kopecks. Subscription index 70465.

33

One inductive method for proving inequalities

S. T. Berkolaiko,
S. B. Skating rink

The arithmetic mean and geometric mean theorem, which states that for any positive $x_1, x_2, \dots, x_n$ the inequality

$$\frac{1}{n} (x_1 + x_2 + \dots + x_n) \geq \sqrt{x_1 x_2 \dots x_n},$$

is one of those mathematical facts whose proofs are less known than their formulations. (Other examples of this kind: in arithmetic - the only factorization of a number into prime factors; in geometry - the theorem that the altitudes of a triangle intersect at one point.) Meanwhile, there are many different ways to prove this remarkable inequality, including elementary ones (for example, in [1] (solution to problem 268) 3 elementary proofs are given, and at the beginning of [5] 12 different proofs are proposed). This note provides another short proof by induction, which also works for other positive inequalities.

We must prove that

$$x_1 + \dots + x_n \geq n (x_1 \dots x_n)^{\frac{1}{n}}$$

(1)

for all integers $n \geq 2$ and positive $x_1, \dots, x_n$.

For $n=2$ this inequality looks like this:

$$x_1 + x_2 \geq 2 (x_1 x_2)^{\frac{1}{2}}$$

(2)

and immediately follows from the obvious inequality

$$(x_1^{\frac{1}{2}} - x_2^{\frac{1}{2}})^2 \geq 0.$$

Let us assume that inequality (1) is true for $n=k$ and prove it for $n=k+1$.

To do this, consider the following expression:

$$x_1 + x_2 + \dots + x_k + x_{k+1} + (k-1) (x_1 x_2 \dots x_{k+1})^{\frac{1}{k+1}}.$$

Divide this sum into two, $k$ terms, and estimate which of them, applying inequality (1) for $n=k$:

$$x_1 + x_2 + \dots + x_k \geq k (x_1 \dots x_k)^{\frac{1}{k}},$$

$$x_{k+1} + (k-1) (x_1 \dots x_{k+1})^{\frac{1}{k+1}} \geq k (x_{k+1} x_1^{\frac{k-1}{k+1}} \dots x_{k+1}^{\frac{k-1}{k+1}})^{\frac{1}{k}}.$$

We consider $(k-1) (x_1 x_2 \dots x_{k+1})^{\frac{1}{k+1}}$ as the sum of $(k-1)$ identical terms $(x_1 x_2 \dots x_{k+1})^{\frac{1}{k+1}}$.

36

In words, prove the required inequality only for $n=2$.

And if we prove the upward convexity of the function $\lg x$ (which is evidence of the proof of inequality (2)), then from our theorem, as one of the special cases, we obtain a theorem about the arithmetic mean and the geometric mean:

$$\lg \left( \frac{x_1 + \ldots + x_n}{n} \right) \leq \frac{\lg x_1 + \ldots + \lg x_n}{n},$$

i.e.

$$\lg \left( \frac{x_1 + \ldots + x_n}{n} \right) \leq \lg \left( x_1 \ldots x_n \right)^{\frac{1}{n}}, \quad \frac{1}{n} \left( x_1 + \ldots + x_n \right) \leq \left( x_1 \ldots x_n \right)^{\frac{1}{n}}.$$

In conclusion, we will provide a list of books in which you can read other proofs of the arithmetic mean and geometric mean theorem.

[1] D. O. Shklyarsky, N. N. Chentsov, I. M. Yaglom, Selected problems and theorems of elementary mathematics, Part I, M., “Nauka”, 1965.

Consider the first of three proofs given in this book (“By Reverse Indication”).

[2] Kretschmar, Algebra Problem Book. M., “Science”, 1968.

[3] E. Beckenbach and R. Belman, Introduction to Inequalities, M., “Mir”, 1965.

[4] G. G. Hardy, D. E. Littelwood, G. Polyana, Inequalities, IL, 1948.

[5] E. Beckenbach and R. Belman, Inequalities, M., “World”, 1965.

Exercises

1. What inequality results if we apply the theorem to the function $y=x^2$? Try to prove this inequality directly.

2. Derive from the general theorem inequalities a)-e). What functions need to be proven to be convex for this?

3. Come up with a few more examples of convex functions and write down the inequality that follows from Theorem 1 when applied to these functions.

4. The function $f$ is defined on the interval $[a, b]$ and has an inverse**) function $g$. Prove that if $f$ is convex upward, then $g$ is convex downward, and vice versa.

5. The function $f(x)$, defined on the interval $[a, b]$, is convex upward. Prove that for any points $x_1, \ldots, x_n$ lying on the segment $[a, b]$ and any positive points $a_1, \ldots, a_n$ the following inequality holds:

$$\frac{a_1 f(x_1) + \ldots + a_n f(x_n)}{a_1 + \ldots + a_n} \leq f\left(\frac{(a_1 x_1 + \ldots + a_n x_n)}{a_1 + \ldots + a_n}\right).$$

(Note that this problem is a generalization of the previously proven theorem, which is obtained for $a_1=a_2=\ldots=a_n=1$.)

Note. To solve this problem, you can use the same technique that we use when proving the theorem.

*) You can take the logarithm to any base greater than one.
**) See «Kvant», No. 1, page 22.

39

ka 9 will be inside the ball. The electrode ball is connected to the brush with a bolt and secured by ball 11, which has a threaded hole.

The lower roller, and therefore the tape, can be turned by hand. But we use an asynchronous single-digit electric motor from an electric player 12 and connected it to the lower roller with a clutch 13.

The electric motor is turned on, the tape runs along the rollers. Along the way, from friction with brush 8, it picked up and deposited electric charges on the ball conductor. The more the tape has to rotate, the higher the potential of the ball will be. But there is a limit here. The fact is that at high electric field strength near the ball, the impact becomes electrically conductive, and charges begin to drain from the ball. The ball’s potential stops growing.

We can calculate to what potential we can charge the ball. The field voltage on the surface of the ball is calculated by the formula $E = \frac{V}{R}$, where $V$ is the potential of the ball, and $R$ is its radius. If $R = 5$ cm, and $E$ for exposure at atmospheric pressure is equal to 30 kV/cm, then the ball can be charged up to 150 thousand volts.

This calculation is correct only for an ideal smooth ball, located very far from all other conducting objects. Therefore, the voltage created by our generator will be lower than the calculated one.

If you manage to make a larger ball, then you can charge it to a higher potential. Above only means that the ball should be very smooth and even.

Now do some experiments with the model.

First of all, determine the sign of the ball’s charge. How to do this is clear. You just have to remember that an ebonite rod rubbed against fur is electrified negatively, and a glass rod rubbed against silk is positively electrified.

Determine how many full revolutions the tape must make in order for the high-voltage electrode to be fully charged. To do this, place a clearly visible mark on the tape and count how many full revolutions the tape makes until the electrode potential increases to its maximum value. Please note that the “generator performance” depends significantly on the position of the upper brush.

If the brush is positioned so that it is close to the place where the tape enters the ball, then the charges from the tape will not be completely removed, and you will have to wait a long time until the high-voltage electrode is charged. By changing the position of the upper brush, find one in which the high-voltage electrode will be fully charged at a minimum number of revolutions of the belt.

Our model uses nylon tape. And Van de Graaff used silk. In the electrostatic generator of the Kharkov Institute, the charging tape was made of rubberized fabric. Try making a charging tape from a different material.

Our charging brush is made from a polystyrene plate; it can be made from limited stack or copper. If you use a wire brush, ground it. The generator begins to work better. Why?

Don’t despair if you fail at first. Remember that even the best existing electrostatic generators produce voltages that are only a third of what they are designed for. All the reasons for this are not yet clear. So there is something to think about and something to invent.

For those who want to learn more about electrostatic generators, we recommend reading the book “Electrostatic accelerators of charged particles”, Gosatomizdat, 1963.

40

PROBLEM WORKER

Chapter 1

Fig. 1.

F42. The rope will be thrown over the block, with part of the rope lying on the table and part on the floor. After the rope was released, it began to move. Find the speed of steady uniform motion of the rope. The height of the table is h.

F43. Find the pressure at the center of a liquid of radius R if the liquid is incompressible and has a density ρ.

Weighted Physics Olympiad, 1969

F44. Two dolphins swim towards each other. One of them makes a sound of frequency ω. What frequency does the other dolphin hear if the speeds of the dolphins relative to the water are the same and equal to v? Speed ​​of sound in water and.

Weighted Physics Olympiad, 1968

F45. A spherical capacitor filled with a dielectric and charged to a certain potential difference is discharged through its dielectric. What will be the magnetic field of the discharge currents in the space between the spheres?

F46. A cube falls onto a ball from a height of 1 m, and then jumps almost 1 m. To what height does the ball jump? To what height will the ball jump if exactly the same ball falls on it from a height of 1 m?

G. L. Komkin

F47. If the ABC process (Fig. 1) is performed on an ideal gas, then the amount of heat Q is imparted to it. What amount of heat is imparted to the gas during the ADC process?

Moscow City Physical Olympiad, 1970

M36. Prove that it is impossible to arrange seven lines and seven points on a plane so that three lines pass through each point and three points lie on each line.

M37. A certain number is inscribed in each cell of an infinite sheet of checkered paper so that the sum of the numbers in any square (the sides of which follow the grid lines) does not exceed one in absolute value. Prove that then there exists a number c such that the sum of the numbers in any rectangle (whose sides go along the lines

41

mesh) no more than $c$; in other words, that the sums of numbers in all rectangular iks are limited. Prove that it is possible to take $c=4$. Perhaps you can incriminate this estimate (for example, prove that our statement is true for $c=3$ or even for $c=2$)?
Yu. I. Ionin

M38. A circle constructed at the height $AD$ of a right triangle $ABC$ as a diameter intersects leg $AB$ at point $K$, and leg $AC$ at point $M$. Line segment $KM$ intersects height $AD$ at point $L$. It is known that the segments $AK$, $AL$ and $AM$ form a geometric progression (i.e. $AK/AL=AL/AM$). Find the acute angles of triangle $ABC$ (Fig. 2).
L. M. Lopovok

Fig. 2.

M39. Prove that non-negative integers $x, y$ satisfy the equation
$$x^2 - mxy + y^2 = 1$$
(where $m$ is a given integer greater than one) if and only if $x$ and $y$ are adjacent numbers of the sequence

$$\varphi_0 = 0, \quad \varphi_1 = 1, \quad \varphi_2 = m,$$
$$\varphi_3 = m^2 - 1, \quad \varphi_4 = m^3 - 2m,$$
$$\varphi_5 = m^4 - 3m^2 + 1, \quad \dots,$$
in which $\varphi_{k+1} = m\varphi_k - \varphi_{k-1}$ for all $k \geqslant 1$.

For example, all solutions to the equation $x^2 - 3xy + y^2 = 1$ for the number $0 \leqslant x < y$ are pairs $(0, 1)$; $(1, 3)$; $(3, 8)$; $(8, 21)$ adjacent members of the sequence $0, 1, 3, 8, 21, 55, \dots$ defined by the conditions $\varphi_0 = 0, \quad \varphi_1 = 1, \quad \varphi_{k+1} = 3\varphi_k - \varphi_{k-1}$ for all $k \geqslant 1$. (This red fact was used in the work of Yu. Matiyasevich related to Hilbert’s 10th problem, which was discussed in the previous issue «Kvant».)

M40. Find the amount
$$1 \cdot n + 2 \cdot (n - 1) + 3 \cdot (n - 2) + \dots$$
$$\dots + (n - 1) \cdot 2 + n \cdot 1.$$

Try solving the following, more general problem: find the sum
$$S_n, k = [1 \cdot 2 \dots k] \times$$
$$\times [n(n - 1) \dots (n - k + 1)] +$$
$$+ [2 \cdot 3 \dots (k + 1)] \times$$
$$\times [(n - 1)(n - 2) \dots (n - k)] +$$
$$+ [3 \cdot 4 \dots (k + 2)] \times$$
$$\times [(n - 2)(n - 1) \dots (n - k - 1)] + \dots$$
$$\dots + [(n - k)(n - k + 1) \dots (n - 1)] \times$$
$$\times [(k + 1)k \dots 2] +$$
$$+ [(n - k + 1)(n - k + 2) \dots n] \times$$
$$\times [k(k - 1) \dots 1].$$

V. N. Berezin

42

M3. (a) On figure 1, and the plane is covered with heel squares of flowers. The centers of squares of the same color are located at the vertices of the square grid. With what number of colors is a similar filling of the plane possible?

(b) On figure 1, b the plane is covered with hexagons of families and colors so that the centers of hexagons of the same color form the vertices of a lattice of identical regular triangles. With what number of colors is a similar construction possible?

Notes. In the first problem, the number of colors can be one (all squares are the same color) or two (like on a chessboard). In the second problem you can easily find solutions with one color and with a third color. It is advisable to give a complete solution to the problems, i.e., describe all colorings that satisfy the specified conditions. However, please send incomplete solutions if they seem interesting to you. Think, for example, is there a solution with thirteen colors in the second problem?

Solution*)

Now we will consider correct only such filling of the plane with squares (or hexagons) in which the grid corresponding to any one color has the same dimensions and directions of the sides of the squares (or triangles) as the grid corresponding to any other color. In other words, all meshes must be obtained from each other in parallel. Of course, different meshes cannot be painted with the same color. The solution to the problem for general cases (squares and hexagons) is similar, and we will consider both cases at once.

1. Let us first prove that if the filling plane is in the indicated way, then the number of colors is equal to $k^2 + l^2$ in the case of squares and $k^2 + kl + l^2$ in the case of hexagons, where $k, l$ are non-negative integers (but not equal to zero at the same time)**).

*) For the beginning of solving this problem, see «Kvant» No. 7, page 54.
**) There are other formulas that represent the same sets of numbers, for example, $k^2 - kl + l^2$ for hexagons,

43

The unit of length is the distance between the centers of two adjacent squares or hexagons.

Let’s draw a grid with thick black lines passing through the centers of squares or hexagons of the same color, say, red (Fig. 2, 3).

In the case of hexagons, we will draw lines in only two directions, so that the grid will not consist of regular triangles, but of rhombuses.

Let $ABCD$ be one square or one diamond of the grid. Let us derive a formula for its area.

In the case of a square, we draw straight lines through the points $A$ and $B$, parallel to the sides of the surrounded squares, and denote the point of their intersection as $M$. The lengths $AM=k$ and $BM=l$ are integers (one of them can be zero). On figure 1 $k=3$, $l=2$. Then $AB=\sqrt{k^2+l^2}$ and the area of ​​$ABCD$ is $k^2+l^2$.

In the case of a rhombus, we draw straight lines through the points $A$ and $B$, parallel to the apsphemas of the hexagons, and denote the point of their intersection as $M$. Angle $AMB$ may turn out to be equal to $120^\circ$ or $60^\circ$. Let’s draw straight lines so that it is equal to $120^\circ$. The lengths $AM=k$ and $BM=l$ are integers (one of them can be zero). On figure 2 $k=1$, $l=2$. Then $AB=\sqrt{k^2+kl+l^2}$, and the area of ​​the rhombus is $\frac{\sqrt{3}}{2}(k^2+kl+l^2)$.

We will prove that the number of colors participating in the coloring is equal to the ratio of the area $ABCD$ to the area of ​​one circumferential square (case (a)) or hexagon (case (6)) and is therefore equal to:

in the case of squares $k^2+l^2$,

in case of hexagons $k^2+kl+l^2$

(since the area of ​​one hexagon is $\frac{\sqrt{3}}{2}$).

This follows immediately from the next lemma.

Main lemma. Part $ABCD$, painted with whatever color is involved in the coloring, either represents one square (in case (a)), corresponding to a hexagon (in case (6)), or consists of pieces (for red - four, for other colors - two), from which the same square or hexagon can be folded.

The proof of the lemma is not difficult, and we invite the reader to carry out

44

Fig. 4. The plane is filled with identical figures with an area of ​​13 squares. Try to find an “elementary” piece of a plane filled in this way and glue a torus from it, as we did with a square.

Note. You need to select 13 figures, from them you need to form a polygon that will not be a square, but nevertheless can easily be glued into a torus. This should be done with a sheet of glue paper.

It’s on its own. Let us only note that the coloring of all squares (rhombuses) of the bold grid is the same, that is, if you cut out a square (rhombus) $ABCD$ from the plane and superimpose it, say, on an adjacent square (rhombus), then part $ABCD$, painted with any color, will exactly match the part of the neighboring square (rhombus), painted with the same color.

There is another way to present this proof, more beautiful, but requiring some imagination. Let us first restrict ourselves to the case of a square grid. Let us express a square $ABCD$ from the plane and make a tube from it - a cylinder, the colored side on the outside, compatible from the sides $AB$ and $DC$. This tube is delimited by two circles derived from sides $AB$ and $DC$. Let’s glue these circles together (by combining point $A=D$ with point $B=C$). For this, the paper tube will have to be solidified, but we still consider its entire painted surface as a single whole, not divided into parts by folds. The surface area of ​​the resulting figure is $k^2+l^2$, and the part of it painted with any of the coloring colors is a square of size $1 \times 1$. We advise you to do all this practically with a square sheet of paper, coloring it with a fifth or more colors.

In the case of hexagons, we will arrive at a similar result if we mark a rectangle in the same way, having one side common with the rhombus $ABCD$ and the other equal to the height of the rhombus.

You can fill the plane with other equal figures in which the areas shaded with different colors are equal. For example, in the solution to problem (a), sent from Kyiv (Belinsky lane 8, apt. 32, the author’s last name is not indicated), it is proposed to fill the plane with figures made up of two squares on the sides $k$ and $l$. Let’s say for $k=2$ and $l=3$ (13 colors) the figure will be the same as in figure 4.

II. Now let us be given the number $m=k^2+l^2$ or $n=k^2+kl+l^2$. Let us show that the plane can be filled in accordance with the conditions with squares of $m$ colors or hexagons of $n$ colors.

Let’s fill the plane with equal squares or regular hexagons and start cutting them out as follows.

Let’s paint one of them red. Let’s count $k$ squares (hexagons) from it in one direction, then turn it by $90^\circ$ for squares and $60^\circ$ for hexagons and count $l$ squares (hexagons) in a new direction, and we will also paint the square (hexagon) in which we arrive in red. On the segment connecting the centers of two red squares (hexagons), as on the side, we will construct a square (a) or a regular triangle (6). By attaching equal squares (regular triangles) to it, we get the centers of all squares (hexagons), which must be painted red; moving all the soybeans in parallel

45

A collection of red squares (hexagons), each time we will get a new collection of unpainted squares (hexagons) and paint it with a new color until we have painted the entire plane. According to what was proven above, the number of colors will be equal to $k^2+l^2$ in case (a) and $k^2+kl+l^2$ in case (b).

III. What natural numbers can be represented as $k^2+l^2$ or $k^2+kl+l^2$? To write down the first few of these numbers, it is convenient to create two tables: table 1 for $k^2+l^2$, table 2 for $k^2+kl+l^2$.

The numbers below the diagonal repeat those already written and do not need to be written. Some numbers appear in the table twice; the corresponding cells are highlighted. This means that with such a number of colors there are two significantly different ways of filling the plane. Now it’s easy to find and write these numbers in ascending order.

First table: 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, …
Second table: 1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25, 27, 28, …

Suppose we have already written down these numbers to some point and are looking for the next largest number.

The red lines drawn on the first table help to do this. To explain how they are carried out, we note that in the first table each number is equal to the square of the distance from the center of the cell in which it stands to point 0 in the upper left corner (we take the side of the cell as a unit of length). Therefore, if we draw several circles with center 0, then they will divide our numbers (that is, the centers of the cells in which they stand) into groups in ascending order. If you try to draw similar lines in the second table by hand, it may seem that they are straight. But this, of course, is not true. In fact, these graphs correspond to the form

$$k^2+kl+l^2=c=\text{const}$$

in a coordinate system with origin 0 and axes going: axis $k$ - to the right, axis $l$ - down. Moving on to another pair of variables: $x=k+l$, $y=k-l$, you can see that these are ellipses elongated in the direction of the $y^*$ axis).

In a sense, we have the answer, but perhaps it can be simplified. For example, if in some other problem we get the answer: all numbers of the form $k^2+l^2+m^2+n^2$, two $k$, $l$, $m$, $n$ are integers, then it can be rewritten as follows: any non-negative integer, since all natural numbers can be represented in this form. It may be in our sequence

*) Those who read the book by N.B. Vasiliev and V.L. Gutenmacher “Straights and Curves”, of course, noticed that the red lines are the level lines of the functions $k^2+l^2$ and $k^2+kl+l^2$ on the plane $(k, l)$.

46

Are all natural numbers included, starting from a certain place? To prove that this is not so, you can use the dotted line system.

Let us draw a red circle with center 0 of radius $n$ in the first table. The centers of all cells containing numbers less than or equal to $n^2$ lie inside or on the edge of a sector of this circle with a central angle of $45^\circ$. Therefore, all such cells lie inside the figure; they are obtained from this sector if we add to it a strip of width 1 bordering it. The area of ​​this figure is less than $\frac{\pi n^2}{8} + 3n + 4$.

Hence, among the first $n^2$ natural numbers there are $\frac{\pi n^2}{8} + 3n + 4$, representable as $k^2 + l^2$. For large $n$ the second number of the first is approximately $\frac{\pi}{8}$. In fact, since some numbers in the table are equal, there are even fewer numbers of the form $k^2 + l^2$. It is easy to see that the fraction of numbers representable as $k^2 + kl + l^2$ is even smaller.

M4. Given the segment $AB$. Find points $C$ on the plane of the set such that in triangle $ABC$ the median drawn from vertex $A$ is equal to the altitude drawn from vertex $B$.

Solution

The editors have received many letters with solutions to this problem, but almost all of them are incomplete. Many readers have forgotten that when finding the geometric locus of points (GLP), it is necessary to clearly verify two things: 1) all points of the found set satisfy the conditions; 2) all points satisfying the conditions belong to the found set. Requirement 1) a lot of things were not taught. We will present two solutions to the problem: one is purely geometric, the second is using the coordinate method.

First decision. Let’s start with 2). Let us be given a segment $AB$ and a path $C$—a point satisfying the conditions, $AD$—the median of triangle $ABC$. Let us complete the triangle to a parallelogram by extending the median $AD$ to the point $E$ so that $AD=DE$. There are two possible cases here: the angle $AEB$ is acute or obtuse.

(a) Let the angle $AEB$ be acute (Fig. 5, a). Let’s draw $BF \perp AC$, $AK \parallel BF$, then in the right triangle $AEK$ the leg $AK$ is equal to half the hypotenuse $AE$, therefore $\angle AEB=30^\circ$.

47

(6) Let angle AEB be of type (Fig. 5, 6). Carrying out BF ⊥ AC, AK || BF, we obtain, similarly to case (a), that ∠AEK=30°, therefore ∠AEB=150° (the difference from case (a) is that now points K and B lie on opposite sides of E).

So, if C is the desired point, then segment AB is visible from point E at an angle of 30° or 150°. As is known, all such points E are located on two circles O₁ and O₂, which are divided by the chord AB into arcs of 300° and 60° (Fig. 6, a), and, therefore, all points C are on the same circles O’₁ and O’₂, obtained from O₁ and O₂ by parallel transfer to the segment l=AB in the direction from B to A (Fig. 6, 6).

Now we prove that any point M of circles O’₁ and O’₂ belongs to the required set of points. Let M be an arbitrary point of one of these circles; then by drawing MK=AB, MK||AB, we get point K on one of the circles O₁ or O₂ (Fig. 7, a, 6). On figure 7, a’ BF ⊥ MA, AL||BF, AL=BF, then (from ΔAKL) AL=1/2 AK, i.e. the point M satisfies the conditions. Similarly on figure 7, 6 BF ⊥ MA, AL=BF, AL||BF, ∠AKB=150°, ∠AKL=180°−∠AKB=30°, i.e. AL=1/2 AK, and point M also satisfies the conditions. So, all points O’₁ and O’₂, except points N and A, satisfy the conditions.

Note that many readers who solved the geometric problem received parts of circles O’₁ and O’₂ as an answer. (Figure 8, a was obtained, for example, by V. Mashanov from the city of Grodno, figure 8, 6 by S. Ivanenko from the city of Fedosia and figure 8, by A. Alyaeva from the Penza region.) The correct solution (although slightly different from the one given here) was added by L. Stolyarov from the city of Penza.

Second solution. (A slight simplification of the solution sent by A. Grishkov from Tomsk.) Let us introduce a rectangular coordinate system with the origin at point A, let point B have coordinates (2; 0), and the desired point C have coordinates (x; y). Let AF be the median in triangle ABC, BK ⊥ AC (Fig. 9). It is easy to show that point F has coordinates (x+2/2; y/2). Then AF²=(x+2/2)²+y²/4. According to the conditions BK²=AF², therefore

48

Fig. 8, a. Fig. 8, b. Fig. 8, p.

from the similarity of triangles AKB and ACD it follows that $\frac{BK^2}{AK^2} = \frac{CD^2}{AD^2}$ or
$$\frac{\left(\frac{x+2}{2}\right)^2 + \frac{y^2}{4}}{4 - \left[\left(\frac{x+2}{2}\right)^2 + \frac{y^2}{4}\right]} = \frac{y^2}{x^2}.$$

Transforming (1), we get
$$y^4 + (2x^2 + 4x - 12)y^2 + (2x + x^2)^2 = 0.$$

This is the equation connecting the coordinates of the required points. Some readers further wrote that it defines a fourth-order curve, which is quite difficult to draw.

In fact, it turns out that the left side of equation (2) is factorized:
$$[(x+1)^2 + (y+\sqrt{3})^2 - 4] [(x+1)^2 + (y-\sqrt{3})^2 - 4] = 0.$$

Fig. 9. Fig. 10.

49

You can guess about it, for example, like this.

Let us introduce the notation: $y^2 = z$. Then (2) is a quadratic equation with respect to $z$. Let’s factorize its left-hand side. To do this, let’s find roots (2).

$$z_{1,2} = \frac{12 - 2x^2 - 4x \pm \sqrt{(12 - 2x^2 - 4x)^2 - 4(2x + x^2)^2}}{2} =$$

$$= \frac{12 - 2x^2 - 4x \pm \sqrt{48(3 - x^2 - 2x)}}{2} = 6 - x^2 - 2x \pm 2\sqrt{3(3 - x^2 - 2x)} =$$

$$= (\sqrt{3 - x^2 - 2x} \pm \sqrt{3})^2.$$

Equation (2) can now be represented as follows:

$$\left| z - (\sqrt{3 - x^2 - 2x} + \sqrt{3}) \right| \left| z - \sqrt{3 - x^2 - 2x} - \sqrt{3} \right|^2 = 0$$

or

$$\left| y^2 - (\sqrt{4 - (x + 1)^2} + \sqrt{3}) \right| \left| y^2 - (\sqrt{4 - (x + 1)^2} - \sqrt{3}) \right|^2 = 0.$$

(see figure 10, where one of these sets is red and the other is green).

Let us transform (4) further:

$$\left| y - \sqrt{4 - (x + 1)^2} + \sqrt{3} \right| \left| y + \sqrt{4 - (x + 1)^2} - \sqrt{3} \right| [\dots] [\dots] = 0;$$

hence we get (3)*.

Ninth-grader P. Kriksunov from Kiev and some other readers who wrote us solutions to this problem noticed that the following more general problem can be solved in a similar way: find a set of points $C$ such that in triangle $ABC$ the ratio of medians $AD$ to height $BF$ is equal to the given number $k$ (either of the two solution methods described above is suitable).

M5. In the set $E$, consisting of $n$ elements, $m$ different subsets (different from $E$ itself) are identified so that for every two elements from $E$ there is exactly one of the given subsets that contains both of these elements.

Prove that $m \geq n$. In what cases is a solution possible?

Solution

From readers’ letters one can judge that this task is extremely difficult, but interesting. Strictly speaking, here we are dealing with two problems: 1) prove that $m \geq n$, 2) in what cases is a solution possible?

As for the first problem, only $A$ solved it completely. Creatures from Leningrad. His proof is based on one of the basic theorems of linear algebra, which states that if there are more $n$-vectors than $n$, then they are linearly dependent.

For those who are familiar with this concept, it will be interesting to come up with such a proof. As for the second problem, it is shown, and this is not surprising, since it will be shown below that it is related to one known, but unsolved mathematical probleme.

For ease of presentation, some readers suggested other formulations of the problem. Here are two of them.

*) Equation $(x - a)^2 + (y - b)^2 = c^2$ defines a circle with center at point $(a; b)$ of radius $c$ (see, for example, I. M. Gelfand, E. G. Glagoleva, A. A. Kirr ilov, Method of coordinates, “Nauka”, 1968).

50

Fig. 11.

a) Students from the same school often gather in groups and go out to eat ice cream. After such a visit, they quarrel so much that no two of them eat ice cream together after that. By the end of the year, they found out that in the future they could only go to the ice cream parlor one by one. Prove that if the number of students visited by this time was more than 1, then it is not less than the number of students in the school.

6. Let there be $n$ points. Through every two points there is exactly one straight line, and each straight line contains no more than $(n-1)$ points. We need to prove that the number of lines is at least $n$.

Are these tasks equivalent to the original one?

In any case, it is convenient, when thinking about this problem, to imagine the elements as “points”, and the bases as “lines”, passing through these points and doing for yourself figure like our figure 11 and 12. (In general, it is impossible not to ensure that all the lines are straight; as problem M36, figure 12 shows, it is impossible to correct it so that the red line is straight, so the problem 6) is not equivalent to the original one.)

Next, we present the solution to the problem, following the instructions of the author of the problem, N. Bourbaki*), and also, for convenience, we rewrite the conditions of the problem.

Given $n$ different elements and has a system $m$ of sets composed of these elements, and:

1. no set of our system contains all the elements at once;
2. every two of the given $n$ elements occur in one of the set of the system;
3. if two elements occur in one of the sets, then they do not appear together in any of the other sets of the system.

Let us prove that $m \geq n$.

Let us give some example of such arrangement of elements. Let $n=5$ and there be elements: $a, b, c, d, e$. Let’s create such a system of a set of these elements;

$(a, b), (a, c, e,), (b, e), (b, c), (b, d), (a, d), (d, e), (c, d)$.

Obviously, it satisfies conditions 1), 2), 3). Here $m=8$, and by the way $8 \geq 5$.

To make the proof more clear, we will sometimes refer to this example.

Proof. Note that $n>2$ and that it is sufficient to prove the inequality $m \geq n$ for a system of sets containing at least two elements.

1. The system consists of at least two sets, then by condition 2) this set would contain all the elements at once, which contradicts conditions 1).

*) See N. Bourbaki, Set Theory, Mir, M., 1965, p. 220.

51

2. Each element is included in at least two sets of the system. If an element were included in only one set, then by virtue of 2) it must contain all $n$ elements, which contradicts 1).

3. One and the same element cannot be included in all sets of the system at once. Let some element, call it $x$, be included in all sets of the system. Then, by condition 3), no two sets contain identical elements, with the exception of the element $x$. Therefore, no two elements other than $x$ occur in any of the set, but this contradicts 2).

4. Let us associate each element with the number of the set of the system in which it is included, that is, we count how many times it is repeated in this system. In the example, the element $a$ is mapped to the number 3, the element $b$ to 4, etc.

What set of the system is comparable to the number of elements it contains? In the example of the first set the number 2 is associated, the second set is associated with 3, etc.

The sum of all numbers corresponding to elements is equal to the sum of all numbers corresponding to sets. In the example $3+4+3+4=2+3+2+2+2+2+2+2=17$.

In fact, if we consider two elements to be different when they are included in different sets, then both sum to the number of elements of all sets of the system.

5. Notation. Let’s take one of those elements that correspond to the smallest number, i.e., which is included in the smallest number of the set of the system. In the example, we can take either $a$, or $c$, or $e$; let’s take $a$. Let us denote this element by $a_n$, and the number of the set in which it is included by $k_n$. In the example $a_5=a$, $k_5=3$. By virtue of paragraphs. 2 and 3 we have $2 \leqslant k_n < m$.

The sets that include $a_n$ will be denoted in some order by $A_1$, $A_2$, …, $A_{k_n}$, and the rest by $A_{k_n+1}$, …, $A_m$. In the example $A_1=(a, b)$, $A_2=(a, c, e)$, $A_3=(a, d)$, $A_4=(b, e)$, …, $A_8=(c, d)$.

Consider the first $k_n$ sets $A_1$, $A_2$, …, $A_{k_n}$. Reasoning in the same way as in point 3, we see that no two of them contain the same elements, with the exception of $\dot{a}_n$. Therefore, we can take one element from each of these sets and denote them respectively by $a_1$, $a_2$, …, $a_{k_n}$. We denote the remaining elements in some order by $a_{k_n+1}$, $a_{k_n+2}$, …, $a_n$. In the example $a_1=b$, $a_2=c$, $a_3=d$, $a_4=e$; then $A_1=(a_1, a_5)$, $A_2=(a_2, a_4, a_5)$, $A_3=(a_3, a_5)$, $A_4=(a_1, a_4)$, $A_5=(a_1, a_2)$, $A_6=(a_1, a_3)$, $A_7=(a_3, a_4)$, $A_8=(a_2, a_3)$.

Now let us denote the numbers corresponding to the elements $a_1$, $a_2$, …, $a_{k_n}$, …, $a_{n-1}$ in the same order by $k_1$, $k_2$, …, $k_{n-1}$. For example, that the element $a_n$ corresponds to the number $k_n$, and it is the smallest of all the numbers $k_1$, $k_2$, …, $k_{n-1}$, $k_n$.

Finally, let us denote the numbers corresponding to the sets $A_1$, $A_2$, …, $A_m$ in the same order by $s_1$, $s_2$, …, $s_{k_n}$, …, $s_m$.

Let us once again pay attention to how we numbered the elements and sets.

First, $k_n$ is the smallest of the numbers $k_1, k_2, ..., k_{n-1}$.

Secondly, $k_n$ is the number of the last of the sets that contain the element $a_n$, and, thus, the element $a_n$ is not included in the sets $A_{k_n+1}$, …, $A_m$.

The set $A_i$ contains the element $a_i$, but does not contain the elements $a_j$ if $1 \leqslant i \leqslant k_n$, $1 \leqslant j \leqslant k_n$ and $i \neq j$. In addition, according to paragraph 4, $k_1 + \dots + k_n = s_1 + \dots + s_m$.

52

6. If the element $a_i$ does not belong to some set $A_j$, then $k_i \geqslant s_j$. Indeed, let the set $A_j$ not contain the element $a_i$ and consist of $s_j$ different elements. then the element $a_i$ must occur with each of these elements in some of the remaining sets of the system. On the other hand, no two of these elements can ever occur in these sets, since they have already occurred in $A_j$. Therefore, the number of sets in which the element $a_i$ is not less than $s_j$.

7. Consider the first $k_n$ set $A_1, A_2, \dots, A_{k_n}$ and the first $k_n$ elements of $a_1, a_2, \dots, a_{k_n}$. They are chosen in such a way that each set $A_i$ contains an element $a_i$ with the same number, but does not contain elements with other numbers, then, according to paragraph 6, $s_1 \leqslant k_2, s_2 \leqslant k_1$ if $k_n = 2$ and

$$\begin{align*} s_1 &\leqslant k_2, \quad s_2 \leqslant k_1, \quad \dots, s_{k_n} \leqslant k_1, \\ s_1 &\leqslant k_{k_n}, \quad s_2 \leqslant k_{k_n}, \quad \dots, s_{k_n} \leqslant k_{k_n-1}, \end{align*}$$

if $k_n > 2$.

In the example $k_n = 3$ and

$$\begin{align*} 2 &= s_1 \leqslant k_2 = 3, \quad 3 &= s_2 \leqslant k_1 = 4, \quad 3 &= s_3 \leqslant k_1 = 4, \\ 2 &= s_1 \leqslant k_3 = 4, \quad 3 &= s_2 \leqslant k_3 = 4, \quad 3 &= s_3 \leqslant k_2 = 3. \end{align*}$$

8. Adding up all the inequalities, we get that

$$(k_n - 1)(s_1 + s_2 + \dots + s_{k_n}) \leqslant (k_n - 1)(k_1 + \dots + k_{k_n})$$

or

$$s_1 + s_2 + \dots + s_{k_n} \leqslant k_1 + \dots + k_{n}.$$

9. Teller we can prove the inequality $m \geqslant n$ required in the problem. Let’s assume that $m < n$. Let’s compare two amounts

$$S = (s_1 + s_2 + \dots + s_{k_n}) + s_{k_n+1} + \dots + s_m$$

And

$$K = (k_1 + k_2 + \dots + k_n) + k_{k_n+1} + \dots + k_n.$$

Note that we have renumbered the set in such a way that the element $a_n$ does not belong to the set $A_{k_n+1}, \dots, A_m$; this means $s_{k_n+1} \leqslant k_n, \dots, s_m \leqslant k_n$ and even more so $s_{k_n+1} \leqslant k_{k_n+1}, \dots, s_m \leqslant k_m$, since $k_n$ is the smallest of all numbers $k_i$. In this case, since $m < n$, we get: $k_{k_n+1} + \dots + k_n > s_{k_n+1} + \dots + s_m$, but then $S < K$, and this contradicts item 4.

The proof that $m \geqslant n$ is complete.

10. Let’s try to find out in what cases equality is possible. If $m = n$, then from items 8, 9 and 4 it follows:

$$k_1 + \dots + k_{k_n} + \dots + k_n = s_1 + \dots + s_{k_n} + \dots + s_n.$$

Obviously, for this it is necessary that the equality

$$k_1 + \dots + k_{k_n} = s_1 + \dots + s_{k_n}$$

and all the inequalities from paragraph 8 were reduced to equalities. Since $k_n$ is the smallest of $k_i$, we have

$$s_{k_n+1} = \dots = s_n = k_{k_n+1} + \dots + k_n.$$

Next we consider two cases.

(a) $k_n = 2$. In this case, as is easy to see, the following set system is possible (Fig. 9): $(a_n, a_1), (a_n, a_2, a_3, \dots, a_{n-1}), (a_1, a_2), (a_1, a_3), \dots, (a_1, a_{n-1})$. For any $n$ it satisfies the conditions of the problem.

(b) $k_n > 2$. In this case, we obtain that all inequalities in paragraph 7 must be