AMC 10 · 2021 · #16
Easy mode Grade 4Problem
Call a positive integer an uphill integer if every digit is bigger than the digit just before it. Each next digit must go up.
For example, 1357, 89, and 5 are all uphill integers. But 32, 1240, and 466 are not (their digits don't keep going up).
How many uphill integers are divisible by 15?
Pick an answer.
AMC 10 2021 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: An "uphill integer" is a positive integer whose digits strictly increase from left to right (like $1357$ or $89$). Count how many uphill integers are divisible by $15$.
Givens: An uphill integer has strictly increasing digits left to right; Examples: $1357, 89, 5$ are uphill; $32, 1240, 466$ are not; We want those divisible by $15$; Choices: (A) $4$, (B) $5$, (C) $6$, (D) $7$, (E) $8$
Unknowns: How many uphill integers are divisible by $15$
Understand
Restated: An "uphill integer" is a positive integer whose digits strictly increase from left to right (like $1357$ or $89$). Count how many uphill integers are divisible by $15$.
Givens: An uphill integer has strictly increasing digits left to right; Examples: $1357, 89, 5$ are uphill; $32, 1240, 466$ are not; We want those divisible by $15$; Choices: (A) $4$, (B) $5$, (C) $6$, (D) $7$, (E) $8$
Plan
Primary tool: #2 Make a Systematic List
Secondary: #9 Solve an Easier Related Problem, #5 Look for a Pattern
Tool #9 (Easier Problem) — first cut the candidate pool by using the divisibility rules. "Divisible by $5$" forces the last digit to be $0$ or $5$, but $0$ as the last digit of an uphill integer would require negative previous digits — impossible. So the last digit must be $5$, and every other digit comes from $\{1, 2, 3, 4\}$. That shrinks the universe from "all uphill integers" to "subsets of $\{1, 2, 3, 4\}$ followed by $5$." Tool #2 (Systematic List) then enumerates every such subset in order of size (empty, singletons, pairs, triples, the full set) and Tool #5 (Pattern — divisibility-by-$3$ rule) filters: keep only the ones whose digit sum is a multiple of $3$. Count what survives.
Execute — Answer: C
4.OA.B.4 Step 1 - Use the divisibility-by-$15$ split.
- $15 = 3 \times 5$ and $\gcd(3, 5) = 1$, so a number is divisible by $15$ exactly when it is divisible by both $3$ and $5$.
- Divisible by $5$ means the last digit is $0$ or $5$.
- An uphill integer ends in $0$ would need every earlier digit to be less than $0$ — impossible.
- So the last digit must be $5$.
💡 Split the hard rule "divisible by $15$" into two simpler rules, then use the easier one ($\div 5$) to lock the last digit.
4.OA.B.4 Step 2 - Since the digits strictly increase and end in $5$, every other digit must come from $\{1, 2, 3, 4\}$ and appear in increasing order.
- So the question becomes: how many subsets of $\{1, 2, 3, 4\}$ (used in order, then followed by $5$) give a digit sum that is a multiple of $3$?
- Pick an ordering rule: enumerate by subset size (length).
💡 Pick the digits going up to $5$ — order is forced by "uphill", so just pick the set.
4.OA.B.4 Step 3 - Size $0$ (just "$5$"): digit sum $= 5$.
- Not a multiple of $3$.
- Skip.
💡 $5$ alone is divisible by $5$ but not by $3$, so not by $15$.
4.OA.B.4 Step 4 - Size $1$ (one extra digit before $5$): try $15, 25, 35, 45$.
- Sums: $6, 7, 8, 9$.
- Multiples of $3$: $6$ and $9$.
- So $\textbf{15}$ and $\textbf{45}$ work — $2$ found.
💡 Sum of digits is $3$ + (extra digit), so the extra digit must be a multiple of $3$ — namely $1$ won't work, but $1$ gives sum $6$ — wait, just check directly: $1$ and $4$ work.
4.OA.B.4 Step 5 - Size $2$ (two extra digits, picked from $\{1,2,3,4\}$): the $C(4, 2) = 6$ subsets give integers $125, 135, 145, 235, 245, 345$.
- Digit sums: $8, 9, 10, 10, 11, 12$.
- Multiples of $3$: $9$ and $12$.
- So $\textbf{135}$ and $\textbf{345}$ work — $2$ found.
💡 List all pairs from $\{1,2,3,4\}$ in order, append $5$, check digit sums.
4.OA.B.4 Step 6 - Size $3$ (three extra digits): the $C(4, 3) = 4$ subsets give $1235, 1245, 1345, 2345$.
- Digit sums: $11, 12, 13, 14$.
- Only $12$ is a multiple of $3$, so only $\textbf{1245}$ works — $1$ found.
💡 Same drill: list, sum digits, check $\div 3$.
4.OA.B.4 Step 7 - Size $4$ (all of $\{1, 2, 3, 4\}$): just $\textbf{12345}$.
- Digit sum $= 1+2+3+4+5 = 15$, divisible by $3$.
- Works — $1$ found.
- Size $\ge 5$ is impossible: there are only $4$ digits available before $5$.
- Total count: $2 + 2 + 1 + 1 = 6$.
- So the answer is $(C)\ 6$.
💡 Add up the counts from each size — six uphill multiples of $15$ in all.
4.OA.B.4 Use the divisibility-by-$15$ split. $15 = 3 \times 5$ and $\gcd(3, 5) = 1$, so a 4.OA.B.4 Since the digits strictly increase and end in $5$, every other digit must come f 4.OA.B.4 Size $0$ (just "$5$"): digit sum $= 5$. Not a multiple of $3$. Skip. 4.OA.B.4 Size $1$ (one extra digit before $5$): try $15, 25, 35, 45$. Sums: $6, 7, 8, 9$. 4.OA.B.4 Size $2$ (two extra digits, picked from $\{1,2,3,4\}$): the $C(4, 2) = 6$ subset 4.OA.B.4 Size $3$ (three extra digits): the $C(4, 3) = 4$ subsets give $1235, 1245, 1345, 4.OA.B.4 Size $4$ (all of $\{1, 2, 3, 4\}$): just $\textbf{12345}$. Digit sum $= 1+2+3+4+ Review
Reasonableness: Sanity check: the list $15, 45, 135, 345, 1245, 12345$ all visibly end in $5$ (so divisible by $5$) and all have digit sums $6, 9, 9, 12, 12, 15$ which are multiples of $3$ — so they really are multiples of $15$. We never missed a case because the total number of subsets of $\{1,2,3,4\}$ is $2^4 = 16$, and we checked each subset's digit-sum mod $3$. Six surviving subsets matches choice (C).
Alternative: Tool #5 (Pattern) — looking at the size-$1$ pairs, the extra digit needs digit-sum $\equiv 1 \pmod 3$ (since $5 \equiv 2$). For size-$2$, the two extras need sum $\equiv 1\pmod 3$. This mod-$3$ classification can be done by hand on the digits $\{1,2,3,4\}$ which break into residue classes $\{3\}, \{1, 4\}, \{2\}$ — a tidier counting argument that recovers the same $6$.
CCSS standards used (min grade 4)
4.OA.B.4Find all factor pairs and recognize multiples; determine prime or composite (Splitting "divisible by $15$" into "divisible by $3$ AND divisible by $5$" via prime factors $15 = 3 \times 5$, and applying the digit-sum rule for $3$ and the last-digit rule for $5$ to each candidate.)
⭐ This AMC 10 problem only needs Grade 4 divisibility rules and a careful list you already know! Divisible by $15$ means divisible by $3$ AND divisible by $5$, so the last digit is $5$, the other digits come from $\{1,2,3,4\}$, and the digit sum must be a multiple of $3$. Listing every subset of $\{1,2,3,4\}$ gives exactly $6$ uphill multiples of $15$.
⭐ This AMC 10 problem only needs Grade 4 divisibility rules and a careful list you already know! Divisible by $15$ means divisible by $3$ AND divisible by $5$, so the last digit is $5$, the other digits come from $\{1,2,3,4\}$, and the digit sum must be a multiple of $3$. Listing every subset of $\{1,2,3,4\}$ gives exactly $6$ uphill multiples of $15$.
More like this
Same archetype — closest grade level first.