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\}\}$