2021 AMC 10B Problem 16

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

Solution

If a number is divisible by

15,

it has a units digit of

0

5.

If the units digit is

0

and the digits are strictly increasing, then the number is

0,

which isn’t positive. Therefore, we can just look at numbers with a units digit of

5.

Next, we need to find uphill integers that are a multiple of

3.

This means the other digits are a subset of

\{1,2,3,4\}.

Taking the sum of the set must have a remainder of

1

when divided by

3.

Also, having or taking out

3

wouldn’t affect the remainder, so we can take the number of subsets without a

3

and multiply it by

2.

There are only

3

such subsets, namely

\{1\}, \{4\},

and

\{1,2,4\}.

Thus, there are

6

total subsets. Thus, the correct answer is C .