# Sorting sets of binary strings into threes

Time for a just-for-fun combinatorial problem! Thanks to my brother Kenneth Monks for suggesting it.

Consider the numbers of the form $2^{2^n}-1$ for positive integers $n$. The first few, for $n=1,2,3,4,\ldots$, are:

$3, 15, 255, 65535, \ldots$

One thing that all of these numbers have in common is that they are divisible by $3$. This is not hard to prove by induction; the first entry is divisible by $3$, and if $2^{2^n}-1$ is divisible by $3$, then $2^{2^{n+1}}-1=(2^{2^n})^2-1=(2^{2^n}-1)(2^{2^n}+1)$ is also divisible by $3$.

But is there a combinatorial proof?

In particular, take the most natural combinatorial interpretation of $2^n$, as the number of binary strings of length $n$. Let $B_n$ be the set of all binary strings of length $n$; then $2^{2^n}$ can be interpreted as the number of subsets of $B_n$.

By throwing away the empty set, the quantity $2^{2^n}-1$ is the number of nonempty subsets of $B_n$. Can we partition these subsets into blocks of three in a natural combinatorial way?

As an example, $B_2=\{00,01,10,11\}$ and the $15$ nonempty subsets of $B_2$ are:

$\{00\},\{01\},\{10\},\{11\},$

$\{00,01\},\{00,10\},\{00,11\},\{01,10\},\{01,11\},\{10,11\},$

$\{00,01,10\},\{00,01,11\},\{00,10,11\},\{01,10,11\},$

$\{00,01,10,11\}$

How would we sort these sets into groups of size $3$?

For each nonempty subset $S$ of $B_n$, consider all of the length $n-1$ substrings formed by removing the first $0$ or $1$ of each element of $S$. For instance, if $$S=\\{101,001,010,111\\}$$ then the substrings formed by chopping off the first digits are $01,10,11$.

Let $w$ be the lexicographically minimal such substring; in the example, $w=01$. Then $S$ either contains:

• $1w$ but not $0w$
• $0w$ but not $1w$
• $1w$ and $0w$

In our running example, $S$ has both (the third possibility). Let $S’$ and $S^\ast$ be the sets containing all elements of $S$ that don’t end in the substring $s$, as well as $1w$, $0w$, or both according to the other two possibilities above that $S$ does not satisfy. In our example, we have

$S’=\{101,010,111\},$

$S^{\ast}=\{001,010,111\}.$

The blocks $\{S,S’,S^\ast\}$ partition the collection of all nonempty subsets into blocks of size $3$, because starting with $S’$ or $S^\ast$ we get the same three sets as if we start with $S$. This completes the proof.

Finally, to illustrate the construction, here are the five blocks of size $3$ for $n=2$:

• $\{\{00\},\{10\},\{00,10\}\}$
• $\{\{01\},\{11\},\{01,11\}\}$
• $\{\{00,01\},\{10,01\},\{00,10,01\}\}$
• $\{\{00,11\},\{10,11\},\{00,10,11\}\}$
• $\{\{00,01,11\},\{10,01,11\},\{00,10,01,11\}\}$