2023 AMC 10B Problem 16

P16-20~4 minPrint

Basic Counting Bases & Digits Map the objects to something easier to count Count the complement and subtract from the total

Define an $upno$ to be a positive integer of $2$ or more digits where the digits are strictly increasing moving left to right. Similarly, define a $downno$ to be a positive integer of $2$ or more digits where the digits are strictly decreasing moving left to right. For instance, the number $258$ is an upno and $8620$ is a downno. Let $U$ equal the total number of $upnos$ and let $D$ equal the total number of $downnos$ . What is $|U-D|$ ?

Show solution without answering

Key insight

Picking the digits decides the number, so count sets of digits. The digit 0 can end a downno but can never start an upno.

Solution

Choosing the digits decides the number. For example, the digits $\{2, 5, 8\}$ give exactly one upno, $258$ , and exactly one downno, $852$ . So instead of counting numbers, count sets of digits.

1. How many sets can you pick from some digits? For each digit you either take it or leave it, two choices. From $9$ digits there are $2^9 = 512$ possible sets; from $10$ digits there are $2^{10} = 1024$ . (These include the empty set and the one-digit sets.)
2. Upnos. The digit $0$ can never be used: in increasing order it would come first, and a number cannot start with $0$ . So the digits come from $1, 2, \ldots, 9$ . Out of the $512$ sets, remove the empty set and the $9$ single-digit sets, since an upno needs at least $2$ digits:
$U = 512 - 1 - 9 = 502.$
3. Downnos. Now $0$ is fine, because in decreasing order it comes last (like $8620$ ). So the digits come from $0, 1, \ldots, 9$ . Out of the $1024$ sets, remove the empty set and the $10$ single-digit sets:
$D = 1024 - 1 - 10 = 1013.$
4. Subtract.
$|U - D| = 1013 - 502 = 511.$

The answer is $\boxed{\textbf{(E)}\ 511}$ .

Why this works

When the order of the digits is forced (increasing or decreasing), each number matches exactly one set of digits, and sets are easy to count with powers of $2$ . The whole difference between $U$ and $D$ comes from the digit $0$ , which can sit at the end of a number but never at the start.

Alternative approach

Match upnos with downnos directly.

Reverse any upno and you get a downno without a $0$ . For example, $258$ becomes $852$ . Every downno without a $0$ comes from exactly one upno this way. So those cancel out in $U - D$ .
The downnos left over are the ones that end in $0$ . Such a number is some digits from $1$ to $9$ written in decreasing order, followed by $0$ .
The digits before the $0$ can be any set from $1$ to $9$ except the empty set (the number needs at least $2$ digits, and one of them is the $0$ ). That is $2^9 - 1 = 511$ choices.

So $D$ is $511$ more than $U$ .

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 decreasing) number is determined by its set of digits: once the digits are chosen, there is exactly one way to arrange them in increasing order and one way in decreasing order. So counting upnos and downnos is counting sets of digits.

Upnos: the digit $0$ cannot appear, because in increasing order it would be the leading digit. So an upno is a subset of $\{1, 2, \dots, 9\}$ with at least $2$ elements:
$U = 2^9 - 1 - 9 = 502.$

Downnos: $0$ may appear, since in decreasing order it lands at the end (like $8620$ ). A downno is a subset of $\{0, 1, \dots, 9\}$ with at least $2$ elements:
$D = 2^{10} - 1 - 10 = 1013.$

Therefore $|U - D| = 1013 - 502 = 511$ .

The answer is $\boxed{\textbf{(E)}\ 511}$ .

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.3)