Library / /13 of 25

, 2008

Combinatorics Difficulty 5.6 AIME, harder Prove it Ukraine

(Malitskii Yrii) Find out what five-digit numbers are there more: (1) those in which all digits follow from left to right in the order of increasing, or (2) those in which each digit is not greater than $5$ and the order those digits follow from left to right is not descending (e.g. $12459$ satisfies the first condition, while $22589$ and $01234$ don't; $11145$ satisfies the second condition, while $21224$ , $12346$ , and $01234$ don't).

Solution

In order to prove the answer let's associate each number in one set of numbers to a single number in the other set. It's enough to associate the number $abcde$ from the first set to the number $a(b-1)(c-2)(d-3)(e-4)$ . This implies that both sets have equal power.

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 and solution reproduced as published; topic and difficulty added by this site.