# How many numbers smaller than $10^6$ contain exactly three '$9$'s and have an odd sum of digits?

i came up with an idea that i choose

Even Even Even 9 9 9 - and i sort it in ways such that all even are the same - $\frac{6!}{3!*3!}$ two are the same - $\frac{6!}{3!*2!}$ all are different - $\frac{6!}{3!}$

other one is that

Odd Odd Even 9 9 9

odd are the same - $\frac {6!}{3!*2!}$ all three are differnt - $\frac{6!} {3!}$

and my result is a sum of all this options. Am i right?

• You're forgetting to pick the numbers, for example your "all even are the same" case should be $\frac{6!}{3! 3!} \cdot 5$ Commented Feb 4, 2017 at 20:51
• also, the three 9s can be at any position, leading 0 cannot come, Commented Feb 4, 2017 at 20:55
• we can assume that 000999=999, it doesn't affect sum of digits or the fact that number is less than 1000000 Commented Feb 4, 2017 at 20:56
• @chelivery i shoold do it as 5 choose 3 for three different, 5 choose 2 for two different and 5 choose 1 in all are the same? Commented Feb 4, 2017 at 20:58
• @Kiran i gues it can 000999 - it comes to 999 so it cool. Commented Feb 4, 2017 at 20:58

An alternative method:

Choose the three locations for the $9$s: there are $\dbinom 63$ possibilities.

Then, among the remaining digits (not $9$s), choose any digit except $9$ for the leftmost place ($9$ possibilities), then choose any digit except $9$ for the middle place ($9$ possibilities).

Among the ways to fill these two digits, there are $4^2 + 5^2$ in which we choose two digits of the same parity and get an even sum, in which case we need to choose an even digit for the last open place ($5$ choices). There are $2\times4\times 5$ ways in which to get an odd sum, in which case we need one more odd digit ($4$ choices, since $9$ is excluded).

So altogether we have $$\binom 63 \left(5(4^2 + 5^2) + 4(2\times4\times 5) \right) = 7300.$$

• I was working on an answer that went in this manner, you've beat me to it. +1, I like this answer the most. Commented Feb 4, 2017 at 21:25
• @Rustyn Thanks, though I think it would be fine for the OP to select one of the other answers since they show how to finish the partial solution presented in the question. Commented Feb 4, 2017 at 21:28
• True. However, I think you've already won the OP over. Commented Feb 4, 2017 at 21:30

• Three even digits and the 9:

• The same even digit every time (5 choices: $0, 2, 4, 6, 8$ and permutation): $5 \cdot \frac{6!}{3! \cdot 3!}$
• Two even digits are the same: $5 \cdot 4 \cdot \frac{6!}{3! \cdot 2!}$
• The three even digits are different: $5 \cdot 4 \cdot 3 \cdot \frac{6!}{3!}$
• Two odd digits, one even (4 choices for the odd digit: $1, 3, 5, 7$):

• The same odd digit : $\underbrace{5}_{even} \cdot \underbrace{4}_{odd} \cdot \frac{6!}{3! \cdot 2!}$
• Odd digits are different: $\underbrace{5}_{even} \cdot \underbrace{4 \cdot 3}_{odd} \cdot \frac{6!}{3!}$

The answer is the sum of all cases.

• which gives 7300 Commented Feb 4, 2017 at 21:08

There are $\frac{6!}{3!3!}$ to choose where the 9's are and where the even numbers are. However, even if we know that the three even numbers are equal, there are $5$ ways to choose if it is $0,2,4,6$ or $8$. (Note that we don't care about leading zeros, because they don't affect the sum of digits.) So there are $5\frac{6!}{3!3!}$ such ways. When we have two different even numbers, surely there is $\frac{6!}{3!2!}$ ways to separate 9's positions, and two even number positions, but there are also $5*4=20$ ways to choose actual even numbers. In the case of different even numbers we have $5*4*3=60$ ways to choose even numbers for the first, second and third non-9 digit and $\frac{6!}{3!3!}$ ways to choose 9's places before. So in the case of even digits there are $$5\frac{6!}{3!3!}+20\frac{6!}{3!2!}+60\frac{6!}{3!3!}=\frac{6!}{3!}(5/6+10+10)=20*(5+60+60)=2500$$ However, note that in fact separating three cases doesn't give any advantage to us. We would better say that there is $\frac{6!}{3!3!}$ ways to choose the places of $9$'s and then $5^3$ ways to choose even numbers for other three places: just five choices for each place, independently from the others. And we obtain $$125\frac{6!}{3!3!}=4*5^4=2500$$ The same, all is ok.

For the case of two odds we can do the following: choose 9s places in $\frac{6!}{3!3!}$ ways, then choose in 3 ways where is even and in 5 ways what is it. For two odds we can choose out of $1,3,5,7$, so we have $4^2$ choices. All in all, for the odd case, $$\frac{6!}{3!3!}*3*5*16=20*15*16=4800$$ And finally, $2500+4800=7300$ is the answer.

This is a slight variation on David K's answer. It's the same except for how we deal with the last digit. I'd hoped to avoid cases by exploiting symmetry, but it turned out I couldn't completely avoid them.

• Choose the positions of the three $9$'s (there are $6 \choose 3$ ways to do this)

• Moving left to right, choose two of the remaining three digits (there are $9^2$ ways to do this)

• Choosing the last digit, call it $k$, it's a little tough to make sure the digit sum is odd. But we can exploit symmetry a bit:

• If you choose any one of $1, 2, 3, 4, 5, 6, 7, 8$, then if you'd chosen $9 - k$ instead you'd wind up with a number whose digit sum is of the opposite parity (e.g., if you choose $6$ and the sum is even, then having chosen $9 - 6 = 3$ would leave you with an odd digit sum). There are $8$ possibilities here, half of them will be acceptable whether the sum without this digit is even or odd.

• It remains how to deal with $0$ (since we've chosen our three $9$'s). Unfortunately, I can't think of a better way than messing with cases of the two non-$9$ chosen digits. We can choose $0$ as the final digit if and only if the two numbers have an even sum. So the two can both be even ($5^2$ ways), or both odd ($4^2$ ways).

So our total is ${6 \choose 3} \cdot \big[ (9^2 \cdot 4) +(4^2 + 5^2)\big]$ (not surprisingly also $7300$), where the sum corresponds to whether our "final" digit is nonzero (in which case we can choose the "first" two freely) or not.

Some brute force which quickly produces, unsurprisingly, 7300. (Python)

N= 1000000

count=0
for i in range(1,N):
nines = 0
dsum = 0
for c in str(i):
if c == '9': nines += 1
dsum += int(c)
if dsum % 2 == 1 and nines == 3: count += 1
print count


Assuming leading zeros allow us to assume all numbers have six digits you need.

A) 1 non-nine odd, two different evens, 3 nines

plus

B) 1 (non-nine odd), two same evens, 3 nines

plus

C) 3 non-nine odds, all different, 3 nines

plus

D) 3 non-nine odds, two the same, 3 nines

E) 3 non-nine odds, all the same, 3 nines.

There are $4$ odds to choose from and $5$ evens.

A) is $4*5*4*{3\choose 1}{6 \choose 3}$. That is, $4$ choices for the non-nine odd, $5$ for the first even, $4$ for the second even. There are ${3\choose 1}$ ways to arrange the odd digit among the two even digits. And there are ${6\choose 3}$ ways to place the three nines among six digits.

B) is $4*5{3\choose 1}{6 \choose 3}$. That is, $4$ choices for the first non-nine odd, $5$ choices for the two evens. There are ${3\choose 1}$ ways to arrange the odd digit among the two even digits. And there are ${6\choose 3}$ ways to place the three nines among six digits.

C) is $4*3*2{6\choose 3}$

D) is $4*3{3 \choose 2}{6\choose 3}/2$

E) is $4*{6 \choose 3}$

There is an alternative.

There is ${6 \choose 3}$ ways to arrange three $9$s is six positions. There are $9^3$ possible options for the remaining three digits. $5^3$ of them are all evens (as there are $5$ choices of non-nine evens). $4^3$ are all odd (as there are $4$ choices of non-nine odds). $4*5^2{3\choose 1}$ of those have $1$ odd and $2$ evens. $4^2*5{3\choose 1}$ of those have $2$ odds and $1$ even.

Detour: Verify the $9^3 = 5^3 + 5^2*4*{3\choose 1} + 5*4^2*{3\choose 1} + 4^3$

$9^3 = (5+4)^3 = 5^3 + 5^2*4*{3\choose 1} + 5*4^2*{3\choose 1} + 4^3$ is just the binomial theorem. Nothing to verify.

End of detour.

Of those $5^3$ (three evens) and $5*4^2*3$ (two odds, one even) have an even sum of digits. So when three $9$s are added the sum will be odd.

So there are ${6 \choose 3}(5^3 + 5*4^2*3)$ six digit numbers with exactly three $9$s and an even sum of digits.