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