+0

# Combinatorics ( IOQM)

0
52
2

Find the number of positive integers N satisfying both the following conditions

I.  2 × 10⁷≤ N < 10⁸

2. The sum of the digits of N is not more than 4

Aug 20, 2023

#2
+177
0

My method of solving this is to consider all the possible ways in which N could have a sum of digits no more than 4 and adding those together.

$$2 \times 10^7 \leq N < 10^8 \\ 20\;000\;000 \leq N < 100\;000\;000$$

Considering all the values of N is a tad overwhelming, so I started with limited my search to the range $$20\;000\;000 \leq N < 30\;000\;000$$. How can the values of N within this range have a sum of digits no more than 4?

1) One way is to ensure all digits are 0. There is only 1 way this could happen.

2) One way is to ensure that one 1 appears in any digit except the leading digit. There are 7 digits available, so there are 7 ways this could happen.

3) One way is to ensure that 2 1's appear in any digit except the leading digit. There are 7 digits available for the first 1 and 6 remaining choices for the second 1. However, order is immaterial, so we must exclude the cases where different orders create the same number. $$\frac{7 * 6}{2} = 21 \text{ ways}$$.

4) One way is to ensure that one 2 appears in any digit except the leading digit. There are 7 digits available, so there are 7 ways this could happen.

I then considered the range $$30\;000\;000 \leq N < 40\;000\;000$$. Luckily, the cases are simpler than the previous range because the leading digit of 3 restricts some of the possibilities.

1) One way is to ensure all digits are 0. There is only 1 way this could happen.

2) One way is to ensure that one 1 appears in any digit except the leading digit. There are 7 digits available, so there are 7 ways this could happen.

I then considered the range $$40\;000\;000 \leq N < 50\;000\;000$$. This case is by far the simplest case.

1) One way is to ensure all digits are 0. There is only 1 way this could happen.

I then realized that there are no more options. For the range $$50\;000\;000 \leq N < 100\;000\;000$$, there are no combinations of digits that meet the criteria since the leading digit exceeds the maximum sum.

Now, just add all the possible ways. $$1 + 7 + 21 + 7 + 1 + 7 + 1 = 45$$ positive integers N that meet both criteria.

Aug 21, 2023