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

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$ .

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

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

Page

Toolbox

Search

2016 USAMO Problems/Problem 1

Problem

Solution

See also