9
$\begingroup$

Problem Statement:-

Consider the collection of all $5$-digit numbers such that the sum of digits of each number is $43$. A number is selected at random from the collection. Find the probability that the number is divisible by $11$.

My Solution:-

Let the five-digit numbers be represented by $x_1x_2x_3x_4x_5$.

As the digits of these numbers should add up to $43$, we have

$$x_1+x_2+x_3+x_4+x_5=43\tag{where $1\le x_i\le9$, $x_i\in\mathbb{N}$}$$

So, the number of such numbers is equal to the coefficient of $x^{43}$ in $\left(\dfrac{1-x^{10}}{1-x}\right)^5=15$

As this is a listable amount of numbers so lets just list them

$$99997\\ 99979\\ 99799\\ 97999\\ 79999\\ 99988\\ 99889\\ 98899\\ 88999\\ 99898\\ 98989\\ 89899\\ 98998\\ 89989\\ 89998$$

Its easy to spot the numbers divisible by 11 which are $97999,\; 99979,\; 98989$

So, the required probability comes out to be $\dfrac{3}{15}=\dfrac{1}{5}$


The number of numbers in this list turned out to be small hence just listing them turned out to be good enough for finding the numbers divisible by $11$, but 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.

$\endgroup$
2
$\begingroup$

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}$$
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I do know about the divisibility rule of 11 and that is how I was quickly able to determine the numbers that were divisible by 11 in the list. Can you show how to find the number of numbers divisible by 11 if 36 was to be the sum of the digits. $\endgroup$ – user350331 Mar 17 '17 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.