# Plants vs Zombies Annihilation

After the zombies ate your brain at the end of level 1, Dr. Zomboss decides to continue sending his legions of undead until they completely destroy your house. At every 4 seconds, he drops a new zombie on some unoccupied spot of your lawn. All zombies move towards the left and each of them needs exactly 4 seconds to traverse through one of the spots on the lawn. Show that after some time T, the total distance traveled by any 1000 consecutive zombies will be almost the same - within range of just 32 spots.

HINT 1

You don't need to be able to point out when the time T comes, just to prove that it exists.

HINT 2

You may want to use your photo camera extensively.

P.S. Unfortunately I can not take the credit for this puzzle. I just simplified/modified a problem from some Math competition, which made the original question easily approachable. I believe that in the context of zombies, it is not that hard to figure it out (but still not that easy). Later will post reference to the original problem.

• I am not familiar with how the zombies function in this scenario. Can you clarify their behavior? Jul 26, 2015 at 13:13
• Do they just skip the previously-destroyed spots on their way until they arrive at the next unoccupied one in every 4 seconds? Jul 26, 2015 at 13:16
• @Nautilus, Goinghamateur: They only move left. No destruction of squares, no fancy AI - just move left.
– Deusovi
Jul 26, 2015 at 13:20
• To clarify: (1) the lawn has 9 spots as in the picture, and (2) the "total distance traveled by 1000 consecutive zombies" is the total amount of steps all those 1000 zombies need(ed) to leave the lawn, regardless of whether they already made those steps or not. Is this right? Jul 26, 2015 at 13:31
• The lawn has 9 spots. Every zombie gets dropped in the center of one of them and then moves with constant speed towards the left. For example, if a zombie gets dropped on the second spot, it will need 2 steps/moves/spots (during which 2 new zombies will be dropped) in order to get in the house. The zombies never stop walking, so the amount of steps made by them and the distance they need to travel initially are the same. Jul 26, 2015 at 16:53

We first notice the following crucial fact:

The number of zombies on the field never decreases.

This is obvious since each step adds one zombie and removes at most one. However, since the number of zombies can never exceed $9$, it follows that, after some time $T$, the number of zombies on the field is constant*. We will prove that zombies created after time $T$ satisfy the desired condition. After this point, the following rule must be observed:

If there is not a zombie at the leftmost plot, a zombie must be added there.

We must follow this as otherwise one would be adding a zombie without removing one.

Now, we consider that, if there are $n$ zombies on the field at all time, we would expect that, as they walk a total of $n$ steps left each turn. We get a bit of a hint on how to use this fact in the $n=2$ case - in particular, if we make a list of which plot the zombies are placed at (with $1$ being the leftmost), we might see a pattern like: $$2,2,3,1,5,1,1,1,4,1,1,2,2,\ldots$$ where (after a point) we will necessarily see a concatenation of patterns of the form: $$k,\underbrace{1,1,\ldots,1,1}_{k-2\text{ times}}$$ since we have to "wait" for the zombie placed at $k$ to reach the start. When we're summing over such a pattern, we can see that we can "shift" the mass away from the $k$ and towards the $1$s to leave a sum of $2(k-1)$. In a sense, when we put a $k>2$ in the pattern, we're taking a "loan" from later in the pattern, which we slowly repay by taking only $1$ step (less than the "allotted" $2$ steps per zombie).

This suggests to us we want to find some function which takes a state of the game as input and tells us how much "debt" we have to repay (we might also call it an energy function). We will define a state as a subset $S$ of the squares in the garden, representing the set which are occupied by zombies right before a new one is placed. Note that thus the rightmost square will never be occupied, as a zombie placed there immediately wanders left and that if there are $n$ zombies $|S|=n-1$ since the state occurs after a zombie has just walked off and before its replacement is added. A legal transition from $S$ to another state consists adding a new element, then decrementing all the elements and removing $0$ if it appears. We wish to find a function $E_n(S)$ on states such that $|S|=n-1$ which satisfies the following crucial property:

Suppose state $S'$ could occur immediately after state $S$ when Dr. Zomboss adds a zombie at position $k$. Then $E_n(S)-E_n(S')=n-k$.

This is to say we are measuring the difference between a given move and the allotment of zombie steps - so if we've got "too many" steps $E_n(S')$ will be more than $E_n(S)$. Notice that this defines $E_n$ up to a constant factor if it exists at all. One may explicitly compute it by choosing $E_n(S)=e$ for some arbitrarily chosen $S$ and $e$ and finding the energy of all states reachable from it - and thinking about that idea for a second leads us to the following valid energy function: $$E_n(S)=\sum_{s\in S}s$$ One may check that this satisfies the desired condition.

Then, the rest is easy: Suppose $S_0$ was the state before the first zombie included in the sum is added and $S_{1000}$ was the state after the last zombie in the sum was added (and the intervening $S_i$ are defined accordingly). In particular, we may show that the number of steps walked by those $1000$ zombies is: $$E(S_{1000})-E(S_0)+1000n.$$ This is easy because if the $i^{th}$ zombie walked a distance of $k_i$, then $E(S_{i})-E(S_{i-1})=k_i-n$, thus we may algebraically manipulate the desired sum as in the following sequence of equivalent expressions: $$k_1+k_2+k_3+\ldots+ k_{999}+k_{1000}$$ $$(k_1-n)+(k_2-n)+(k_3-n)+\ldots + (k_{999}-n)+(k_{1000}-n)+1000n$$ $$[E(S_1)-E(S_0)]+[E(S_2)-E(S_1)]+\ldots +[E(S_{1000})-E(S_{999})]+1000n$$ where this last sum telescopes to $$E(S_{1000})-E(S_{0})+1000n.$$ Now, if we let $A$ be the state with the least energy and $B$ be the state with the most, the we have: $$E(A)-E(B)+1000n \leq E(S_{1000})-E(S_{0})+1000n\leq E(B)-E(A)+1000n.$$ meaning the difference between any pair of such sums may be at most $2[E(B)-E(A)]$.

Clearly, $B=\{8,7,\ldots,9-n\}$ has the most energy and $A=\{1,2,\ldots, n\}$ has the least - and $A$ is a translation of $B$ leftwards by $(8-n)$ meaning the difference between the energy is $n(8-n)$. This is maximized when $n=4$ yielding $16$ as the total difference in energy. Thus, no such sum may differ by more than $2\cdot 16=32$ after the field settles into a constant number of zombies.

(*More strongly, if we consider a game state to be the set of plots on which zombies lie and say $A\sim B$ if state $A$ could occur after state $B$ and vice versa, then it happens that $A\sim B$ is equivalent to $|A|=|B|$ meaning that the number of zombies is essentially the only invariant of this type - so we're in trouble if this $T$ doesn't cut it!)

@MiloBrandt already posted a solution (make sure to upvote him!), but I wanted to give an alternative explanation.

As Milo noted, the number of zombies never decreases and therefore at some moment it stabilizes, say at $1 \leq K\leq 9$ zombies after time $T$.

Now consider any $1000$ consecutive zombies appearing past time $T$ and take a picture of the lawn in 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 all pictures.

Now notice that almost all of the selected $1000$ zombies appear on as many pictures as lawn spots they travel. 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 made, 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 \begin{align}&&1000K \pm \{[(10-K)+(11-K)+...+8]-[1+2+...+K-1]\}\\ =&&1000K \pm (9-K)(K-1). \end{align} Since $(9-K)(K-1)$ is a number between $0$ and $16$, this solves the problem.

This problem was supposedly the hardest question from this year's IMO, but thought it could be translated into a nice puzzle. Hope you liked it. http://imo2015.org/solution.php?lang=en

Once again, make sure to upvote Milo's answer, as he uploaded first a legit solution.