Lesson goal: Digit sums and divisibility by 11

Previous: Cryptarithmetic and divisibility | Home | Next: The integer geometric progression puzzle

In the 1970 MAA High School Mathematics Contest (Problem #31), contestants were asked:

If a number is selected at random from the set of all five-digit numbers in which the sum of the digits is equal to 43, what is the probability that this number will be divisible by 11?

Let's break down this puzzle using combinatorics and the famous alternating divisibility rule:
  1. Finding all five-digit numbers with digit sum 43: The maximum possible sum of five digits is $9 \times 5 = 45$ (for the number $99999$). To reach a sum of $43$, we must reduce the sum by exactly $45 - 43 = 2$. There are only two ways to do this:
    • Reduce one digit by 2: Use four 9s and one 7. The permutations of $\{9, 9, 9, 9, 7\}$ give $\frac{5!}{4!} = 5$ numbers ($79999, 97999, 99799, 99979, 99997$).
    • Reduce two digits by 1 each: Use three 9s and two 8s. The permutations of $\{9, 9, 9, 8, 8\}$ give $\frac{5!}{3!2!} = 10$ numbers.
    Together, there are exactly $5 + 10 = 15$ five-digit numbers whose digits sum to 43.

  2. The Alternating Divisibility Rule for 11: An integer is divisible by 11 if and only if the alternating sum of its digits $(d_1 - d_2 + d_3 - d_4 + d_5)$ is a multiple of 11:
    • For the $\{7, 9, 9, 9, 9\}$ family, putting the $7$ in an even slot (2nd or 4th position) gives $(9 + 9 + 9) - (7 + 9) = 27 - 16 = 11$, which is divisible by 11! This gives 2 numbers: $97999$ and $99979$.
    • For the $\{8, 8, 9, 9, 9\}$ family, putting both $8$s in even slots (2nd and 4th position) gives $(9 + 9 + 9) - (8 + 8) = 27 - 16 = 11$, giving 1 number: $98989$.
    Therefore, exactly $2 + 1 = 3$ of the 15 numbers are divisible by 11.
The probability is: $$P = \frac{3}{15} = \frac{1}{5} = 20\%$$ In this lesson, we write a program that loops through all 5-digit numbers, checks both conditions, and prints every matching number!
matching = 0
divisible_by_11 = 0
for n = 10000, 99999 do
if digit_sum(n) == 43 then
matching = matching + 1
-- Divisible by 11 test: Replace ???? with 11 if n % ???? == 0 then
divisible_by_11 = divisible_by_11 + 1
end
end
end
Move the mouse over a dotted box for more information.

The program finds all 15 valid numbers and identifies the exact 3 that are divisible by 11 ($97999$, $98989$, and $99979$), proving the probability is $3/15 = 1/5$.

Now you try. Run the code above to verify the 15 numbers. Then try changing 43 to 44 to see how many 5-digit numbers have digit sum 44 and what fraction is divisible by 11!

Type your code here:


See your results here: