Difference between revisions of "2019 USAJMO Problems/Problem 5"
Alexlikemath (talk | contribs) m (Minor change) |
Mathiscool12 (talk | contribs) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 27: | Line 27: | ||
===Finishing off=== | ===Finishing off=== | ||
− | To finish off, we have <math>\frac{(2n)!}{2^n} \cdot 2^{n(n+1)}</math> ways to fill in the | + | To finish off, we have <math>\frac{(2n)!}{2^n} \cdot 2^{n(n+1)}</math> ways to fill in the grid, which gets us <math>\boxed{(2n)! \cdot 2^{n^2}}</math> |
− | - | + | - AlexLikeMath |
Latest revision as of 02:29, 14 May 2020
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
Contents
Solution 1
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
.
-Stormersyle
Solution 2
There are ways to choose
. Since, there are
ways to choose
, and after that, to generate
, you take
and add 2 new elements, getting you
ways to generate
. And you can keep going down the line, and you get that there are
ways to pick
Then we can fill out the rest of the gird. First, let’s prove a lemma.
Lemma
Claim: If we know what is and what
is, then there are 2 choices for both
and
.
Proof: Note and
, so
. Let
be a set that contains all the elements in
that are not in
.
. We know
contains total
elements. And
contains total
elements. That means
contains only 2 elements since
. Let’s call these 2 elements
.
.
contains 1 elements more than
and 1 elements less than
. That 1 elements has to select from
. It’s easy to see
or
, so there are 2 choice for
. Same thing applies to
.
Filling in the rest of the grid
We used our proved lemma, and we can fill in then we can fill in the next diagonal, until all
are filled, where
. But, we haven’t finished everything! Fortunately, filling out the rest of the diagonals in a similar fashion is pretty simple. And, it’s easy to see that we have made
decisions, each with 2 choices, when filling out the rest of the grid, so there are
ways to finish off.
Finishing off
To finish off, we have ways to fill in the grid, which gets us
- AlexLikeMath
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
2019 USAJMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |