2017 AMC 12B Problem 11

Question

Call a positive integer monotonous if it is a one-digit number or its digits, when read from left to right, form either a strictly increasing or a strictly decreasing sequence. For example,

3,

23578,

and

987620

are monotonous, but

88,

7434,

and

23557

are not. How many monotonous positive integers are there?

1024

1524

1533

1536

2048

Answer: B

Concepts:subsets bijection inclusion-exclusion

Difficulty rating: 1590

Small hint:

Each nonempty subset of

\{1, 2, \ldots, 9\}

gives exactly one strictly increasing number

Big hint:

Decreasing numbers correspond to subsets of

\{0, 1, \ldots, 9\}

except

\varnothing

and

\{0\};

single digits are counted twice

Solution:

Strictly increasing monotonous numbers correspond to nonempty subsets of

\{1, \ldots, 9\},

giving

2^9 - 1 = 511.

Strictly decreasing ones correspond to subsets of

\{0, 1, \ldots, 9\}

other than

\varnothing

and

\{0\}

(a leading

0

is not allowed), giving

2^{10} - 2 = 1022.

The nine single-digit numbers are counted in both, so the total is

511 + 1022 - 9 = 1524.

Thus, the correct answer is B.