\documentclass{article}
\usepackage{a4}
\voffset=-1cm
\hoffset=-2cm
\advance\textwidth by 4cm
\advance\textheight by 1cm
\frenchspacing
\usepackage{amssymb}
\let\eps\varepsilon
\begin{document}

\begin{center}\LARGE
\textbf{Охота на Снарка}

\textbf{(решения)}

\end{center}

\textbf{0.} (А.~Голубов, М.~Каленков)

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

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

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

\textbf{$\eps$.}
Заметим, что если зафиксировать горизонтальную линию~$L$ на
достаточном расстоянии выше Снарка, то на ней можно выделить
отрезок, который Снарк только и может достичь (область
достижимости). 
За один ход Снарк может изменить абсциссу не более чем на~$n$, а 
ордината увеличивается не менее чем на~1, поэтому область достижимости 
содержится в отрезке
длины $\ell=3x(n+1)$, где $x$~--- количество горизонталей между 
текущим положением Снарка и линией~$L$. Далее именно этот отрезок и 
будем называть областью достижимости. Для того чтобы Снарк не прорвался 
за линию~$L$, над областью достижимости надо выстроить барьер 
высоты~$n$. 

Снарк проходит половину 
расстояния до линии~$L$ не быстрее, чем за $\frac{x}{2n}$ ходов. 
Всё это 
время Булочник строит барьер над всей областью достижимости, равномерно 
заполняя булочками ближайший к линии~$L$ ряд.
Он успевает поставить по крайней мере $\frac{x}{2n}$ булочек. 
Весь барьер требует $3x(n+1)\cdot n$ булочек,
таким образом
%, если Булочник расставляет булочки через равные
%промежутки, 
он успеет заполнить по крайней мере
$$
\frac{x}{2n^2\cdot 3x(n+1)}>\frac{1}{6n^3}
$$
часть барьера.

Когда Снарк пройдёт половину расстояния~$x$, ширина области
достижимости уменьшится вдвое (поскольку $\ell$ зависит от~$x$ 
линейно), следовательно, уменьшится вдвое и число булочек, требуемых 
для постройки барьера.  Значит, пока Снарк будет преодолевать половину 
оставшегося расстояния $x/2$, Булочник сумеет построить ещё $1/6n^3$ 
часть того участка барьера, через который Снарк может прорваться. 
Повторяя указанные действия, через $6n^3$ раз Булочник полностью 
выстроит участок барьера перед Снарком. Чтобы описанная стратегия 
привела к успеху, $x$ должно быть достаточно велико, например 
$x>2^{6n^3+1}$.

\textbf{$2\eps$.}  Частный случай следующей задачи.

\textbf{$3\eps$.} Обозначим $D=1\,000\,000+1$. 
Покажем, что Булочник может заставить Снарка 
увеличивать ординату не реже чем один раз за~$T$ ходов. 
Тогда его можно ловить как $\eps$-Снарка скорости~$Tn$.

Опишем стратегию вытеснения Снарка вверх.  
Пока Снарк не 
увеличивает ординату, Булочник выстраивает стенки высоты $D$ и ширины $n$
слева и справа от 
положения Снарка в начале вытеснения, 
так чтобы между стенками было $4Dn^2+1$ вертикалей (верхние стороны 
стенок лежат на горизонтали, в которой находится Снарк в начале 
вытеснения).  Заполняя пространство между стенками, Булочник 
вынуждает Снарка увеличивать координату $y$ не реже, чем раз за 
$(4Dn^2+1)D+2Dn$ ходов.  Таким образом, $T$ можно считать равным 
$(4Dn^2+1)D+2Dn$.

\textbf{$4\eps$.}  Частный случай следующей задачи.

\textbf{$5\eps$.} Обозначим через  $D=1\,000\,000+1$, а через $N$~--- 
максимальное количество ходов, за которое ловится $3\eps$-Снарк 
той же скорости и с тем же значением $D$.  Булочник выбирает настолько 
большой квадрат с центром в начале координат, что он содержит начальное 
положение Снарка и сторона квадрата не менее $2K+1$ (значение $K$ 
укажем позже).

Первая стадия состоит в том, что Булочник заполняет булочками в очень большом 
квадрате четыре угловых квадрата со стороной $Nn+\max(D,n)$
(так что $K=4n(Nn+\max(D,n))^2+Nn+\max(D,n)$).
Пока Снарк не приближается к границе очень большого квадрата ближе, чем 
на $Nn$, Булочник заполняет клетки очень большого квадрата 
произвольным образом. Рано или поздно Снарк будет вынужден приблизиться 
к границе квадрата на указанную величину. Теперь расстояние от Снарка 
до начала координат определяется значением лишь одной координаты, и 
Булочник может запереть Снарка, пользуясь стратегией из задачи 
$3\eps$. 

\textbf{1/2001.}  Предположим, что Булочник ловит подозрительного 
Снарка. Тогда найдётся такое число $k$, что Снарк будет пойман не более 
чем за $k$ ходов. 
Считаем, что 
Булочник придерживается определённой стратегии, так что его поведение 
детерминированно. Рассмотрим \emph{дерево игры}, 
состоящее из всех позиций игры после хода Булочника. Две позиции 
соединяются направленным ребром, если вторая получается из 
первой после некоторого хода Снарка и ответа Булочника.
Таким образом, в 
дереве игры из каждой вершины исходит лишь конечное число рёбер (не 
более чем $(2n+1)^2$).  Поскольку Снарк ловится, в дереве нет 
бесконечных ветвей.  Но тогда в дереве конечное число вершин. Это легко 
доказывается индуктивным рассуждением от противного.  Пусть в дереве 
бесконечное число вершин.  Построим бесконечную ветвь, начинающуюся из 
корня, выбирая каждый раз среди потомков последней из уже выбранных 
вершин ту, у которой бесконечное количество потомков (она существует, 
так как ветвление конечно).  

Теперь Булочник будет ловить обыкновенного Снарка, 
придерживаясь следующей стратегии. Пока Снарк не 
возвращается в те клетки доски, на которые он мог сделать ход ранее, 
Булочник играет по стратегии ловли подозрительного Снарка. Когда Снарк 
возвращается, Булочник забывает все ходы, начиная с момента, когда 
Снарк первый раз мог сделать ход в текущую клетку, и продолжает ловлю 
подозрительного Снарка. Если клетка, на которую Булочник должен 
сделать ход, уже занята, то он делает ход в произвольную свободную 
клетку большого квадрата со стороной $2nk+1$ и с центром в 
начальном положении Снарка. 

Если Снарк сделает $k$ ходов подряд без возвращения, он будет пойман 
как подозрительный. В противном случае Снарк не покидает пределов 
большого квадрата, так что рано или поздно он будет отловлен. 

\textbf{1/2000.} Перенумеруем все клетки плоскости.

В задаче $5\eps$ описана стратегия поимки Снарка, 
который никогда не подходит к началу координат на расстояние, меньшее 
по сравнению с некоторым предыдущим моментом на $D=1\,000\,000$ или 
более. Нетрудно убедиться, что все эти рассуждения переносятся без 
изменения на любое число $D$ и любую клетку доски%
%в качестве начала координат
. Поэтому Булочник может каждым вторым ходом играть против Снарка 
удвоенной скорости $2n$, заставляя его приблизиться к первой клетке 
$(x_1,y_1)$ на расстояние $D(x_1,y_1)$; каждым вторым из оставшихся 
ходов~--- играть против Снарка учетверённой скорости, заставляя его 
приблизиться ко второй клетке $(x_2,y_2)$ на расстояние $D(x_2,y_2)$; 
\dots Снарк будет вынужден рано или поздно приближаться к любой клетке 
на требуемое расстояние.



\end{document}


размещает булочки через одну на участке (участках)
границы квадрата, ближайшем (ближайших) к Снарку. Если же Снарк
подходит к границе слишком близко, Булочник начинает заполнять
пробелы на границе, пользуясь тем, что плотность булочек на
границе в непосредственной близости от Снарка составляет 1/2.

Приведём теперь детали. Пусть большой квадрат имеет размеры
$(2K+1)\times(2K+1)$, где $K\geqslant22$. Выделим несколько зон.
Зона
\лк безразличия\пк~--- квадрат $(2C+1)\times(2C+1)$, где
$C=4\cdot5$, концентрический большому квадрату. Зона \лк
неопределённости\пк\ состоит из 10~линий, параллельных
диагоналям большого квадрата и симметрично примыкающих к
диагоналям, за вычетом клеток, попадающих в зону
\лк безразличия\пк. \лк Буферная\пк\ зона состоит из клеток,
примыкающих к границе, и имеет ширину~2. Наконец, оставшуюся
часть квадрата занимает зона \лк спокойствия\пк.

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

Заметим, что Булочник выстраивает \лк забор\пк\ по границе вдвое
быстрее, чем двигается Снарк или с той же скоростью, если Снарк
находится в зоне неопределённости. Поэтому Снарк не может
покинуть пределы квадрата.
