3. On a square grid $2012 \times 2012$, a fly and $k$ spiders are located. A move consists of the following: the fly moves to an adjacent vertex or stays in the same place, and then each of the $k$ spiders moves to an adjacent vertex or stays in the same place (multiple spiders can be in the same vertex). At any moment, each spider and the fly can see the positions of the others.

a) Find the smallest $k$ such that the spiders can catch the fly in a finite number of moves, regardless of the initial positions of the fly and the spiders.

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

(Vertices are adjacent if they differ in exactly one coordinate by 1. A spider catches the fly if they are in the same vertex.)

(Nikola Milosavljević)

Time for work 270 minutes.

Each problem is worth 7 points.

# SERBIAN MATHEMATICAL OLYMPIAD

for high school students

Belgrade, 01.04.2012.

## Second day
3. A single spider cannot catch a fly. It is enough for the fly to remain stationary if the spider is not on an adjacent field, or to move to the diagonally opposite field if it is.

We will prove that two spiders are sufficient for both parts of the problem - let's denote them as $P$ and $Q$, the fly as $M$, and the $x$- and $y$-coordinates of point $A$ as $A_{x}$ and $A_{y}$.

(a) Place the coordinate origin at the bottom left corner of the grid. Initially, moving along the $x$-axis, $P$ achieves $P_{x} = M_{x}$ in a finite number of moves. Similarly, $Q$ achieves $Q_{y} = M_{y}$. Then the spiders move as follows: whenever the fly changes its $x$-coordinate, $P$ does the same to maintain $P_{x} = M_{x}$, otherwise it moves one step closer to the fly along the $y$-axis; the movement of $Q$ is analogous. In this way, the quantity $\left|P_{y} - M_{y}\right| + \left|Q_{x} - M_{x}\right|$ either decreases or remains the same, and it can remain the same for at most $2 \cdot 2010$ moves (when the fly retreats). Therefore, after a finite number of moves, at least one of the terms will become zero, i.e., the fly will be caught.

(b) Ignoring the $z$-axis, based on part (a), one of the spiders, say $P$, can achieve $P_{x} = M_{x}$ and $P_{y} = M_{y}$. Furthermore, whenever the fly makes a move along the $z$-axis, spider $P$ moves towards it, and otherwise, it moves so that it is always directly below the fly. Clearly, the fly can make only a finite number of moves along the $z$-axis or remain in place without being caught by spider $P$. Therefore, from some point onward, the fly must move exclusively within its $xy$-plane without stopping.

Now, spider $Q$ reaches the $xy$-plane in which the fly is moving in a finite number of moves. Also, by staying in place when necessary, $Q$ achieves that $f = \left|Q_{x} - M_{x}\right| + \left|Q_{y} - M_{y}\right|$ is even. In each subsequent move, spider $Q$ moves closer to the fly along the $x$-axis if $\left|Q_{x} - M_{x}\right| > \left|Q_{y} - M_{y}\right|$, and along the $y$-axis otherwise. After each move, the value of $f$ does not increase and does not change its parity, and it can remain the same only a finite number of times (when the fly runs away from the spider towards the edge of the grid). Therefore, at some point, $f$ will be $0$, and the fly will be caught.