Problem
Let X1​,X2​,…,X100​ be a sequence of mutually distinct nonempty 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
Solution with Danielle Wang: the answer is that ∣S∣≥8.
Proof that ∣S∣≥8 is necessary. Since we must have 2∣S∣≥100, we must have ∣S∣≥7.
To see that ∣S∣=8 is the minimum possible size, consider a chain on the set S={1,2,…,7} satisfying Xi​∩Xi+1​=∅ and Xi​∪Xi+1â€‹î€ =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 (17​)+(27​)=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 (37​)=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 X1​,X2​,…,X2n−1+1​ of S = {1,…,n} satisfying Xi​∩Xi+1​=∅ and Xi​∪Xi+1â€‹î€ =S for each n≥4.
For S={1,2,3,4}, the following chain of length 23+1=9 will work:
34​1​23​4​12​3​14​2​13​.
Now, given a chain of subsets of {1,2,…,n} the following procedure produces a chain of subsets of {1,2,…,n+1}:
- take the original chain, delete any element, and make two copies of this chain, which now has even length;
- glue the two copies together, joined by ∅ in between; and then
- 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:
34534​115​23523​445​12512​335​14514​225​5​
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 2n−1+1, then the new chain has length 2n+1, as desired. This construction yields a chain of length 129 when S={1,2,…,8}.
Remark. Here is the construction for n=8 in its full glory.
3456783434534678345634783457834634567348345834673456834734573468​115678167815178156161578181567167158171568168157​2356782323523678235623782357823623567238235823672356823723572368​445678467845478456464578484567467458474568468457​1256781212512678125612781257812612567128125812671256812712571268​335678367835378356368383567367358373568368​145678141457814561478145781456714814587145681471457​2678267827862628672672768268​56785565785675856857​​
The problems on this page are the property of the MAA's American Mathematics Competitions