Number of $5$-digit numbers which are divisible by $11$ and whose digits add up to $43$

As you note, the requirement for a digit sum of $43$ restricts the possible digit choices quite sharply.

In general numbers divisible by $11$ have alternating digit sums (eg. adding $a$s and $b$s from $abababa$) that differ by a multiple of $11$ (which could be zero, if sums are equal). This is due to powers of $10$ alternating between $-1$ and $1 \bmod 11$.

In this case since the total digit sum is odd, we must have alternating sums that differ by $11$, that is $16$ and $27$ for the two- and three-digit sums respectively. Clearly this gives us something of the form $9\;\square\;9\;\square\;9$ and the options for the intervening digits adding to $16$ are $(7,9),(8,8),(9,7)$ as you found.

By request in comments:

If the digit sum were $36$, all other conditions unchanged, we would have to have the digit sums equal $\to (18,18)$ (as a difference of $22 \to (29,7)$ is not feasible). Then there is only one option for the two-digit set $(9,9)$ and we can find the number of divisions on the three-digit set by a small inclusion-exclusion to partition the $18$ into three valid digits. First there are two options that include a zero, $(99099,99990)$ after which we can take the partitions as being non-zero. Then without constraint on the upper size of partition, the options would be $\binom {17}2$, and removing the cases with a digit greater than $9$ reduces this by $3\cdot \binom 82$, giving $2+136-84=54$ options.


what if the sum of the digits of the number turns out to be such that the number of numbers satisfying the condition turns out to be too big. In that case, how am I supposed to find the number of numbers which are divisible by $11$ without the help of a computer but just with pen and paper.

Let us consider the collection of all $5$-digit numbers such that the sum of digits of each number is $S$.

We know that $$\text{$\overline{x_1x_2x_3x_4x_5}$ is divisible by $11\iff x_1-x_2+x_3-x_4+x_5=-11,0,11,22$}$$ since $-17=1-9+0-9+0\le x_1-x_2+x_3-x_4+x_5\le 9-0+9-0+9=27$.

  • If $S$ is odd, then we want to find the number of $(x_1,x_2,x_3,x_4,x_5)$ where $0\le x_i\le 9\in\mathbb Z$ with $x_1\not=0$ such that $$\begin{cases} x_1+x_2+x_3+x_4+x_5=S \\ x_1-x_2+x_3-x_4+x_5=-11\end{cases}\quad\text{or}\quad \begin{cases} x_1+x_2+x_3+x_4+x_5=S \\ x_1-x_2+x_3-x_4+x_5=11\end{cases},$$ i.e. $$\begin{cases}x_1+x_3+x_5=\frac{S-11}{2}\\ x_2+x_4=\frac{S+11}{2}\end{cases}\quad\text{or}\quad \begin{cases}x_1+x_3+x_5=\frac{S+11}{2}\\ x_2+x_4=\frac{S-11}{2}\end{cases}$$So, using Newton's generalized binomial theorem, we have that the number we want is given by $$\begin{align}&\left([x^{(S-11)/2}] \left(\frac{x-x^{10}}{1-x}\right)\left(\frac{1-x^{10}}{1-x}\right)^2\right)\times\left([x^{(S+11)/2}]\left(\frac{1-x^{10}}{1-x}\right)^2\right)\\\\&\qquad +\left([x^{(S+11)/2}] \left(\frac{x-x^{10}}{1-x}\right)\left(\frac{1-x^{10}}{1-x}\right)^2\right)\times\left([x^{(S-11)/2}]\left(\frac{1-x^{10}}{1-x}\right)^2\right)\\\\&=\left([x^{(S-11)/2}](x-x^{10})(1-x^{10})^2(1-x)^{-3}\right)\times \left([x^{(S+11)/2}](1-x^{10})^2(1-x)^{-2}\right)\\\\&\qquad +\left([x^{(S+11)/2}](x-x^{10})(1-x^{10})^2(1-x)^{-3}\right)\times \left([x^{(S-11)/2}](1-x^{10})^2(1-x)^{-2}\right)\\\\&=\left([x^{(S-11)/2}](x-x^{10}-2x^{11}+2x^{20}+x^{21}-x^{30})\sum_{j=0}^{\infty}\binom{j+2}{2}x^j\right)\\\\&\qquad\qquad\qquad\times \left([x^{(S+11)/2}](1-2x^{10}+x^{20})\sum_{j=0}^{\infty}(j+1)x^j\right)\\\\&\qquad +\left([x^{(S+11)/2}](x-x^{10}-2x^{11}+2x^{20}+x^{21}-x^{30})\sum_{j=0}^{\infty}\binom{j+2}{2}x^j\right)\\\\&\qquad\qquad\qquad\times \left([x^{(S-11)/2}](1-2x^{10}+x^{20})\sum_{j=0}^{\infty}(j+1)x^j\right)\end{align}$$

So, if $S=43$, then the number we want is $$\begin{align}&\left(\binom{17}{2}-\binom 82-2\binom 72\right)\times (28-2\times 18+8)\\\\&\qquad +\left(\binom{28}{2}-\binom{19}{2}-2\binom{18}{2}+2\binom 92+\binom 82\right)\times (17-2\times 7)=3\end{align}$$

  • If $S$ is even, then we want to find the number of $(x_1,x_2,x_3,x_4,x_5)$ where $0\le x_i\le 9\in\mathbb Z$ with $x_1\not=0$ such that $$\begin{cases} x_1+x_2+x_3+x_4+x_5=S \\ x_1-x_2+x_3-x_4+x_5=0\end{cases}\quad\text{or}\quad \begin{cases} x_1+x_2+x_3+x_4+x_5=S \\ x_1-x_2+x_3-x_4+x_5=22\end{cases},$$ i.e. $$\begin{cases}x_1+x_3+x_5=\frac{S}{2}\\ x_2+x_4=\frac{S}{2}\end{cases}\quad\text{or}\quad \begin{cases}x_1+x_3+x_5=\frac{S+22}{2}\\ x_2+x_4=\frac{S-22}{2}\end{cases}$$So, similarly as the case where $S$ is odd, the number we want is given by $$\begin{align}&\left([x^{S/2}](x-x^{10}-2x^{11}+2x^{20}+x^{21}-x^{30})\sum_{j=0}^{\infty}\binom{j+2}{2}x^j\right)\\\\&\qquad\qquad\qquad\times \left([x^{S/2}](1-2x^{10}+x^{20})\sum_{j=0}^{\infty}(j+1)x^j\right)\\\\&\qquad +\left([x^{(S+22)/2}](x-x^{10}-2x^{11}+2x^{20}+x^{21}-x^{30})\sum_{j=0}^{\infty}\binom{j+2}{2}x^j\right)\\\\&\qquad\qquad\qquad\times \left([x^{(S-22)/2}](1-2x^{10}+x^{20})\sum_{j=0}^{\infty}(j+1)x^j\right)\end{align}$$ So, if $S=36$, then the number we want is $$\begin{align}&\left(\binom{19}{2}-\binom{10}{2}-2\binom 92\right)\times(19-2\times 9)\\\\&\qquad +\left(\binom{30}{2}-\binom{21}{2}-2\binom{20}{2}+2\binom{11}{2}+\binom{10}{2}\right)\times 8=54\end{align}$$

Tags:

Combinatorics

Elementary Number Theory

Related

Number of $9-$digit numbers, all digits are different and nonzero and having no consecutive digits in consecutive positions Function is continuous if and only if preimages of elements of a subbase are open. A multiplication algorithm found in a book by Paul Erdős: how does it work? Is there an elementary proof that $y^2=8x^4+1$ has no integral solution for $x\ge2$? If $(f_n)\to0$ in $L^2$ and the derivatives converge in $L^2$, must the limit be 0? In what sense is the kernel of a group homomorphism a universal arrow in a comma category? Graph Theory proving planarity Number of Derangements of the word BOTTLE Determine if this series converges or diverges Showing that $m^2-n^2+1$ is a square What is predicate lifting? Proving $\int_0^\infty\frac{\sin(x)}x\ dx=\frac{\pi}2$. Why is this step correct?

Recent Posts