[Задача о представлении максимума чисел в виде суммы]

Квант 1970, №4 с. 24, 26, 27 Тег 2HDA

ЗАДАЧИ

Пусть каждый юноша другит не менее чем с $m$ девушками, а каждый девушка — не более чем с $m$ юношами ( $m$ — произвольное натуральное число). Докажите, что в этом случае выполнен условие теоремы о сватовстве.
Школьники на кружке решили задачи. Оказалось, что каждый решил по 4 задачи и каждый задача была решена четырьмя школьниками. Докажите, что можно организовать разбор задачи так, чтобы каждый школьник расскаалровно одну задачу и чтобы все задачи были разобраны (по одному разу).
Дана транспортиная сеть. Множество вершин, содержащие выход, по не содержащие вход, называют разрезом сети. Пропускной способностью разреза $B$ называется число $c(B)$ , равное числу дут, входящих в $B$ . Если через $\phi$ обозначает поток, то $|\phi|$ будет обозначает величины потока. Докажите, что для любого потока $\phi$ и любого разреза $B$ верно переваненство: $|\phi| \leq c(B)$ .
Разрез $B$ называет минимальный, если его пропускная способность $c(B)$ — самая маленькая среди пропускных способностей всех разрезов. Вывести с помощью алгоритма Форда—Фолкерсона, что пропускная способность минимального разреза равна величины максимального потока — max $|\phi| = \min c(B)$ (теорема Форда—Фолкерсона).
Проверить, что если $\phi$ — максимальный поток, то разрез, получащийся обедининием всех непомеченных вершин (пометки делаются, исходя из потока $\phi$ , методом Форда—Фолкерсона), является минимальным.
Доказать, что обедининие и пересечение любых двух минимальных разрезов есть снова минимальных разрез.
Доказать, что разрез из непомеченных вершин (для максимального потока) является обедининием всех минимальных разрезов. Вывести отсюда, что этот разрез не зависит от того, с помощью какого максимального разреза делались потоки.

ЛИТЕРАТУРА

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

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

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

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

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

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

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

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

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

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

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

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

Ф19. Форма сообщающихся сосудов показана на рисунке 1. Куда по-teчет вода по трубке, соединяющей сосуды, если нагреть воду в одном из сосудов?

Ф20. Параллельно оси цилиндра радиуса $R$ на расстоянии $\frac{R}{2}$ от его центра просверлено отверстие. Радиус отверстия равен $\frac{R}{2}$ . Цилиндр лежит на дошечке, которое медленно поднимают за один конец (рис. 2). Найти предельный угол наклона дошечки, при котором цилиндр еще будет находиться в равновесии. Коэффициент треня цилиндра о дошечку равен 0,2.

Всесоюзная заочная olимпиада, 1967 г.

Ф21. Оси якорей двух одинаковых электродвигателей постоянного токажестко соединены друг с другом. Если к обмоткам якорей подключены одинаковые источники тока с э. д. с. ε, то угловая скорость врашення якорей без нагрузки равна $\omega_0$ ; если двигаели затормозить так, чтобы они не врашались, то через обмотки якорей идет ток $I_0$ . Один из источников тока переключили так, что врашшение моменты двигаелей противоположны. Какой внешний момент нужно приложить к оси якорей для того, чтобы они врашались с за-

данной угловой скоростью $\omega$ ? Трение в движательях пренебрежимо мало; магнитное поле статара создается постоянным магнитом.

III Всесоюзная физическая olимпиада, 1969 г.

Ф22. Два кузнеца образывают кусок железа. Сначала егоkladут на наковальню и быют молотком по очереди, потом подвешивают к потолку и быют одновременно с разных сторон. Сила удара каждого кузнеца одинаковова в обихх случаях. В каком случае кусок железа больше нагреется за одинудар?

А. М. Будкер

Ф23. На горизонтальной плоскости находится две одинаковые тонкостей трубы массы $m$ каждый. Оси их параллельны, а радиус равны $R$ . Вначале одна из трубок поконтся, а вторая катится без просkalывания по направлению к первой до стольновения. Скорость поступательного движения трубы равна $v_0$ . Как зависит от времени (нарисайте графики) поступательные и угловые скорости врашения труб? Коэффициент треня скольжения труб о горизонтальную поверхность равен $k$ , трение между трубами при стольновении пренебрежимо мало, удар абсолотно упругий.

III Всесоюзная физическая olимпиада, 1969 г.

М16. Докажите, что многочлен $p(x)$ с цельми коэффициентами, который при трех различных цельх значениях $x$ принимает значение 1, не может иметь ни одного целого корня.

М17. Крестьянин, подойдя к развилке двух дорог, расходящся под углом в $60^\circ$ , просил: «Как пройти в селье $NN$ ?» Ему ответили: «Иди по левой дороге до деревни $N$ — это в восьми верстах отсюда, — там увидишь, что направо под прямым углом отходит большаяровная дорога — это как раз дорога в $NN$ . А можно идти другим путем: сейчас по правой дороге; как выйдешь к железной дороге, — значит, половину пути проще; тут поверни налево и идти прямо по шпалам до самого $NN$ . — «Ну, а какой путь короче-то будет?»—《Да все равно, что так, что этак, никакой разницы». И пошел крестьян по правой дороге.

Сколько верст ему придется идти до $NN$ ? Большое десяти или меньше? А если идти от развилки до $NN$ напрямик? (Все дороги считаются прямыми.)

М18. a) Докажите, что для любой точки $M$ окружности, описанной около правильно треугольника $ABC$ , один из трех отрезков $MA, MB, MC$ равен сумме двух других.

Три равные окружности $\gamma_1, \gamma_2, \gamma_3$ попарно касаются друг друга, и вокруг них описана окружность $\gamma$ , которая касается всех трех: $\gamma_1, \gamma_2$ и $\gamma_3$ . Докажите, что для любой точки $M$ окружности $\gamma$ касательная, проведенная из точки $M$ к одной их трех окружностей $\gamma_1, \gamma_2, \gamma_3$ , равна сумме касательных, проведенных из точки $M$ к двум других окружностями.

M19. В бесконечной цепочке невных клеток каждой клетка может находиться в одном из двух состояний: «покой» и «возбужdenе». Если в данный момент клетка возбудилась, то она посылает сигнал, который через единицу времени (скажем, через одну миллисекунду) доходит до обеих соседи с ней клеток. Каждый клетка возбуждается в том и только в том случае, если к ней приходит сигнал от одной из соседи клеток;

если сигнал приходит одновременно с двух сторон, то они погашаются, и клетка не возбуждается. Например, если в начальной момент времени $t=0$ возбудить три соседи клетки, а остальные оставить в покое, то возбужнение будет распространяться так, как показано на рисунке 3). (Возбужdenные клетки — синние).

Пусть в начальной момент времени возбуждана только одна клетка. Сколько клеток будет находиться в возбужdenном состоянии через 15 месек? через 65 месек? через 1000 месек? вообще через $t$ месек?

Что будет в том случае, если цепочка не бесконечная, а содержит всего $N$ клеток, соединенных в окружность (рис. 4), — будет ли возбужdenе поддерживать бесконечную долго или затухнет?

H. Васильев

M20. Можно ли разить правильный треугольник на миллион выпukых многоугольников так, чтобы любая пряма пересекала не более сорока из этих многоугольников? (Мы говорим, что пряма пересекает многоугольник, если она имеет с ним хотя бы одну одну общую точку.)

XXXI Московская математическая олимпиада

*) Это предположение не отражает realidad поведения клеток нервной системы жизни организмов.