2025 AMC 12A Problem 23

Question

Call a positive integer fair if no digit is used more than once, it has no

0

s, and no digit is adjacent to two greater digits. For example,

196,

23,

and

12463

are fair, but

1546,

320,

and

34321

are not fair. How many fair positive integers are there?

511

2584

9841

17711

19682

A fair number has no interior digit smaller than both of its neighbors

Build a valid arrangement of a chosen digit set by placing digits largest-to-smallest, each at either end:

2^{n-1}

ways for

n

digits

The digits are distinct and drawn from

\{1, \ldots, 9\},

and “no digit adjacent to two greater digits” means no interior digit is smaller than both neighbors.

For a fixed set of

n

digits, build the arrangement by inserting digits from largest to smallest; each new (smaller) digit must go to one of the two ends, giving

2^{n-1}

valid arrangements.

Summing over all nonempty digit subsets,

\begin{gathered} \sum_{n=1}^{9}\binom{9}{n}2^{n-1} \\ = \frac{1}{2}\sum_{n=1}^{9}\binom{9}{n}2^{n} \\ = \frac{3^9 - 1}{2} = \frac{19682}{2} = 9841. \end{gathered}

Thus, the correct answer is C.

Problem 23 in other years