2016 USAMO Problems/Problem 1

Revision as of 16:57, 21 April 2016 by Benq (talk | contribs) (Created page with "== Problem == Let <math>X_1, X_2, \ldots, X_{100}</math> be a sequence of mutually distinct nonempty subsets of a set <math>S</math>. Any two sets <math>X_i</math> and <math>...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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. AMC logo.png

See also

2016 USAMO (ProblemsResources)
First Problem Followed by
Problem 2
1 2 3 4 5 6
All USAMO Problems and Solutions
2016 USAJMO (ProblemsResources)
Preceded by
Problem 2
Followed by
Problem 4
1 2 3 4 5 6
All USAJMO Problems and Solutions
Invalid username
Login to AoPS