Can Bacteria Escape This Box? Impossible Proof
44sThe puzzle setup is intriguing and the claim of impossibility creates curiosity and suspense.
▶ Play ClipAI Summary
This video presents a mathematical puzzle involving a bacterium that replicates on a grid, and asks whether it's possible to clear a 4x4 box of lattice points. The solution uses an invariant—a weighted sum that remains constant—to prove that clearing the box is impossible.
Chapters
[00:01]
Puzzle setup
A bacterium at the origin can replicate if the spots above and to the right are empty, filling both and vacating the original. The goal is to clear a 4x4 box of 16 lattice points.
[00:26]
Small box examples
A 2x2 box takes 8 moves to clear. A 3x3 box seems nearly impossible, and a 4x4 box appears astronomically hard.
[01:11]
Invariant: weighted sum
Assign weights to each diagonal line: origin weight 1, next line 1/2, next 1/4, etc. Each replication keeps the total weighted sum constant at 1.
[01:49]
Impossibility proof
To clear a box, the sum of weights outside must be at least 1. The total weight of the infinite grid is 4, but the 4x4 box's inside weight is ~3.5, leaving only ~0.5 outside—so it's impossible.
[02:43]
Other shapes
A 3x3 box is also impossible (inside weight 3.0625), and an 8-point shape is only barely possible (inside weight exactly 3).
Study Flashcards (5)
How many moves does it take to clear a 2x2 box?
easy
Click to reveal answer
How many moves does it take to clear a 2x2 box?
easy
Click to reveal answer
The minimum number of moves to clear a 2x2 box is 8.
00:26
What is the invariant in the bacteria grid puzzle?
medium
Click to reveal answer
What is the invariant in the bacteria grid puzzle?
medium
Click to reveal answer
The weighted sum of all bacteria on the grid remains constant at 1.
01:36
What is the total weight of all lattice points on the infinite grid?
medium
Click to reveal answer
What is the total weight of all lattice points on the infinite grid?
medium
Click to reveal answer
The total weight of all points on the infinite grid is 4.
02:16
Why is it impossible to clear a 4x4 box?
hard
Click to reveal answer
Why is it impossible to clear a 4x4 box?
hard
Click to reveal answer
It is impossible to clear a 4x4 box because the sum of weights outside the box is less than 1.
02:29
What is the sum of weights inside a 3x3 box?
medium
Click to reveal answer
What is the sum of weights inside a 3x3 box?
medium
Click to reveal answer
The sum of weights inside a 3x3 box is 3.0625.
02:43
💡 Key Takeaways
🔧
Finding an invariant
Introduces the core problem-solving technique: finding a quantity that remains constant to prove impossibility.
01:11
📊
Total weight of the grid is 4
Provides the key numerical fact that makes the impossibility proof work.
02:16
💡
Impossibility of clearing 4x4 box
Delivers the main result: the puzzle is impossible, not just hard.
02:29Full Transcript
[00:01] bacteria replicating on a grid. We start with just one cell at the origin and at any point if the spots one above and one to the right of that bacterium are empty, then it's allowed to replicate populating both of those spots leaving
[00:14] the previous spot it was on unoccupied. The puzzle is to find the minimum number of moves required [music] to clear all 16 lattice points inside this box here. a smaller box. For example, at the
[00:26] lattice point obviously just takes one move. If you move up to a 2 by 2 box playing around you'll find that it takes eight moves to clear that box. So you pattern? Could it be something related to powers of two? But as soon as you
[00:42] lattice points, it becomes clear this is [music] going to take an astronomical make space for the cell at 2 0 to replicate once, we need all these other starts to seem unlikely that it's even possible to clear this box of nine
[00:58] lattice points, let alone one with 16 lattice [music] points. Often in problem about a situation that can unfold in some huge or infinite number of ways, it's often helpful to find some quantity that always must remain the same no
[01:11] case, if you think about how each replication [music] moves you from one of these diagonal lines to its neighbor on the right, then because each replication turns one [music] cell into two, you might think to count the total
[01:23] number of cells with a weight where each line has half the weight of the preceding one. So for example, the point at the origin has a weight of one, all of the points on this line have a weight of 1/2. So after the first replication,
[01:36] the total weighted sum of the cells stays fixed at one. And more generally, here, any move [music] that you make doesn't change the total weight. So no matter what you do, the weighted sum of all the bacteria on the grid has to stay
[01:49] fixed at where it started, namely one. So in order to clear a box, you need the sum of all of the weights outside of that box to be at least one. Without this, even given infinite time, the bacteria could never possibly escape.
[02:03] together all of the weights on this infinite grid. Now, you might know that 1 + 1/2 + 1/4 and so on converges to 2. of lattice points. Repeating this for each of the rows above and adding up the
[02:16] results, you get a very similar sum that converges to 4, meaning the total weight on the entire grid is only four. But, the sum of the weights inside that box with 16 lattice points adds up to be a little above 3.5. So, the sum of the
[02:29] weights outside that box is notably less than one, meaning there is simply no way to cram all of the descendants of that first bacterium outside of that box. So, answer is that it's impossible, and this is the proof. In fact, there's no way
[02:43] for the bacteria to even escape this smaller 3x3 box of nine lattice points, since their weights add up to 3.0625. And you can even make the argument that this shape with eight lattice points could only be cleared just barely if you
[02:56] had infinite [music] time, since the sum of its weights is exactly three.
