Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 USAJMO Problems/Problem 5"
 
(18 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
Let <math>n</math> be a nonnegative integer. Determine the number of ways that one can choose <math>(n+1)^2</math> sets <math>S_{i,j}\subseteq\{1,2,\ldots,2n\}</math>, for integers <math>i,j</math> with <math>0\leq i,j\leq n</math>, such that:
 
Let <math>n</math> be a nonnegative integer. Determine the number of ways that one can choose <math>(n+1)^2</math> sets <math>S_{i,j}\subseteq\{1,2,\ldots,2n\}</math>, for integers <math>i,j</math> with <math>0\leq i,j\leq n</math>, such that:
 +
  
 
1. for all <math>0\leq i,j\leq n</math>, the set <math>S_{i,j}</math> has <math>i+j</math> elements; and
 
1. for all <math>0\leq i,j\leq n</math>, the set <math>S_{i,j}</math> has <math>i+j</math> elements; and
  
 
2. <math>S_{i,j}\subseteq S_{k,l}</math> whenever <math>0\leq i\leq k\leq n</math> and <math>0\leq j\leq l\leq n</math>.
 
2. <math>S_{i,j}\subseteq S_{k,l}</math> whenever <math>0\leq i\leq k\leq n</math> and <math>0\leq j\leq l\leq n</math>.
 +
  
 
Proposed by Ricky Liu
 
Proposed by Ricky Liu
 +
 +
==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>.
 +
 +
-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 after that, to generate <math>S_{2,2}</math>, you take <math>S_{1,1}</math> and add 2 new elements, getting you <math>\binom{2n-2}{2}</math> ways to generate <math>S_{2,2}</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===
 +
<b>Claim:</b> 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>.
 +
 +
<b>Proof:</b> Note <math>a \leq a+1</math> and <math>b \leq b+1</math>, so <math>S_{a,b}\subseteq S_{a+1,b+1}</math>. 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 = S_{a+1,b+1} - S_{a,b} </math>. We know <math>S_{a+1,b+1}</math> contains total <math>a+b+2</math> elements. And <math>S_{a,b}</math> contains total <math>a+b</math> elements. That means <math>A</math> contains only 2 elements since <math>(a+b+2)-(a+b) = 2</math>. Let’s call these 2 elements <math>m, n</math>. <math>A = \{m, n\}</math>. <math>S_{a,b+1}</math> contains 1 elements more than <math>S_{a,b}</math> and 1 elements less than <math>S_{a+1,b+1}</math>. That 1 elements has to select from <math>A</math>. It’s easy to see <math>S_{a,b+1} = S_{a,b}\cup \{m\}</math> or <math>S_{a,b+1} = S_{a,b}\cup \{n\}</math>, so there are 2 choice 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(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 grid, which gets us <math>\boxed{(2n)! \cdot 2^{n^2}}</math>
 +
 +
- AlexLikeMath
 +
 +
 +
{{MAA Notice}}
 +
 +
==See also==
 +
{{USAJMO newbox|year=2019|num-b=4|num-a=6}}

Latest revision as of 01:29, 14 May 2020

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 after that, to generate $S_{2,2}$, you take $S_{1,1}$ and add 2 new elements, getting you $\binom{2n-2}{2}$ ways to generate $S_{2,2}$. 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

Claim: 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}$.

Proof: Note $a \leq a+1$ and $b \leq b+1$, so $S_{a,b}\subseteq S_{a+1,b+1}$. Let $A$ be a set that contains all the elements in $S_{a+1,b+1}$ that are not in $S_{a,b}$. $A = S_{a+1,b+1} - S_{a,b}$. We know $S_{a+1,b+1}$ contains total $a+b+2$ elements. And $S_{a,b}$ contains total $a+b$ elements. That means $A$ contains only 2 elements since $(a+b+2)-(a+b) = 2$. Let’s call these 2 elements $m, n$. $A = \{m, n\}$. $S_{a,b+1}$ contains 1 elements more than $S_{a,b}$ and 1 elements less than $S_{a+1,b+1}$. That 1 elements has to select from $A$. It’s easy to see $S_{a,b+1} = S_{a,b}\cup \{m\}$ or $S_{a,b+1} = S_{a,b}\cup \{n\}$, so there are 2 choice 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 grid, 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. AMC logo.png

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_USAJMO_Problems/Problem_5&oldid=122387"