If you write all the whole numbers from 1 to 9999 but skip every number that contains the digit 4. How many times would you have to write the digit 1?

Question

This is question is taken from an early round of a Norwegian national math competition where you have on average 5 minutes to solve each question.

I tried to solve the question by writing every number with four digits and with introductory zeros where it was needed. For example 0001 and 0101 would be the numbers 1 and 101. I then divided the different numbers into four groups based on how many times the digit 1 appeared in the number. I called these group 1,2,3 and 4. 0001 would then belong to group 1 and 0101 to group 2. I first found out in how many ways I could place the digit 1 in each group, then multiplied it by the number of combinations with the other possible eight digits (0,2,3,5,6,7,8,9). This would be the number of combinations for each group and I lastly multiplied it with the number of times 1 appeared in the number. This is done for all of the groups under:

$\binom{4}{1}\cdot8^3\cdot1$ times in group 1

$\binom{4}{2}\cdot8^2\cdot2$ times in group 2

$\binom{4}{3}\cdot8^1\cdot3$ times in group 3

$\binom{4}{4}\cdot8^0\cdot4$ times in group 4

The sum of all these calculations will be the 2916 and the correct number of times 1 appears (I think). Is this calculation/way of thinking correct? And is there a more efficient way to do it?

Answer 1

Consider an alphabet with 9 letters (0,1,2,3,5,6,7,8,9)

Consider all words that you can create with 4 letters in this alphabet : $9^4$ words.

So $4 \times 9^4$ letters will be used.

Each letter is used equally, so each letter is used $4 \times 9^3=2916$ times.

Answer 2

Here is what I would think is the quickest way to do it.

As you already wrote, use leading zeroes so that all numbers have 4 digits. You can even include $0000$ to make things easier as that will not affect the result.

Let's count how many times a 1 appears in the first 'thousands' position. The other three digits could be anything except 4, so there are $9\cdot9\cdot9=729$ such numbers. There will sometimes be 1s in those other positions, but we are not counting them just yet. This shows that the digit 1 appears exactly $729$ times in the first position.

Using the same argument, the number of times a 1 appears in each of the other digit positions is also $729$. There are four digit positions, so this leads to a total of $4\cdot729=2916$ times that the digit 1 appears.

Answer 3

The answer is correct. I try to do it in another way:

Count the $1$'s in thousandth place first.

There is 1000 $1$'s from $1$ to $9999$. But we need to exclude those contain $4$.

There is $3\times 100-3\times10+1 = 271$ numbers contain $4$.

So there is $1000-271 = 729$ $1$'s in thousandth place.

Use the same argument. There is $729$ $1$'s in hundredth place, tenth place and unit place. So totally , there is $729 \times 4=2916$ $1$'s

Answer 4

One handwaving quick approach

• How many digits in total do you write for $0000$ to $9999$?
  • $4 \times 10^4$
• How many of those are $1$s?
  • $\frac{1}{10} \times 4 \times 10^4 = 4 \times 10^3$

But you are missing anything with a particular digit, which is like working in base $9$ rather than base $10$, so the answer is presumably $4 \times 9^3 = 2916$

Answer 5

Your direct approach looks good, and may well be the easiest approach for this particular problem. The alternative approach, which generalizes better and is used below is Inclusion-Exclusion.

See this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.

It is harmless to zero fill the numbers, since neither of the digits being interrogated, $(1)$'s and $(4)$'s are $(0)$'s. Further, you can harmlessly include the number $(0000)$, as the first number under investigation. Therefore, you are examining all $[(10)^4]$ 4 digit numbers.

Let $S$ denote the enumeration of all $(1)$'s, among the 4 digit numbers, where the prohibition against the digit $(4)$ is ignored. Clearly, enumerating column my column, since each column will have exactly $(1/10)$ of its digits be a $(1)$, the enumeration here is

$$T_0 = \frac{4 \times [(10)^4]}{10} = 4000. \tag1 $$

For $k \in \{1,2,3,4\}$ let $S_k$ denote the portion of the $4000$ occurrences of the digit $(1)$ that occur when the $4$ digit number has a $(4)$ in the $k$-th digit place, reading from left to right.

Then, the desired enumeration will be

$$T_0 - ~\text{the corresponding enumeration from} ~|S_1 \cup S_2 \cup S_3 \cup S_4|.$$

For $r \in \{1,2,3,4\}$ let $T_r$ denote the enumeration of the $(1)$'s in the $~\displaystyle \binom{4}{r}$ terms represented by the summation of

$$\sum_{1 \leq i_1 < \cdots < i_r \leq 4} |S_{i_1} \cap \cdots \cap S_{i_r}|.$$

Then, in accordance with Inclusion-Exclusion, the desired enumeration will be

$$\sum_{r=0}^4 (-1)^r T_r.$$

---

Actually, I haven't worded the above definitions very well. However, the details below will clarify my intent. Further, there will be many considerations of symmetry which will simplify the computations.

Under the assumption that the leftmost digit is $(4)$, with the other $(3)$ digits unconstrained, it is clear that there will be $1000$ numbers under consideration. At random, within these $(1000)$ numbers, the probability of a $(1)$ in each of the other $(3)$ columns is $(1/10)$.

So, focusing only on the $(1000)$ numbers that have a $(4)$ in the leftmost digit (i.e. focusing on the set $S_1$), the number of occurrences of a $(1)$ in one of the other $(3)$ digits will be

$$3 \times \frac{1000}{10} = 300.$$

Further, by considerations of symmetry, you have the same enumeration for $S_2, S_3,$ and $S_4$. Therefore,

$$T_1 = 1200.$$

---

For $S_1 \cap S_2$, you have $2$ columns unconstrained, the 3rd and the 4th column, reading left to right. Further, the same symmetry considerations prevail.

Examining (in effect) only $S_1 \cap S_2$, you are examining $(100)$ numbers. In these $(100)$ numbers, the number of occurrences of a $(1)$ in the 3rd digit, combined with the number of occurrences of a $(1)$ in the 4th digit will be

$$2 \times \frac{100}{10} = 20.$$

With the same considerations of symmetry in the computation of $T_2$ as was present in the computation of $T_1$, you have that

$$T_2 = \binom{4}{2} \times 20 = 120.$$

---

Similarly,

$$T_3 = \binom{4}{3} \times \frac{10}{10} = 4.$$

That is, $T_3$ is computed by consideration of the 4 numbers $4441, 4414, 4144, 1444.$

Clearly,

$$T_4 = 0,$$

by consideration of the number $4444.$

---

Therefore, the final computation is

$$4000 - 1200 + 120 - 4 + 0 = 2916.$$