mathschallenge.net logo

Never Decreasing Digits

Problem

A number has strictly increasing digits if each digit exceeds the digit to its left and is said to be a strictly increasing number; for example, 1357.
A number has increasing digits if each digit is not exceeded by the digit to its left and is said to be an increasing number; for example, 45579.

There are exactly 219 increasing numbers below one-thousand.

How many numbers below one million are increasing?


Solution

We will begin by deriving, from first principles, the information given in the problem relating to numbers below one-thousand.

It is possible to use binary strings to produce increasing numbers. Consider the following algorithm.

Let S be binary string
Let C = 0
Let K = 1
Label A
   Let D be value of Kth digit of S
   If D = 1 then output C
   If D = 0 then increment c by 1
   Increment K by 1
If K has not exceeded the length of S then goto A
Stop

For example, the binary string $001101001$ would produce 2235.

In general it can be seen that an $n$-digit increasing number will be produced by a binary string containing $n$ $1$'s, and the maximum digit will be represented by the number of $0$'s, as each zero causes the "counter" to increase by 1.

Using this idea we can represent all the 3-digit increasing numbers made up of the digits 0, 1, and 2 using 5-digit binary strings consisting of three $1$'s and two $0$'s:

$\begin{align}11100 &= 000\\11010 &= 001\\11001 &= 002\\10110 &= 011\\10101 &= 012\\10011 &= 022\\01110 &= 111\\01101 &= 112\\01011 &= 122\\00111 &= 222\end{align}$

But we must subtract one to remove $000$, so there are $\dbinom{5}{3} - 1 = 9$ such numbers.

In the same way a 3-digit increasing number using each of the digits 0 to 9 requires a binary string containing three 1's and nine 0's; that is, there are exactly $\dbinom{12}{3} - 1 = 219$ increasing numbers below one-thousand.

Now we can return to the problem: increasing numbers below one million.

As the numbers contain six digits the binary string will contain six 1's and nine 0's. Hence there are $\dbinom{15}{6} - 1 = 5004$ increasing numbers below one million.

Check out the related (strictly) Increasing Digits problem.

Problem ID: 263 (29 Jan 2006)     Difficulty: 4 Star

Only Show Problem