Problem Statement

How many integers at most \(100000\) have digits that sum to \(9\)?
Some examples include: \(81\), \(144\), and \(13212\).

Original Problem Link: Click here

Solution

We are asked to count how many positive integers ≤ \(100000\) have digits that sum to exactly \(9\).

Now, notice that:

• \(100000\) is a \(6\)-digit number, but there’s only one such number: exactly \(100000\), whose digit sum is \(1\).
• So we can safely say we’re only concerned with numbers having at most \(5\) digits.

That means we need to count all non-negative integer solutions to:

\[a + b + c + d + e = 9\]

Where each of \(a, b, c, d, e\) is a digit (i.e., between \(0\) and \(9\)), representing the digits of the number. Leading zeros are allowed here since we are working with the digit representation, not the number itself.

This becomes a classic Stars and Bars problem.

We are basically solving:

\[\text{Number of integer solutions to } x_1 + x_2 + x_3 + x_4 + x_5 = 9,\quad x_i \geq 0\]

Which is given by:

\[\binom{9 + 5 - 1}{5 - 1} = \binom{13}{4} = 715\]

So, there are \(715\) such digit combinations.

But we have to be a bit careful — this gives us digit-strings of length \(5\).
However, we’re interested in actual numbers, so we need to make sure we’re not counting combinations that start with a zero and would otherwise be \(4\)-digit or smaller.

But in this formulation, it’s fine — since leading zeros are just placeholders in the digit count. For example, \(00810\) (digit sum \(9\)) is really just \(810\), which is ≤ \(100000\). So all such digit combinations are valid.

So the total number of integers at most \(100000\) whose digits sum to \(9\) is \(\boxed{715}\)

---

💡 Did you enjoy this problem? Check out more puzzles in the Problems section!