A positive integer with at most 9 digits is said to be good if its units digit is 0 or 1, its tens digit is 0, 1 or 2, its hundreds digit is 0, 1, 2 or 3, its thousands digit is 0, 1, 2, 3, or 4, and so on. Thus the first ten good numbers are 1, 10, 11, 20, 21, 100, 101, 110, 111 and 120. What is the 100-th good number?. The first thing and also the most obvious thing i did was to find patterns such as:- to find the unit digit at n we have its cycles between 0 and 1 so we just have to find if 100 divides by 2 and it does so we have its last digit as 0. then we can have the same for the tenth digit having two 0s two 1s and two 2s repeating(except 1 0s at the first terms so we will have to deduct 1 from the remainder when division of 100/3) we get tenth digit as 2. we can do the same for the hundreth digit cycling with 5 0s 6 1s 7 2s and so on so we can use the sum of arithmetic progression formula and then find the remainder with 100. the hundredth digit is 2. i can go on but there doesnt seem to be a way to find how many digits does the hundredth number have. Also my method seems to be very time consuming and i am sure there is a better approach.
-
$\begingroup$ The amount of such numbers with one digit equals $2!$, with two digits $3!$, with three numbers $4!$, ..., I believe this to be a good starting point :-) $\endgroup$– DominiqueJun 23 at 6:25
3 Answers
It is easier to count the non-negative integers, then take away $1$. For instance, the number of non-negative good integers with up to (not exactly) $3$ digits is $4 \times 3 \times 2 = 24$ (choose any of $0$ to $3$ for the hundreds digit, $0$ to $2$ for the tens and $0$ or $1$ for the units). However, this includes $000$ which isn't positive, so there are only $23$ good numbers with up to $3$ digits. Then there will be $24$ $4$-digit numbers starting with $1$ (append any $3$-digit number, including $000$), $24$ starting with $2$ and $24$ starting with $3$, That makes $95$ good numbers so far. Then just count up to get $4020$ as the hundredth.
The Amount of 1-digit Good Numbers
We have that $1$ is the only 1-digit good number, and so there is exactly $\boldsymbol 1$ one-digit good number.
The Amount of 2-digit Good Numbers
The tens digit has two options of $1$ and $2$ to make the number a two-digit number, and the units digit now has $2$ options of $0$ and $1$. There would be $2\times2=\boldsymbol{4}$ two-digit good numbers in total.
Finding a Pattern
The first digit (from the left) of a number cannot be $0$, and so, we can see that the amount of $n$-digit good numbers ($1\le n\le 9$) is
$$n\times n!$$
This is because the first digit of the number does not have the option $0$, but only the options of $1$ to $n$, which is $n$ numbers. For the rest of the digits, if the digit is the $a$th place from the right, where $1\le a\le n-1$, there would be $a+1$ possibilities for the digit. Without the leading digit, the possibilities would be
$$n\times(n-1)\times\dots\times2=n!$$
This would mean there are:
- 18 three-digit good numbers
- 96 four-digit good numbers
We can see that there are $1+4+18=23$ good numbers that are less than or equal to three digits. We now need to find the $100-23=77$th four-digit good number.
Final Steps
There are 96 four-digit good numbers in total, which means there are $24$ numbers each starting with 1, 2, 3 and 4. This means that there are $72$ four-digit good numbers not starting with four.
The 73rd to 77th four-digit good numbers are 4000, 4001, 4010, 4011, 4020.
Therefore, the 77th four-digit good number (the 100th good number) is $\mathbf{4020}$.
There are $n \times n!$ "good" numbers with $n$ digits. Thus the 100-th "good" number is exactly the 77-th 4-digit "good" number. Since $77=4!\times 3+ 5$ and the fourth positive "good" number is 20, then the 100-th "good" number will be 4020.
