Problem

Source: Serbian National Olympiad 2012, Problem 3

Tags: analytic geometry, geometry, 3D geometry, combinatorics proposed, combinatorics



A fly and $k$ spiders are placed in some vertices of $2012 \times 2012$ lattice. One move consists of following: firstly, fly goes to some adjacent vertex or stays where it is and then every spider goes to some adjacent vertex or stays where it is (more than one spider can be in the same vertex). Spiders and fly knows where are the others all the time. a) Find the smallest $k$ so that spiders can catch the fly in finite number of moves, regardless of their initial position. b) Answer the same question for three-dimensional lattice $2012\times 2012\times 2012$. (Vertices in lattice are adjacent if exactly one coordinate of one vertex is different from the same coordinate of the other vertex, and their difference is equal to $1$. Spider catches a fly if they are in the same vertex.)