2019 USAMO Problems/Problem 4
Contents
Problem
Let be a nonnegative integer. Determine the number of ways that one can choose sets , for integers with , such that:
for all , the set has elements; and
whenever and .
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 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |