Posted on Mar 6, 2026
Monthly Mindbenders (February 2026): MoMath PDF.
A bacterium starts at \((0,0)\). A bacterium at \((x,y)\) may divide (if both target points are empty), disappearing and being replaced by bacteria at \((x+1,y)\) and \((x,y+1)\).
Roughly how many divisions are needed before the box with corners \((0,0)\), \((0,3)\), \((3,3)\), \((3,0)\) is clear?
Impossible. In fact, it is already impossible to clear the smaller box from \((0,0)\) to \((2,2)\).
If we define the box as \(0 \le x,y \le n\), then:
n = 0 is clearable: one division at \((0,0)\) moves bacteria to \((1,0)\) and \((0,1)\), clearing the box.
n = 1 is also clearable: there are valid sequences that clear the 2x2 box (for example, one shortest sequence uses 8 divisions).
The first impossible case is \(n=2\), which is exactly the 3x3 box used in the invariant proof below.
Click a bacterium to divide it (if legal). A division at \((x,y)\) replaces that bacterium with bacteria at \((x+1,y)\) and \((x,y+1)\), only when both target points are empty.
Loading...
Loading...
Use the invariant weight:
\[ W=\sum_{\text{occupied }(x,y)}2^{-(x+y)}. \]
Initially, only \((0,0)\) is occupied, so \(W=1\).
One division at \((x,y)\) replaces weight \(2^{-(x+y)}\) by:
\[ 2^{-(x+1+y)} + 2^{-(x+y+1)} = 2\cdot 2^{-(x+y+1)} = 2^{-(x+y)}. \]
So every allowed division preserves \(W\); therefore \(W\) is always exactly 1.
If the 3x3 box \(0 \le x,y \le 2\) were clear, every bacterium would lie outside it. The maximum possible outside weight is the sum over all outside lattice points:
\[ \sum_{x,y\ge 0}2^{-(x+y)}-\sum_{x=0}^{2}\sum_{y=0}^{2}2^{-(x+y)} \]
\[ =4-\left(1+\frac12+\frac14\right)^2 =4-\left(\frac74\right)^2 =4-\frac{49}{16} =\frac{15}{16}<1. \]
But \(W\) must remain 1, contradiction. So the 3x3 box can never be cleared, and therefore the 4x4 box from \((0,0)\) to \((3,3)\) cannot be cleared either.
More MoMath Mindbenders: Previous | Next