XXIII OM - I - Zadanie 9

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

Ile liczb naturalnych mniejszych od $10^n$ ma zapis dziesiętny, którego cyfry tworzą ciąg niemalejący?

Rozwiązanie

Niech $A$ będzie zbiorem liczb naturalnych mniejszych od $10^n$ , mających zapis dziesiętny, którego cyfry tworzą ciąg niemalejący. Umówmy się w zapisie każdej z liczb zbioru $A$ umieszczać tyle zer na początku, by łącznie zapis tej liczby miał $n$ cyfr.

Niech $B$ będzie zbiorem liczb naturalnych mniejszych od $10^{n+10}$ mających zapis dziesiętny (z zerami na początku), którego cyfry tworzą ciąg niemalejący i w którym występuje każda z dziesięciu cyfr.

Każdemu zapisowi liczby zbioru $A$ przyporządkujmy zapis, w którym każda cyfra $0, 1, 2, \ldots, 9$ występuje o jeden raz więcej i cyfry tworzą ciąg niemalejący. Przyporządkowanie to określa odwzorowanie $f$ zbioru $A$ w zbiór $B$ . Przy tym liczba $x = \underbrace{00\ldots 0}_{n+1} 12\ldots 9$ należąca do $B$ nie odpowiada żadnej liczbie zbioru $A$ .

Odwzorowanie $f \colon A \to B - \{x\}$ jest wzajemnie jednoznaczne; odwzorowanie do niego odwrotne polega na skreśleniu po jednej cyfrze każdego rodzaju w zapisie liczby zbioru $B - \{x\}$ . Zatem liczba elementów zbioru $B$ jest o $1$ większa od liczby elementów zbioru $A$ .

Zapis dowolnej liczby zbioru $B$ składa się z $n + 10$ cyfr. Między kolejnymi cyframi jest więc $n + 9$ miejsc. Umówmy się w takim zapisie stawiać kreskę między cyframi, jeżeli są one różne. Kresek takich jest $9$ , ponieważ różnych cyfr jest $10$ i każda z nich występuje w zapisie liczby zbioru $B$ .

Aby wyznaczyć liczbę elementów zbioru $B$ zauważmy, że zapis liczby zbioru $B$ jest jednoznacznie wyznaczony przez dowolne rozmieszczenie $9$ kresek na $n+9$ miejscach. Zatem zbiór $B$ ma $\displaystyle \binom{n+9}{9}$ elementów, a zbiór $A$ ma $\displaystyle \binom{n+9}{9}-1$ elementów.