Putnam 2000, Problem B-5

Let $S_0$ be a finite set of positive integers. We define finite sets $S_1, S_2, \ldots$ of positive integers as follows: the integer $a$ is in $S_{n+1}$ if and only if exactly one of $a-1$ or $a$ is in $S_n$. Show that there exist infinitely many integers $N$ for which $S_N = S_0 \cup \{N + a : a \in S_0\}$.

Solution:
We claim that all integers \(N\) of the form \(2^k\), with \(k\) a positive integer and \(N > \max\{S_0\}\), satisfy the desired conditions.  

It follows from the definition of \(S_n\), and induction on \(n\), that  
\[
\sum_{j \in S_n} x^j \equiv (1 + x) \sum_{j \in S_{n-1}} x^j \equiv (1 + x)^n \sum_{j \in S_0} x^j \pmod{2}.
\]  

From the identity \((x + y)^2 \equiv x^2 + y^2 \pmod{2}\) and induction on \(n\), we have \((x + y)^{2^n} \equiv x^{2^n} + y^{2^n} \pmod{2}\). Hence if we choose \(N\) to be a power of \(2\) greater than \(\max\{S_0\}\), then  
\[
\sum_{j \in S_n} \equiv (1 + x^N) \sum_{j \in S_0} x^j
\]  
and \(S_N = S_0 \cup \{N + a : a \in S_0\}\), as desired.