Maths Olympiad Prep

Library / HMMT November /390 of 672

HMMT November

Algebra Difficulty 5.0 AIME, harder Find the answer

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

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let dd be the number of digits of NN. Suppose that NN does not itself have leftmost digit 1 . Then the number of integers 1,2,…,N1,2, \ldots, N which have leftmost digit 1 is 1+10+102+…+10d−1=10d−191+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{2 N}{5}, or 5(10d−1)=18N5\left(10^{d}-1\right)=18 N. But the left-hand side is odd, so this is impossible. Thus NN must have leftmost digit 1 . In this case, the number of integers 1,2,…,N1,2, \ldots, N which have leftmost digit 1 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 3. 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 3 . Both d=1d=1 and d=4d=4 make NN less than 2017, 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: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.