2016 USAMO Problems/Problem 1
Problem
Let be a sequence of mutually distinct nonempty subsets of a set . Any two sets and are disjoint and their union is not the whole set , that is, and , for all . Find the smallest possible number of elements in .
Solution
The answer is that .
First, we provide a inductive construction for . Actually, for we will provide a construction for which has elements in a line. (This is sufficient, since we then get for .) The idea is to start with the following construction for : Then inductively, we do the following procedure to move from to : take the chain for elements, delete an element, and make two copies of the chain (which now has even length). Glue the two copies together, joined by in between. Then place the element in alternating positions starting with the first (in particular, this hits ). For example, the first iteration of this construction gives: Now let's check is sufficient. Consider a chain on a set of size . (We need else .) Observe that there are sets of size can only be neighbored by sets of size , of which there are . So there are sets of size . Also, there are sets of size . So the total number of sets in a chain can be at most .
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
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 |