23 ноября 2011

Разбор задачи ММ144 Математического Марафона

=================================================

ММ144 (5 баллов)

На поле e4 стоит чёрный король. Первый игрок ставит на любую клетку доски, не находящуюся под боем чёрного короля, белых королей (по одному за ход). Второй игрок делает (правильный) ход чёрным королём. Игра заканчивается, когда у чёрного короля не будет ходов. Каково минимальное количество ходов, за которое первый игрок может достичь цели?

=================================================


Решение

Приведём решение Сергея Половинкина.

Пусть $f$ - минимальное количество ходов, за которое первый игрок может достичь цели при некотором заданном положении черного короля.
На следующих рисунках приведены значения $f$ для квадратных досок для всех начальных положений черного короля.

Изображение

Изображение

Изображение


Можно сделать некоторые выводы (за небольшими исключениями):
1. Для угловых клеток - $f(0)=3$
2. Слои клеток на краях доски (без углов), назовем эти слои первыми - $f(1)=4$
3. Для слоев клеток, соседних с краевыми слоями (пусть это будет второй слой) $f(2)=5$
4. Для третьего слоя $f(3)=6$
5. Для более дальних слоев $f(4)=7$ и $f(5)=7$.
6. Исключения представляют клетки в 1-ом и 2-ом слоях, расположенные в 3-ем слое относительно другого края (поля с1, с2 или а3, b3).
7. Есть еще и не типовые исключения - на досках $3 \times 3$ и $5 \times 5$

Разберем эти результаты подробнее. Понятно, что на краю доски (особенно в углах) проще запатовать короля черных, поэтому при удалении от края значения $f$ возрастают.
С другой стороны, в некоторых случаях, отсутствие возможности белым "зайти с тыла", ограничивает возможности патования, это объясняет п.6.

Рассмотрим соответствующий пример.
Начальное положение черного короля удобно задать в виде нулевого хода черных, а каждый следующий ход с номером - выставление белого короля и ход черного.
Возьмем доску $6 \times 6$ и рассмотрим типовую партию при черном короле на b2:
Изображение
0. ... Крb2
1. Крd3

Белые играют естественным образом, черным, чтобы сразу не попасть на край доски (где белые выиграют проще и быстрее) приходится играть
1. ... Крb3
Изображение
И теперь белые отсекают черных снизу, играя
2. Крb1! Крb4
Черные сделали вынужденный ход, хотя следующий свой ход белые бы сделали на любой ход черных
3. Крb6!
Отсекая черных сверху!
Изображение
У черных осталось всего 4 клетки, своим 4-м ходом белые уменьшат это количество до двух, а 5-м - запатуют черных.

А на доске $5 \times 5$ белые лишены возможности "отсечь" черных сверху на 3-ем ходу, именно поэтому при короле на $b2$ выигрыш белых на досках всех размерностей достигается быстрее, чем на доске $5 \times 5$ !
Там есть еще одна "хитрость", поэтому покажем соответствующую партию.
0. ... Крb2
1. Крd4! Крb3
2. Kpb1 Kpb4
3. Kpb2 Kpa5!

Изображение
Белые сыграли тоньше на 1-ом ходу, черные делают прекрасный 3-ий ход, два края доски не дают белым возможности выиграть быстрее 6-ти ходов!
Нечто подобное, только попроще, происходит при короле на с1 (а3).

Теперь как выигрывают белые за 6 ходов при короле черных на 3-ей линии.
Пусть черный король стоит $c3$ на доске $8 \times 8$, белые отвечают, например, $Kpe3$
Изображение
Основной вариант
0. ... Крc3
1. Крe3 Крc4
2. Kpc6 Kpb4
3. Kpb6 Kpb3
4. Kpb1

Изображение
Как бы теперь ни играли черные, белые патуют их за 2 хода, например:
4. ... Крb4 5. Kpb2 Kpc4 6. Kpa4 $\times$ или 4. ... Крc4 5. Kpa4 Kpc3 6. Kpc5 $\times$
Другие варианты:
1. ... Крc2 2. Kpa2 Kpd1 3. Kpd3 или 1. ... Крb3 2. Kpb1 Kpb4 3. Kpb6 с переходом к основному варианту.
Таким образом можно запатовать короля черных на любом поле 3-ей линии за $6$ ходов, в том числе и при попадании на "неудобные" поля типа $c2$ и $b3$.

Теперь понятно, как проще всего выиграть за $7$ ходов в искомой позиции. При короле на $e4$ можно пойти 1. Крc5 и теперь черный король имеет неутешительный выбор - или пойти на 3-ю линию (где мы выигрываем за 6 ходов как уже показано) или сделать ход 1. ... Крe5 , что еще быстрее проигрывает после 2. Крg5 с простыми вариантами.

На самом деле к выигрышу белых в $7$ ходов ведет множество продолжений, вот они
Изображение
На этом рисунке показано - за сколько ходов выигрывают белые при соответствующем первом ходе короля.

Обсуждение=================================================
Рассмотрим доски большего размера.
Могут возникнуть 2 гипотезы - 7 ходов хватит для патования короля на доске любого размера или количество ходов будет и дальше расти. На самом деле число $8$ впервые появляется на доске $11 \times 11$
Изображение

Но дальнейшего роста уже не происходит, за 8 ходов можно запатовать черного короля на бесконечной доске.
Посмотрим, как это происходит на доске $11 \times 11$, черный король расположен на $f6$, белые играют королем на $h6$. Теперь черные должны играть очень точно, сделать серию единственных ходов, чтобы не проиграть быстрее 8 ходов :
Изображение
С учетом симметрии у черных 3 возможных хода - $e6$, $e5$($e7$) и $f5$($f7$). Но в тогда в случае 0. ... Крf6 1. Kph6 Kpe6 2. Kpc6 и белые выигрывают в 7 ходов по уже показанным образцам, также достаточно 7 ходов и после 0. ... Крf6 1. Kph6 Kpf5 2. Kpd4 .
Таким образом, черные обязаны играть 0. ... Крf6 1. Kph6 Kpe5! . Восклицательный знак означает единственность хода.
Далее возможны следующие варианты
2. Kpd3 Kpd6!
2. Kpc4 Kpd6! 3. Kpb7 Kpe7!
2. Kpc4 Kpd6! 3. Kpe5 Kpc7!
И только в случае этих единственных ходов белым потребуется 8 ходов.
Но самый интересный такой вариант
2. Kpc5 Kpf4!
Теперь на 3. Kpf2 у черных есть 2 допустимых хода - на $e4$ и $g4$, поэтому сильнее
3. Kpg2 Kpe4! , а на 4. Kpe2 уже любой из 3-х возможных ходов черных ведет к выигрышу на 8-ом ходу. Но при этом белые не пускают черного короля к краю доски, т.е. запатовывают его в центре. Белые могли поставить больше проблем на 4-ом ходу, сходив на $e6$ или $g4$, тогда у черных было бы по 2 допустимых хода.

Поскольку в этой партии ни одна сторона не пользовалась краями доски, то можно к 7 приведенным выше пунктам, добавить 8-ой: $f(x)=8$ при $x \geqslant 6$.

Награды=================================================
За правильное решение задачи и развитие темы Сергей Половинкин получает 5+2=7 призовых баллов.
Дмитрий Пашуткин и Анатолий Казмерчук получают 4 балла. Александр Ларин получает 3 балла.

Эстетическая оценка задачи: 5

Комментариев нет:

Отправить комментарий