0
$\begingroup$

How many natural numbers below 1 million have their sum of digits equal to 18?

One way to solve this would be to make all possible cases in which the digits of the no. add up to 18 and then permute them as well as repeat this process for 1-digit, 2-digit... up till 6-digit.....but obviously thats a very cumbersome way to solve this problem. Anyone can help me out with a shorter solution?

Thanks in advance!!

$\endgroup$
5
  • $\begingroup$ An upper bound would be the number of multiples of nine. $\endgroup$
    – JustKevin
    Commented Nov 3, 2016 at 18:11
  • $\begingroup$ These are just the ordered $6-$tuples of non-negative integers which sum to $18$. Stars and Bars gives us a way to count these. $\endgroup$
    – lulu
    Commented Nov 3, 2016 at 18:20
  • $\begingroup$ @lulu nope, $11 + 2 +5$ doesn't correspond to any such number, because $11$ is not a digit. $\endgroup$ Commented Nov 3, 2016 at 18:22
  • $\begingroup$ Aah!! Thanks Gabriel!! I tried using the multinomial approach for solving but it lead me to the wrong answer.....I knew I was missing something.....but couldnt get it and hence posted the question here. Sometimes simple things jump out of our mind.....Thanks a lot again!! $\endgroup$
    – SirXYZ
    Commented Nov 3, 2016 at 18:24
  • $\begingroup$ @GabrielBurns you are correct, of course. Thanks for the correction (+1). $\endgroup$
    – lulu
    Commented Nov 3, 2016 at 18:30

1 Answer 1

3
$\begingroup$

You can use a stars and bars approach to count the total number of (ordered) ways to add six numbers (possibly including zero) totaling $18$, then subtract $6$ times the number of ways to add six numbers totaling $8$ (thus removing the cases where one of the numbers is $\ge 10$).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .