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
Let represent the set of sets of the form for , denote , and . Begin by considering and . Then given we can create by adding one element (). Using this, the number of ways to form the sequence of are where we successively add one of the remaining elements of to get consecutive terms in the sequence.
Now consider when we are given and we need to find . So far, there have been chosen distinct elements (via ). After finding we will have distinct elements and so in this process we only add one unique element to sets among . There are ways to chose such a new element called .
Now notice that is a permutation of by noting and, Furthermore, Therefore is a permutation of for . Now let be the first such that . By definition, . Then the number of ways to order is as there are 2 permutations for each pair before and each pair after is determined by . For , the permutation is completely determined so there is one way.
Overall the number of ways to add the 'th row is,
In total, there are ways to find and for each there are ways for . So the answer is,
|2019 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|