Difference between revisions of "2019 USAJMO Problems/Problem 5"

Revision as of 14:26, 20 April 2019

Let $n$ be a nonnegative integer. Determine the number of ways that one can choose $(n+1)^2$ sets $S_{i,j}\subseteq\{1,2,\ldots,2n\}$ , for integers $i,j$ with $0\leq i,j\leq n$ , such that:

1. for all $0\leq i,j\leq n$ , the set $S_{i,j}$ has $i+j$ elements; and

2. $S_{i,j}\subseteq S_{k,l}$ whenever $0\leq i\leq k\leq n$ and $0\leq j\leq l\leq n$ .

Proposed by Ricky Liu

Solution 1

Note that there are $(2n)!$ ways to choose $S_{1, 0}, S_{2, 0}... S_{n, 0}, S_{n, 1}, S_{n, 2}... S{n, n}$ , because there are $2n$ ways to choose which number $S_{1, 0}$ is, $2n-1$ ways to choose which number to append to make $S_{2, 0}$ , $2n-2$ ways to choose which number to append to make $S_{3, 0}$ ... After that, note that $S_{n-1, 1}$ contains the $n-1$ in $S_{n-1. 0}$ and 1 other element chosen from the 2 elements in $S_{n, 1}$ not in $S_{n-1, 0}$ so there are 2 ways for $S_{n-1, 1}$ . By the same logic there are 2 ways for $S_{n-1, 2}$ as well so $2^n$ total ways for all $S_{n-1, j}$ , so doing the same thing $n-1$ more times yields a final answer of $(2n)!\cdot 2^{n^2}$ .

-Stormersyle

Solution 2

There are $\frac{(2n)!}{2^n}$ ways to choose $S_{0,0}, S_{1,1} .... S_{n,n}$ , since, there are $\binom{2n}{2}$ ways to choose $S_{1,1}$ , and you can keep going down the line, and you get that there are $\frac{(2n)!}{2^n}$ ways to pick $S_{0,0}, S_{1,1} ... S_{n,n}$ Then we can fill out the rest of the gird. First, let’s prove a lemma.

Lemma

If we know what $S_{a,b}$ is and what $S_{a+1,b+1}$ is, then there are 2 choices for both $S_{a,b+1}$ and $S_{a+1,b}$ . 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}$ . $A$ contains 2 elements, since (a+1+b+1)-(a+b) = 2. Let’s call the 2 elements, $m,n$ . And, it’s easy to see $S_{a,b+1} = S_{a,b}$ +(m or n), so there are 2 possibilities for $S_{a,b+1}$ Same thing applies to $S_{a+1,b}$

Filling in the rest of the grid

We used our proved lemma, and we can fill in $S_{0,1}, S_{1,2} ... S_{n-1,n}$ then we can fill in the next diagonal, until all $S_{i,j}$ are filled, where $i \leq j$ . 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 $n(n+1)$ decisions, each with 2 choices, when filling out the rest of the grid, so there are $2^{n (n+1)}$ ways to finish off.

Finishing off

To finish off, we have $\frac{(2n)!}{2^n} \cdot 2^{n(n+1)}$ ways to fill in the gird, which gets us $\boxed{(2n)! \cdot 2^{n^2}}$

-Alexlikemath

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

@@ Line 19: / Line 19: @@
 ===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 <math>S_{a+1,b+1}</math> that are not in <math>S_{a,b}</math> 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>.
+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 <math>A</math> be a set that contains all the elements in <math>S_{a+1,b+1}</math> that are not in <math>S_{a,b}</math>. <math>A</math> contains 2 elements, since (a+1+b+1)-(a+b) = 2. Let’s call the 2 elements, <math>m,n</math>. And, it’s easy to see <math>S_{a,b+1} = S_{a,b}</math>+(m or n), so there are 2 possibilities for <math>S_{a,b+1}</math> Same thing applies to <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! 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 <math>n(n+1)</math> decisions, each with 2 choices, when filling out the rest of the grid, so there are <math>2^{n
+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! 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 <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.

2019 USAJMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search