# Math Olympiad Problem regarding sum of digits.

For a positive integer $n$, let $S(n)$ be the sum of the base-10 digits of $n$. For how many numbers $n < 10^5$ does $S(n) = 14$?

I have divided the problem into three respective cases in which the number may contain 2 digits, 3 digits, and 4 digits. In case 1 there are 5 possibilities. But, how can I effectively find the number of numbers efficiently.

• KingKONG: Could you please provide the source of this question, since you used "contest-math" as a tag? Sharing that information is important, because we are strict about not permitting users to ask a question that's a part of a current/open contest-question within time-frame in which the contest is current, but can be reposted after the deadline has passed. – Namaste Apr 22 '17 at 15:53

Along the lines of Doug M's approach, I get$\\[8pt]$

$$\binom{18}{4}-5\binom{8}{4} = 2710$$

Explanation:

Allowing leading zeros (which won't affect the count), each positive integer $n < 10^5$ has a unique representation in the form

$$n = d_4(10^4)+d_3(10^3)+d_2(10^2)+d_1(10)+d_0$$

where each $d_i$ is an integer between $0$ and $9$ inclusive.

By the stars-and-bars formula, the equation

$$d_4 + d_3 + d_2 + d_1 + d_0=14$$

has ${\large{\binom{18}{4}}}$ solutions $(d_4,d_3,d_2,d_1,d_0)$ in nonnegative integers.

This is an overcount since it includes $5$-tuples with some $d_i > 9$, so we need to remove these extraneous solutions from the count.

Since the total sum is $14$, if some $d_i > 9$, there can be only one such $d_i$. There are $5$ possible positions for the oversize $d_i$, and once the location is set, the other $4$ positions must be filled with digits whose sum is at most $4$. By stars-and-bars, there are $$\binom{8}{4}$$ such $4$-tuples, and once chosen, the value of the oversize $d_i$ is uniquely determined, so $n$ is uniquely determined. The factor of $5$ is needed to account for the choice of position for the oversize $d_i$.

It is a stars and bars problem

there are 4 bars and 14 stars

and there is no bin with more than 9 stars.

${18\choose 4} - 5 {8\choose 4} = 2710$

• Except that the OP made a mistake -- there are at most 5 digits, not 4. – quasi Apr 22 '17 at 5:53
• @quasi ha ha, so it is! – Doug M Apr 22 '17 at 6:36