Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
@Thijs Laarhoven:Yes you are right,but I am not getting,how could we solve that equations with that constraints? –  Quixotic Sep 20 '11 at 0:55
    
There was a mistake in the original formulation. You should be solving $x_1 + x_2 + x_3 = 15$ with $0 \leq x_i \leq 9$, $x_1 \neq 0$ but also $x_1 \neq 9$ (as solutions above $900$ are not allowed). –  TMM Sep 20 '11 at 1:22
    
(I apologize if I am the reason everyone made this oversight of not allowing $x_1 = 9$. My bad!) –  TMM Sep 20 '11 at 1:24
    
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. –  Ross Millikan Feb 23 '12 at 5:20

5 Answers 5

up vote 8 down vote accepted

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.

share|improve this answer
    
+1,This is a beautiful explanation!,even for the last two counting we could use the same approach as explained in before paragraphs,It seems I understood it completely now.Thanks a lot :) –  Quixotic Sep 20 '11 at 2:42
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$.) –  TMM Sep 20 '11 at 13:22

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

share|improve this answer
    
But brute-force says the answer is $62$?! –  Quixotic Sep 20 '11 at 1:12
    
@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. –  Brian M. Scott Sep 20 '11 at 1:22

HINT:

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

share|improve this answer
    
I can see this before,but what I am not getting how to solve this equations with those constraints? –  Quixotic Sep 20 '11 at 0:58
    
What constraint prevents you from being able to solve it? –  mixedmath Sep 20 '11 at 0:59
    
$x_1 \geq 1, \; x_1, x_2, x_3 \leq 10$ –  Quixotic Sep 20 '11 at 1:00
    
There are many solutions... start cranking some out! –  The Chaz 2.0 Sep 20 '11 at 1:00
    
@Fool: those are $all$ the constraints. Are you saying you can't handle either the lower or the upper bounds separately? –  mixedmath Sep 20 '11 at 1:04

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

share|improve this answer
    
I prefer (and +1 to) Brian's answer; this is more for support and/or getting started. –  The Chaz 2.0 Sep 20 '11 at 1:12

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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