Problem #5

Consider numbers from 0 to 999999. At each place, probability of every digit is equal i.e. $\frac{1}{10}$ . So at each place, "one" will appear $\frac{10^{6}}{10}=10^5$ times. Therefore at 6 places, it will appear 600000 times. In the last number 1000000, it will appear $600001^{th}$ time!!

I know its a bit messy! Hope clean enough to understand!

I found the metaphor of one-armed bandit gambling machine useful here.

---

Consider numbers from 0 to 999999. We can as well add leading 0 to any number below 100000, since it has no effect on the number of 1's in the original string from problem statement. This is handy since we can now let the one-armed bandit have 5 drums numbered from 5 (leftmost) to 1 (rightmost), each containing digits from 0 to 9.

Now, if we know how many 1's are contributed by drum 1, drum 2, etc., and not mixing counts from different drums, the total number of 1's would be of form:

$N(1) * M(1) + N(2)* M(2) + ... + N(5) * M(5)$

where

• $N(i)$ is the number of revolutions $i$ -th drum makes to count from 0 to 999999
• $M(i)$ is the number of 1's per revolution of $i$ -th drum when counting from 0 to 999999

---

Getting at $N(i)$ :

There is $10^6$ numbers from 0 to 999999. There must be $10^6/10^i$ number of revolutions of drum i to count to the last number. It can be verified for smaller magnitudes, e.g. $10^2/10^1$ for numbers 0 to 99.

Given that, $N(i) = 10^6/10^i$

---

Finding $M(i)$ :

For i=1, given that we agreed to count 1's on all drums separately, one revolution can only yield one 1's.

For i=2, there are two cases:

• when the drum shows "1", every turn of 1st drum adds to the count of 1's
• when the drum shows anything else, turning of 1st drum adds nothing

There's 10 turns of 1st drum when 2nd shows "1".

For i=3

• when the drum shows "1", every turn of 1st drum adds to the count of 1's
• otherwise, nothing is added

There's 100 turns of 1st drum when 3rd shows "1".

etc..

---

Bringing all together

$10^6/10^1*1 + 10^6/1^2*10 + 10^6/10^3*100 + ... + 10^6/10^6*100000 = 600000$

Since we've not included the 1000000 and the single 1 it provides in our consideration: $6000000 + 1 = 6000000$ .

The answer is $6000000$ .