2017 AMC 10B Problem 17

P16-20~5 minPrint

Basic Counting Bases & Digits Map the objects to something easier to count Split into exhaustive cases and handle each

Call a positive integer $\textbf{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 without answering

Key insight

Choosing a set of different digits gives exactly one increasing number and one decreasing number. Count digit sets: 511 increasing, 1022 decreasing, minus the 9 one-digit numbers counted twice.

Solution

Start with an example. The digit set $\{2, 3, 5, 7, 8\}$ gives exactly one increasing number, $23578$ , and exactly one decreasing number, $87532$ . The digits of a monotonous number are all different, and once you know which digits are used, the order is forced. So count sets of digits instead of numbers.

Increasing numbers. The digit $0$ cannot be used: in an increasing number it would have to come first. So the digits come from $1$ to $9$ . Each of these $9$ digits is either in or out, giving $2^9 = 512$ sets, and we throw away the empty set: $511$ numbers.
Decreasing numbers. Now $0$ is allowed, because it goes last (as in $987620$ ). The digits come from $0$ to $9$ : $2^{10} = 1024$ sets. Throw away the empty set, and also the set $\{0\}$ alone, which would give the number $0$ , not a positive integer. That leaves $1022$ numbers.
Counted twice. The one-digit numbers $1$ to $9$ appear in both lists. A number with two or more digits cannot be both increasing and decreasing, so nothing else is repeated. That is $9$ repeats.
Total: $511 + 1022 - 9 = 1524$ .

The answer is $\boxed{\textbf{(B)}\ 1524}$ .

Why this works

When the order of the objects is forced (smallest to largest, or largest to smallest), counting arrangements is the same as counting which objects are chosen, and "in or out" for each digit gives powers of $2$ . The only care needed is at the edges: where the digit $0$ may go, and which numbers belong to both lists.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

A strictly increasing or strictly decreasing number is determined by its set of digits: sort the set one way or the other. So count digit sets.

Increasing numbers: the digits are distinct and $0$ cannot appear (it would have to come first). Any nonempty subset of $\{1, \dots, 9\}$ works: $2^9 - 1 = 511$ numbers.

Decreasing numbers: any nonempty subset of $\{0, 1, \dots, 9\}$ , written largest to smallest, gives a valid positive integer, except the subset $\{0\}$ alone. That is $2^{10} - 1 - 1 = 1022$ numbers.

Overlap: the one-digit numbers $1$ through $9$ appear in both lists ( $9$ numbers). Nothing else does, since a number with two or more digits cannot be both increasing and decreasing.

Total: $511 + 1022 - 9 = 1524$ .

The answer is $\boxed{\textbf{(B)}\ 1524}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Number Theory, Chapter 8: Base Numbers
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)