Let $X_{1}, X_{2}, \ldots, X_{100}$ be a sequence of mutually distinct nonempty subsets of a set $S$. Any two sets $X_{i}$ and $X_{i+1}$ are disjoint and their union is not the whole set $S$, that is, $X_{i} \cap X_{i+1}=\emptyset$ and $X_{i} \cup X_{i+1} \neq S$, for all $i \in\{1, \ldots, 99\}$. Find the smallest possible number of elements in $S$.
Solution with Danielle Wang: the answer is that $|S| \geq 8$.
बा Proof that $|S| \geq 8$ is necessary. Since we must have $2^{|S|} \geq 100$, we must have $|S| \geq 7$.

To see that $|S|=8$ is the minimum possible size, consider a chain on the set $S=$ $\{1,2, \ldots, 7\}$ satisfying $X_{i} \cap X_{i+1}=\emptyset$ and $X_{i} \cup X_{i+1} \neq S$. Because of these requirements any subset of size 4 or more can only be neighbored by sets of size 2 or less, of which there are $\binom{7}{1}+\binom{7}{2}=28$ available. Thus, the chain can contain no more than 29 sets of size 4 or more and no more than 28 sets of size 2 or less. Finally, since there are only $\binom{7}{3}=35$ sets of size 3 available, the total number of sets in such a chain can be at most $29+28+35=92<100$, contradiction.

ब Construction. We will provide an inductive construction for a chain of subsets $X_{1}, X_{2}, \ldots, X_{2^{n-1}+1}$ of $S=\{1, \ldots, n\}$ satisfying $X_{i} \cap X_{i+1}=\varnothing$ and $X_{i} \cup X_{i+1} \neq S$ for each $n \geq 4$.
For $S=\{1,2,3,4\}$, the following chain of length $2^{3}+1=9$ will work:
$\begin{array}{lllllllll}34 & 1 & 23 & 4 & 12 & 3 & 14 & 2 & 13\end{array}$

Now, given a chain of subsets of $\{1,2, \ldots, n\}$ the following procedure produces a chain of subsets of $\{1,2, \ldots, n+1\}$ :
1. take the original chain, delete any element, and make two copies of this chain, which now has even length;
2. glue the two copies together, joined by $\varnothing$ in between; and then
3. insert the element $n+1$ into the sets in alternating positions of the chain starting with the first.

For example, the first iteration of this construction gives:
\begin{tabular}{ccccccccc}
345 & 1 & 235 & 4 & 125 & 3 & 145 & 2 & 5 \\
34 & 15 & 23 & 45 & 12 & 35 & 14 & 25 &
\end{tabular}

It can be easily checked that if the original chain satisfies the requirements, then so does the new chain, and if the original chain has length $2^{n-1}+1$, then the new chain has length $2^{n}+1$, as desired. This construction yields a chain of length 129 when $S=\{1,2, \ldots, 8\}$.
Remark. Here is the construction for $n=8$ in its full glory.
\begin{tabular}{ccccccccc}
345678 & 1 & 235678 & 4 & 125678 & 3 & 145678 & 2 & 5678 \\
34 & 15678 & 23 & 45678 & 12 & 35678 & 14 & 678 & \\
345 & 1678 & 235 & 4678 & 125 & 3678 & 145 & 2678 & 5 \\
34678 & 15 & 23678 & 45 & 12678 & 35 & 78 & & \\
\hline 3456 & 178 & 2356 & 478 & 1256 & 378 & 1456 & 278 & 56 \\
3478 & 156 & 2378 & 456 & 1278 & 356 & 1478 & 6 & \\
34578 & 16 & 23578 & 46 & 12578 & 36 & 14578 & 26 & 578 \\
346 & 1578 & 236 & 4578 & 126 & 8 & & & \\
\hline \hline 34567 & 18 & 23567 & 48 & 12567 & 38 & 14567 & 28 & 567 \\
348 & 1567 & 238 & 4567 & 128 & 3567 & 148 & 67 & \\
3458 & 167 & 2358 & 467 & 1258 & 367 & 1458 & 267 & 58 \\
3467 & 158 & 2367 & 458 & 1267 & 358 & 7 & & \\
\hline 34568 & 17 & 23568 & 47 & 12568 & 37 & 14568 & 27 & 568 \\
347 & 1568 & 237 & 4568 & 127 & 3568 & 147 & 68 & \\
3457 & 168 & 2357 & 468 & 1257 & 368 & 1457 & 268 & 57 \\
3468 & 157 & 2368 & 457 & 1268 & & & &
\end{tabular}