Problem: Let $X_1$, $X_2$, \dots, $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, \dots, 99\}$.
Find the smallest possible number of elements in $S$.

Solution: Solution with Danielle Wang: the answer is that $|S| \ge 8$.

\paragraph{Proof that $|S| \ge 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, \dots, 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 71 + \binom 72 = 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 73 = 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.

\paragraph{Construction.}
We will provide an inductive construction for a chain of subsets
$X_1, X_2, \dots, X_{2^{n-1} + 1}$ of $S = \left\{ 1, \dots, n \right\}$
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}{ccccccccc}
  34 & 1 & 23 & 4 & 12 & 3 & 14 & 2 & 13
\end{array}.
\]
Now, given a chain of subsets of $\{1, 2, \dots, n\}$
the following procedure produces a
chain of subsets of $\{1, 2, \dots, n+1\}$:
\begin{enumerate}
\item take the original chain, delete any element,
  and make two copies of this chain, which now has even length;
\item glue the two copies together,
  joined by $\varnothing$ in between; and then
\item insert the element $n+1$ into the sets in alternating positions
  of the chain starting with the first.
\end{enumerate}
For example, the first iteration of this construction gives:
\[
 \begin{array}{ccccccccc}
 345 & 1 & 235 & 4 & 125 & 3 & 145 & 2 & 5 \\
 34 & 15 & 23 & 45 & 12 & 35 & 14 & 25 &
 \end{array}
\]
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, \dots, 8\}$.

\begin{remark*}
  Here is the construction for $n=8$ in its full glory.
 \[
  \begin{array}{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{array}
 \]
\end{remark*}