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$

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, $\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.$

Thus, the correct answer is C.

2025 AMC 12A Problem 23

Solution:

Problem 23 in Other Years