USAMO

Combinatorics Difficulty 7.8 National Olympiad, round 2 Find the answer

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$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

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

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.