
4. All possible 6-digit numbers, in each of which the digits occur in non-increasing order (from left to right, e.g., 877550) are written as a sequence in increasing order. Find the 2005 -th number in this sequence.


## Solution I:

Consider a 6-digit number whose digits from left to right are in non increasing order. If 1 is the first digit of such a number, then the subsequent digits cannot exceed 1. The set of all such numbers with initial digit equal to 1 is

$$
\{100000,110000,111000,111100,111110,1111111\} .
$$

There are elements in this set.

Let us consider 6-digit numbers with initial digit 2. Starting form 200000, we can go up to 222222 . We count these numbers as follows:

| 200000 | - | 211111 | $:$ | 6 |
| :--- | :--- | :--- | :--- | :--- |
| 220000 | - | 221111 | $:$ | 5 |
| 222000 | - | 222111 | $:$ | 4 |
| 222200 | - | 222211 | $:$ | 3 |
| 222220 | - | 222221 | $:$ | 2 |
| 222222 | - | 222222 | $:$ | 1 |

The number of such numbers is 21. Similarly we count numbers with initial digit 3 ; the sequence starts from 300000 and ends with 333333 . We have

| 300000 | -322222 | $:$ | 21 |  |
| :---: | :---: | :---: | :---: | :---: |
| 330000 | - | 332222 | $:$ | 15 |
| 333000 | - | 333222 | $:$ | 10 |
| 333300 | -333322 | $:$ | 6 |  |
| 333330 | - | 333332 | $:$ | 3 |
| 333333 | -333333 | $:$ | 1 |  |

We obtain the total number of numbers starting from 3 equal to 56. Similarly,

| 400000 | 433333 | 56 |
| :---: | :---: | :---: |
| 440000 | 443333 | 35 |
| 444000 | 444333 | 20 |
| 444400 | 444433 | 10 |
| 444440 | 444443 | 4 |
| 444444 | $-\quad 444444$ | 1 |
|  |  | 126 |
| 500000 | 544444 | 126 |
| 550000 | 554444 | 70 |
| 555000 | 555444 | 35 |
| 555500 | 555544 | 15 |
| 555550 | 555554 | 5 |
| 555555 | 555555 | 1 |
|  |  | 252 |
| 600000 | 655555 | 252 |
| 660000 | $-\quad 665555$ | 126 |
| 666000 | $-\quad 666555$ | 56 |
| 666600 | $-\quad 666655$ | 21 |
| 666660 | $-\quad 666665$ | 6 |
| 666666 | $-\quad 666666$ | 1 |
|  |  | $\overline{462}$ |
| 700000 | $-\quad 766666$ | 462 |
| 770000 | $-\quad 776666$ | 210 |
| 777000 | $-\quad 777666$ | 84 |
| 777700 | $-\quad 777766$ | 28 |
| 777770 | $-\quad 777776$ | 7 |
| 777777 | 777777 | 1 |
|  |  | 792 |

Thus the number of 6-digit numbers where digits are non-increasing starting from 100000 and ending with 777777 is

$$
792+462+252+126+56+21+6=1715
$$

Since $2005-1715=290$, we have to consider only 290 numbers in the sequence with initial digit 8 . We have

$$
\begin{aligned}
& 800000-855555 \quad: \quad 252 \\
& 860000-863333: 35 \\
& 864000-864110 \quad: \quad 3
\end{aligned}
$$

Thus the required number is $\underline{864110}$.

