[Math] How many seven-digit numbers satisfy the following conditions

combinatoricspermutations

How many seven-digit numbers divisible by 11 have the sum of their digits equal to 59?

I am able to get the seven-digit numbers divisible by 11

and

I am also able to get the seven-digit numbers whose sum of their digits equal to 59.

But i am not able to get how i can get the count of 7 digit numbers satisying both the condition.

Thanks in advance.

Thanks in advance.

Best Answer

If we look at the number $a_6a_5a_4a_3a_2a_1a_0$: $$a_6a_5a_4a_3a_2a_1a_0 = a_610^6+a_510^5+ \dots +a_010^0 \\ \equiv a_6(-1)^6 + \dots+a_0(-1)^0 \mod 11 = a_6 -a_5+a_4-a_3+a_2-a_1+a_0 \mod 11$$ So if the number will be divisible by 11 we require $$a_6 -a_5+a_4-a_3+a_2-a_1+a_0 = 11m$$

We take note that $0 \leq a_i \leq 9$ so possible values of $11m$ are limited to: $$-27 = 4\cdot0-3\cdot9\leq 11m \leq 4\cdot 9-3\cdot0 = 36$$ Which really means that $11m \in \{-22,-11,0,11,22,33\}$

The other requirement of the question was that $a_6 + \dots +a_0 = 59$. From this and the above equation (not sure how to number them and align them nicely in TeX) we add and subtract and get much nicer equations:

$$a_6 +a_4+a_2+a_0 = \frac{59+11m} 2 \\a_5+a_3+a_1 =\frac{ 59-11m}2$$

Of course the LHS is whole, so the right hand side must be as well, which means $m$ needs to be odd. So we reduce our options to:

$$11m \in \{-11,11,33\} \implies \frac{59+11m} 2 \in \{24,35,46\}$$ Of course the sum of four digits can't be $46$ from our above inequality on $a_i$, and similarly $$\frac{59-11m} 2 \in \{35,24\}$$ But the sum of three digits can't be $35$, so we're left with $$a_6 +a_4+a_2+a_0 = 35 \\a_5+a_3+a_1 =24$$

It's easy to see that the only options for the four digits is a permutation of $9998$, and the three digits must be a permutation of one of $\{699,789,888\}$.

Order doesn't matter, so basic combinatorics gives $4\cdot(3 + 3! + 1) = 40$ such numbers.