Problem:
Let X1​,X2​,…,X100​ be a sequence of mutually distinct non-empty subsets of a set S. Any two sets Xi​ and Xi+1​ are disjoint and their union is not the whole set S, that is, Xi​∩Xi+1​=∅ and Xi​∪Xi+1â€‹î€ =S, for all i∈{1,…,99}. Find the smallest possible number of elements in S.
Solution:
The answer is that ∣S∣≥8.
First, we provide a inductive construction for S={1,…,8}. Actually, for n≥4 we will provide a construction for S={1,…,n} which has 2n−1+1 elements in a line. (This is sufficient, since we then get 129 for n=8.) The idea is to start with the following construction for ∣S∣=4:
34​1​23​4​12​3​14​2​13.​
Then inductively, we do the following procedure to move from n to n+1 : take the chain for n elements, delete an element, and make two copies of the chain (which now has even length). Glue the two copies together, joined by ∅ in between. Then place the element n+1 in alternating positions starting with the first (in particular, this hits n+1 ).
Explicitly, when n=8 this construction gives
3456783434534678345634783457834634567348345834673456834734573468​115678167815178156161578181567167158171568168157​2356782323523678235623782357823623567238235823672356823723572368​445678467845478456464578484567467458474568468457​1256781212512678125612781257812612567128125812671256812712571268​335678367835378356368383567367358373568368​145678141457814561478145781456714814587145681471457​2678267827862628672672768268​56785565785675856857​​
Now let's check ∣S∣≥8 is sufficient. Consider a chain on a set of size ∣S∣=7. (We need ∣S∣≥7 else 2∣S∣<100.) Observe that there are sets of size ≥4 can only be neighbored by sets of size ≤2, of which there are (17​)+(27​)=28. So there are ≤30 sets of size ≥4. Also, there are (37​)=35 sets of size 3 . So the total number of sets in a chain can be at most 30+28+35=93<100.
The problems on this page are the property of the MAA's American Mathematics Competitions