Skip to main content
OlympiadHQ

Browse · MathNet

Print

Ukrajina 2008

Ukraine 2008 counting and probability

Problem

(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 and the order those digits follow from left to right is not descending (e.g. satisfies the first condition, while and don't; satisfies the second condition, while , , and 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 from the first set to the number . This implies that both sets have equal power.
Final answer
They are equal in number.

Techniques

Recursion, bijectionCounting two ways