[The problem of representing the maximum number as a sum]

24

TASKS

1. Let every boy be friends with no less than $m$ girls, and every girl be friends with no more than $m$ boys ($m$ is an arbitrary natural number). Prove that in this case the conditions of the matchmaking theorem are satisfied.

2. Schoolchildren solved problems in a circle. It turned out that everyone solved 4 problems and each problem was solved by four schoolchildren. Prove that it is possible to organize the analysis of a problem so that each student solves exactly one problem and so that all problems are analyzed (one time).

3. A transport network is given. The set of vertices that contain an output but do not contain an input is called a network cut. The capacity of the cut $B$ is the number $c(B)$, equal to the number of blows included in $B$. If $\phi$ denotes flow, then $|\phi|$ will denote the magnitude of the flow. Prove that for any flow $\phi$ and any cut $B$ the following transformation is true: $|\phi| \leq c(B)$.

4. A cut $B$ is called minimal if its capacity $c(B)$ is the smallest among the capacities of all cuts. Using the Ford-Folkerson algorithm, deduce that the throughput of the minimum cut is equal to the maximum flow - max $|\phi| = \min c(B)$ (Ford-Folkerson theorem).

5. Check that if $\phi$ is a maximal flow, then the cut obtained by unifying all unlabeled vertices (labels are made based on the flow $\phi$ using the Ford-Falkerson method) is minimal.

6. Prove that the union and intersection of any two minimal cuts is again a minimal cut.

7. Prove that a cut of unlabeled vertices (for a maximum flow) is the union of all minimal cuts. Deduce from this that this cut does not depend on the maximum cut used to make the flows.

LITERATURE

1. A. Kofman, R. Faure, Will engage in operations research, “World”, 1966.
2. K. Berge, Graph theory and its application, IL, 1962.
3. L. Ford, D. Folkerson, Flows in Networks, World, 1966.
4. O. Ore, Graph Theory, Hayka, 1968.
5. D. Gale, Theory of linear economic models, IL, 1963.

PARIS OF MATHEMATICS AND PHYSICISTS

In Paris, many buildings are associated with the memory of outstanding scientists of past centuries. Further, Louver, which was once a stronghold of kings, just before the revolution of 1789 became a meeting place for academicians. Although later, under Napoleon I, Louver became a museum, but even then some scientists were quartered there. A letter from Legendre has been preserved, in which this mathematician begged to be accommodated in the old part of the palace.

There are streets in Paris named after mathematicians, physicists and astronomers, and not all of these scientists are French. These names are: Legendre, Reaumore, Pascal, Pierre Curie, Marie Curie, Lambert, Buofon, Franklin, Carnot, Arago, Descartes, Leibniz…

The phrase “The number $z$ is the greater of the two numbers $x$ and $y$” can be written using the formula as follows:

$$z = \frac{1}{2} (|x - y| + x + y).$$

How to write the phrase “The number $u$ is the most of the three numbers $x, y$ and $z$”?

Prove that the word ABABAB is divisible by 7 (A and B are any numbers).

FOOTBALL QUESTION

As you know, football cup games are held according to the so-called Olympic system: the loser is eliminated, in case of a loser there is a replay.

That year there were no replays, and 75 teams took part in the games.

How many cup matches were played?

26

F19. The shape of communicating vessels is shown in figure 1. Where does water flow through the tube connecting the vessels if you heat the water in one of the vessels?

F20. A hole is drilled parallel to the axis of a cylinder of radius $R$ at a distance $\frac{R}{2}$ from its center. The hole radius is $\frac{R}{2}$. The cylinder lies on a plate, which is slowly lifted at one end (Fig. 2). Find the maximum angle of inclination of the plate at which the cylinder will still be in equilibrium. The friction coefficient of the cylinder on the plate is 0.2.

All-Union correspondence Olympiad, 1967

F21. The armature axes of two identical DC motors are rigidly connected to each other. If identical current sources with e. are connected to the armature windings. d.s. ε, then the angular speed of rotation of the anchors without load is equal to $\omega_0$; if the motors are slowed down so that they do not rotate, then current $I_0$ flows through the armature windings. One of the current sources was switched so that the rotating torques of the engines are opposite. What external moment must be applied to the axis of the anchors so that they rotate with force?

given angular velocity $\omega$? Friction in the engines is negligible; The magnetic field of the statar is created by a permanent magnet.

III All-Union Physics Olympiad, 1969

F22. Two blacksmiths form a piece of iron. First, they place it on an anvil and hammer it one at a time, then they hang it from the ceiling and hit it from different sides at the same time. The force of each blacksmith’s blow is the same in both cases. In what case will a piece of iron heat up more in one blow?

A. M. Budker

F23. On a horizontal plane there are two identical thin pipes of mass $m$ each. Their axes are parallel, and their radius is equal to $R$. First, one of the tubes ends, and the second rolls without slipping towards the first until it collides. The translational speed of the pipe is $v_0$. How do the translational and angular velocities of pipe rotation depend on time (draw graphs)? The friction coefficient of sliding pipes on a horizontal surface is $k$, the friction between pipes during a collision is negligible, the impact is absolutely elastic.

III All-Union Physics Olympiad, 1969

27

M16. Prove that the polynomial $p(x)$ with objective coefficients, which takes the value 1 for three different objective values ​​of $x$, cannot have a single integer root.

M17. A peasant, approaching a fork in two roads, diverging at an angle of $60^\circ$, asked: “How to get to the village $NN$?” They answered him: “Go along the left road to the village $N$ - this is eight versts from here - there you will see that a large level road goes off to the right at a right angle - this is exactly the road to $NN$. Or you can go the other way: now along the right road; when you get to the railway, that means half the way is easier; here turn left and go straight along the sleepers until $NN$. - “Well, which way will be shorter?” - 《It doesn’t matter what this is, what that way, it makes no difference.” And the peasants went along the right road.

How many miles will he have to walk to $NN$? Big ten or less? What if you go straight from the fork to $NN$? (All roads are considered straight.)

M18. a) Prove that for any point $M$ of the circle circumscribed about the regular triangle $ABC$, one of the three segments $MA, MB, MC$ is equal to the sum of the other two.

6. Three equal circles $\gamma_1, \gamma_2, \gamma_3$ touch each other in pairs, and a circle $\gamma$ is described around them, which touches all three: $\gamma_1, \gamma_2$ and $\gamma_3$. Prove that for any point $M$ of the circle $\gamma$, the tangent drawn from the point $M$ to one of the three circles $\gamma_1, \gamma_2, \gamma_3$ is equal to the sum of the tangents drawn from the point $M$ to the other two circles.

M19. In an endless chain of neural cells, each cell can be in one of two states: “rest” and “excited”. If a cell is excited at the moment, then it sends a signal that, after a unit of time (say, one millisecond), reaches both neighboring cells. Each cell is excited if and only if it receives a signal from one of its neighboring cells;

if the signal arrives simultaneously from both sides, then they are extinguished and the cell is not excited. For example, if at the initial time $t=0$ three neighbors of the cell are excited and the rest are left alone, then the excitation will spread as shown in figure 3). (Excited cells are blue).

Let only one cell be excited at the initial moment of time. How many cells will be in an excited state after 15 months? in 65 months? in 1000 months? in $t$ months?

What will happen if the chain is not infinite, but contains only $N$ cells connected in a circle (Fig. 4) - will the excitement continue to be infinite for a long time or will it die out?

N. Vasiliev

M20. Is it possible to divide a regular triangle into a million convex polygons so that any straight line intersects no more than forty of these polygons? (We say that a line intersects a polygon if it has at least one common point with it.)

XXXI Moscow Mathematical Olympiad

*) This assumption does not reflect the realidad behavior of cells in the nervous system of living organisms.