The What
You have probably heard of the Putnam Competition. If you haven’t, well it’s almost the IMO in the Imperial System. Or maybe the NEERC of ACM ICPC. Michael Jordan of Baseball?Ok it’s a mathematical competition, and quite a prestigous one, always known for beautiful and hard problems.
This is the story of how my early undergrad years obsession with cellular automata met a problem in the 2000 Putnam Competition that I was doing for fun last week.
The Problem
Let S0 be a finite set of positive integers. An integer a is a member of Sn if and only if exactly one of a and a-1 is in Sn-1. Prove that there are infinitely many N such that SN = S0 ∪ {a + N | a ∈ S0}.So if S0 = {0, 1, 3}, we’ll have S1 = {0, 2, 3, 4}, S2 = {0, 1, 2, 5}, and so on.
It’s definitely worth tyring, so I suggest you give it a minute or two.
The Connection
I’ll go through a few basic things about cellular automata and you’ll be able to follow along even if this is your first time hearing the term. Also if you try to keep the problem mind while reading along, you’ll be able to tell which way we are going at each step. If you are already familiar with CA then skip right ahead.I am not trying to be too precise here. If you would like to know more about cellular automata, I suggest you put aside at least 2 hours(!) and start your binge reading at the wiki page.
Cellular Automata
Think of a cellular automata as an initial state, and an update function from all possible states to all possible states. We are going to apply this function to the initial state to get a new state, and do the same thing with the output of the function over and over again: x0, f(x0), f(f(x0)), …Imagine one of those stadium waves in motion.
Now take a snapshot of the system and let that be your initial state (we only care about the spectators, and whether or not they’re standing). Now define the function to update the world in the following way:
- A spectator will stand up (or stay standing up) if the person immediately to her right is standing up
- Otherwise she will sit down/remain seated
Why you can get away with calling a function and an input a cellular automata though, is: - A discrete nature of the state of the system, which is composed of cells (spectators), while each cell is allowed to be in finitely many states (standing, sitting)
and the update function being: - Local, meaning it is defined in terms of the state of the world around each cell, affecting only the output of that particular cell (you look to your right, and decide your own move) - Universal, meaning the function definition is the same for all of the cells (everybody looks to her right and decides based on one function)
You must now see the difference between the above (usual) strategy of creating waves vs. defining a centralized function in the stadium which has to microdefine the behavior of every single person explicitly for ~260,000 possible states of the system.
Elementary Cellular Automata
Suppose you have a (usually infinite) row of cells each one adjacent to the two neighboring ones, each allowed to be in one of two states: 0 or 1
1 0 1 0 0 1 0 1 1 1 ...
Everybody (including your neighbors) does this at the same time in each turn to calculate the own values for their next round. In other words, the steps happen atomically.
Let’s apply the above rule to the following initial configuration:
If we apply it once we get:
Back to the problem
Remember the problem? Finite S0, An integer a is a member of Sn if and only if exactly one of a and a-1 is in Sn-1, Prove there are infinitely many SN = S0 ∪ {a + N | a ∈ S0}.With all this CA context, this should (or probably already has) remind(ed) you of how this is going to connect to CA. Let’s write the above problem in CA language:
With start from an arbitrary initial position.
A cell i turns to/stays at one in a new round t iff exactly one of i and i-1 has been one in the previous ronud t-1.
Prove that there are infinitely many rounds N that look like they are the initial round
Now let’s see how it runs:
This is a fantastic property which enables the starting points to care less about the existence of each other. This is a great tool for calculating the nth state of a run from any initial state S: We can calculate the nth state of the simple one dot configuration, then for every black square in S, we shift the result equal to the offset, and sum up everything modulo 2.
You can see this formally if we go over an example in algebraic notation:
Initial state with cells i and j being on: S0 (i, j) ≡ xi + xj
Next round based on rule 60: S1 (i, j) ≡ (1 + x) S0 (i, j) ≡ xi + xj + x i + 1 + x j + 1
Rewriting right hand side: ≡ (1 + x) xi + (1 + x) xj ≡ S0 (i) + S0 (j)
Let’s revisit rule 60 now.
Lemma:
Observe that the simple starting position satisfies the condition of SN from the problem statement infinitely many times at 2n cycles. That is in the first row the of the biggest triangle that you so far, where there are exactly two black cells, with the distance of 2n.
It’s easy to prove why this happens with an induction on n: The dot on the left is going to do the same thing in the next 2n ronuds. The dot on the right is also going to that but with everything shifted 2n times. They will therefore create 4 points in the 2n+1th round, but two of those two points conincide (on the 2nth cell) and cancel each other out. What remains is two black cells on 0 and 2n+1.
Here’s how 60 doesn’t mind multiple black cells in its initial position and will happily generate suitable S2n states for us:
Final blow
We are now only left to prove the above lemma for the general starting position. We claim that for all n such that 2n > max{S0}, we have a correct S2n.To prove this, let’s look at this round for every black cell i in the starting position one by one.
We know each of them is going to generate the double black cell Sierpinski pattern at round 2n, in cells 0 + i and 2n + i. But who else can influence these two cells?
Candidate 1: cell number 0 + i - 2n, to disturb cell 0: impossible. 2n > max{S0}. There can’t be a black cell there as all elements of S0 are positive.
Candidate 2: cell number 2n, to disturb cell 2n, again impossible for the exact same reason.
Which after a marathon of keypresses concludes a proof which you can see almost instantly, given you know about rule 60.
P.s. I have paid great attention to put only pixel perfect graphs above so you wouldn’t be disturbed by at least one very particular kind of OCD while reading along.
P.p.s. Which pun do you think was the cheesiest?
