Paris of mathematicians and physicists

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?