2023 AMC 10B Problem 16

Problem 16 of 25IntermediateNumber Theory Combinatorics

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

Solution

An upno is just a choice of at least

2

digits, written in increasing order. A

0

can never appear: it can’t lead and can’t follow a smaller digit. So the digits come from

\{1, \ldots, 9\},

giving

U = 2^9 - 1 - 9 = 502.

A downno can end in

0,

so its digits are any subset of

\{0, \ldots, 9\}

of size

\ge 2,

giving

D = 2^{10} - 1 - 10 = 1013.

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

Therefore, the answer is E.

Tagged: subsets · digits