Bacteria Grid Puzzle Solution

Key Concepts

Lattice Point Replication: A cellular automaton-style puzzle where a bacterium at $(x, y)$ replicates into $(x+1, y)$ and $(x, y+1)$, provided those spots are empty, while the original cell vanishes.
Invariant Quantity: A mathematical property that remains constant regardless of the sequence of moves.
Weighted Sum (Potential Function): A method of assigning values to grid points such that the total sum of weights remains constant throughout the replication process.
Convergence of Geometric Series: The mathematical principle used to calculate the total weight of the infinite grid.

The Replication Puzzle

The puzzle involves a bacterium starting at the origin $(0,0)$ of a grid. The rule for replication is: if the spots $(x+1, y)$ and $(x, y+1)$ are empty, the bacterium at $(x, y)$ can replicate, occupying those two spots and leaving the original spot empty. The objective is to clear all lattice points within a defined box (e.g., a 4x4 box containing 16 points).

Methodology: The Invariant Weighted Sum

To determine if a box can be cleared, the problem utilizes the concept of an invariant. By assigning a weight to each lattice point $(x, y)$ defined by $w(x, y) = (1/2)^{x+y}$, we can track the total "weight" of the system.

Weight Assignment: The origin $(0,0)$ is assigned a weight of $1$. Points on the first diagonal $(1,0)$ and $(0,1)$ are assigned $1/2$, and so on.
Conservation of Weight: When a bacterium at $(x, y)$ replicates, it is replaced by two bacteria at $(x+1, y)$ and $(x, y+1)$. The sum of the weights of the new positions is: $w(x+1, y) + w(x, y+1) = (1/2)^{x+1+y} + (1/2)^{x+y+1} = 2 \cdot (1/2)^{x+y+1} = (1/2)^{x+y} = w(x, y)$. Because the sum of the weights remains constant at $1$ throughout any number of moves, the total weight of the bacteria on the grid is always $1$.

Analysis of Grid Capacity

To clear a box, the bacteria must eventually occupy all points within that box and then move out of it. This requires the total weight of the points outside the box to be at least $1$.

Infinite Grid Calculation: The sum of weights for the entire infinite grid is calculated by summing the geometric series for each row and then summing those results. The total weight of the entire grid converges to $4$.
The 4x4 Box (16 points): The sum of the weights of the 16 points inside this box is slightly greater than $3.5$. Consequently, the sum of the weights of all points outside the box is less than $0.5$. Since the total weight of the bacteria is fixed at $1$, it is mathematically impossible for the bacteria to ever clear the 16-point box.
The 3x3 Box (9 points): The sum of the weights inside this box is $3.0625$. Because the total weight of the grid is $4$, the weight outside is $4 - 3.0625 = 0.9375$. Since $0.9375 < 1$, the bacteria cannot escape this box either.

Key Arguments and Findings

Impossibility Proof: The puzzle is a "cruel" one because the answer is not a number of moves, but a proof of impossibility. The constraints of the replication rules prevent the population from ever reaching the required density to clear the specified boxes.
Small-Scale Deception: While small boxes (1x1 or 2x2) can be cleared, the exponential growth of the required moves and the strict limit imposed by the weighted sum demonstrate that larger boxes are unreachable.

Conclusion

The primary takeaway is the power of using invariant quantities in problem-solving. By identifying a property that does not change (the weighted sum of $1$), one can bypass the need to simulate an "astronomical" number of moves and definitively prove that clearing a 4x4 or even a 3x3 box is impossible under the given rules.