Replicating Amoebas

 This is a puzzle from Peter Winkler who himself got it from some field medalist apparently.

You have an amoeba at $(0,0)$. An amoeba can replicate by splitting itself,  and placing them one to the right and one above.

So if an amoeba is at $(x,y)$ after the replication of that, there will be no amoeba at $(x,y)$, one at $(x+1, y)$ and one at $(x, y+1)$.

This replication can only happen if the two target spots are empty. Otherwise the amoeba will not replicate. 

For eg starting with $(0,0)$ consider the following.

A split, now we have $(1,0)$ and $(0,1)$. 

The $(0,1)$ splits, now we have $(1,0), (1,1), (0,2)$.

Now if the $(1,0)$ wants to split, it cannot, because one of the targets $(1,1)$ is occupied.

Ok now for the puzzle.

You start with one amoeba at $(0,0)$. 

How many replications do we need to clear the square (including the inside of it) $(0,0), (2,0), (2,2), (0,2)$ of amoebas?

Solution.

.

.

.

.

.

The answer is, it is impossible to clear that grid!

We come up with an invariant. Give weight $1$ to the initial amoeba. If an amoeba of weight $w$ splits, give weights $\frac{w}{2}$ to each of its clones. Thus the total weight of amoebas is preserved.

Now the weights are non-positive powers of $2$ and given the location of the amoeba, you can actually determine its weight.

The weights look something like this ($(0,0)$ is bottom left of matrix)

$$\begin{matrix} \vdots & \vdots & \vdots & \vdots \\ \frac{1}{8} & \frac{1}{16} & \frac{1}{32} & \frac{1}{64} &\dots \\ \frac{1}{4} & \frac{1}{8} & \frac{1}{16} & \frac{1}{32}  & \dots \\ \frac{1}{2} & \frac{1}{4} & \frac{1}{8} & \frac{1}{16} & \dots \\ 1 & \frac{1}{2} & \frac{1}{4} & \frac{1}{8} & \dots \end{matrix}$$

Now the sum of all the weights in the grid of our interest  is $$ 1 + 2 \times \frac{1}{2} + 3 \times \frac{1}{4} + 2 \times \frac{1}{8}  + \frac{1}{16} = 3 \frac{1}{16}$$

The sum of weights of all the possible spaces is $S + \frac{S}{2} + \frac{S}{4} + \dots = S^2 $ where $S$ is the sum of the weights of the bottom row. 

It is easily seen that $S=2$, so the whole infinite grid sum is $4$.

Thus the sum of weights outside our grid of interest is no more than $4 - 3\frac{1}{16} < 1$.

Thus it is impossible to clear that grid, starting with a single amoeba at $(0,0)$, of initial weight $1$: there has to be some amoeba inside the grid to preserve the total weight of $1$.