2019 USAJMO Problems/Problem 5
Let be a nonnegative integer. Determine the number of ways that one can choose
sets
, for integers
with
, such that:
1. for all , the set
has
elements; and
2. whenever
and
.
Proposed by Ricky Liu
Solution
We claim the answer is .
Proof:
Note that there are ways to choose
, because there are
ways to choose which number
is,
ways to choose which number to append to make
,
ways to choose which number to append to make
... After that, note that
contains the
in
and 1 other element chosen from the 2 elements in
not in
so there are 2 ways for
. By the same logic there are 2 ways for
as well so
total ways for all
, so doing the same thing
more times yields a final answer of
, as desired.
-Stormersyle