Maths Olympiad Prep

Library / HMMT November /563 of 672

HMMT November, 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+…+10d−1=10d−19 1 + 10 + 10^{2} + \ldots + 10^{d-1} = \frac{10^{d} - 1}{9}
so we must have 10d−19=2N5\frac{10^{d} - 1}{9} = \frac{2N}{5}, or 5(10d−1)=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+…+10d−2+(N−10d−1+1)=10d−1−19+N−10d−1+1=N−8(10d−1−19). \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 N−8(10d−1−19)=25NN - 8\left(\frac{10^{d-1} - 1}{9}\right) = \frac{2}{5} N, or N=403(10d−1−19)N = \frac{40}{3}\left(\frac{10^{d-1} - 1}{9}\right). Then, 10d−1−19\frac{10^{d-1} - 1}{9} must be divisible by 33. The base-ten representation of 10d−1−19\frac{10^{d-1} - 1}{9} has d−1d-1 ones, so d−1d-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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.