2021 AMC 10B Problem 16

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.

1. The last digit must be $0$ or $5$.
2. In an uphill number the last digit is the biggest digit. A $0$ can never be the biggest, so the last digit is $5$.
3. 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.

1. 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.
2. List the choices:

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

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

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

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