Матбой

50

Матбой
И. Н. Берштейн

Во время Всесоюзной олимпiadы проводился традиционный математический бой*) между командами двух физико-математических интернатов — Ленинградского и Московского. В этом году от каждой интерната выступило по 11 человек; жюри предложило 11 задач.

После освежкашнегоочного бдения (задачи стали известны участникам накануне вечером) команды вызвали друг друга на бой. Ему предшествовал конкурс капитанов (Москва — Аркадий Вайнтроб, Ленинград — Виктор Козырев), победитель которого завоевывал своей команде право выбрать первый ход. Над было ответить на вопрос: сколько корней имеет уравнение $\log \frac{1}{16} x = \left( \frac{1}{16} \right)^x$.

Это не задача, а скорее загадка. Капитаны не знали ее условия заранее, и им достаточно было любым способом отгадать ответ. (Te, кто считает, что это очень просто, пусть засекут время и попробуют сами. Учитите, что если вы называете неверный ответ, то победа автоматически присуждается противнику. С другой стороны, не торопясь ждать, пока неверный ответ назовет противник — тоже не самая разумная тактика).

После этого начался бой. Сначала Москвы вызвали ленинградцев на решение следующего задачи.

*) Матбой — это игра, похожая отчасти на KBH, отчасти на психологический поединок, отчасти на математической олимпiadу. Ее правила напечатаны в «Кванте» № 10 за 1972 год.

В дальнейшем перед каждой задачей будет стоять (M), если вызывали москвичи, и (Л) — если ленинградцы.

№ 1 (M). n точек соединены n — 1 отрезком так, что любые две точки связываетровноднацепочкаотрезков. На отрезках каким-то образом расставлены стрелки. Разрешается неограниченное число раз продельать следующую операцию: если в какой-то точке нет входящих в нее стрелок, а все стрелки из нее выходят, то можно изменить направление всех этих стрелок на обратное. Например, $\leftrightarrow$ можно передать в $\rightarrow$ $\leftarrow$

Доказать, что таким операциями можно изменить направление всех стрелок на любое направление. Оценить сверху и снизу минимальное число M таких операций, которое зависит от достаточно чтовы при любом соединении n точек отрезками изменить любое направление стрелок на любое другое.

Обе команды решили первую часть задачи, но не смогли дать точной оценки числа M.

№ 2 (Л). Существует ли многочлен от двух переменных P(x, y), такой, что

a) для всех x, y P(x, y) > 0;

b) для любого положительного числа c существуют такие x, y, что P(x, y) < c.

Одна из наиболее интересных задач матбиоя. В начале поединка Москвы были уверены в существование такого многочлена, а ленинградцы — в обратном.

№ 3 (M). Имеется 128 гирь и анализические всесы со стрелкой. При взвешивание разрешается класс равное число гирь на каждой чашку весов (и при этом стрелка укажет разницу в весе гирь на двух чашках). Вес первой гири известен точно. За какое минимальное число взвешивания можно узнать суммарный вес гирь?

Предлагая эту задачу, члены жюри не знали ее решения (это допускается правлими). В результате матбиоя его так и не узнали…

51

№ 4 (Л). Дано 11 натуральных чисел. Доказать, что можно выписать несколько из них подряд так, что в образовавшемся числе каждой цифра встречается четное число раз.

№ 5 (М). В окружность диаметра $D$ вписан $k$-угольник. В нем проведи $k - 3$ попарно непересекающей диагонали так, что он разбился на треугольники. В каждой из треугольников вписали круг; их радиусы — $R_1, R_2, \dots, R_{k-2}$. Доказать, что $R_1 + \dots + R_{k-2} < D$.

Это довольно трудная и красивая задача. Тем не менее ее сделали обе команды.

№ 6 (Л). Существуют ли 99 различных нечетных натуральных чисел $a_1, a_2, \dots, a_{99}$ таких, что $\frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_{99}} = 1$?

Во время переписки в условия этой задачи было пропущено слово «нечетных», из-за чего решение оказалось слишком простым. В том виде, в котором задача приведена здесь, участники не сумели решить ее до конца.

№ 7 (М). Фирма «Рога и копыта» приобретла счетную машину, на которой выполнять только одну операцию: $a*b = 1 - \frac{a}{b}$. Тем не менее О. Бендер научился выполнять на ней все четыре арифметических действия. Как?

№ 8 (Л). Треугольник называется «хорошим», если все его углы не больше 120°. «Хороший» треугольник разбивает на несколько треугольников. Доказать, что среди них есть хотя бы один «хороший».

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

№ 9. Смотри задачу 1 первого дня 9-го класса со следующим изменением: эксперт знает, что 6 может фальшивые, а остальные 8 — настоящие (и знает, какие именно фальшивые).

№ 10. В квадратной таблице $100 \times 100$ клетки диагонали закрашены синим цветом. Множество клеток таблицы называется бингом, если оно не содержит синх клеток и после некоторой перестановки строк и столбцов превращается в прямого угольник. Какое минимальное число бингов (может быть, пересекающихся) нужно, чтобы покрыть

a) всего доку, кроме диагонали,
b) всего нижнюю половину dockи под диагональю (и, если нужно, часть верхней, но без диагонали).

№ 11. На рисунке приведена схема улиц города Энска. Требуется пустить по городу несколько колщевых маршрутов автовуса так, чтобы по каждому участку пути проходилровно один автовос (причем только в одном направлении). Сколько способами это можно сделать? (Направления маршрутов не учитываются).

У участников матоя была, кроме того, возможность набирать дополнительные очки, рассказывая свои сообщения по поводу нерешенных или не до конца решенных задач. Ленинградцы почтите разобрали задачу № 6 в правильной формулировке, аmockвичи рассказыли часть задачи про «бинги».

В итоге победили москвичи, разумно построившие свой бой не только с математической, но и с тактической точки зрения. Счет 28 : 22.