Охота на Снарка

Докажите сначала, что Булочник может поймать Снарка силы 1, если он всегда увеличивает свою y-координату.

«Стену» для Снарка, всегда увеличивающего свою y-координату, можно строить очень близко. Скажем, 10 клеток будет достаточно.

Можно ловить Снарка как бы со всех четырёх сторон аналогично тому, как ловится Снарк, прыгающий вверх. Осталось позаботиться о том, чтобы при «переключении» от одной стороны к другой Снарк никак не смог убежать.

Рис. 1

Начнём с ловли Снарка, который всегда увеличивает свою y-координату. Заметим, что если Булочнику удалось организовать барьер из трёх подряд идущих булочек перед Снарком (см. рис. 1), то его дело в шляпе, ведь Булочник сможет его поддерживать независимо от ходов Снарка: нужно просто ставить булочку с того края «стенки», к которой ближе Снарк. Чтобы построить для Снарка такую ловушку, Булочник построит сеть с не очень крупными ячейками. Как только Снарк к ней приблизится, Булочник начнёт заполнять ячейки прямо перед Снарком и добьётся ситуации на рис. 1. Теперь опишем решение совсем строго.

На рис. 2 жёлтым выделена область, в которой может оказаться Снарк. На расстоянии 10 от Снарка через 4 пустых клетки Булочник поставит по булочке. На это потребуется 5 ходов, Снарк за это время окажется в одной из красных клеток. Теперь Булочник начинает заполнять ячейки сети. Булочник всегда ставит булочку прямо над Снарком, если это возможно, или в ближайшую соседнюю свободную клетку. На следующем ходе прямо над Снарком будут находиться уже хотя бы две булочки. Если Снарк изменит направление движения или пойдёт строго вверх, то Булочник выставит третью булочку рядом, и его задача будет выполнена. Если же Снарк всё время ходит, перемещаясь в одном направлении, то не позже чем через 4 хода над ним окажется один из узлов сети, поставленный заранее. И это позволит Булочнику поставить третью булочку в барьер.

Рис. 2

Задача. Найдите минимальное количество булочек, достаточное для поимки такого Снарка.

Замечание. Ширину ячеек 4 можно заменить на любую ширину n > 1: на расстоянии k от начального положения имеется 2k + 1 возможных положений Снарка. Чтобы построить сетку шириной n, достаточно 2k/(1 + n) + 2 булочек, при этом должен остаться промежуток в n + 1 строку от Снарка до стены. Значит, нам подойдёт любое достаточно большое k при котором

    2k/(1 + n) + 2 + n + 1 ≤ k.

Теперь будем ловить общего Снарка силы 1. Неформально идея решения состоит в следующем. Булочник выбирает достаточно большой квадрат с центром в начальном положении Снарка и добивается того, чтобы Снарк никогда не покинул пределы квадрата. Для этого Булочник первыми ходами заполняет булочками 4 угловых квадрата достаточно большого размера. Затем, пока Снарк далеко от границы квадрата, Булочник равномерно заполняет стороны квадрата так, чтобы образовалась сеть с не очень крупными ячейками. Когда Снарк подходит к границе достаточно близко, Булочник заполняет промежутки в сети. Близкие клетки образуют буферную зону шириной в некоторое заранее заданное количество линий. Нам будет достаточно буферной зоны шириной в 9 линий (рис. 3).

Рис. 3

Заметим, что периметр квадрата в 8 раз больше, чем количество ходов, которое требуется Снарку силы 1 для того, чтобы дойти до границы этого квадрата. Так как t/8 > t/9 + const при достаточно большом t, то при достаточной величине квадрата можно заполнить границу сетью с величиной ячеек в 8 клеток (плотности 1/9) и расставить булочки в углах большого квадрата (длины сторон угловых квадратов должны превышать ширину буферной зоны) до того как Снарк войдёт в буферную зону. Угловые квадраты разбивают буферную зону на четыре компоненты — четыре прямоугольника, прилегающих к сторонам большого квадрата.

Когда Снарк впервые входит в буферную зону, Булочник ставит булочку в проекцию Снарка на ближайшую к нему сторону («над ним»). По мере движения Снарка Булочник успевает выставлять над ним булочки, и поэтому рядом с проекцией Снарка будут находиться хотя бы две булочки (возможно, уже будет и третья булочка — булочка из сети). Как только Снарк изменит направление движения вдоль этой стороны или пойдёт строго по направлению к ней, Булочник моментально выставит третью булочку рядом с проекцией, и его задача будет выполнена.

Если же Снарк всё время ходит, перемещаясь вдоль стороны в одном направлении, то не позже чем через 8 ходов под его проекцией окажется один из узлов сети, поставленный заранее. И это позволит Булочнику поставить третью булочку рядом с проекцией. Так как ширина буферной зоны больше, чем ширина ячеек сети, Булочник успеет реализовать один из этих вариантов. После этого Булочник без труда будет сохранять ситуацию, при которой под проекцией Снарка на сторону находятся три булочки. Поэтому даже когда Снарк подойдёт вплотную к границе, перед ним окажется непреодолимый барьер.

У нас в России задача о Снарке появилась в 2001 году на летней конференции Турнира Городов. Задача об «Ангеле и Дьяволе» стала называться задачей о Снарке и Булочнике по довольно банальным причинам: из соображений корректности, «мало ли что»... На конференции школьники пытались поймать Снарка силы 1, а также Снарков силы n, но прыгающих с некоторыми ограничениями.
Тогда, в 2001 году, ответ на общий вопрос был неизвестен. Да и вообще задача о Снарке силы 2 и более долгое время оставалась открытой. В своей статье о данной задаче (PDF, 167 Кб) Конвей обещал $100 за выигрышную стратегию для Снарка силы больше 1, и $1000 за выигрышную стратегию для булочника.

Задача относится к теории игр. Игры в реальном мире и в экономике всегда заканчиваются за конечное число шагов, однако в математике зачастую рассматриваются игры, способные продолжаться бесконечно долго. Причём победитель и его выигрыш иногда не могут быть определены до окончания всех ходов. Можно показать, что во всех играх наподобие задачи о Снарке (то есть в играх, где игроки ходят последовательно и исход игры не зависит от случая — например, в шахматах, го, ним и т. д.) либо у одного из игроков есть выигрышная стратегия, либо у второго игрока есть беспроигрышная стратегия. Впрочем в задаче о Снарке существование выигрышной стратегии у одного из игроков очевидно и без этого факта.

И если про Снарка силы 1 решение было уже в самой первой статье Конвея, то про Снарка большей силы не был ясен даже ответ. Весьма познавательны следующие задачи (из-за которых можно подумать, что Снарка силы больше 1 можно поймать):

Задача 1. Пусть Снарк силы n каждым ходом увеличивает свою y-координату. Докажите, что Булочник может его запереть.

Задача 2. Пусть Снарк силы n каждым ходом увеличивает расстояние до центра. Докажите, что Булочник может его запереть (эта задача была решена только в 1996 году).

Задача 3. Предположим, что Снарк подозрителен, и если он однажды мог прыгнуть на клетку, но не сделал этого, то никогда больше он на эту клетку не прыгнет. Докажите, что если Булочник может поймать подозрительного Снарка, то он может поймать и обыкновенного Снарка той же силы.

Окончательное решение задача о Снарке силы n в общем случае (“Angel problem”) получила только в 2006 году. Оказывается, несмотря на то что для любого n, «бегущего вверх», Снарка удаётся поймать, у Снарка силы 2 в общем случае существует выигрышная стратегия. Забавно, но различные решения этой задачи были даны практически одновременно несколькими разными математиками. Достались ли кому-нибудь заветные $100 — неизвестно.

Кроме того, существуют трёхмерные варианты охоты на Снарка, например:

Задача 4. Охота происходит в пространстве, разделённом на кубики. Пусть Снарк каждым ходом может перепрыгнуть на любой соседний по грани кубик (шесть возможных ходов). Сможет ли Булочник запереть такого Снарка?