РЕШУ ОЛИМП, математика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 6839 Добавить в вариант

Белая фигура «жук» стоит в угловой клетке доски 1000 × n, где n  — нечётное натуральное число, большее 2020. В двух ближайших к ней углах доски стоят два чёрных шахматных слона. При каждом ходе жук или переходит на клетку, соседнюю по стороне, или ходит как шахматный конь. Жук хочет достичь противоположного угла доски, не проходя через клетки, занятые или атакованные слоном, и побывав на каждой из остальных клеток ровно по одному разу. Покажите, что количество путей, по которым может пройти жук, не зависит от n.

(Николай Белухов)

Спрятать решение

Решение.

Сориентируем доску так, чтобы у неё было 1000 столбцов и n строк, а жук сидел в нижнем левом углу. Покрасим клетки в шахматном порядке, причём клетку жука сделаем белой. Занумеруем столбцы числами от 1 до 1000 слева направо, а строки числами от 1 до n снизу вверх.

Рассмотрим некоторый путь жука из клетки $левая круглая скобка 1, 1 правая круглая скобка$ в клетку $левая круглая скобка 1000, n правая круглая скобка .$ Из каждой клетки пути нарисуем стрелку в следующую клетку. Тогда из каждой белой клетки пути стрелка ведёт в чёрную.

Пусть i  — чётное число, причём $1000 меньше или равно i меньше или равно n минус 1003.$ Между строками i и $i плюс 1$ проведём горизонтальную прямую ℓ.

Ниже прямой ℓ количество белых клеток в пути превосходит количество чёрных не меньше чем на 1000, так как 1000 чёрных клеток в нижних строках находятся под боем слона. Поэтому не меньше 1000 стрелок идут из белых клеток ниже ℓ в чёрные клетки выше ℓ. Но так может проходить лишь стрелка из клетки в строке $i минус 1$ или i. А поскольку там всего 1000 белых клеток, в каждой из них начинается стрелка, идущая в чёрную клетку строки $i плюс 1$ или $i плюс 2.$

Стрелка из клетки $левая круглая скобка 1, i минус 1 правая круглая скобка$ может идти только в $левая круглая скобка 2, i плюс 1 правая круглая скобка .$ Тогда стрелка из $левая круглая скобка 3, i минус 1 правая круглая скобка$ может идти только в $левая круглая скобка 4, i плюс 1 правая круглая скобка .$ Последовательно рассматривая клетки

$левая круглая скобка 5, i минус 1 правая круглая скобка , левая круглая скобка 7, i минус 1 правая круглая скобка , \ldots, левая круглая скобка 999, i минус 1 правая круглая скобка , левая круглая скобка 1000, i правая круглая скобка , левая круглая скобка 998, i правая круглая скобка , \ldots, левая круглая скобка 2, i правая круглая скобка ,$

видим, что все 1000 стрелок в действительности определены однозначно (рис. 1).

Рис 1.

Аналогичное верно для $i плюс 2$ и, значит, для белых клеток в строках $i плюс 1$ и $i плюс 2.$ Поэтому если жук пришёл в белую клетку выше ℓ, то он уже никогда не вернётся в клетку ниже ℓ. Действительно, пусть жук впервые пересекает $\ell$ сверху вниз после того, как он побывал в белой клетке выше ℓ. Перед пересечением этой прямой жук находился в строке $i плюс 1$ или $i плюс 2.$ Если жук был в белой клетке, то он пошёл бы вверх. А если жук был в чёрной клетке, то он пришёл в неё из клетки ниже ℓ — значит, он уже спускался ниже ℓ, побывав в белой клетке выше ℓ. Получили противоречие.

Среди стрелок из белых клеток строк $i минус 1$ и i рассмотрим пройденную последней. Так как до этого жук не побывал в белой клетке выше ℓ, то из концов остальных таких стрелок он спускался ниже ℓ. Таким образом, лишь из одной чёрной клетки в строках $i плюс 1$ и $i плюс 2$ стрелка ведёт в белую клетку выше ℓ.

Поскольку стрелка из $левая круглая скобка 1, i плюс 2 правая круглая скобка$ не может вести в белую клетку ниже ℓ, стрелки из всех остальных чёрных клеток в строках $i плюс 1$ и $i плюс 2$ должны вести в белые клетки ниже ℓ. Последовательно рассматривая клетки

$левая круглая скобка 3, i плюс 2 правая круглая скобка , левая круглая скобка 5, i плюс 2 правая круглая скобка , \ldots, левая круглая скобка 999, i плюс 2 правая круглая скобка , левая круглая скобка 1000, i плюс 1 правая круглая скобка , левая круглая скобка 998, i плюс 1 правая круглая скобка , \ldots, левая круглая скобка 2, i плюс 1 правая круглая скобка ,$

видим, что все 999 стрелок в действительности определены однозначно (рис. 2).

Рис 2.

Аналогичное рассуждение для всех чётных значений i между 1000 и $n минус 1003$ показывает, что средняя часть пути жука определена однозначно и при росте n продолжается в виде пружины (рис. 3).

Рис 3.

Следовательно, количество возможных путей не зависит от n.

Замечание. Конструкция на рисунке 4 показывает, что рассматриваемые пути действительно существуют.

Рис 4.

Турнир городов, 11, 10 класс, Осенний тур, 2021 год

Классификатор: Разное. Логические задачи, Разное. Процессы и операции

Спрятать решение · Помощь