Maths Olympiad Prep

Library / /5 of 16

Combinatorics Difficulty 4.6 AIME Find the answer Italy

Problem:

Aisha writes on a sheet of paper all the numbers from 11 to 20202020. What is the difference between the number of "1" digits and the number of "0" digits that she has written?

Pick one

Solution

Solution:

The answer is (C). Observe that, given a number with decimal representation abcdabcd, if we fix a0a \neq 0, we have 1010 choices for each of the digits b,c,db, c, d: among these 1010 choices, exactly one is "1", just as exactly one is "0". Notice moreover that the same reasoning can be carried out with a three-digit number abcabc and a two-digit number abab.

This allows us to say that, if a1a \neq 1, the number of "1"s and the number of "0"s between a000a000 and a999a999 is the same; if instead a=1a=1, we will have 10001000 "1"s (coming from the digit aa written a thousand times) more than the "0"s.

Similarly, if a1a \neq 1, the number of "1"s and "0"s between a00a00 and a99a99 and between a0a0 and a9a9 is the same. If instead a=1a=1 we have 100100 more "1"s between 100100 and 199199 and 1010 more "1"s between 1010 and 1919.

Let us call ΔN\Delta N the difference between the number of "1"s and the number of "0"s in the set of numbers NN. We can then state that:

- Calling N1N_1 the set of numbers between 11 and 99 we have ΔN1=1\Delta N_1=1;
- calling N2N_2 the set of numbers between 1010 and 1919 we have ΔN2=10\Delta N_2=10;
- calling N3N_3 the set of numbers between 2020 and 9999 we have ΔN3=0\Delta N_3=0;
- calling N4N_4 the set of numbers between 100100 and 199199 we have ΔN4=100\Delta N_4=100;
- calling N5N_5 the set of numbers between 200200 and 999999 we have ΔN5=0\Delta N_5=0;
- calling N6N_6 the set of numbers between 10001000 and 19991999 we have ΔN6=1000\Delta N_6=1000.

It only remains to count ΔN7\Delta N_7 with N7N_7 the set of numbers between 20002000 and 20202020, but it is easy to verify that ΔN7=22\Delta N_7=-22. Hence, if NN is the set of all numbers between 11 and 20202020, ΔN=i=17ΔNi=111122=1089\Delta N=\sum_{i=1}^{7} \Delta N_i=1111-22=1089.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.