I was not a big fan of this question, because the construction was not elegant at all.

Solution with Danielle Wang: the answer is that $|S| \ge 8$. First, we provide a inductive construction for $S = \left\{ 1, \dots, 8 \right\}$. Actually, for $n \ge 4$ we will provide a construction for $S = \left\{ 1, \dots, n \right\}$ which has $2^{n-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$: \[ \begin{array}{ccccccccc} 34 & 1 & 23 & 4 & 12 & 3 & 14 & 2 & 13 \end{array}. \]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 $\varnothing$ in between. Then place the element $n+1$ in alternating positions starting with the first (in particular, this hits $n+1$). 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} \] Now let's check $|S| \ge 8$ is sufficient. Consider a chain on a set of size $|S| = 7$. (We need $|S| \ge 7$ else $2^{|S|} < 100$.) Observe that there are sets of size $\ge 4$ can only be neighbored by sets of size $\le 2$, of which there are $\textstyle\binom 71 + \textstyle\binom 72 = 28$. So there are $\le 30$ sets of size $\ge 4$. Also, there are $\textstyle\binom 73 = 35$ sets of size $3$. So the total number of sets in a chain can be at most $30 + 28 + 35 = 93 < 100$.

I know several people (including me) who wrote out the entire construction for $|S|=8$. The graders are going to have fun with those .

At least you didn't put 100 subsets for the construction like I (and someone else, and maybe many others) did. edit: SNIPED

This basically takes 10 minutes to get the answer and then an hour writing up the construction.......

hm I didn't write out the entire thing. I wrote out up until like $X_{60}$ then said the rest was easy to finish. Could this be bad?

Lord.of.AMC wrote: At least you didn't put 100 subsets for the construction like I (and someone else, and maybe many others) did. edit: SNIPED Hmm it's not too hard to write out in full (especially with copy-paste ). Here is mine. \[ \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} \] EDIT: oops, I meant "not too hard to write out conditioned on finding it"

mathwizard888 wrote: I know several people (including me) who wrote out the entire construction for $|S|=8$. The graders are going to have fun with those . Oops

v_Enhance wrote: Lord.of.AMC wrote: At least you didn't put 100 subsets for the construction like I (and someone else, and maybe many others) did. edit: SNIPED Hmm it's not too hard. Here is mine. Repeating this gives the full construction. \[ \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} \] @v_Enhance how did you write a solution and make the construction so fast?

Lord.of.AMC wrote: At least you didn't put 100 subsets for the construction like I (and someone else, and maybe many others) did. edit: SNIPED So upset rn! I literally did this! Then, I decided to check my list during the last 15 minutes, and realized that the entire middle section was wrong. So I started over and ended up having to turn in a list with only ~50 subsets listed.

I proved that there existed a construction such that there are $2^{\mid {S} \mid -1}$ elements when $\mid S \mid \ge 4$ using induction.

The only USAMO problem I solved. I wrote out part of the construction(the outline), then tried to explain it. For most of the time I spent on this I tried to prove S=7

claserken wrote: @v_Enhance how did you write a solution and make the construction so fast? I'm a retired contestant now in college (in fact the author of JMO2 and USAMO3). So I wrote up the solution after spending about half an hour solving it earlier in the afternoon.

Is it possible to do this problem using Hall's Marriage Theorem?

v_Enhance wrote: Hmm it's not too hard. Yeah I would post mine but that would destroy anonymity of my solution.

eyzhang wrote: Lord.of.AMC wrote: At least you didn't put 100 subsets for the construction like I (and someone else, and maybe many others) did. edit: SNIPED So upset rn! I literally did this! Then, I decided to check my list during the last 15 minutes, and realized that the entire middle section was wrong. So I started over and ended up having to turn in a list with only ~50 subsets listed. How many points do you guys think I'll lose for a partial list?

bestwillcui1 wrote: This basically takes 10 minutes to get the answer and then an hour writing up the construction....... Wait it took me 10 minutes to get the answer, a half hour to find the construction, and 15 minutes to write it up.

How many points if you weren't able to finish the construction but you had a rough outline like 50 terms through ?

Hmmm, my construction didnt use any 5-element or 6-element subsets. Yet, I believe it still worked. Was it necessary to include 5-element or 6-element subsets.

What a silly problem. The answer is $|S|=8$. Clearly $|S|\leq 6$ fail because there are not even $100$ subsets. Now observe that if $|S|=7$, any subsets of size $4$ or larger must be adjacent to two subsets of size $2$ or less, otherwise their union is either $S$ or they are not disjoint. Hence there are at most $\binom{7}{2}+\binom{7}{1}$ subsets of size $4$ or larger, which gives a total of: $$\binom{7}{1}+\binom{7}{2}+\binom{7}{3}+\binom{7}{2}+\binom{7}{1}=7+21+35+21+7=91<100$$subsets, at most, so there are not enough substs in this case. It remains to given a construction for $|S|=8$. Here is an explicit construction: $$123,4567,12,3678,125,3468,127,3458,126,3457,128,4567,138,2567,134,2678,$$$$135,2478,136,2458,137,2568,147,2368,145,2367,148,2357,146,2378,156,2347,$$$$158,2346,157,2348,167,2345,178,3456,278,1345,268,1347,258,1346,257,1348,$$$$256,1378,246,1578,236,1578,234,1678,235,1467,358,1247,356,1248,367,1258,$$$$346,1278,345,1268,347,1256,348,1267,458,1236,478,1235,467,1238,456,1237,$$$$568,1234,567,1,45678,2,15678,3,25678,4,12378,5,12348,6,12345,7,12346,8,12347,56.$$The first 5 rows contain 16 subsets each, while the last row contains 20.

We claim that the answer is $8$. We first shows that all numbers less than than $8$ fail, and then show that $8$ is achievable. For $|S|=1,2,\cdots, 6,$ the number of possible subsets is not even greater than $100,$ so clearly these fail. For $|S|=7,$ we note that there are $2^7=128$ possible subsets. Call a subset usable if it is possible to use it as an $X_i$. Of the subsets of a 7 element set, the empty set, the entire set itself, and each of the subsets that has $6$ elements are unusable. Also, notice that any $5$ element subset must be adjacent to at least one set, and the only set it could be adjacent to is a set containing one element. There are only $7$ one element subsets, so there can be at most $7$ 5 element subsets(the way to achieve this would be to have the string $X_1 X_2 X_3\cdots X_{14}$ be $51515151515151$ or $15151515151515$(where the number represents the number of elements in $X_i$) Note that in the first string beginning with a $5$, we cannot add another $5$ on the right end because that would mean the $5$ element subset would have to be adjacent a non 1 element subset). This means there are at least $21-7=14$ additional unusable subsets. Using a similar method, we can find that of the $\binom 7 3 = 35$ 4 element subsets, at least $35-7-21=7$ of them are usable. This already strong enough to show there are less than $100$ usable sets, as $128-1-1-7-14-7=98<100$. We now show that if there are $8$ elements in $S,$ we can construct such a sequence of $X_i$. Let $X_1=[1,2,3,5,6,7], X_2 = [8], X_4=[7], X_6=[6], \cdots X_{16}=[1]$. We make all of $X_3, X_5, \cdots X_{15}$ 6 element subsets, and notice each of them is uniquely determined by their two adjacent sets(8-2=6). While I won't type it out here, you basically just do the same thing for the rest of the sets, going $[8,7], [8,6], \cdots [8,1] [7,1], [7,2]\cdots [7,6] [6,5],$.

The answer is eight. Let $|S| = b$. Clearly we must have $2^b - 1 \ge 100$, or $b \ge 7$ in order to have a hundred distinct non-empty sets. To show that $b = 7$ is impossible, first notice that if $|X_i| = k$, then $1 \le |X_{i + 1}| \le b - k - 1$. If $k \ge b - 1$, then the maximal bound is less than the minimal bound, meaning that there is no possible value for $|X_{i + 1}|$. Hence, we can't use any of the subsets with six or more elements, removing eight possible subsets. Now notice that the subsets of magnitude five must be paired with a subset of one, meaning that a maximum of seven out of the $\binom{7}{5} = 21$ subsets of magnitude five can be used, meaning that twenty-two subsets are unusable now. Then for each of the subsets of magnitude four, we must have a subset of magnitude one or two adjacent to it, but for each one we pair with a four we lose a one to pair with a five meaning that pairing a one with a four doesn't change the total number of subsets possible. Hence, only $\binom{7}{2} = 21$ are usable out of the $\binom{7}{4} = 35$ subsets, meaning that thirty-six are unusable which has dropped below the bound of one-hundred. Since I'm lazy, I wont type out the entire construction but the general idea is to pair $k$ with $7 - k$ and take the unused element and swap it with a used one in the $k$ side and repeat, changing the value of $k$ when needed.

the answer is 8 Showing that $|S|<8$ doesn't work: Obviously, $|S|=7$ because $2^{|S|}>100$. If $|X_i|\ge4$, then $|X_{i-1}|\le2$ or $i=1$. There are $28$ subsets that have $1$ or $2$ elements. Thus, there are at most $29$ $|X_i|\ge4$. We find that there are at most $35$ $|X_i|=3$. Also, we know that there are at most $28$ $|X_i|\le2$. So the maximum number of subsets is $29+35+28=92<100$. ook another attempt for construction i think i found something with 134 elements 1278 356 1248 357 1268 345 1678 234 1568 237 4568 137 2458 367 1258 346 2578 146 2358 467 1358 246 1578 236 1458 267 1348 256 3478 12 348 15 238 16 458 13 568 17 368 27 468 37 258 47 1238 57 248 6 127 3568 124 3578 126 3458 167 2348 156 2378 456 1378 245 3678 125 3468 257 1468 235 4678 135 2468 157 2368 145 2678 134 2568 347 128 34 158 23 168 45 138 56 178 36 278 46 378 25 478 123 578 24 68 35 26 18 5 136 247 1356 2 14 28 67 148 2357 48 1235 78 1345 268 1457 38 1245 3 1246 358 1247 58 1234 567 1 457 1236 8 147 2356 4 12358 7 2346

I claim that the answer is $8$. Note that $|S| \geq 7$ is obvious as otherwise we won't have $100$ subsets. Remark that a subset with four or more elements must be followed with a subset with $2$ or less elements. Thus the maximal number of subsets is $$\binom{7}{1} + \binom{7}{2} + \binom{7}{3} + \binom{7}{2}+\binom{7}{1} < 100,$$so $|S| \geq 8$ is necessary. For the construction: 234567 1 345678 2 456781 3 567812 4 678123 5 781234 6 812345 7 123456 8 (16 elements) 12 34 56 78 23 45 67 81 24 35 46 57 68 71 82 13 25 36 47 58 61 72 83 14 26 37 48 51 (28 elements) Now, I claim that there exists a permutation of all 56 of the 3-element subsets such as any two adjacent subsets are disjoint; this will give us $16+28+56 = 100$ subsets total. We will use the probabilistic method; note that by randomly selecting a permutation of the $56$ subsets, we have $56!$ total permutations. However, each of the $55$ adjacent subsets in the permutation have a $\tfrac{10}{55}$ probability of being disjoint, so the total expected number of successful permutations is $$\frac{56!}{\left(\frac{10}{55} \right) ^{55} } > 1,$$by pairing the terms of $56!$. Thus we have a working construction for $|S| = 8.$ Remarks: Does this even work?

megarnie wrote: 12348 56 23478 15 23468 17 23458 16 24578 13 24568 37 14568 23 45678 12 35678 14 25678 34 15678 24 13578 26 13478 25 14678 35 12478 36 12578 46 12378 45 12368 47 13568 27 13468 57 123468 5 123478 6 123578 4 125678 3 245678 1 345678 2 123458 7 1234 568 2347 158 2346 178 2345 168 2457 138 2456 378 1456 238 4567 128 3567 148 2567 348 1567 248 1357 268 1347 258 1467 358 1247 368 1257 468 1237 458 1236 478 1356 278 1346 578 12346 58 12347 68 12357 48 (Please tell me if I made a mistake here) Since you asked, the following are errors: $X_{40} \cup X_{41} = \{57\} \cup \{123468\} = S$ $X_{52} \cap X_{53} = \{2\} \cap \{123458\} = \{2\}$ $X_{94} \cup X_{95} = \{578\} \cup \{12346\} = S$ Better luck next time

IAmTheHazard wrote: It remains to given a construction for $|S|=8$. Here is an explicit construction: $$123,4567,12,3678,125,3468,127,3458,126,3457,128,4567,138,2567,134,2678,$$$$135,2478,136,2458,137,2568,147,2368,145,2367,148,2357,146,2378,156,2347,$$$$158,2346,157,2348,167,2345,178,3456,278,1345,268,1347,258,1346,257,1348,$$$$256,1378,246,1578,236,1578,234,1678,235,1467,358,1247,356,1248,367,1258,$$$$346,1278,345,1268,347,1256,348,1267,458,1236,478,1235,467,1238,456,1237,$$$$568,1234,567,1,45678,2,15678,3,25678,4,12378,5,12348,6,12345,7,12346,8,12347,56.$$The first 5 rows contain 16 subsets each, while the last row contains 20. You have $X_2 = X_{12} = \{4567\}$ and $X_{52} = X_{54} = \{1578\}$.

Eyed wrote: Construction was annoying > Construction: \begin{tabular}{|cccccccccc|} 1 & 345678 & 2 & 145678 & 3 & 1235678 & 4 & 123678 & 5 & 123478 \\ 6 & 123458 & 7 & 123456 & 8 & & & & & \\\hline 12 & 45678 & 13 & 25678 & 14 & 23678 & 15 & 23478 & 16 & 23458 \\ 17 & 23456 & 18 & 34567 & 28 & 14567 & 38 & 12567 & 48 & 12367 \\ 58 & 12347 & 68 & 12345 & 78 & 13456 & 27 & 14568 & 37 & 12568 \\ 47 & 12368 & 57 & 12348 & 67 & 13458 & 26 & 14578 & 36 & 12578 \\ 46 & 12378 & 56 & 13478 & 25 & 14678 & 35 & 12678 & 45 & 13678 \\ 24 & 15678 & 34 & & & & & & & \\\hline 678 & 345 & 128 & 567 & 234 & 178 & 456 & 123 & 468 & 571 \\ 682 & 713 & 824 & 135 & 246 & 357 & 125 & 378 & 156 & 247 \\ 126 & 478 & 256 & 348 & 267 & 458 & 236 & 148 & 237 & 158 \\ 367 & 145 & & & & & & & & \\ \end{tabular} This construction fails due to: $X_5 \cap X_6 = \{3\} \cap \{1235678\} = \{3\}$ $X_6 \cup X_7 = \{1235678\} \cup \{4\} = S$ $X_{84} \cap X_{85} = \{357\} \cap \{125\} = \{5\}$ $X_{88} \cap X_{89} = \{247\} \cap \{126\} = \{2\}$.

The smallest possible value of $|S|$ is $8$. A construction, which is classified into five "cyclic groups", is shown below. $AAAAB\{\}\{\}\{\}$, +1 Shift, 8 Pairs: $$1234, 5; 6781, 2; 3456, 7; 8123, 4; 5678, 1; 2345, 6; 7812, 3; 4567, 8;$$$AABABBCC$, +1 Shift, 8 Triples: $$124, 356, 78; 235, 467, 81; 346, 578, 12; 457, 681, 23; 568, 712, 34; 671, 823, 45; 782, 134, 56; 813, 245, 67;$$$AAABCBCB$, +1 Shift, 8 Triples: $$123, 468, 57; 234, 571, 68; 345, 682, 71; 456, 713, 82; 567, 824, 13; 678, 135, 24; 781, 246, 35; 812, 357, 46;$$$AACBACBB$, +3 Shift, 8 Triples: $$125, 478, 36; 458, 723, 61; 783, 256, 14; 236, 581, 47; 561, 834, 72; 814, 367, 25; 347, 612, 58; 672, 145, 83;$$$ABCACBAC$, +5 Shift, 4 Triples: $$147, 26, 583; 614, 73, 258; 361, 48, 725; 836, 15, 472.$$ Now, we will show $|S| \ge 8$. First of all, $2^{|S|} - 1\ge 100$ clearly holds, yielding $|S| \ge 7$. If $|S| = 7$, then at least $$100 - \left( \binom{7}{1} + \binom{7}{2} + \binom{7}{3} \right) = 37$$subsets will contain at least $4$ elements. But such subsets can only be adjacent to subsets with at most $2$ elements, so there must be at least $36$ subsets with $1$ or $2$ elements, which is absurd because $36 > \binom{7}{1} + \binom{7}{2}$. This proves $|S| \ge 8$, as desired. $\blacksquare$ Addendum: Evan's program has confirmed that my construction works . I hope the "cyclic shift" notation is motivated for readers—one can look at and classify all possible distributions of terms for subsets with cardinality $2$ or $3$ and attempt to piece them together into non-overlapping triples with periods of length $4$ or $8$. One motivating observation was $2 \cdot \binom{8}{2} = \binom{8}{3}$. (Although I noticed it in passing, this equality is the result of a common combinatorial identity.)

Obviously, $n\leq6$ fails as there are less than $99$ subsets. If $n=7$, then any subset with $\geq 4$ terms can only be next to subsets with $\leq 2$ terms, But there are 64 subsets with $\geq 4$ terms but only 29 subsets with $\leq 2$ terms, so at most 30 subsets with $\geq 4$ terms can be used. As a result, at least 34 subsets cannot be used. There are only less than 99 usable subsets, impossible. $n=8$ works by construction, so the minimum $n$ is $8$ Full proof here: https://infinityintegral.substack.com/p/usajmo-2016-contest-review

We claim that $8$ elements are required. Claim: This is impossible with $7$ elements. Proof. Note that there are at least $\binom{7}{7} + \binom{7}{6} + \binom{7}{5} + \binom{7}{4} - 27 = 37$ subsets with size at least $4$, and at most $\binom{7}{2} + \binom{7}{1} = 28$ elements with size at most $2$. Since there must be an $X_i$ with size $2$ between those with size $4$, no cosntruction can exist. $\blacksquare$ Claim: This is possible with $8$ elements. Proof. Note that $\binom{8}{1} + \binom{8}{2} + \binom{8}{3} + 8 = 100$. We give a construction as follows: Alternate $8$ subsets of size $4$ with those of size $1$ for the first $16$ $X_i$. For the size $2$ subsets, visualize the $8$ elements as an octogon, and place one of each distance, and cyclic shift to finish. For the size $3$ subsets. Then there's $7$ ways to place the three elements up to rotation, manually create the cyclic shift and chain them. $\blacksquare$

There's an interesting construction based on the fact that you can always put $S- (a, b, c, d)$ between $(a, b)$ and $(c,d)$. So, we can just order the 1 element subsets, then the 2 element subsets, then the 3 element subsets, and insert 8 random 4 element subsets in between 2 element subsets based on this method.

We claim that we can create a sequence of subsets of $S$ $X_i$ of length $2^{n-1} + 1$ where $n = |S|$(for $n > 3$. This gives us an answer of $\min(|S|) = 8$ since we can delete $29$ subsets from a sequence of $2^{8-1} + 1 = 129$ subsets to get $100$. We will do induction with our base case of $n = 4$ being true(a construction is $(1,2), (3), (1, 4), (2), (1, 3), (4), (2, 3), (1), (3, 4)$. For our inductive step, take a preexisting valid sequence of $2^{n-1} + 1$ subsets, delete a subset, double it, add $ \emptyset$ and add the new $n+1$th element to every other subset. This works since neither condition is broken. Thus, $|S| = 8$ works. $|S| < 7$ clearly doesn't work as there would be less than $100$ total subsets. If $|S| = 7$ then all subsets of size $2$ or less must be adjacent to a subset of size $4$, which gives us a total of $2\binom{7}{2} + 1 = 57$ subsets that have size $\neq 3$ in the sequence. Then $\binom{7}{3} = 35$ so $57 + 35 = 92 < 100$ so $|S| = 7$ is impossible. (storage)

My construction idea is first write 50 quadruples for the indexes, to fill all the gaps just use biggest subset which does not share element with any of it's neighbors. Then all the 4 element sets are increasing order and 3 element sets are non increasing order (So it's not hard to deal with). But there is some numbers appear multiple times, but we can insert some nicer sets instead of them. Here is my construction: 1234 678 1235 478 458 1236 1237 456 1238 7 1245 378 1246 358 1246 356 1248 37 1256 348 1257 346 1258 34 1267 345 1268 35 1278 6 1345 278 1346 258 1347 256 1348 27 1356 248 1357 246 1358 24 1367 245 1368 45 1378 2 1456 238 1457 236 1458 23 1467 235 1468 25 16 28 57 46 58 47 3 48 67 5 2346 158 2347 156 2348 17 2356 148 2357 146 2358 14 2367 145 2368 4 2378 1 2456 138 2457 136 2458 13 2467 135 2468 15 2478 56