3. In some vertices of a square grid $2012 \times 2012$ there are a fly and $k$ spiders. In each second, the fly moves to a neighboring vertex or waits, followed by each of the $k$ spiders moving to a neighboring vertex or waiting (there can be more than one spider in the same vertex). At all times, the fly and the spiders know the positions of the others.

a) Find the smallest $k$ such that the spiders can catch the fly in a finite time, no matter the initial positions of the fly and the spiders.

b) Answer the same question for a cube grid $2012 \times 2012 \times 2012$.

(Two vertices are neighboring if they are on a distance 1. A spider catches the fly if they are both at the same vertex.)

(Nikola Milosavljević)

Time allowed: 270 minutes. Each problem is worth 7 points.

## Second Day
3. One spider cannot catch the fly if the fly waits for the spider to arrive to a neighboring cell, and then repeatedly moves onto a cell diagonally adjacent to the spider's. We shall show that the two spiders are enough in both (a) and (b) - denote them by $P$ and $Q$, the fly by $M$, and $x$ - and $y$-coordinates of point $A$ by $A_{x}$ and $A_{y}$.
(a) Set a cartesian coordinate system with the origin at the lower-left corner. First, moving along the $x$-axis, $P$ can achieve that $P_{x}=M_{x}$ in finitely many steps. Analogously, $Q$ achieves that $Q_{y}=M_{y}$. From this moment on, the spiders move in the following way: whenever the fly changes its $x$-coordinate, $P$ does the same to keep $P_{x}=M_{x}$, otherwise it moves one step along the $y$-axis towards the fly; $Q$ moves analogously. In this way, the quantity $\left|P_{y}-M_{y}\right|+\left|Q_{x}-M_{x}\right|$ either decreases or does not change, and it can stay unchanged through at most $2 \cdot 2010$ moves (when the fly flees). Hence after finitely many moves at least one summand will be zero, i.e. the fly will be caught.

(b) Disregarding the $z$-axis, by the part (a), one of the spiders, say $P$, can achieve that $P_{x}=M_{x}$ and $P_{y}=M_{y}$. In the next phase, whenever the fly moves along the $z$-axis, spider $P$ moves towards it, otherwise $P$ moves so as to stay straight under the fly. Clearly, in this manner the fly can make only finitely moves along the $z$-axis or stay still, before it would be caught by $P$. Hence, from some moment on, the fly must move within the same $x y$-plane, without staying still.

Next, spider $Q$ reaches the $x y$-plane of the fly. Also, staying still if needed, $Q$ achieves that $f=\left|Q_{x}-M_{x}\right|+\left|Q_{y}-M_{y}\right|$ be even. In every subsequent move, spider $Q$ moves towards the fly along the $x$-axis if $\left|Q_{x}-M_{x}\right|>\left|Q_{y}-M_{y}\right|$, otherwise it moves along the $y$-axis. After every move, the quantity $f$ does not increase or change parity, and only finitely many times can it stay unchanged. Therefore, in some moment we shall have $f=0$ and the fly will be caught.