AMC 10 · 2021 · #16

Grade 4 number-theory

Archetype Small-Domain Constrained Search

digit-constraintsdivisibility-rulesdigit-sumsystematic-enumeration systematic-enumerationcasework ↑ Prerequisites: divisibility-rulesdigit-sum

📏 Medium solution 💡 3 insights

📘 View easy version →

Problem

Call a positive integer an uphill integer if every digit is strictly greater than the previous digit. For example, $1357, 89,$ and $5$ are all uphill integers, but $32, 1240,$ and $466$ are not. How many uphill integers are divisible by $15$ ?

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

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$.

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

#9 Solve an Easier Related Problem 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$.

$15 = 3 \times 5,\ \gcd(3,5)=1$; last digit $= 5$

💡 Split the hard rule "divisible by $15$" into two simpler rules, then use the easier one ($\div 5$) to lock the last digit.

#2 Make a Systematic List 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).

Choose a subset $T \subseteq \{1,2,3,4\}$; the integer is the digits of $T$ in order, then $5$

💡 Pick the digits going up to $5$ — order is forced by "uphill", so just pick the set.

#5 Look for a Pattern 4.OA.B.4 Step 3

Size $0$ (just "$5$"): digit sum $= 5$.
Not a multiple of $3$.
Skip.

$$5 \to 5\not\equiv 0\pmod{3}$$

💡 $5$ alone is divisible by $5$ but not by $3$, so not by $15$.

#2 Make a Systematic List 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.

$$15{:}\,1{+}5{=}6\checkmark,\ 25{:}\,7,\ 35{:}\,8,\ 45{:}\,4{+}5{=}9\checkmark$$

💡 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.

#2 Make a Systematic List 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.

$135{:}\,9\checkmark,\ 345{:}\,12\checkmark$ (others fail $\div 3$)

💡 List all pairs from $\{1,2,3,4\}$ in order, append $5$, check digit sums.

#2 Make a Systematic List 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.

$$1245{:}\,1{+}2{+}4{+}5{=}12\checkmark$$

💡 Same drill: list, sum digits, check $\div 3$.

#2 Make a Systematic List 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$.

$12345{:}\,15\checkmark$; total $=2+2+1+1=\textbf{6}\;\Rightarrow\;(C)$

💡 Add up the counts from each size — six uphill multiples of $15$ in all.

[1] #9 4.OA.B.4 Use the divisibility-by-$15$ split. $15 = 3 \times 5$ and $\gcd(3, 5) = 1$, so a

[2] #2 4.OA.B.4 Since the digits strictly increase and end in $5$, every other digit must come f

[3] #5 4.OA.B.4 Size $0$ (just "$5$"): digit sum $= 5$. Not a multiple of $3$. Skip.

[4] #2 4.OA.B.4 Size $1$ (one extra digit before $5$): try $15, 25, 35, 45$. Sums: $6, 7, 8, 9$.

[5] #2 4.OA.B.4 Size $2$ (two extra digits, picked from $\{1,2,3,4\}$): the $C(4, 2) = 6$ subset

[6] #2 4.OA.B.4 Size $3$ (three extra digits): the $C(4, 3) = 4$ subsets give $1235, 1245, 1345,

[7] #2 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.4 Find 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$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 4)

More like this