Zombie Attack

Since the number of zombies on the lawn never decreases, it must stabilize at some point. Therefore after some time T, there will be exactly K zombies on the lawn at all times, 1 ≤ K ≤ 9.

Consider any 1000 consecutive zombies appearing past time T and take a picture of the lawn at the moment each of them gets dropped on it – this makes a total of 1000 pictures. Since on every picture, there are exactly K zombies, we see exactly 1000K zombies on these pictures.

Now notice that almost all of the selected 1000 zombies appear on as many pictures as lawn spots they traverse. The zombies for which this is not true are just the K zombies, which appear on the last picture. We easily see that they have traveled between 1 + 2 + … + K − 1 and (10 − K) + (11 − K) + … + 8 spots more than the number of pictures they appear on.

Similarly, on the 1000 pictures we have taken, there are K−1 additional zombies, which appear multiple times (you can see all of them on the first picture). The total number of times they show up is again between 1 + 2 + … + K − 1 and (10 − K) + (11 − K) + … + 8.

Therefore we conclude that the total distance the selected 1000 zombies travel is equal to 1000K ± {[(10 − K) + (11 − K) + … + 8] − [1 + 2 + … + K − 1]} = 1000K ± (9 − K)(K − 1).Since (9 − K)(K − 1) is a number between 0 and 16, this solves the problem.