10
$\begingroup$

How many numbers between $100$ and $900$ have sum of their digits equal to $15$?

I was wondering if we could derive any direct combinatoric formula to solve problem like this,my strategy is kind of trying all permutation for $100$ to $200$ then $200$ to $300$ then ...,and finally summing them up to get $62$ (if I there is not mistake)though this may not be very difficult to solve using this approach (as we are dealing with $3$ digits numbers with individual digits not greater than $9$)but is this also the fastest/efficient one?

  • 0
    My fastest solution would be to open a spreadsheet, make column A with the numbers 100 to 900, columns B-D with the various digits (tens by mod(int(a*/10),10), add them up, and if(E*=15,1,0) in column F, add column F.2012-02-23

5 Answers 5

1

I wrote a simple brute force test for this:

[Test] public void GivenNumbersBetween100And900_WhenCalculatingItsNumbers_ThenPrintThoseWhoEqual15() {     var counter = 0;     for (var hundredth = 1; hundredth <= 9; hundredth++)     {         for (var tenth = 0; tenth <= 9; tenth++)         {             for (var singles = 0; singles <= 9; singles++)             {                 if (hundredth + tenth + singles == 15 && 100*hundredth + 10*tenth + singles <= 900)                 {                     counter++;                     Console.WriteLine("{0:D3}: {1}{2}{3}", counter, hundredth, tenth, singles);                 }             }         }     }     Assert.That(counter, Is.EqualTo(62)); } 

And the result is:

001: 159 002: 168 003: 177 004: 186 005: 195 006: 249 007: 258 008: 267 009: 276 010: 285 011: 294 012: 339 013: 348 014: 357 015: 366 016: 375 017: 384 018: 393 019: 429 020: 438 021: 447 022: 456 023: 465 024: 474 025: 483 026: 492 027: 519 028: 528 029: 537 030: 546 031: 555 032: 564 033: 573 034: 582 035: 591 036: 609 037: 618 038: 627 039: 636 040: 645 041: 654 042: 663 043: 672 044: 681 045: 690 046: 708 047: 717 048: 726 049: 735 050: 744 051: 753 052: 762 053: 771 054: 780 055: 807 056: 816 057: 825 058: 834 059: 843 060: 852 061: 861 062: 870 
  • 0
    @lil It was written as a unit test, so it has a dependency to nUnit. Try to remove [Test]-attribute, and the Assert-line, then it should only depend on the .net framework. Good luck.2018-05-01
10

This is almost a standard stars-and-bars (or marbles and boxes) problem. You have $15$ marbles, and you want to distribute them amongst $3$ boxes (the digits) in such a way that the first box gets at least one marble and at most $8$ marbles and each of the other two boxes gets at most $9$ marbles. ($900$ is the only allowable $3$-digit number beginning with $9$, and its digits don’t sum to $15$, so it can be ignored.) Equivalently, you’re looking for non-negative integer solutions to $x_1+x_2+x_3=15$ subject to the constraints $1\le x_1 \le 8, x_2,x_3 \le 9$.

After putting one marble in the first box, you’ve $14$ left to distribute. Ignoring the upper bounds, this can be done in $\dbinom{14+3-1}{3-1}=\dbinom{16}{2}=120$ ways. The ways that have at least $9$ marbles in the first box are bad, so they have to be subtracted off. After putting $9$ marbles in the first box, you’ve $6$ left to distribute; this can be done in $\dbinom{6+3-1}{3-1}=\dbinom{8}{2}=28$ ways. Similarly, there are $\dbinom{4+3-1}{3-1}=\dbinom{6}{2}=15$ distributions that have too many marbles in the second box (because after putting one in the first box and $10$ in the second box you’ve only $4$ left to distribute) and $15$ that have too many in the third box. It’s not possible to have too many marbles in two boxes: that would require at least $19$ marbles. Thus, the final count is $120-28-2(15)=62$ numbers between $100$ and $900$ whose digits sum to $15$.

  • 0
    @FoolForMath: You’re right: in the last step I carelessly forgot that I still had to put one marble in the first box. I’ve corrected it now.2011-09-20
10

This problem can be reduced to solving

$x_1 + x_2 + x_3 = 15, \quad 0 \leq x_i \leq 9, \quad x_1 \neq 0, \quad x_1 \neq 9$

First, we solve

$x_1 + x_2 + x_3 = 15, \quad 0 \leq x_i \leq 15$

This is a standard stars and bars problem, with solution $\binom{15+3-1}{15} = 136$. Now which solutions are wrong? Well, first of all those with one of them above $10$. But if, say, $x_1 \geq 10$, then we can write x_1' = x_1 - 10 and x_2' = x_2, x_3' = x_3 to reduce the problem to

x_1' + x_2' + x_3' = 5, \quad 0 \leq x_i' \leq 5

This is again a standard stars and bars problem, with solution $\binom{5+3-1}{5} = 21$. Since exactly one of $x_1,x_2,x_3$ could be above $10$, this gives $3 \cdot 21 = 63$ wrong solutions in total. So there are $136 - 63 = 73$ solutions to

$x_1 + x_2 + x_3 = 15, \quad 0 \leq x_i \leq 9$

Finally, we need to subtract $4$ solutions with $x_1 = 0$ (i.e. $(x_2,x_3) \in {(6,9),(7,8),(8,7),(9,6)}$), but also subtract $7$ solutions for $x_1 = 9$ (i.e. $(x_2,x_3) \in {(0,6),\ldots,(6,0)}$). This gives $62$ solutions in total.

  • 1
    @Fool: Very true. The numbers $4$ and $7$ come from solving $x_2 + x_3 = 15, \quad 0 \leq x_i \leq 9$ and $x_2 + x_3 = 6, \quad 0 \leq x_i \leq 6$ respectively, so we're actually solving two more stars and bars problems here. (Three actually, as for the first you have to do a split again of $0 \leq x_i \leq 15$ and subtracting the wrong solutions. For the first you get $\binom{15+2-1}{15} - 2 \cdot \binom{5+2-1}{5} = 4$ and for the second you get $\binom{6+2-1}{6} = 7$.)2011-09-20
3

HINT:

$x_1 + x_2 + x_3 = 15, \; x_1 \geq 1, \; x_1, x_2, x_3 < 10$ is very relevant here.

  • 0
    Yes, this is true too. I'll omit it in the nature of the hint.2011-09-20
1

There is a high mass:volume ratio, so here we go ...

I'll just get you started counting, since other answers are being posted.
$15 = 9 + 6 + 0$. How many permutations of this are between $100$ and $900$?

$15 = 9 + 5 + 1$. How many ...?

$15 = 9 + 4 + 2$...

...


$15 = 8 + 7 + 0$

...

$15 = 7 + 7 + 1$...

  • 0
    I prefer (a$n$d +1 to) Brian's answer; this is more for *support* and/or *getting started*.2011-09-20