1
$\begingroup$

I want to find out how many natural numbers are there less than $90000$ that have the sum of digits equal to $8$.

$x_1+x_2+x_3+x_4+x_5=8$ where $5>x_i>0$.

Relaxing $5>x_i$ for now we get $\binom{7}4$ number of solutions.

Now let $x_1>5$.Clearly there are no solutions for this. So is the answer $\binom{7}4$ ?

$\endgroup$
  • $\begingroup$ less than 90000 or 80000? $\endgroup$ – user88595 Jan 17 '14 at 11:28
  • $\begingroup$ @user88595 i made it 900000 but it doesn't make a difference $\endgroup$ – user81883 Jan 17 '14 at 11:32
  • $\begingroup$ Why do you say that $x_i > 0$? Shouldn't it be $x_i \geq 0$? $\endgroup$ – user121926 Jan 17 '14 at 11:32
  • 5
    $\begingroup$ 20060 is a natural number, and it has zeros in it. $\endgroup$ – user121926 Jan 17 '14 at 11:33
  • 1
    $\begingroup$ So you're requiring that none of the digits should be $0$? In that case, maybe you should consider rewording your question. $\endgroup$ – user121926 Jan 17 '14 at 11:39
1
$\begingroup$

I also got 35. Did it the old fashioned way so there may be an error. Note we can't pick any digit to be 5 either because there would be 4 more digits to pick each of which must be at least 1 so the total sum becomes > 8.

1) Pick the first digit to be 4 then all other digits must be 1

4 1 1 1 1

there are 5 positions where 4 can go so there are 5 of these numbers.

2) Pick the first digit to be 3 then we cannot pick another 3 because we would go over. Pick the second digit 2

3 2

now , all remaining digits must be 1

3 2 1 1 1

keeping 3 fixed , there are four positions for 2. Since there are five positions for 3 we use the multiplication principle to get 5×4 = 20 of these numbers.

3) Pick the first digit to be 2. There is no need to pick 3 as any digit because that has been done already above at 2). Pick the second digit to be 2

2 2

the sum is already 4. now there are three digits remaining to pick and one of them must be 2

2 2 2

we are forced to pick 1 for the remaining digits

2 2 2 1 1

let's work with the 1's switching their position. We can use the same argument as before to get 5×4 = 20 but now we divide by two because the digits switching position are equal. There are 10 of these numbers.

There is no need to pick the first digit to be 1 because all possible configurations have been counted already. We are done counting.

5 + 20 + 10 = 35

$\endgroup$
1
$\begingroup$

One way to do this is to use what's called the stars and bars theorem. This states that the number of integer solutions to $$ y_1+y_2+\cdots+y_n = m, \quad y_i\ge0 $$ is $$\binom{m+n-1}{m} $$ For example, with $n=2, m=3$ we could view this as the number of ways of arranging three stars and one (i.e., $n-1$) bar separating the stars, so we'd have correspondences like these $$\begin{align} y_1=1,\ y_2=2&\ \longleftrightarrow\ *|**\\ y_1=3,\ y_2=0&\ \longleftrightarrow\ ***| \end{align}$$ Now this doesn't quite solve your problem, since you require that the solutions be strictly greater than zero, but if we take your problem $$ x_1+x_2+\cdots+x_5 = 8, \quad x_i\color{red}{>}0 $$ and let $y_i=x_i-1$, we'd then have the equivalent $$ x_1+x_2+\cdots+x_5 = 8\Longrightarrow (y_1+1)+(y_2+1)+\cdots+(y_5+1)=8 $$ giving us the form we need: $$ y_1+y_2+\cdots+y_5 = 3, \quad y_i\color{red}{\ge} 0 $$ which the theorem says has $\binom{3+5-1}{3}=\binom{7}{3}=35$ solutions, as expected.

$\endgroup$

Your Answer

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