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 USAMO Problems/Problem 4"

(Created page with "==Problem== 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\}</ma...")
 
m (→‎Solution 1)
 
(2 intermediate revisions by 2 users not shown)
Line 7: Line 7:
  
 
==Solution 1==
 
==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>, etc. 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^{\left(n^2\right)}</math>.
  
 
-Stormersyle
 
-Stormersyle
Line 26: Line 26:
 
===Finishing 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>
+
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
 
-Alexlikemath
  
 +
==Solution 3==
 +
Let <math>C_{j}</math> represent the set of sets of the form <math>S_{ij}</math> for <math>1 \le i \le n</math>, <math>a_{ij}</math> denote <math>S_{(i+1)j} \backslash S_{ij}</math>, and <math>b_{ij} = S_{i(j+1)} \backslash S_{ij}</math>. Begin by considering <math>C_0</math> and <math>S_{00} = \emptyset</math>. Then  given <math>S_{i0}</math> we can create <math>S_{(i+1)0}</math> by adding one element (<math>a_{i0}</math>). Using this, the number of ways to form the sequence of <math>S_{00}, S_{10}, \dots, S_{n0}</math> are <math>(2n)(2n-1) \cdots (n+1)</math> where we successively add one of the remaining elements of <math>[2n]</math> to get consecutive terms in the sequence.
 +
 +
Now consider when we are given <math>C_{j}</math> and we need to find <math>C_{j+1}</math>. So far, there have been <math>n + j</math> chosen distinct elements (via <math>S_{nj}</math>). After finding <math>C_{j+1}</math> we will have <math>n + j + 1</math> distinct elements and so in this process we only add one unique element to sets among <math>C_{j+1}</math>. There are <math>2n - (n+j) = n-j</math> ways to chose such a new element called <math>x</math>.
 +
 +
Now notice that <math>b_{0j}, a_{0(j+1)}, a_{1(j+1)}, \dots, a_{(n-1)(j+1)}</math> is a permutation of <math>x,  a_{0j}, \dots, a_{(n-1)j}</math> by noting <math>b_{nj} = x</math> and,
 +
<cmath>S_{0j} + b_{0j} +  a_{0(j+1)} +  a_{1(j+1)} +  \cdots +  a_{(n-1)(j+1)} = S_{n(j+1)} = S_{0j} +  a_{0j}+ a_{1j} +  \cdots +  a_{(n-1)j} + b_{nj}</cmath>
 +
Furthermore,
 +
<cmath>\begin{align*}
 +
S_{0j} + b_{0j} + a_{0(j+1)} &= S_{1(j+1)} =  S_{0j} +  a_{0j} +  b_{1j} \\
 +
S_{1j} + b_{1j} + a_{1(j+1)} &= S_{2(j+1)} = S_{1j} +  a_{1j} +  b_{2j} \\
 +
&\cdots \\
 +
S_{(n-1)j} + b_{(n-1)j} + a_{(n-1)(j+1)} &= S_{n(j+1)} =  S_{(n-1)j} +  a_{(n-1)j} +  b_{nj} .
 +
\end{align*}</cmath>
 +
Therefore <math>b_{ij}, a_{i(j+1)}</math> is a permutation of <math>a_{ij}, b_{(i+1)j}</math> for <math>i < n</math>. Now let <math>k</math> be the first <math>i</math> such that <math>b_{ij} = x</math>. By definition, <math>b_{(k+1)j}, \dots = x</math>. Then the number of ways to order <math>x,  a_{0j}, \dots, a_{(n-1)j}</math> is <math>2^{k-1}</math> as there are 2 permutations for each pair before <math>\{b_{ij}, a_{i(j+1)}\} = \{a_{ij}, b_{(i+1)j}\}</math> and each pair after is determined by <math>b_{ij}= b_{(i+1)j} = k, a_{i(j+1)} = a_{ij}</math>. For <math>k  = 0</math>, the permutation is completely determined so there is one way.
 +
 +
Overall the number of ways to add the <math>j+1</math>'th row is, <cmath>(n-j)(1 + \sum_{k = 1}^n 2^{k-1}) = 2^n(n-j).</cmath>
 +
 +
In total, there are <math>(2n)(2n-1)\cdots (n+1)</math> ways to find <math>C_0</math> and for each <math>C_{j}</math> there are <math>2^n(n-j+1)</math> ways for <math>1 \le j \le n</math>. So the answer is, <cmath>\frac{2n!}{n!}(2^nn)(2^{n}(n-1)) \cdots (2^{n}1) = \boxed{2^{n^2} \cdot (2n)!}.</cmath>
 +
 +
~Aaryabhatta1
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 18:17, 26 April 2023

Problem

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:

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

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

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}$, etc. 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^{\left(n^2\right)}$.

-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

Solution 3

Let $C_{j}$ represent the set of sets of the form $S_{ij}$ for $1 \le i \le n$, $a_{ij}$ denote $S_{(i+1)j} \backslash S_{ij}$, and $b_{ij} = S_{i(j+1)} \backslash S_{ij}$. Begin by considering $C_0$ and $S_{00} = \emptyset$. Then given $S_{i0}$ we can create $S_{(i+1)0}$ by adding one element ($a_{i0}$). Using this, the number of ways to form the sequence of $S_{00}, S_{10}, \dots, S_{n0}$ are $(2n)(2n-1) \cdots (n+1)$ where we successively add one of the remaining elements of $[2n]$ to get consecutive terms in the sequence.

Now consider when we are given $C_{j}$ and we need to find $C_{j+1}$. So far, there have been $n + j$ chosen distinct elements (via $S_{nj}$). After finding $C_{j+1}$ we will have $n + j + 1$ distinct elements and so in this process we only add one unique element to sets among $C_{j+1}$. There are $2n - (n+j) = n-j$ ways to chose such a new element called $x$.

Now notice that $b_{0j}, a_{0(j+1)}, a_{1(j+1)}, \dots, a_{(n-1)(j+1)}$ is a permutation of $x, a_{0j}, \dots, a_{(n-1)j}$ by noting $b_{nj} = x$ and, \[S_{0j} + b_{0j} + a_{0(j+1)} + a_{1(j+1)} + \cdots + a_{(n-1)(j+1)} = S_{n(j+1)} = S_{0j} + a_{0j}+ a_{1j} + \cdots + a_{(n-1)j} + b_{nj}\] Furthermore, \begin{align*} S_{0j} + b_{0j} + a_{0(j+1)} &= S_{1(j+1)} = S_{0j} + a_{0j} + b_{1j} \\ S_{1j} + b_{1j} + a_{1(j+1)} &= S_{2(j+1)} = S_{1j} + a_{1j} + b_{2j} \\ &\cdots \\ S_{(n-1)j} + b_{(n-1)j} + a_{(n-1)(j+1)} &= S_{n(j+1)} = S_{(n-1)j} + a_{(n-1)j} + b_{nj} . \end{align*} Therefore $b_{ij}, a_{i(j+1)}$ is a permutation of $a_{ij}, b_{(i+1)j}$ for $i < n$. Now let $k$ be the first $i$ such that $b_{ij} = x$. By definition, $b_{(k+1)j}, \dots = x$. Then the number of ways to order $x, a_{0j}, \dots, a_{(n-1)j}$ is $2^{k-1}$ as there are 2 permutations for each pair before $\{b_{ij}, a_{i(j+1)}\} = \{a_{ij}, b_{(i+1)j}\}$ and each pair after is determined by $b_{ij}= b_{(i+1)j} = k, a_{i(j+1)} = a_{ij}$. For $k = 0$, the permutation is completely determined so there is one way.

Overall the number of ways to add the $j+1$'th row is, \[(n-j)(1 + \sum_{k = 1}^n 2^{k-1}) = 2^n(n-j).\]

In total, there are $(2n)(2n-1)\cdots (n+1)$ ways to find $C_0$ and for each $C_{j}$ there are $2^n(n-j+1)$ ways for $1 \le j \le n$. So the answer is, \[\frac{2n!}{n!}(2^nn)(2^{n}(n-1)) \cdots (2^{n}1) = \boxed{2^{n^2} \cdot (2n)!}.\]

~Aaryabhatta1

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

See also

2019 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_USAMO_Problems/Problem_4&oldid=192529"