2026 February and March Mindbender
Published:
Today, I discuss my solutions towards the Feburary and March mindbenders! The puzzles can be found here.
Lattice Bacteria Puzzle
Puzzle Statement
Consider an integer 2-D grid. A bacterium begins at the origin. Each bacteria may divide; that is, a bacterium at the point \((x, y)\) can be replaced by one at \((x+1, y)\) and \((x, y+1)\), supposing those two squares were previously bacteria-free. Roughly, how many divisions must take place before the closed box with corners at \((0,0), (0,3), (3,3)\), and \((3,0)\) is clear of bacteria?
An attempt via dynamic programming
First was via dynamic programming. Let \(f(w, h)\) be the amount of divisions for a bacteria to clear a \(w \times h\) grid. The problem asks to find \(f(4,4)\).
If \(w = h = 1\), then it takes only one division. Otherwise, after one division, the top bacteria must clear a \(w \times (h-1)\) grid, and the right bacteria must clear a \((w-1) \times h\) grid. Thus, the recurrence I formulated is:
\[f(w, h) = \begin{cases} 1 & w = h = 1 \\ 1 + f(w-1, h) + f(w, h-1) & \text{otherwise} \end{cases}\]| h \ w | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 |
| 2 | 2 | 5 | 9 | 14 |
| 3 | 3 | 9 | 19 | 34 |
| 4 | 4 | 14 | 34 | 69 |
Note that the general solution is that
\[f(w, h) = \binom{w+h}{w} - 1\]This does not work. After a bacteria clears the grid, it does not magically disappear. In other words, I cannot isolate the two bacteria separately.
Simulations
Ok, at this point I gave up and wrote a simple simulation to see how long it would take. In a loop, I would:
- check if there are any bacteria in the \(w \times h\) grid
- try to get that bacteria to divide
- if there was a bacteria in the way, then recurse to split that other bacteria
So I wrote this up and ran it. Then waited. Then waited. Then waited…
At this point, I got suspicious. Looking through the states, it seemed that I entered an infinite recursive descent.
The Solution
Finally, it got through in my head that it may not be possible to clear the grid. How would I prove this?
I recalled a similar problem my friend showed me. Similar, there was an integer grid of bacteria, but now there were infinite bacteria at every coordinate \((x, y)\) for $x \le 0$$. They divide in a peculiar way, with two (orthogonally) adjacent bacteria mating to spawn a new bacteria. That is, there are two ways they can divide:
- a bacteria at \((x, y)\) and \((x+1, y)\) being replaced with \((x+2, y)\)
- a bacteria at \((x, y)\) and \((x, y+1)\) being replaced with \((x, y+2)\) The question is can a bacteria reach \(x=5\)?
A general approach towards solving such problems is to find invariants. Suppose each configuration of bacteria has some potential that is maintained by these divisions. I’ll leave the solution to this related problem hidden, but as a hint, the golden ratio shows up!
Suppose we assign a value to each grid \((x, y)\), so that \(\phi(x,y) = 2^{-(x+y)}\). The potential is the sum of \(\phi\) over occupied grid positions. With this, upon a split,
\[\phi(x,y) = \phi(x+1, y) + \phi(x,y+1)\]so that the potential is constant! The starting potential is \(1\). What must be the potential be if the \(4 \times 4\) grid was empty? Well, there can be at most one bacteria on each grid square, so
\[\begin{aligned} \phi & \le \sum_{x, y \ge 0} \phi(x, y) - \sum_{0 \le x, y \le 3} \phi(x, y) \\ & = \sum_{x=0}^\infty 2^{-x} \sum_{y=0}^\infty 2^{-y} - \frac{225}{64} \\ & = 2 \sum_{x=0}^\infty 2^{-x} - \frac{225}{64} = 4 - \frac{225}{64} = \frac{31}{64} < 1 \end{aligned}\]So the potential must decrease! However, divisions do not change the potential, so it is impossible to clear the grid.
Note that even clearing a \(3 \times 3\) grid is impossible, as the remaining potential adds up to \(\frac{30}{32} < 1\).
Equal-Sum Subsets Puzzle
Your friend chooses 10 distinct integers from \(1\) to \(100\). Is it always possible to find two disjoint, non-empty subsets of their 10 numbers that have the same sum?
Pigeonhole and Solution
Unfortunately, I have seen this puzzle before as an application of the pigeonhole principle.
The first observation to make is that the disjointness only means that you need to choose two distinct subsets. That is, given two overlapping but distinct subsets that add to the same sum, then removing the overlapping numbers would find a winning pair of disjoint subsets.
Given 10 numbers \(x_1, \ldots, x_10\), there are \(2^{10} - 2 = 1022\) possible subsets (ignoring trivial ones). However, any subset must sum to at least \(1+2+\ldots+10 = 55\), and at most \(100+99+\ldots+91 = 955\), so there are \(901\) possible sums. As \(1022\) subsets must have a range of \(901\) values, two of them must have the same sum, by pigeonhole!
Pick those two subsets, remove the overlapping values, and thus you can always find two disjoint non-empty subsets of the same value!