Prove that a list of subsets of a finite set can be made such that
i. The empty set is the first in the list.
ii. Every subset is used only once in the list.
iii. Each subset in the list is obtained by either adding one element from the preceding subset, or removing one element.
So I've been thinking about this puzzle a bit, and feel like I almost see the pattern, but I'm not sure yet how to generalize it.
I've been coming at it from the angle of partitions by way of cardinality on the power set $\mathcal{P}(X)$ ($X$ a finite set), and ways to "distribute" the various "cardinality classes" of elements of $\mathcal{P}(X)$ into the $2^{|X|}$ possible places of the list such that they fulfill the requirements.
Example, $n=3$:
\begin{array} {|r|r|}
\hline \text{Cardinality of subset} & \text{# subsets in } \mathcal{P}(X) \\
\hline 0 & 1 \\
\hline 1 & 3 \\
\hline 2 & 3 \\
\hline 3 & 1 \\
\hline
\end{array}
Using this partition of $\mathcal{P}(X)$, we can arrange the subsets in the following way which will fulfill the requirements when filled in with the appropriate $a_i \in \mathcal{P}(X)$ (each subset $a_i$ is identified by its cardinality):
\begin{array} {|r|r|}\hline \text{List Entry} & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 \\ \hline \text{Cardinality of }a_i & 0 & 1 & 2 & 1 & 2 & 1 & 2 & 3 \\ \hline \end{array}
One interesting thing I noticed is that the partitioning of the power set by cardinality of each element (i.e., subset of $X$) appears to follow the Fibonacci sequence, which may or may not be useful, but feels like it should be…
\begin{array} {|r|r|}
\hline \text{Cardinality of } X & \text{Partition of } \mathcal{P}(X) \\
\hline 3 & 1,3,3,1 \\
\hline 4 & 1,4,6,4,1 \\
\hline 5 & 1,5,10,10,5,1 \\
\hline 6 & 1,6,15,20,15,6,1 \\
\hline
\end{array}
Anyway, I managed to find a solution for $n=4$, using the partitioning method to determine where to put subsets of each cardinality in the sequence. The following I believe to be a framework for a solution for $n=4$ (replace the cardinality identifier placeholders with the appropriate subsets such that the intersections work out correctly):
\begin{array} {|r|r|}\hline \text{List Entry} & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 & a_9 & a_{10} & a_{11} & a_{12} & a_{13} & a_{14} & a_{15} & a_{16} \\ \text{Cardinality of $a_i$} & \hline 0 & 1 & 2 & 3 & 2 & 3 & 2 & 3 & 4 & 3 & 2 & 1 & 2 & 1 & 2 & 1 \\ \hline \end{array}
However, so far I've not been able to generalize this for any $n$. I guess it gets a bit more complicated than just the cardinalities, because you also have to guarantee that in each pair of entries in the list you have $\geq 1$ element in the intersection of the two (since we can only add or remove one element at a time). I also think that the correct way to arrange the subsets may differ depending if $n$ is even or odd.
So I was thinking if I can derive some fact about how often each element $x_n \in X$ must appear in each "cardinality class" of $\mathcal{P}(X)$ (so that we can say it's possible to choose an element from that class for the next list entry and still have a nonempty intersection), as well as an algorithm for placing the various elements of the cardinality classes among the list entries, then I could prove the result in general.
Am I on the right track with any of this?
Best Answer
The statement is trivially true for $n=1$. Suppose it is true for all sets of cardinality $n$, and let's prove it for an arbitrary set $S$ of cardinality $n+1$.
Pick an element $a\in S$, and let $T=S\setminus\{a\}$. As $T$ is of cardinality $n$, there is the sequence $T_0=\emptyset,T_1,\ldots,T_{2^n-1}$ which satisfies the conditions of the problem. Now, prove that the sequence $T_0,T_1,\ldots,T_{2^n-1},T_{2^n-1}\cup\{a\},\ldots,T_1\cup\{a\},T_0\cup\{a\}$ enumerates all the subsets of $S$ and also satisfies the conditions of the problem. In other words, just take the sequence of subsets of $T$ followed by the same sequence, in the opposite order, with $a$ added to each subset.