2021 AMC 10B Problem 16

P16-20~4 minPrint

Divisibility & Factors Bases & Digits Basic Counting Organized listing / direct enumeration

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

Show solution without answering

Key insight

Uphill numbers cannot end in 0, so a multiple of 5 ends in 5. Then choose digits from 1 to 4 so the digit sum is a multiple of 3.

Solution

A number is divisible by $15$ exactly when it is divisible by both $5$ and $3$ . Handle $5$ first, because it pins down the last digit.

Step 1: divisible by 5.

The last digit must be $0$ or $5$ .
In an uphill number the last digit is the biggest digit. A $0$ can never be the biggest, so the last digit is $5$ .
Every other digit is smaller than $5$ , and $0$ cannot come first, so the other digits come from $1, 2, 3, 4$ . Once you choose which of those digits to use, there is only one uphill order for them. So an uphill number ending in $5$ is just "a choice of some of the digits $1, 2, 3, 4$ , then a $5$ ."

Step 2: divisible by 3.

The digit sum must be a multiple of $3$ . The $5$ already adds $5$ , so the chosen digits must add up to $1$ , $4$ , $7$ or $10$ (then the total is $6$ , $9$ , $12$ or $15$ ). The largest possible sum is $1 + 2 + 3 + 4 = 10$ , so we can stop there.
List the choices:

chosen digits add to	choices	numbers
$1$	$1$	$15$
$4$	$4$ ; $\ 1, 3$	$45$ , $135$
$7$	$3, 4$ ; $\ 1, 2, 4$	$345$ , $1245$
$10$	$1, 2, 3, 4$	$12345$

(Choosing no extra digits gives just $5$ , whose digit sum $5$ is not a multiple of $3$ .)
That is $6$ numbers: $15, 45, 135, 345, 1245, 12345$ .

The answer is $\boxed{\textbf{(C)}\ 6}$ .

Why this works

Because the digits must go up, an uphill number is decided entirely by which digits it uses. So counting uphill numbers is really counting choices of digits. The divisibility rules for $5$ and $3$ then become simple rules about those digits: the largest is $5$ , and the sum is a multiple of $3$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Divisible by $15$ means divisible by $5$ and by $3$ .

Divisible by 5. The last digit is $0$ or $5$ . In an uphill integer the last digit is the largest digit, so it cannot be $0$ . Hence the number ends in $5$ , and its earlier digits form an increasing string chosen from $\{1, 2, 3, 4\}$ (a leading $0$ is not allowed).

Divisible by 3. The digit sum must be a multiple of $3$ . The chosen subset of $\{1,2,3,4\}$ must have sum $\equiv 1 \pmod 3$ (since $5 \equiv 2$ ). Listing subsets by sum:

sum $1$ : $\{1\}$ , sum $4$ : $\{4\}, \{1,3\}$ , sum $7$ : $\{3,4\}, \{1,2,4\}$ , sum $10$ : $\{1,2,3,4\}$ .

Those six subsets give the numbers $15, 45, 135, 345, 1245, 12345$ , all multiples of $15$ . (The empty subset gives $5$ , not divisible by $3$ .)

The answer is $\boxed{\textbf{(C)}\ 6}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 8: Base Numbers
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)