Difference between revisions of "2019 USAJMO Problems/Problem 5"
Kevinmathz (talk | contribs) |
Stormersyle (talk | contribs) |
||
Line 8: | Line 8: | ||
Proposed by Ricky Liu | Proposed by Ricky Liu | ||
+ | |||
+ | ==Solution== | ||
+ | We claim the answer is <math>(2n)!\cdot 2^{n^2}</math>. | ||
+ | Proof: | ||
+ | Note that there are <math>(2n)!</math> ways to choose <math>S_{1, 0}, S_{2, 0}... S_{n, 0}, S_{n, 1}, S_{n, 2}... S{n, n}</math>, because there are <math>2n</math> ways to choose which number <math>S_{1, 0}</math> is, <math>2n-1</math> ways to choose which number to append to make <math>S_{2, 0}</math>, <math>2n-2</math> ways to choose which number to append to make <math>S_{3, 0}</math>... After that, note that <math>S_{n-1, 1}</math> contains the <math>n-1</math> in <math>S_{n-1. 0}</math> and 1 other element chosen from the 2 elements in <math>S_{n, 1}</math> not in <math>S_{n-1, 0}</math> so there are 2 ways for <math>S_{n-1, 1}</math>. By the same logic there are 2 ways for <math>S_{n-1, 2}</math> as well so <math>2^n</math> total ways for all <math>S_{n-1, j}</math>, so doing the same thing <math>n-1</math> more times yields a final answer of <math>(2n)!\cdot 2^{n^2}</math>, as desired. |
Revision as of 19:48, 19 April 2019
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.