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.)
Problem
Source: Serbian National Olympiad 2012, Problem 3
Tags: analytic geometry, geometry, 3D geometry, combinatorics proposed, combinatorics
06.04.2012 12:11
In a $n^r$space where $n$ is finite, we just need $r$ spiders. It is easy to see that it works. For $r=2$ $k=1$ doesn't go, so first part solved.
06.04.2012 18:33
SCP wrote: In a $n^r$space where $n$ is finite, we just need $r$ spiders. Proof it doesn't work with $r>k$ spiders, take $k=r-1:$ Starting in such a way that the fly isn't taken yet: we have $r$ $n^{r-1}$ subspaces, hence we can take one subspace where no spider is, the fly will move in this subspace, there are at least $(r-1)$ adjacent vertices + teh vertex where the fly is and because each spider can only catch max. one vertex in the subspace, we have min. $r-k\ge 1$ safe vertex. I would check this one more time. That's not quite true.
06.04.2012 19:53
It seems I'll find my mistake with looking for $r=3.$
10.04.2012 11:27
I proved in \[n*n\] and in \[n*n*n\] board the answer is k=2.
10.04.2012 12:40
I thought I'll prove it now: really other way of view: suppose it is imposs.: look to one spider: suppose the smallest distance a spider can go to the fly, is $a>2$ (sum of differences of coordinates). Now the spider can go closer to the fly: -so that each coordinate will be different: take a corner of the cube and make the rectangular cuboid formed by that corner and the place of the spider, so that the fly is inside it, each time smaller: the fly never goes on the boundary, or the smallest distance is less than $a$, but because the cuboid becomes smaller and can't do that for $\infty$ steps, we get contradiction. OR - the fly and the spider are always in same plane and by taking a corner of the plane, the spider can go closer. OR -always on same line, similar case, the spider just go to the fly until it reaches the boundary Hence we can place both spiders to max. $a=2$ of the fly and in that case, take the two OR-cases to get $a=1$ already. Now one spider can place them with $a=1$ next to the fly, the other takes $a=2$ (such that the fly and this spider are in an other plane than the second spider) and will be with two coordinates different after some time/ it is possible, just go again to the boundary. Now the fly always had $6$ direction, but only $3$ make it keeps alive and so the fly goes to one certain corner of the cube, the formed cuboid becomes smaller and so it will be ever catched. So, I agree I made my $1000^{th}$ stupid mistake already on ML.
25.04.2012 19:16
too see this problem and more generalization (without proof) see this one: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1259467&sid=cd5faf0c1e2627d937d6e4a6173c7b03#p1259467