2025 AMC 10A Problem 24

The first two conditions say the digits form a sequence of distinct elements of $\{1,2,\ldots,9\}$, so a fair number uses a subset of size $k$ for some $1 \le k \le 9$, and no leading-zero worry arises. The third condition says no interior digit has both of its neighbours larger — that is, no interior digit is a local minimum. (End digits have only one neighbour, so they are never at fault.)

Step 1: the shape of a fair number. A string of distinct digits has no interior local minimum exactly when it increases up to its largest digit and then decreases.

One direction is immediate: in a string $a_1 < a_2 < \cdots < a_p > a_{p+1} > \cdots > a_k$, every digit before the peak has a smaller digit on its left, every digit after the peak has a smaller digit on its right, and the peak is larger than both neighbours, so nothing is a local minimum.

Conversely, suppose the string is not of that shape. Then somewhere it goes down and later comes back up: there is a descent $a_i > a_{i+1}$ followed by an ascent $a_j < a_{j+1}$ with $j \ge i+1$. Take the first ascent after that descent; then $a_{i+1} > a_{i+2} > \cdots > a_j$, so $a_{j-1} > a_j$ while $a_{j+1} > a_j$, and position $j$ is an interior local minimum. So the number is not fair.

Step 2: count the orderings of a fixed digit set. Fix a set of $k$ digits. Its largest element must sit at the peak. Each of the other $k-1$ digits is assigned to the increasing run (left of the peak) or the decreasing run (right of the peak); once the sides are chosen, the order within each run is forced, since the left run must be increasing and the right run decreasing. Different side-assignments give different strings, so there are exactly
$$2^{\,k-1}$$
fair numbers using that digit set. Sanity check with $k=3$ and digits $\{1,2,3\}$: the four strings are $123$, $132$, $231$, $321$, while $213$ and $312$ both have the $1$ trapped between two larger digits.

Step 3: sum over all digit sets.
$$\sum_{k=1}^{9}\binom{9}{k} 2^{\,k-1} = \frac12 \sum_{k=1}^{9}\binom{9}{k} 2^{k} = \frac12\left(\sum_{k=0}^{9}\binom{9}{k}2^k \cdot 1^{\,9-k} - 1\right) = \frac{3^9 - 1}{2} = \frac{19683 - 1}{2} = 9841.$$

(Quick checks: $k=1$ gives $9$ one-digit numbers, and $k=2$ gives $\binom92 \cdot 2 = 72$, which is every two-digit number with distinct nonzero digits, as it should be — no two-digit number can fail the adjacency rule.)

The answer is $\boxed{\textbf{(C)}\ 9841}$.

A local condition on neighbours ("nothing sits in a valley") is almost always secretly a global shape condition, and identifying that shape is what turns an intractable adjacency constraint into a clean choice for each element. Once the shape is "up then down", counting splits in the standard way: choose which digits appear, then count the arrangements of that fixed set, and the second count depends only on $k$. The factor $2^{k-1}$ rather than $2^k$ is the whole difficulty of the problem — the maximum has no choice of side — and it is exactly what separates the correct $9841$ from the decoy $19682$.

Count in one stroke by labelling. Give each of the digits $1$ through $9$ one of three labels: unused, left (on the ascending run), or right (on the descending run). That is $3^9$ labellings. Every labelling except the all-unused one determines a string — read the left-labelled digits in increasing order, then the right-labelled ones in decreasing order — and each fair number arises exactly twice, because its largest digit can be labelled left or right without changing the string. Hence
$$3^9 = 2 \cdot (\text{number of fair numbers}) + 1,$$
which again gives $\frac{3^9-1}{2} = 9841$.

• Summing binom(9,k) 2^k instead of binom(9,k) 2^(k-1), which gives 3^9 - 1 = 19682, choice (E); the factor 2^(k-1) is right because the largest digit's position is forced.
• Treating the first or last digit as capable of being "adjacent to two greater digits"; an end digit has only one neighbour, so $196$ and $23$ are fair even though their smallest digit is at an end.
• Forgetting that the number of digits ranges over all of $1$ through $9$, and counting only nine-digit numbers ($2^8 = 256$) or only the subsets ($2^9 - 1 = 511$, choice (A)).