2021 AMC 10B Problem 16

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

Strictly increasing digits means the number is determined by its set of digits, so counting uphill integers is counting subsets. Divisibility rules then become conditions on the set: the largest element is $5$, and the sum is a multiple of $3$. Convert digit conditions into set conditions and enumerate.

• Allowing numbers ending in 0 (such as 120 or 1230), which are not uphill since 0 is less than the previous digit.
• Checking divisibility by $3$ only for two-digit candidates and missing $1245$ or $12345$.