Maths Olympiad Prep

Library / /15 of 21

Combinatorics Difficulty 6.7 National olympiad Prove it North Macedonia

A natural number is called "happy" if the sum of its digits is 77. Let (an)n=1(a_n)_{n=1}^\infty be the increasing sequence of happy numbers. If an=2005a_n = 2005, compute a5na_{5n}.

Solution

We will use:
Lemma 1. The number of solutions of the equation x1+x2++xk=nx_1 + x_2 + \dots + x_k = n in the set of natural numbers is Cn1k1C_{n-1}^{k-1}.
Proof. Consider nn ones arranged in a row, and an arrangement of k1k-1 signs "+" between k1k-1 pairs of ones.
This arrangement of the "+" signs can be done in Cn1k1C_{n-1}^{k-1} ways while every such possibility arranges the ones in kk non-empty subsets.
Let the number of ones in every one of the subsets be m1,m2,,mkm_1, m_2, \dots, m_k (clearly mi>0m_i > 0). Then xi=mi,i=1,2,,kx_i = m_i, i = 1, 2, \dots, k is a solution of the first equation and every solution can be obtained in this way.
This ends the proof of the lemma.
Lemma 2. The number of solutions of the equation x1+x2++xk=nx_1 + x_2 + \dots + x_k = n in the set of non-negative integers (N0)(N_0) is Cn+k1k1C_{n+k-1}^{k-1} i.e. Cn+k1nC_{n+k-1}^n.
Proof. The proof is obtained directly from Lemma 1 by substituting xi=yi1x_i = y_i - 1, i=1,2,...,ki = 1, 2, ..., k.
Lemma 3. The number of solutions of the equation
x1+x2++xk=n(1) x_1 + x_2 + \dots + x_k = n \tag{1}
in the set of non-negative integers (N0)(N_0), where x11x_1 \ge 1 is Cn+k2k1C_{n+k-2}^{k-1} i.e. Cn+k2n1C_{n+k-2}^{n-1}.
Proof. We make substitutions x1=y1x_1 = y_1, xi=yi1x_i = y_i - 1 for i=2,...,ki = 2, ..., k; x1=y1x_1 = y_1, xi=yi1x_i = y_i - 1 for i=2,...,ki = 2, ..., k
Then the equation (1) is equivalent to the equation
y1+y2++yk=n+k1,(2) y_1 + y_2 + \dots + y_k = n + k - 1, \tag{2}
where clearly for i=1,2,...,ki = 1, 2, ..., k it holds that yi=xi+11y_i = x_i + 1 \ge 1 i.e. the numbers yiy_i are natural numbers for every i=1,2,...,ki = 1, 2, ..., k.
To every solution (x1,x2,...,xk)(x_1, x_2, ..., x_k) of equation (1) corresponds a unique solution (y1,y2,...,yk)(y_1, y_2, ..., y_k) of the equation (2) and vice-versa. Therefore we get that the number of solutions of equation (1) in the set of non-negative whole numbers under the condition x11x_1 \ge 1 is equal to the number of solutions of the equation (2) in the set of natural numbers which according to Lemma 1 is equal to Cn+k2k1C_{n+k-2}^{k-1} i.e. Cn+k2n1C_{n+k-2}^{n-1}.
Now according to Lemma 3 for n=7n=7, the number of “lucky” numbers having kk digits is
p(k)=Ck+56. p(k) = C_{k+5}^{6}.
So we have
p(1)=C66=1p(1) = C_6^6 = 1, p(2)=C76=7p(2) = C_7^6 = 7 and p(3)=C86=28p(3) = C_8^6 = 28.
The number of four-digit “lucky” numbers in the form abcabc is actually equal to the number of solutions of the equation a+b+c=6a+b+c=6 in the set of non-negative whole numbers and according to Lemma 2 that number is equal to C6+312=C82=28C_{6+3-1}^2 = C_8^2 = 28. Now, 20052005 is the least 4-digit “lucky” number of the form 2abc2abc. Therefore 20052005 is the 1+7+28+28+1=651+7+28+28+1=65-th in order “lucky” number.
So a65=2005a_{65} = 2005 i.e. n=65n=65 which implies 5n=3255n=325.
Then we have p(4)=C96=84p(4) = C_9^6 = 84, p(5)=C106=210p(5) = C_{10}^6 = 210 which implies that
p(1)+p(2)+p(3)+p(4)+p(5)=1+7+28+84+210=330. p(1) + p(2) + p(3) + p(4) + p(5) = 1 + 7 + 28 + 84 + 210 = 330.
So there is a total of 330330 “lucky” numbers having at most 55 digits.
The least six “lucky” numbers arranged in decreasing order are 7000070000, 6100061000, 6010060100, 6001060010, 6000160001 and 5200052000.
Therefore, a5n=a325=52000a_{5n} = a_{325} = 52000.

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.