Finding Gemstones: on the quest for mathematical beauty and truth
< Previous Post Next Post >

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:





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



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