Высшая проба 2020, 7 класс, задача 6

Ответ. .

Решение. Для начала докажем, что при (доска ) Семён сможет этого добиться.
Рассмотрим вертикали и горизонтали, расположенные в одной клетке от края доски (это -я и
-я горизонтали и вертикали и ). Назовём их критическими рядами, а их пересечения
(клетки , , и ) – узлами.
Докажем следующие два утверждения.
) Семён может добиться следующего: если таракан пришёл на критический ряд, то оба узла на
этом ряду уже заняты камнями.
) Если таракан пришёл на критический ряд, оба узла которого уже заняты камнями, то Семён
может не дать таракану выйти с этого ряда на соседний с ним край.
Начнём с утверждения : пусть таракан на критическом ряду. Тогда Семён каждый раз кидает
камешек на соседнюю с тараканом клетку края (если она ещё свободна – если занята, он может
кидать куда хочет). Такая клетка только одна везде, кроме узлов, а узлы уже заняты.
Следовательно, с этого ряда таракан на край выйти не сможет.
Теперь докажем утверждение .
Пусть Семён первым ходом кидает камень в клетку , а дальше, если таракан не на
критическом ряду, занимает любой свободный узел того ряда, в сторону которого таракан
последний раз полз (или любой другой свободный узел, если в этом ряду уже оба узла заняты;
если заняты все четыре узла, а таракан всё ещё не на критическом ряду, Семён может кидать
куда угодно на доске).
Чтобы добраться до своего первого критического ряда, таракан должен сделать хотя бы три
хода в его сторону; следовательно, хотя бы уже два раза он полз в сторону этого ряда (но не
достигал его), что означает, что на этом ряду заняты оба узла (либо их занимали после этих
двух ходов, либо после какого-то из этих ходов их не занимали, так как они уже были заняты).
Заметим, что, так как прошло не менее трёх ходов, хотя бы три узла уже заняты.
По утверждению , таракан не может выйти с этого ряда на край. Пусть он пытается ползти с
него внутрь (от края). Тогда он больше не на критическом ряду (иначе он начинал бы с узла, а
узлы этого ряда заняты), и следующим ходом закрывается четвёртый узел (если он ещё не
занят), то есть на любом критическом ряду, куда ещё мог бы прийти таракан, уже будут заняты
оба его узла. Утверждение доказано.
Объединяя утверждения и , получаем, что Семён может не дать таракану выйти на край ни с
какого критического ряда, т.е. выигрывает.
Заметим, что при Семён может применить ту же стратегию, не давая таракану выйти из
центрального квадрата , т.е. тоже выигрывает.
Докажем, что при (доска ) таракан может спастись.
Лемма. Пусть таракан в одной клетке от края, и в прямоугольнике , содержащем таракана и
один из углов, нет ни одного камня. Тогда таракан может выйти на край.
Доказательство. Если Семён кинет камень куда угодно, кроме соседней клетки края, таракан
ползёт туда и выигрывает; иначе таракан ползёт вдоль длинной стороны прямоугольника и
оказывается в той же ситуации при k на единицу меньшем. Когда k достигает , этот ход таракана
тоже приведёт его к краю.
Действительно, предположим, что первым ходом Семён кидает камень не ниже и не левее центра
(этого всегда можно добиться, повернувшись относительно доски), то есть не ниже 4горизонтали и не левее вертикали d.
Тогда таракан ползёт вниз, на клетку .
Если после этого Семён кидает камень куда угодно, кроме клеток и , то таракан ползёт на
; иначе он ползёт на .
Если таракан оказался на , то на нижних двух горизонталях не более одного камня, причём не
на ; тогда либо снизу и справа, либо снизу и слева от таракана камней нет, и выполнено
условие леммы.
Пусть таракан на . Тогда на трёх левых вертикалях нет ни одного камня (второй камень был на
вертикали d, а первый не левее); если после этого Семён кидает камень на или , то таракан
ползёт на , а если куда-либо ещё, то на .
Наконец, если таракан оказался на , то слева и снизу от него камней нет, и он выигрывает по
лемме; если же он оказался на , то на двух левых вертикалях не более одного камня, причём не
на , то есть либо снизу и слева, либо сверху и слева от таракана камней нет, и он опять же
выигрывает по лемме