2025 AMC 10B Problem 22
A seven-digit positive integer is chosen at random. What is the probability that the number is divisible by , given that the sum of its digits is
Show solution without answering
Key insight
A digit sum of 61 is 2 short of seven 9s, leaving only 28 numbers. The test for 11 passes only when the whole shortfall is in even places.
Solution
Step 1: list the possible numbers. Seven 9s add to . A digit sum of is less, so the digits are all 9s except for a total "shortfall" of . That happens in two ways:
- one digit is and the rest are : the can be in any of places, so numbers;
- two digits are and the rest are : choose of the places, numbers.
That is numbers, all equally likely. (None starts with , since every digit is at least .)
Step 2: the test for 11. Number the places to from the left. A number is a multiple of exactly when
is a multiple of (this can be or negative too).
Step 3: start from 9999999. For all 9s, this difference is .
- Lowering a digit in an odd place (1, 3, 5, 7) makes the difference smaller by that amount.
- Lowering a digit in an even place (2, 4, 6) makes the difference bigger by that amount.
The total lowering is , so the difference is somewhere from to . The only multiple of in that range is . So we need the difference to be exactly , which means all of the shortfall must be in even places.
Step 4: count the good numbers.
- One : it must be in place , or . That gives numbers.
- Two s: both must be in even places, ways. That gives numbers.
So of the numbers work, and the probability is
The answer is .
Why this works
A digit sum close to the largest possible value leaves very few numbers, so thinking of "how far short of all 9s" makes the list tiny. The test for adds and subtracts digits, so instead of testing numbers one by one, start from and track how each lowered digit changes the result. The range to leaves only one possible multiple of , which settles everything.
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
The sample space. Seven digits sum to at most , so a digit sum of means the digits are all except for a total shortfall of . There are exactly two ways to distribute that shortfall:
- one digit is and the other six are : numbers, one for each position;
- two digits are and the other five are : numbers.
Every digit is at least , so the leading digit is never and all strings are genuine seven-digit numbers. The condition leaves equally likely numbers.
The divisibility test. A number is divisible by exactly when its alternating digit sum
is a multiple of . Four positions () carry a plus sign and three () carry a minus sign, so if every digit were then
Lowering a digit in a plus position decreases by the same amount; lowering one in a minus position increases . The total shortfall is , so
and the only multiple of in that range is . So , which happens exactly when the whole shortfall of sits in minus (even) positions.
Counting.
- One . It must occupy one of the three even positions: numbers.
- Two s. Both must occupy even positions: numbers.
That is numbers out of , so the probability is
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques (§8.5)
- Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.