\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{The Hunting on the Snark}

\textbf{(solutions)}

\end{center}

\textbf{0.} (by A.~Golubov and M.~Kalenkov)

Informally speaking the idea of the solution can be described as
follows. First the Baker chooses a large enough square centered
at the initial position of the Snark. 
The Baker tries to lock the
Snark within this large square. During first several 
moves Baker
fills with the
cakes four squares in the corners of the large square. These four 
smaller squares should also be large enough. Then, while the Snark is 
``far enough'' from the border of the large square the Baker forms a 
net on this border with relatively small gaps.  When the Snark 
reaches the boundary layer of the border the Baker fills in the gaps.  
The boundary layer is the band of width~9.


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

It appears that the perimeter of the large square is eight times as
big as the number of moves that the Snark needs to
reach the border of this square. Since
$t/8>t/9+\mathrm{const}$ for large enough $t$ 
the Baker is able to form a net with
8-square gaps (in other words, a net of density 1/9) and fill the 
corner squares with cakes (sides of the corner squares should be 
greater than the width of the boundary layer) before the Snark reaches 
the boundary layer. This way the boundary layer is split into four 
different parts~--- four rectangles going along the border of the large 
square.  Right after the Snark jumps into the boundary layer the 
Baker starts to fill in the gaps in the net in the following way. He 
tries to build a barrier of three cakes underneath the Snark. Once 
such a barrier is built the Baker can easily expand this barrier 
on time ever after no matter which direction the Snark moves. Now we 
need only to prove that the Baker can create a barrier before the Snark 
escapes from the large square.

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

When the Snark jumps into the boundary layer for the first time
the Baker puts a cake at the projection of the Snark on the
nearest side of the large square (``underneath him''). As the
Snark moves the Baker puts cakes underneath him, therefore there
are always two cakes near the projection of the Snark. Should
the Snark change the direction along the border or jump
directly towards it the Baker immediately puts the third cake near
the projection of the Snark and his goal is fulfilled. If the
Snark makes eight moves in the same direction, he stands above a cake
of the net at some moment. At this moment the Baker puts the
third cake to the barrier. Once the barrier has been created,
the Baker can expand it on time as the Snark moves around it. So when 
the Snark moves to the border of the square, he runs into the barrier 
formed by three cakes.

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

\textbf{$\eps$.}
It is obvious that if we fix a horizontal line~$L$ at some
distance above the Snark's current position then there exists a segment 
on this line through which the Snark will necessarily pass (reachable 
area). In one move the Snark can change his $x$-coordinate at most by
$n$ while his $y$-coordinate increases at least by 1, therefore his
reachable area can be covered by a the segment of length 
$\ell=3x(n+1)$, where $x$ equals the number of horizontal lines between 
the current position of the Snark and line $L$. In what follows
Below we will call this segment the reachable area. It is sufficient 
to build a barrier of height $n$ above the reachable area in order to 
prevent the Snark from crossing line $L$.

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

The Snark cannot reach distance $x/2$ from line $L$ in less than
$\frac{x}{2n}$ moves. Meanwhile, the Baker partially builds the
barrier over the reachable area by placing cakes uniformly on the
line next to line $L$ from below. He places  $\frac{x}{2n}$ cakes
while the whole barrier requires $3x(n+1)\cdot n$. So the Baker can 
fill 
$$
\frac{x}{2n^2\cdot 3x(n+1)}>\frac{1}{6n^3}
$$
share of the barrier at least.

%Снарк проходит половину
%расстояния до линии~$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}
%$$
%часть барьера.

Consider the moment when the Snark passes through half distance~$x$, 
then the width of his reachable area is halved (as $\ell$ is a linear 
function of $x$). Therefore the number of cakes needed for building
the barrier is halved too. While the Snark is passing through half 
of the remaining distance $x/2$, the Baker can fill another $1/6n^3$ 
share of the barrier over his updated reachable area. After $6n^3$ 
repetitions of the above procedure the Baker will complete the barrier 
over the reachable area of the Snark. If $x$ is large enough, 
e.~g. $x>2^{6n^3+1}$, this the Baker will succeed in catching the 
Snark.

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

\textbf{$2\eps$.} This is a corollary of the next problem.

\textbf{$3\eps$.} Let $D$ be equal to $1\,000\,000+1$. We will show 
that the Baker can force the Snark to increase its $y$-coordinate at 
least once in $T$ moves. Then this Snark can be caught by using the 
strategy of catching the $\eps$-Snark of velocity $Tn$.

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

Now we describe the strategy of pushing the Snark upwards. As long as 
the Snark does not go above the position he holds at the beginning of 
pushing (\emph{starting position}), the Baker builds walls of height 
$D$ and width $n$ to the left and to the right of the starting 
position.  There should be $4Dn^2+1$ 
vertical lines between these walls and their upper borders should lie 
on the same horizontal line that the Snark was at the beginning of 
pushing. After completing the walls the Baker fills the space between 
them. In this way the Snark will be forced to increase his 
$y$-coordinate at least once in $(4Dn^2+1)D+2Dn$ moves. So 
$T$ is equal to $(4Dn^2+1)D+2Dn$.

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

\textbf{$4\eps$.} This is a corollary of the next problem.
 
\textbf{$5\eps$.} Let $D$ be equal to $1\,000\,000+1$. Let $N$ denote 
the maximum number of moves required to catch the $3\eps$-Snark of the 
same velocity for the same value of $D$. The Baker chooses so huge a
square centered at the origin that this square contains the initial 
position of the Snark. The side of this square we will denote by $2K+1$ 
where the value of $K$ will be indicated below.

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

On the first stage the Baker fills the four corner squares in the huge 
square with cakes. Their sides will be $Nn+\max(D,n)$, then we can take
$K=4n(Nn+\max(D,n))^2+Nn+\max(D,n)$. While the Snark is 
moving further than $Nn$ squares from the border of the huge square, 
the Baker fills squares in the huge square as he likes. But sooner or 
later the Snark will be forced to come closer than that. From that 
moment the distance between the origin and the Snark depends on one of 
his coordinates only. This gives the Baker an opportunity to catch the 
Snark as in problem $3\eps$.

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

\textbf{1/2001.} Suppose the Baker can catch the suspicious Snark. Then 
there exists a number $k$ such that the Snark will be caught in less 
than $k+1$ moves. We suppose that the Baker puts cakes according to his 
strategy, i.~e., his behavior is deterministic. Let us consider the 
\emph{tree of the game}. It consists of all possible positions of the 
game after the Baker's moves. An edge connects one position to another 
iff the latter can be obtained from the former after the Snark's move 
and the Baker's answer. Hence each vertex of the tree has only finite 
number of outgoing edges (no greater than $(2n+1)^2$). The Snark is 
caught in any case, therefore there are no infinite branches in the 
tree. It follows that the tree has only finite number of vertices. It 
can be easily proved by induction. If the tree would have infinite 
number of vertices we would be able to construct an infinite branch. On 
each step we would choose a branch  going from the last chosen vertex 
having infinitely many descendants (such a branch exists due to finite 
branching at any vertex).

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

Now the Baker will use the following strategy to catch the usual Snark. 
If the Snark jumps to a square that he couldn't reach before, the 
Baker plays according to the strategy for catching the suspicious 
Snark. But if the Snark jumps to a square that he could jump on 
beforehand, the Baker ``forgets'' all the moves from the moment the 
Snark could jump on this square for the first time. Then the Baker 
continues to catch the suspicious Snark. It may happen that the Baker 
should put a cake on the square already occupied with a cake. In this 
case he can put a cake on any square inside a large square centered at
the initial position of the Snark with side $2nk+1$.

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

If the Snark behaves as a suspicious one during $k$ moves he will be 
caught. Otherwise he will never leave the large square and therefore he
will be caught too.

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

\textbf{1/2000.} Let us enumerate all squares of the plane. 

%Перенумеруем все клетки плоскости.

It is clear that the strategy described in problem $5\eps$ can be 
generalized to the case of any square considered as an origin and any 
number $D$. Therefore the Baker can do every 2nd move according to 
the strategy for catching $5\eps$-Snark of velocity $2n$  for 
$D=D(x_1,y_1)$ (considering $(x_1,y_1)$ as the origin). Every 2nd 
move of the remaining ones the Baker will perform the same strategy 
against the $5\eps$-Snark of velocity $4n$ for 
$D=D(x_2,y_2)$ (considering $(x_2,y_2)$ as the origin) etc. The Snark 
will be forced to come closer to each of the squares.

%В задаче $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, то центральный). Если
Снарк двигается по буферной зоне, то Булочник продолжает
оды в направлении движения Снарка.

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