2025 AMC 12A Problem 23

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?

Show solution

Solution

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.