Париж математиков и физиков

24

ЗАДАЧИ

1. Пусть каждый юноша другит не менее чем с $m$ девушками, а каждый девушка — не более чем с $m$ юношами ($m$ — произвольное натуральное число). Докажите, что в этом случае выполнен условие теоремы о сватовстве.

2. Школьники на кружке решили задачи. Оказалось, что каждый решил по 4 задачи и каждый задача была решена четырьмя школьниками. Докажите, что можно организовать разбор задачи так, чтобы каждый школьник расскаалровно одну задачу и чтобы все задачи были разобраны (по одному разу).

3. Дана транспортиная сеть. Множество вершин, содержащие выход, по не содержащие вход, называют разрезом сети. Пропускной способностью разреза $B$ называется число $c(B)$, равное числу дут, входящих в $B$. Если через $\phi$ обозначает поток, то $|\phi|$ будет обозначает величины потока. Докажите, что для любого потока $\phi$ и любого разреза $B$ верно переваненство: $|\phi| \leq c(B)$.

4. Разрез $B$ называет минимальный, если его пропускная способность $c(B)$ — самая маленькая среди пропускных способностей всех разрезов. Вывести с помощью алгоритма Форда—Фолкерсона, что пропускная способность минимального разреза равна величины максимального потока — max $|\phi| = \min c(B)$ (теорема Форда—Фолкерсона).

5. Проверить, что если $\phi$ — максимальный поток, то разрез, получащийся обедининием всех непомеченных вершин (пометки делаются, исходя из потока $\phi$, методом Форда—Фолкерсона), является минимальным.

6. Доказать, что обедининие и пересечение любых двух минимальных разрезов есть снова минимальных разрез.

7. Доказать, что разрез из непомеченных вершин (для максимального потока) является обедининием всех минимальных разрезов. Вывести отсюда, что этот разрез не зависит от того, с помощью какого максимального разреза делались потоки.

ЛИТЕРАТУРА

1. А. Кофман, Р. Фор, Займется исследованием операций, «Мир», 1966.
2. К. Берж, Теория графов и ее применение, ИЛ, 1962.
3. Л. Форд, Д. Фолкерсон, Потоки в сетях, «Мир», 1966.
4. О. Оре, Теория графов, «Нayka», 1968.
5. Д. Гэйл, Теория линейных экономических моделей, ИЛ, 1963.

ПАРИЖ МАТЕМАТИКОВ И ФИЗИКОВ

В Париже многое здания связанны с памятью о выдающих ученых прошливх столей. Далее Лувер, который неогда был оплотом королей, перед самой революцией 1789 года стал местом заcedания академиков Хотя позднее, при Наполеоне I, Лувер стал музеем, но и тогда в нем были расквартированны некоторые учены. Сохранилиись письмо Лежандра, в котором этот математик умолял поселить его в старой части дворца.

В Париже есть улицы, носящие имена математиков, физиков и астрономов, причем не все из этих ученых французы. Вот эти имена: Лежандр, Реомор, Паскаль, Пьер Кюри, Мария Кюри, Ламберт, Бюофон, Франклин, Карно, Араго, Декарт, Лейбниц…

Фразу «Число $z$ есть наиболее из двух чисел $x$ и $y$» с помощью формулы можно записать так:

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

А как записать фразу «Число $u$ есть наиболее из трех чисел $x, y$ и $z$»?

Доказать, что слово АБАБАБ делится на 7 (А и Б — любые цифры).

ФУТБОЛЬНЫЙ ВОПРОС

Как известно, игры на кубок по футбольу проводятся по так называемой olимпийской системе: проигравший выбывает, в случаеничей — переигровка.

В тот год переигровок не было, а в играх участвовали 75 команда.

Сколько было сыграно матчей на кубок?