-3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Namaste Apr 22 '17 at 15:53
4
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.