1

Find $K$.

What I tried: Multinomial Theorem. But I have no clue how I should evaluate when the equation says $a+b+c \ge 10$, where $a, b$ and $c$ are three digits of the number. The inequality is what has made my mind spin, otherwise the question would've been fairly simpler using the Multinomial Theorem.

I'm in 11th grade (or high school) so please bear with me if I come off as stupid or don't know some basic stuff. Thank you!

N. F. Taussig
  • 76,571
ItsMe
  • 21

3 Answers3

2

It might be easier to solve a problem like this by reducing it to a simpler one!
Start by trying to find all 2-digit natural numbers whose sum is <10.
I looked for patterns and then solved the larger problem with 3 digits.

for 2 digits there are 90 possible 2 digit numbers (since 01,02,03,... are not included).
for A+B<10, where A is 1-9, B is 0-9

  1. if A=9, then B=0
  2. if A=8, then B=0 or B=1
  3. if A=7, then B=0 or B=1 or B=2
    etc

    so 9+8+7+6+5+...+0, this looks familiar! its just the sum for integers $\frac{n(n+1)}{2}$
    so for the number of two digit numbers whose digit sum is <10 we have:
    $\frac{9(9+1)}{2}=45$
    (recognize that this is half of the total possible digits so we know the other half of the digits sum to >=10)
    Also, we can now find the number of 2-digit numbers whose digit sum is less than ANY number, not just 10

    for example $\frac{8(8+1)}{2}=36$
    for the number of 2-digit numbers whose digit sum is <8

    for three digits, there are exactly 900 possible digits. Intuitively there seems like there will be more 3 digit numbers with their digit sums being >=10 so it might be easier to find all 3 digit numbers whose digits are <10 first (especially if you're doing this by hand!).

    we use the same idea as we did for the 2-digit solution.

if ABC is our 3-digit number (not ABC is not multiplied, those are digits)
then A is 1-9 and we find the same pattern as before

  1. A=1 then $\frac{9(9+1)}{2}=45$ this is the number of 1BC digits whose digit sum is <10
  2. A=2 then $\frac{8(8+1)}{2}=36$ this is the number of 2BC digits whose digit sum is <10
  3. A=3 then $\frac{7(7+1)}{2}=28$ this is the number of 3BC digits whose digit sum is <10
    etc, and we can add these numbers to get the total number of digits whose digit sum is <10

this is just another sum so we can slap it all together in a nice little package

$$\sum_{i=1}^9 \frac{i(i+1)}{2} = 165$$ This is the number of 3-digit numbers whose digit sum is <10.
Since our total number of possible digits is 900, and 165 of them have digit sums <10, then 735 of them have digit sums >=10.

PS. this is my first post so any feedback is welcome! I'm sure there are many clever ways to solve this problem that are easier/faster/more intuitive. this just happens to be the first way i thought about it:)

leif porkristl
  • 21
  • that is an elegant solution! – D S Dec 03 '22 at 18:42
  • 1
    In your 2-digit case, seems like you did not list the correct examples for the possible values of $A$ and $B$. For example, when $A = 1$, then $B$ can be $8$, $7$, $6$, $\dots$, $0$. – VTand Dec 03 '22 at 19:27
  • you're right! I originally wrote that list out to calculate cases for digit sums being >=10. looks like i forgot to change it. Thanks for pointing that out, ill edit it with the correct values now:) – leif porkristl Dec 03 '22 at 20:52
2

Let us consider the cases where the sum is less than 10. Let $a,b,c$ be the digits, we have: $$10>a>0$$$$10>b\ge0$$$$10>c\ge0$$ Now, we need to find the cases $a+b+c\le 9$ and subtract it from the total cases. Let us introduce a non-negative variable $k$. The inequality now becomes an equality: $$a+b+c+k = 9$$ (Note that we cannot have digits greater than 9, so, if the number in the question had been greater than 10, we would have had a nasty case, but it is fairly easy now.)

The number of solutions to this are given by $^{9+4-1}C_{4-1}$ = 220 (where each digit is less than 10, which is lucky). But the trouble is, we have also counted the cases where $a = 0$, which makes it a 2-digit number. So, we need to subtract these cases where $b+c+k = 9$. This is $^{9+3-1}C_{3-1}$ = 55.

Thus, the number of cases where the sum of digits of the 3-digit number is less than 10 is 220 - 55 = 165. There are a total of $9\times 10\times 10$ = 900 3-digit numbers.

Therefore, the number of 3-digit numbers whose sum of digits is at least 10 is 900-165 = 735.

D S
  • 4,961
0

Duplicate Q , but retained as "stars and bars" approach

It can be solved neatly, using stars and bars

As is usual, in using stars and bars, we often need to apply inclusion-exclusion if there is an upper limit.
Here there are also differing lower limits, so we will first equalize the lower limits by preplacing a digit in $x_1$, so
$\;x_1+x_2+x_3+x_4 \geq 10,$
and upper limit becomes $8$ for $x_1$ and $9$ for the rest, so if we put $9$ in the first digit or $10$ in any other, they are the "bad" cases to be excluded.

If we make the change of variables over non-negative integers, $y_1=9-x_1,\; y_2=9-x_2,\;y_3=9-x_3$, we get

$y_1+y_2+y_3 \leq 16$, and adding a non-negative slack $s$,

$y_1+y_2+y_3+s = 16$

Now apply stars and bars and weed out "bad" cases to get

$\binom{19}3 - \binom93 -\binom21\binom{10}3 = \boxed{735}$

true blue anil
  • 41,295