|
|
 |
Условие
Белая фигура «жук» стоит в угловой клетке доски $1000\times n$, где $n$ — нечётное натуральное число, большее $2020$. В двух ближайших к ней углах доски стоят два чёрных шахматных слона. При каждом ходе жук или переходит на клетку, соседнюю по стороне, или ходит как шахматный конь. Жук хочет достичь противоположного угла доски, не проходя через клетки, занятые или атакованные слоном, и побывав на каждой из остальных клеток ровно по одному разу. Покажите, что количество путей, по которым может пройти жук, не зависит от $n$.Решение
Сориентируем доску так, чтобы у неё было $1000$ столбцов и $n$ строк, а жук сидел в нижнем левом углу. Покрасим клетки в шахматном порядке, причём клетку жука сделаем белой. Занумеруем столбцы числами от $1$ до $1000$ слева направо, а строки числами от $1$ до $n$ снизу вверх.Рассмотрим некоторый путь жука из клетки $(1, 1)$ в клетку $(1000, n)$. Из каждой клетки пути нарисуем стрелку в следующую клетку. Тогда из каждой белой клетки пути стрелка ведёт в чёрную.
Пусть $i$ — чётное число, причём $1000 \le i \le n - 1003$. Между строками $i$ и $i + 1$ проведём горизонтальную прямую $\ell$.
Ниже прямой $\ell$ количество белых клеток в пути превосходит количество чёрных не меньше чем на $1000$, так как $1000$ чёрных клеток в нижних строках находятся под боем слона. Поэтому не меньше $1000$ стрелок идут из белых клеток ниже $\ell$ в чёрные клетки выше $\ell$. Но так может проходить лишь стрелка из клетки в строке $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)$, ..., $(999, i - 1)$, $(1000, i)$, $(998, i)$, ..., $(2, i)$, видим, что все $1000$ стрелок в действительности определены однозначно (см. рис.).
Аналогичное верно для $i + 2$ и, значит, для белых клеток в строках $i + 1$ и $i + 2$. Поэтому если жук пришёл в белую клетку выше $\ell$, то он уже никогда не вернётся в клетку ниже $\ell$. Действительно, пусть жук впервые пересекает $\ell$ сверху вниз после того, как он побывал в белой клетке выше $\ell$. Перед пересечением этой прямой жук находился в строке $i+1$ или $i+2$. Если жук был в белой клетке, то он пошёл бы вверх. А если жук был в чёрной клетке, то он пришёл в неё из клетки ниже $\ell$ — значит, он уже спускался ниже $\ell$, побывав в белой клетке выше $\ell$. Получили противоречие.
Среди стрелок из белых клеток строк $i-1$ и $i$ рассмотрим пройденную последней. Так как до этого жук не побывал в белой клетке выше $\ell$, то из концов остальных таких стрелок он спускался ниже $\ell$. Таким образом, лишь из одной чёрной клетки в строках $i + 1$ и $i + 2$ стрелка ведёт в белую клетку выше $\ell$.
Поскольку стрелка из $(1, i + 2)$ не может вести в белую клетку ниже $\ell$, стрелки из всех остальных чёрных клеток в строках $i + 1$ и $i + 2$ должны вести в белые клетки ниже $\ell$. Последовательно рассматривая клетки $(3, i + 2)$, $(5, i + 2)$, ..., $(999, i + 2)$, $(1000, i + 1)$, $(998, i + 1)$, ..., $(2, i + 1)$, видим, что все $999$ стрелок в действительности определены однозначно (см. рис.).
Аналогичное рассуждение для всех чётных значений $i$ между $1000$ и $n - 1003$ показывает, что средняя часть пути жука определена однозначно и при росте $n$ продолжается в виде пружины (см. рис.).
Следовательно, количество возможных путей не зависит от $n$.
Замечание. Конструкция на рисунке 4 показывает, что рассматриваемые пути действительно существуют.
