Library / Harvard-MIT Mathematics Tournament /183 of 352

Harvard-MIT Mathematics Tournament

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:
Find the number of 20-tuples of integers $x_{1}, \ldots, x_{10}, y_{1}, \ldots, y_{10}$ with the following properties:

- $1 \leq x_{i} \leq 10$ and $1 \leq y_{i} \leq 10$ for each $i$ ;
- $x_{i} \leq x_{i+1}$ for $i=1, \ldots, 9$ ;
- if $x_{i}=x_{i+1}$ , then $y_{i} \leq y_{i+1}$ .

Solution

Solution:
By setting $z_{i}=10 x_{i}+y_{i}$ , we see that the problem is equivalent to choosing a nondecreasing sequence of numbers $z_{1}, z_{2}, \ldots, z_{10}$ from the values $11,12, \ldots, 110$ . Making a further substitution by setting $w_{i}=z_{i}-11+i$ , we see that the problem is equivalent to choosing a strictly increasing sequence of numbers $w_{1}, \ldots, w_{10}$ from among the values $1,2, \ldots, 109$ . There are $\binom{109}{10}$ ways to do this.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.