Задача 7. Игра Кощея

Сначала — маленькая доска

Таблица $100\times100$ слишком большая, чтобы следить за всеми числами сразу. Поэтому сначала посмотрим, как работает ИИ на доске $4\times4$ с числами от $1$ до $16$ (рисунок ниже; с этой же расстановки начинается модель).

Число $16$ стоит во второй строке, во втором столбце. После первого шага оно оказалось во всех четырёх соседних клетках: у каждой из них $16$ — самый большой сосед. А в собственной клетке $16$ больше нет! Клетка не смотрит на своё число, и туда пришло наибольшее из соседних чисел $9$, $6$, $2$ и $10$, то есть $10$.

После второго шага $16$ вернулось в свою клетку и попало ещё в шесть клеток — в те, куда из его клетки можно попасть, дважды перейдя в соседнюю клетку. Число $16$ как будто прыгает: на одном шаге оно в одних клетках, на следующем — в других. А число $15$ после второго шага исчезло совсем.

Пересчитывать так таблицу $100\times100$ десять тысяч раз невозможно. Нужен способ сразу сказать, откуда взялось число в клетке после любого числа шагов.

Откуда приходит число

Назовём переходом перемещение из клетки в соседнюю (через общую сторону), а маршрутом — несколько переходов подряд. Маршрут может возвращаться назад и проходить одну и ту же клетку много раз.

Через один шаг в клетке $K$ стоит наибольшее из начальных чисел её соседей, то есть клеток, куда ведёт маршрут из одного перехода. Оказывается, дальше всё устроено так же:

через $t$ шагов в клетке $K$ стоит наибольшее из начальных чисел тех клеток, где может закончиться маршрут ровно из $t$ переходов, начатый в $K$.

Почему это верно. Для одного шага это само правило ИИ. Пусть для $t$ шагов это уже известно. На следующем шаге $K$ берёт наибольшее из чисел своих соседей. У каждого соседа сейчас стоит наибольшее из начальных чисел клеток, до которых от него ведёт маршрут из $t$ переходов. А маршрут из $K$ длиной $t+1$ — это первый переход в соседа и ещё $t$ переходов от него. Значит, $K$ получает наибольшее из начальных чисел клеток, до которых от $K$ ведёт маршрут ровно из $t+1$ перехода. Так утверждение переходит с $1$ шага на $2$, с $2$ на $3$ и дальше — на любое число шагов.

Проверим на доске из шага 1. Из клетки, где стояло $16$, за два перехода можно попасть в шесть клеток (они на рисунке к шагу 1 после второго шага заняты числом $16$) и вернуться обратно, сходив «туда-обратно». Наибольшее начальное число в этих семи клетках — само $16$, поэтому после второго шага $16$ снова в своей клетке.

Как до этого додуматься: когда одно и то же действие повторяется очень много раз, полезно описать результат сразу после $t$ шагов, а не пересчитывать таблицу шаг за шагом.

Шахматная раскраска: пункт а)

Раскрасим таблицу как шахматную доску. Соседние клетки разного цвета, поэтому каждый переход меняет цвет: после одного перехода мы на клетке другого цвета, после двух — снова своего, после трёх — опять другого. Значит, маршрут из $K$ с чётным числом переходов кончается на клетке того же цвета, что и $K$, а с нечётным — на клетке другого цвета. Это видно и на рисунке к шагу 2: отмеченные клетки идут через одну, как клетки одного цвета на шахматной доске. Отсюда и идея раскраски.

Возьмём теперь любые две соседние клетки $K$ и $L$ — они разного цвета. По шагу 2 через $t$ шагов в $K$ стоит наибольшее из начальных чисел одной группы клеток, а в $L$ — другой группы. Если $t$ чётное, группа для $K$ — клетки цвета $K$, а группа для $L$ — клетки цвета $L$; если $t$ нечётное — наоборот. В обоих случаях группы разного цвета, и общих клеток у них нет.

Наибольшее число группы — это число, стоявшее вначале в одной из её клеток. Все начальные числа различны, а клетки разные, поэтому числа в $K$ и $L$ тоже различны.

Итак, в любой момент любые два соседних числа различны. Как бы Кощей ни расставил числа, все они никогда не станут одинаковыми. Ответ на пункт а): нет.

Что останется через 10 000 шагов: пункт б)

Под «ходом» в пунктах б) и в) понимаем шаг ИИ. Возьмём клетку $K$ и любую клетку $M$ того же цвета. Найдём маршрут из $K$ в $M$, в котором ровно $10\,000$ переходов.

Сначала идём из $K$ по её строке до столбца, в котором стоит $M$, — это не больше $99$ переходов. Потом идём по этому столбцу до $M$ — тоже не больше $99$. Всего не больше $99+99=198$ переходов. Число переходов в таком маршруте чётное: он начинается и кончается на клетках одного цвета, а каждый переход меняет цвет.

Пусть в этом маршруте $d$ переходов. До $10\,000$ не хватает $10\,000-d$ переходов — это чётное число, ведь $10\,000$ и $d$ оба чётные. Добавим недостающие переходы парами: из $M$ в соседнюю клетку и обратно в $M$. Например, если первый маршрут состоит из $36$ переходов, добавим $(10\,000-36):2=4982$ пары «туда-обратно».

Итак, за $10\,000$ переходов из $K$ можно попасть в любую клетку того же цвета и ни в одну клетку другого цвета (число $10\,000$ чётное). По шагу 2 через $10\,000$ шагов в каждой чёрной клетке стоит наибольшее из начальных чисел всех чёрных клеток — назовём его чёрным максимумом. А в каждой белой клетке стоит белый максимум — наибольшее из начальных чисел белых клеток. По шагу 3 эти числа различны.

Значит, через $10\,000$ ходов в таблице ровно два различных числа — при любой расстановке. Больше двух остаться не может, поэтому ответ на пункт б): $2$.

Если число шагов нечётное и больше $198$, рассуждение такое же, только клетку $M$ берём другого цвета: маршрут до неё тоже не длиннее $198$ переходов, число переходов в нём нечётное, и остаток снова чётный — его тратим парами «туда-обратно». Поэтому из $K$ можно попасть в любую клетку другого цвета, и после каждого следующего шага чёрный и белый максимумы просто меняются местами.

На доске $4\times4$ самый длинный такой маршрут — $3+3=6$ переходов, поэтому там два числа остаются самое позднее через $6$ шагов. Для расстановки из шага 1 это $16$ и $13$ — проверь в модели.

Наименьшее число: пункт в)

Через $10\,000$ ходов в таблице стоят только чёрный и белый максимумы. Один из них равен $10\,000$: это число где-то стоит, и на своём цвете оно самое большое. Остаётся понять, насколько маленьким может быть другой максимум.

Оценка. В каждой строке таблицы $50$ чёрных и $50$ белых клеток, поэтому чёрных клеток $50\cdot100=5000$, и белых тоже $5000$. На чёрных клетках стоят $5000$ различных натуральных чисел. Если бы все они были не больше $4999$, то различных чисел набралось бы не больше $4999$, а их $5000$. Значит, чёрный максимум не меньше $5000$. Точно так же и белый максимум не меньше $5000$. Поэтому число меньше $5000$ через $10\,000$ ходов остаться не может.

Пример. Оценка подсказывает, как его построить: чтобы максимум одного цвета был как можно меньше, отдадим этому цвету самые маленькие числа. Поставим на чёрные клетки числа от $1$ до $5000$, а на белые — от $5001$ до $10\,000$. Тогда чёрный максимум равен $5000$, белый — $10\,000$, и через $10\,000$ ходов во всех чёрных клетках стоит $5000$ (рисунок ниже).

Оценка и пример сходятся. Ответ на пункт в): $5000$.