5. In the place of Srednje Zuze, every phone number has five digits arranged in non-increasing or non-decreasing order, and the first digit is not 0. How many phone numbers can exist in this place at most?

## Third grade - B category
5. If all digits are the same, there are 9 such numbers (all except 00000, as it does not satisfy the conditions of the problem). Let's further consider numbers that have at least two different digits.

First, let's count how many such numbers can have digits in non-decreasing order. Each such number is uniquely determined by the selection of five digits that make it up (once the digits are chosen, the number is obtained by sorting them in non-decreasing order), and among the digits, there must not be a 0 (if there were, it would have to go at the beginning of the phone number due to the non-decreasing order, which is prohibited by the problem's conditions). If the number is composed of only two different digits, they form one of the following patterns: first one digit, then four of the same (larger than the previous one); first two of the same, then three of the same (larger than the previous ones); first three of the same, then two more of the same; first four of the same, then one more larger. Thus, from two fixed digits, we can make 4 phone numbers, and since these 2 digits can be chosen in $\binom{9}{2}$ ways, there are $4 \cdot \binom{9}{2}$ such phone numbers. If the number is composed of three different digits, they form one of the following patterns: $3+1+1, 1+3+1, 1+1+3, 2+2+1, 2+1+2$, or $1+2+2$, which is 6 possibilities, and since these three digits can be chosen in $\binom{9}{3}$ ways, this gives $6 \cdot \binom{9}{3}$ numbers. If the number is composed of four different digits, they form one of the following patterns: $1+1+1+2, 1+1+2+1, 1+2+1+1$, or $2+1+1+1$, so there are $4 \cdot \binom{9}{4}$ such numbers. Finally, those with all different digits have $\binom{9}{5}$.

Now let's count the numbers whose digits are in non-increasing order. The reasoning is the same, only we need to keep in mind that now we have 10 digits to choose from (since here the numbers can contain the digit 0), so we get another $4 \cdot \binom{10}{2} + 6 \cdot \binom{10}{3} + 4 \cdot \binom{10}{4} + \binom{10}{5}$ phone numbers.

The total result is: $9 + 4 \cdot \binom{9}{2} + 6 \cdot \binom{9}{3} + 4 \cdot \binom{9}{4} + \binom{9}{5} + 4 \cdot \binom{10}{2} + 6 \cdot \binom{10}{3} + 4 \cdot \binom{10}{4} + \binom{10}{5} = 9 + 144 + 504 + 504 + 126 + 180 + 720 + 840 + 252 = 3279$ phone numbers.

## Third Grade - B Category