Maths Olympiad Prep

Library / /625 of 740

, 2017

Algebra Difficulty 5.4 AIME, harder Prove it United States

Problem:

Michael writes down all the integers between 11 and NN inclusive on a piece of paper and discovers that exactly 40%40\% of them have leftmost digit 11. Given that N>2017N > 2017, find the smallest possible value of NN.

Solution

Solution:

Let dd be the number of digits of NN. Suppose that NN does not itself have leftmost digit 11. Then the number of integers 1,2,,N1, 2, \ldots, N which have leftmost digit 11 is
1+10+102++10d1=10d19 1 + 10 + 10^{2} + \ldots + 10^{d-1} = \frac{10^{d} - 1}{9}
so we must have 10d19=2N5\frac{10^{d} - 1}{9} = \frac{2N}{5}, or 5(10d1)=18N5\left(10^{d} - 1\right) = 18N. But the left-hand side is odd, so this is impossible.

Thus NN must have leftmost digit 11. In this case, the number of integers 1,2,,N1, 2, \ldots, N which have leftmost digit 11 is
1+10+102++10d2+(N10d1+1)=10d119+N10d1+1=N8(10d119). \begin{aligned} & 1 + 10 + 10^{2} + \ldots + 10^{d-2} + \left(N - 10^{d-1} + 1\right) \\ = & \frac{10^{d-1} - 1}{9} + N - 10^{d-1} + 1 \\ = & N - 8\left(\frac{10^{d-1} - 1}{9}\right) . \end{aligned}
Therefore we need N8(10d119)=25NN - 8\left(\frac{10^{d-1} - 1}{9}\right) = \frac{2}{5} N, or N=403(10d119)N = \frac{40}{3}\left(\frac{10^{d-1} - 1}{9}\right). Then, 10d119\frac{10^{d-1} - 1}{9} must be divisible by 33. The base-ten representation of 10d119\frac{10^{d-1} - 1}{9} has d1d-1 ones, so d1d-1 must be divisible by 33. Both d=1d=1 and d=4d=4 make NN less than 20172017, but d=7d=7 gives the answer N=403(111111)=1481480N = \frac{40}{3}(111111) = 1481480.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.