Maths Olympiad Prep

Library / /265 of 348

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. Spacing and $ signs are ignored.

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++10d1=10d191+10+10^{2}+\ldots+10^{d-1}=\frac{10^{d}-1}{9} so we must have 10d19=2N5\frac{10^{d}-1}{9}=\frac{2 N}{5}, or 5(10d1)=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++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 3. The base-ten representation of 10d119\frac{10^{d-1}-1}{9} has d1d-1 ones, so d1d-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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.