Maths Olympiad Prep

Library / /87 of 87

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Serbia

Problem:

At some vertices of a 2012×20122012 \times 2012 square grid there is a fly and kk spiders. One move consists of the following: the fly moves to an adjacent vertex or stays at the same place, and after that each of the kk spiders moves to some adjacent vertex or stays at the same place (there can be more than one spider at a vertex). At every moment each spider and the fly have knowledge of the positions of the others.
a) Find the smallest kk such that the spiders can catch the fly in a finite number of moves, regardless of the starting position of the fly and the spiders.
b) Answer the same question for the cubic grid 2012×2012×20122012 \times 2012 \times 2012.
(Vertices are adjacent if they differ in exactly one coordinate, and by 1. A spider catches the fly if they are located at the same vertex.)
(Nikola Milosavljević)

Solution

Solution:

One spider cannot catch the fly. It suffices that the fly does not move if the spider is not on an adjacent field, that is, that it moves to the field diagonally opposite the spider's if it is.
We will prove that two spiders suffice in both parts of the problem - let us denote them by PP and QQ, the fly by MM, and the xx- and yy-coordinate of a point AA by AxA_{x} and AyA_{y}.

a) Let us place the origin of the coordinate system in the lower left corner of the grid. At the start, moving along the xx-axis, PP achieves in a finite number of moves that Px=MxP_{x}=M_{x}. Analogously, QQ achieves that Qy=MyQ_{y}=M_{y}. Afterwards the spiders move in the following way: whenever the fly changes its xx-coordinate, PP does the same so that Px=MxP_{x}=M_{x} remains true, otherwise it approaches the fly by one step along the yy-axis; the movement of QQ is analogous. In this way the quantity PyMy+QxMx|P_{y}-M_{y}|+|Q_{x}-M_{x}| either decreases or stays the same, where it can stay the same for at most 220102 \cdot 2010 moves (when the fly is retreating). Therefore, after a finite number of moves at least one summand will become zero, i.e. the fly will be caught.

б) Disregarding the zz-axis, based on part (a), one of the spiders, say PP, can achieve that Px=MxP_{x}=M_{x} and Py=MyP_{y}=M_{y}. Further, whenever the fly makes a step along the zz-axis, the spider PP moves toward it, and otherwise it moves so as always to be exactly below the fly. It is clear that the fly can make a step along the zz-axis, or stay in place, only finitely many times without being caught by the spider PP. Therefore, starting from some moment, the fly must move exclusively within its xyxy-plane, without staying in place.
Now the spider QQ reaches, in a finite number of moves, the xyxy-plane in which the fly is moving. Also, by staying in place as needed, QQ achieves that f=QxMx+QyMyf=|Q_{x}-M_{x}|+|Q_{y}-M_{y}| is even. In each subsequent move, the spider QQ approaches the fly along the xx-axis if QxMx>QyMy|Q_{x}-M_{x}|>|Q_{y}-M_{y}|, and along the yy-axis otherwise. After each move, the quantity ff does not increase and does not change its parity, and it can remain the same only finitely many times (when the fly is fleeing from the spider toward the edge of the grid). Therefore, at some moment f=0f=0 will hold, and the fly will be caught.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from sr; metadata (topic, difficulty) added by this project.