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$?
Turn to the next page for my solution, or share your solution below!