Cellular Automata Meets Putnam Problem

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 S₀ be a finite set of positive integers. An integer a is a member of S_n if and only if exactly one of a and a-1 is in S_n-1. Prove that there are infinitely many N such that S_N = S₀ ∪ {a + N | a ∈ S₀}.
So if S₀ = {0, 1, 3}, we’ll have S₁ = {0, 2, 3, 4}, S₂ = {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: x₀, f(x₀), f(f(x₀)), …
Imagine one of those stadium waves in motion.

source: sciencelearn.org.nz

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

To “see” your cellular automata in action, apply the above function subsequently to your snapshot every second in 3, 2, and go!
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 ~2^60,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

Let’s decide to call the black ones 1. The above configuration corresponds to:

1 0 1 0 0 1 0 1 1 1 ...

In the elementary cellular atuomata, your function (remember it’s local and universal) is allowed to look at the current cell, the cell to the right, and the cell to the left. Your function should provide answer for all of the possible inputs that it can obtain from the three. In fact your function consists of exactly 8 (input,output) pairs:

The above table represents one of 2⁽²³⁾ possible update functions. That is, the world around you will always look like one of the configurations on the left. Depending on which one it actually represents you would choose your color after we apply the update function. In this case each cell says: - If I am the only one with value of 1, I’m going to stay 1. - If my left neighbor is the only one with a 1, I’m gonna turn to 1. - Otherwise I will stay at/turn to 0.
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:

Now if we apply it again on this last one, we will get:

And again:

As it is the case above, we usually want to look at these states next to each other. Which is why you will usually see these shown like:

Each of the possible 256 functions is known by a number from 0 to 255 (I’m not going to go through why that is a good idea and why it makes sense. Hint: look to the right of the image of the function table, then tilt your head 90 degrees). Here is how each of them looks like. For example here’s rule 99 which is kind of my favorite. (When not specified, it usually means that the initial state consists of one 1 cell)

Back to the problem

Remember the problem? Finite S₀, An integer a is a member of S_n if and only if exactly one of a and a-1 is in S_n-1, Prove there are infinitely many S_N = S₀ ∪ {a + N | a ∈ S₀}.
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

Let’s build the function:

As you can see we don’t care about the guy on the right, which makes sense based on the problem statement.
Now let’s see how it runs:

Can you see the proof to one special case of the problem?

This is rule number 60, and hard to forget after you come across it once, not only because of the beautiful Sierpinski-like triangle pattern, but also because of the fact that it is one of only eight so called additive rules. What that means is conveyed by the following ~1000 pictures (from wolfram mathworld) better than ~1 million words:

This shows what happens if you were to start from an initial position with two black states instead of one. This happens when you can write the rule as some formula of your neighbors modulo 2, which is clearly the case in our problem: me_t = (left_t-1 + me_t-1) mod 2.
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: S_{0 (i, j)} ≡ xⁱ + x^j
Next round based on rule 60: S_{1 (i, j)} ≡ (1 + x) S_{0 (i, j)} ≡ xⁱ + x^j + x ^{i + 1} + x ^{j + 1}
Rewriting right hand side: ≡ (1 + x) xⁱ + (1 + x) x^j ≡ S_{0 (i)} + S_{0 (j)}
Let’s revisit rule 60 now.
Lemma:
Observe that the simple starting position satisfies the condition of S_N from the problem statement infinitely many times at 2ⁿ 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 2ⁿ.

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 2ⁿ ronuds. The dot on the right is also going to that but with everything shifted 2ⁿ times. They will therefore create 4 points in the 2ⁿ⁺¹th round, but two of those two points conincide (on the 2ⁿth cell) and cancel each other out. What remains is two black cells on 0 and 2ⁿ⁺¹.
Here’s how 60 doesn’t mind multiple black cells in its initial position and will happily generate suitable S_2ⁿ states for us:

And here’s for example how 169 very much minds different starting positions (also note the density of the black cells)

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 2ⁿ > max{S₀}, we have a correct S_2ⁿ.
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 2ⁿ, in cells 0 + i and 2ⁿ + i. But who else can influence these two cells?
Candidate 1: cell number 0 + i - 2ⁿ, to disturb cell 0: impossible. 2ⁿ > max{S₀}. There can’t be a black cell there as all elements of S₀ are positive.
Candidate 2: cell number 2ⁿ, to disturb cell 2ⁿ, 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?