Skip to main content

2017 AMC 10B Problem 17

Problem 17 of 25IntermediateNumber TheoryCombinatorics

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,3, 23578,23578, and 987620987620 are monotonous, but 88,88, 7434,7434, and 2355723557 are not. How many monotonous positive integers are there?

Answer choices

Show solution

Solution

The strictly increasing positive integers correspond to the nonempty subsets of {1,2,3,4,5,6,7,8,9}\{1,2,3,4,5,6,7,8,9\}, written in increasing order. There are 29−1=5112^9-1=511 of these. The strictly decreasing positive integers correspond to subsets of {0,1,2,3,4,5,6,7,8,9}\{0,1,2,3,4,5,6,7,8,9\}, written in decreasing order, except for the empty set and {0}\{0\}. There are 210−2=10222^{10}-2=1022 of these. The one-digit numbers 11 through 99 were counted in both groups, so the total is 511+1022−9=1524511+1022-9=1524. Thus, B is the correct answer.
AoPS wiki

Tagged: subsets · digits · bijection

More practice