100% of all numbers contain a 3

Or: Infinity Weirdness, Part 1.

What percentage of all whole numbers contain at least one digit 3? It seems like a simple enough question. The simplest way to start trying to answer it is to have a look at some numbers, and do some counting.

Let's look at 1-digit numbers first. There are 10 of them: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Only one of these 10 contains a 3, so that's 10%.

Now, let's extend our list to the first 100 whole numbers: 0 through 99. We know that 10% of the numbers from 0 to 9 contain a 3. It's the same 10% with numbers from 10 to 19, because they are just the numbers from 0 to 9 with a 1 attached. Adding a 1 doesn't affect our count of numbers with 3s. Similarly, our count is 10% for 20-29, 40-49, 50-59, and so on. The interesting case is 30-39; obviously, all 100% of these numbers contain a 3. Taken together, our count looks like this:

0 - 9: 10%
10 - 19: 10%
20 - 29: 10%
30 - 39: 100%
40 - 49: 10%
...
90 - 99: 10%

We have 9 sets at 10%, and 1 set at 100%. Average this out, and we find that 19% of the numbers from 0 to 99 contain at least one 3.

The way this step from 1-digit numbers to 2-digit numbers worked gives us an insight into how this works generally. When we add a digit, we're adding each of the digits 0 - 9 to all of our existing numbers. 9 of these 10 digits (0-2, 4-9) have no effect on the count of 3s, and the last digit (3) creates a 100% count.

This means that if X is the fraction of n-digit numbers containing a 3, then the fraction of n+1-digit numbers containing a 3 is given by: 0.9X + 0.1. In more formal notation, this is a recursion where:

F_n+1 = 0.9F_n + 0.1
F₁ = 0.1

This can be expressed as a closed form in the following way (this can be shown with a small induction proof):

F_n = 1 - 0.9ⁿ

That's fine; the first few values of this are 10%, 19%, 27.1%. But we're interested in all the whole numbers, and the limit as n goes to infinity here is 100%. So we end up with an odd conclusion: 100% of all whole numbers contain a 3, even though not all whole numbers contain a 3. It's an important difference when dealing with infinite sets - 100% and all don't mean the same thing.