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 |