Maths Olympiad Prep

Library / /7 of 11

Combinatorics Difficulty 4.8 AIME Find the answer China

A natural number aa is called a "lucky number" if the sum of its digits is 77. Arrange all "lucky numbers" in ascending order, and we get a sequence a1,a2,a_1, a_2, \dots. If an=2005a_n = 2005, then a5n=______a_{5n} = \_\_\_\_\_\_.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Since the number of non-negative integer solutions of the equation x1+x2++xk=mx_1 + x_2 + \dots + x_k = m is Cm+k1kC_{m+k-1}^k, the number of integer solutions, when x11x_1 \ge 1 and xi0 (i2)x_i \ge 0\ (i \ge 2), is Cm+k2m1C_{m+k-2}^{m-1}. Let m=7m=7, the number of lucky numbers with kk digits is p(k)=Ck+56p(k) = C_{k+5}^6.

Since 20052005 is the minimum lucky number of the type 2abc\overline{2abc} and p(1)=C66=1p(1) = C_6^6 = 1, p(2)=C76=7p(2) = C_7^6 = 7, p(3)=C86=28p(3) = C_8^6 = 28. Note that the number of four-digit lucky numbers of the type 1abc\overline{1abc} is the number of non-negative integer solutions of a+b+c=6a+b+c=6, i.e. C6+316=28C_{6+3-1}^6 = 28. Thus 1+7+28+28+1=651+7+28+28+1=65 and 20052005 is the 6565-th lucky number, i.e. a65=2005a_{65}=2005, so n=65n=65, 5n=3255n=325.

Furthermore p(4)=C99=84p(4) = C_9^9 = 84, p(5)=C109=210p(5) = C_{10}^9 = 210 and k=15p(k)=330\sum_{k=1}^{5} p(k) = 330.

Therefore the last six lucky numbers with 55 digits, from the largest to the smallest, are 70 00070\ 000, 61 00061\ 000, 60 10060\ 100, 60 01060\ 010, 60 00160\ 001, 52 00052\ 000. So the 325325-th lucky number is 52 00052\ 000, i.e. a325=52 000a_{325} = 52\ 000.

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 and solution reproduced as published; topic and difficulty added by this site.