Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2000/03/47.pdf Дата изменения: Fri Dec 23 19:25:51 2005 Дата индексирования: Tue Oct 2 00:13:11 2012 Кодировка: Windows-1251 Поисковые слова: http astrokuban.info astrokuban

МАТЕМАТИЧЕСКИЙ

КРУЖОК

47
соответственно. Докажите, что угол MON острый. (Эта задача предлагалась на Международной математической олимпиаде 1998 года.)

а зависящую лишь от данной точки O и данного угла. 2. Вписанная в треугольник ABC окружность с центром O касается сторон BC, CA

и AB в точках A1 , B1 и C1 соответственно (рис.8). Через вершину B параллельно A1C1 проведена прямая, пересекающаяся с прямыми B1C1 и B1 A1 в точках M и N

Прогулки короля
И.АКУЛИЧ

В

классником и участником Всесоюзной математической олимпиады, я боролся с одной задачей (автор ее А.Ходулев). За прошедшие годы условия и решения остальных задач олимпиады постепенно потускнели и стерлись из моей памяти, а она сохранилась. Это настоящий шедевр: изящное условие, очень естественное, 'этюдное' решение. Такое не забывается! Впрочем, судите сами. Задача. Король обошел шахматную доску, побывав на каждом поле. Когда соединили отрезками центры полей, которые он последовательно проходил, получили замкнутую ломаную без самопересечений. Какое наибольшее и какое наименьшее число диагональных ходов мог иметь путь короля? Насчет наименьшего числа все ясно: оно равно нулю, и пример построить проще простого (рис.1). Эту часть задачи я осилил. А вот найти наибольшее не смог. Точнее, я нарисовал маршрут, в котором 36 диагональных ходов (рис.2), но не сумел доказать, что этот маршрут наилучший. Так и написал: 'У меня больше не получилось'. Жюри поставило за это оценку ' m ' (что-то вроде двойки с плюсом). Как же доказать, что замкнутый несамопересекающийся маршрут короля содержит не более 36 диагональ-

1973 ГОДУ, БУДУЧИ ДЕВЯТИ-

ных ходов? Оказывается, надо рассмотреть последовательные выходы А и В короля на границу доски. Если поля А и В не соседние (рис.3), то путь от А до В разбивает поле на две части. Всякая ломаная, соединяющая клетки из разных частей, пересекает путь АВ, что ведет к самопересечению пути короля. Поэтому А и В соседние поля. Поскольку цвета этих полей разные, а при ходах по диагонали цвет не меняется, то между двумя соседними выходами на границу должен быть и 'прямой' ход. Поскольку граничных полей 28, выходов на границу тоже 28, и 'прямых' ходов не меньше 28. Тогда диагональных не больше чем 64 28 = 36. Задача решена!1 Вторым по силе чувством после очарования была досада: как же не додумался до такого естественного и короткого решения! А через четверть века вдруг возникли следующие вопросы (и опять непонятно, почему не рань1 Между прочим, из формулы Пика

ше): в задаче рассмотрен замкнутый самопересекающийся путь короля, который по одному разу побывал на всех клетках доски. А что будет, если путь незамкнутый? Или самопересекающийся? Так задача Ходулева породила еще несколько новых. Первой из них поддалась задача, в которой путь короля несамопересекающийся и незамкнутый (пример такого маршрута на рисунке 4, где король сделал 49 диагональных ходов). Как доказать, что число 49 максимально возможное? Очень просто. Назовем узлом общую точку четырех клеток шахматной доски. Всего узлов, очевидно, 49. Каждый диагональный ход проходит через узел, а два раза пройти через узел без самопересечения пути невозможно. Все! Дальше я занялся самопересекающимся незамкнутым маршрутом. Помучиться пришлось изрядно. Краткостью и красотой найденное мною решение не обладает. Поэтому изложу его мелким шрифтом.
Король сделал всего 63 хода. Очевидно, диагональные ходы не меняют цвет поля, на котором находится король, а каждый 'прямой' (т.е. вертикальный или горизонтальный) ход приводит к переходу с одного цвета на другой. Таким образом, весь путь короля состоит из нескольких цепочек полей одного цвета, соединенных между собой 'прямыми' ходами. (Цепочка может состоять из единственного поля; все ходы внутри одной цепочки диагональные.) Докажем, что число белых цепочек не меньше чем 4. Для этого разобьем все возможные ходы, соединяющие белые поля, на группы, как показано на рисунке 5. Из этих девяти групп шесть имеют вид креста, две расположены в левом нижнем и в правом верхнем углах доски и одна в центре.

S = i + b 2 -1 для площади S многоугольника с вершинами в узлах клетчатой бумаги, где i количество узлов, расположенных строго внутри многоугольника, а b количество узлов, расположенных на границе, следует, что любой замкнутый несамопересекающийся путь короля ограничивает площадь (в клетках) S = 0 + 64/2 1 = 31. (Подробности в статье Н.Васильева 'Вокруг формулы Пика', Приложение к журналу 'Квант' ?2 за 1998 год.)

)

*

Рис. 1

Рис. 2

Рис. 3

Рис. 4