2017 AMC 12B Problem 11

Problem 11 of 25IntermediateCombinatorics

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?

Show solution

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.

AoPS wiki

Tagged: subsets · bijection · inclusion-exclusion

Answer choices

Solution

More practice