2016 USAMO Problems/Problem 1

Problem

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 1

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 $\binom 71 + \binom 72 = 28$ . So there are $\le 30$ sets of size $\ge 4$ . Also, there are $\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$ .

Solution 2

My proof that $|S|\ge 8$ is basically the same as the one above. Here is another construction for $|S| = 8$ that I like because it works with remainders and it's pretty intuitive. The basic idea is to assign different subsets to different remainders when divided by particular numbers, and then to use the Chinese Remainder Theorem to show that all of the subsets are distinct. The motivation for this comes from the fact that we want $X_i$ and $X_{i+1}$ to always be disjoint, so remainders are a great way to systematically make that happen, since $i$ and $i+1$ do not have the same remainder modulo any positive integer greater than $1.$ Anyway, here is the construction:

Let $S = \left\{ {1, 2, ..., 8} \right\}.$ For $i = 1, 2, ..., 98,$ we will choose which elements of the set $\left\{ {1, 2, 3, 4} \right\}$ belong to $X_i$ based on the remainder of $i$ modulo $9,$ and we will choose which elements of the set $\left\{ {5, 6, 7, 8} \right\}$ belong to $X_i$ based on the remainder of $i$ modulo $11.$ We do this as follows: $X_i\cap\left\{ {1, 2, 3, 4} \right\} = \begin{array}{ll} \emptyset & i\equiv 0 \text{ (mod } 9\text{)} \\ \left\{ {1, 2} \right\} & i\equiv 1 \text{ (mod } 9\text{)} \\ \left\{ {3} \right\} & i\equiv 2 \text{ (mod } 9\text{)} \\ \left\{ {1, 4} \right\} & i\equiv 3 \text{ (mod } 9\text{)} \\ \left\{ {2} \right\} & i\equiv 4 \text{ (mod } 9\text{)} \\ \left\{ {3, 4} \right\} & i\equiv 5 \text{ (mod } 9\text{)} \\ \left\{ {1} \right\} & i\equiv 6 \text{ (mod } 9\text{)} \\ \left\{ {2, 3} \right\} & i\equiv 7 \text{ (mod } 9\text{)} \\ \left\{ {4} \right\} & i\equiv 8 \text{ (mod } 9\text{)} \\ \end{array}$ $X_i\cap\left\{ {5, 6, 7, 8} \right\} = \begin{array}{ll} \emptyset & i\equiv 0 \text{ (mod } 11\text{)} \\ \left\{ {5, 6} \right\} & i\equiv 1 \text{ (mod } 11\text{)} \\ \left\{ {7, 8} \right\} & i\equiv 2 \text{ (mod } 11\text{)} \\ \left\{ {5} \right\} & i\equiv 3 \text{ (mod } 11\text{)} \\ \left\{ {6, 8} \right\} & i\equiv 4 \text{ (mod } 11\text{)} \\ \left\{ {5, 7} \right\} & i\equiv 5 \text{ (mod } 11\text{)} \\ \left\{ {6} \right\} & i\equiv 6 \text{ (mod } 11\text{)} \\ \left\{ {5, 8} \right\} & i\equiv 7 \text{ (mod } 11\text{)} \\ \left\{ {6, 7} \right\} & i\equiv 8 \text{ (mod } 11\text{)} \\ \left\{ {8} \right\} & i\equiv 9 \text{ (mod } 11\text{)} \\ \left\{ {7} \right\} & i\equiv 10 \text{ (mod } 11\text{)} \\ \end{array}$ Finally, we specially define $X_{99} = \left\{ {1, 2, 3} \right\}$ and $X_{100} = \left\{ {5, 6, 7} \right\}.$

It is relatively easy to see that this configuration satisfies all of the desired conditions. We see that $X_{98} = \left\{ {4, 7} \right\},$ so $X_{98}$ and $X_{99}$ are disjoint, as are $X_{99}$ and $X_{100}.$ The remainder configuration above takes care of the rest, so any two consecutive sets are disjoint. Then, by the Chinese Remainder Theorem, no two integers from $1$ to $98$ have the same combination of residues modulo $9$ and modulo $11,$ so all of the sets $X_i$ are distinct for $i = 1, 2, ..., 98.$ It is also easy to verify that none of these match $X_{99}$ or $X_{100},$ since they all have at most two elements of $\left\{ {1, 2, 3, 4} \right\}$ and at most two elements of $\left\{ {5, 6, 7, 8} \right\},$ whereas $X_{99}$ and $X_{100}$ do not satisfy this; hence all of the sets are distinct. Finally, notice that, for any pair of consecutive sets, at least one of them has at most $3$ elements, while the other has at most $4.$ Thus, their union always has at most $7$ elements, so $X_i\cup X_{i+1}\neq S$ for all $i = 1, 2, ..., 99.$

All of the conditions are satisfied, so this configuration works. We thus conclude that $\text{min}\left(\left|S\right|\right) = 8.$

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

2016 USAMO (Problems • Resources)
First Problem	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2016 USAMO Problems/Problem 1

Contents

Problem

Solution 1

Solution 2

See also