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
    @Thijs Laarhoven:Yes you are right,but I am not getting,how could we solve that equations with that constraints?2011-09-20
  • 0
    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).2011-09-20
  • 0
    (I apologize if I am the reason everyone made this oversight of not allowing $x_1 = 9$. My bad!)2011-09-20
  • 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
    which language did you code this in? Would love to use this code to check my answer to a similar problem2018-05-01
  • 0
    @Lil it was written in C#.2018-05-01
  • 0
    is this code ready to copy and paste in a c# compiler? It's not working for me.2018-05-01
  • 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
    But brute-force says the answer is $62$?!2011-09-20
  • 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.

  • 0
    +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 :)2011-09-20
  • 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
    I can see this before,but what I am not getting how to solve this equations with those constraints?2011-09-20
  • 0
    What constraint prevents you from being able to solve it?2011-09-20
  • 0
    $x_1 \geq 1, \; x_1, x_2, x_3 \leq 10$2011-09-20
  • 0
    There are many solutions... start cranking some out!2011-09-20
  • 0
    @Fool: those are $all$ the constraints. Are you saying you can't handle either the lower or the upper bounds separately?2011-09-20
  • 0
    After reading the problem in the first time itself I could see that equation however I only know how to solve it for $x_i \in [0,\infty)$ or for $x_i \in [1,\infty)$ but I never did anything like that with specified upper bound and an individual lower bound,hence I used the other approach.2011-09-20
  • 0
    You also need $x_1 \leq 8$ which I carelessly overlooked as well.2011-09-20
  • 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 (and +1 to) Brian's answer; this is more for *support* and/or *getting started*.2011-09-20