Maths Olympiad Prep

Library / /198 of 377

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

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

- 1xi101 \leq x_{i} \leq 10 and 1yi101 \leq y_{i} \leq 10 for each ii;
- xixi+1x_{i} \leq x_{i+1} for i=1,,9i=1, \ldots, 9;
- if xi=xi+1x_{i}=x_{i+1}, then yiyi+1y_{i} \leq y_{i+1}.

Solution

Solution:
By setting zi=10xi+yiz_{i}=10 x_{i}+y_{i}, we see that the problem is equivalent to choosing a nondecreasing sequence of numbers z1,z2,,z10z_{1}, z_{2}, \ldots, z_{10} from the values 11,12,,11011,12, \ldots, 110. Making a further substitution by setting wi=zi11+iw_{i}=z_{i}-11+i, we see that the problem is equivalent to choosing a strictly increasing sequence of numbers w1,,w10w_{1}, \ldots, w_{10} from among the values 1,2,,1091,2, \ldots, 109. There are (10910)\binom{109}{10} ways to do this.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.