2019 USAMO Problems/Problem 4
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 .
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 .
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.
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.
To finish off, we have ways to fill in the grid, which gets us
|2019 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|