Difference between revisions of "2019 USAJMO Problems/Problem 5"
m |
Alexlikemath (talk | contribs) m (I will add another solution.) |
||
Line 9: | Line 9: | ||
Proposed by Ricky Liu | Proposed by Ricky Liu | ||
− | ==Solution== | + | ==Solution 1== |
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>. | 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>. | ||
-Stormersyle | -Stormersyle | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | There are <math>\frac{(2n)!}{2^n}</math> ways to choose <math>S_{0,0}, S_{1,1} .... S_{n,n}</math>, since, there are <math>\binom{2n}{2}</math> ways to choose <math>S_{1,1}</math>, and you can keep going down the line, and you get that there are <math>\frac{(2n)!}{2^n}</math> ways to pick <math>S_{0,0}, S{1,1} ... S{n,n}</math> Then we can fill out the rest of the gird. First, let’s prove a lemma. | ||
+ | |||
+ | ===Lemma=== | ||
+ | If we know what <math>S_{a,b}</math> is and what <math>S_{a+1,b+1}</math> is, then there are 2 choices for both <math>S_{a,b+1}</math> and <math>S_{a+1,b}</math>. It’s easy to see why. Let A be a set that contains all the elements in S_{a+1,b+1} that are not in S_{a,b} By the problem statement, <math>S_{a,b} \subseteq S_{a+1,b}, S_{a,b+1} \subseteq S_{a+1,b+1}</math>, and using the fact that <math> S_{a,b+1}</math> is 1 element larger than <math>S_{a,b}</math> , and 1 element smaller than <math>S_{a+1,b+1}</math> and same with <math>S_{a+1,b}</math>, we get that, <math>S_{a+1,b}, S_{a,b+1} = S_{a,b}+</math> some element, and, <math>S_{a+1,b}, S_{b,a+1} = S_{a+1,b+1}-</math> some other element. We can combine the two equations and get that <math>S_{a,b}+</math>some element <math>= S_{a+1,b+1}-</math>some other element. Rearranging the sides, and main the substitution for A, we get, <math>A =</math> some element + some other element. And, there are obviously 2 ways to pick what the “some element” is, and that leads to 2 choices for both <math>S_{a,b+1}</math> and <math>S_{a+1,b}</math>. | ||
+ | |||
+ | ===Filling in the rest of the grid=== | ||
+ | We used our proved lemma, and we can fill in <math>S_{0,1}, S{1,2} ... S{n-1,n}</math> then we can fill in the next diagonal, until all <math>S_{i,j}</math> are filled, where <math>i \leq j</math> But, we haven’t finished everything! But filling out the rest of the diagonals in a similar fashion is pretty simple. And, it’s easy to see that we have made <math>n(n+1)</math> decisions, each with 2 choices, when filling out the rest of the grid, so there are <math>2^{n | ||
+ | (n+1)}</math> ways to finish off. | ||
+ | |||
+ | ===Finishing off=== | ||
+ | To finish off, we have <math>\frac{(2n)!}{2^n} \cdot 2^{n(n+1)}</math> ways to fill in the gird, which gets us <math>\boxed{(2n)! \cdot 2^{n^2}}</math> | ||
+ | |||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 11:54, 20 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
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 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
If we know what is and what is, then there are 2 choices for both and . It’s easy to see why. Let A be a set that contains all the elements in S_{a+1,b+1} that are not in S_{a,b} By the problem statement, , and using the fact that is 1 element larger than , and 1 element smaller than and same with , we get that, some element, and, some other element. We can combine the two equations and get that some element some other element. Rearranging the sides, and main the substitution for A, we get, some element + some other element. And, there are obviously 2 ways to pick what the “some element” is, and that leads to 2 choices for both and .
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! But 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 gird, which gets us
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 |