2025 AMC 10A Problem 24

P21-25~10 minPrint

Basic Counting Arrangements with Restrictions Apply an identity: SFFT, sum of squares, difference of cubes, Vieta Map the objects to something easier to count

Call a positive integer fair if no digit is used more than once, it has no 0s, 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 without answering

Key insight

A fair number's digits climb to the largest digit, then fall. Once the digits are chosen, every digit except the largest just picks the left or right side.

Solution

Step 1: understand the rule.

A fair number uses digits from $1$ to $9$ , each at most once. The third rule says no digit may sit in a "valley", with a bigger digit on both sides. A digit at either end has only one neighbour, so an end digit is never a problem.

2. Try a small case to see the pattern. With the digits $1, 2, 3$ there are six orders:
- $123$ , $132$ , $231$ , $321$ are fair;
- $213$ and $312$ are not, because the $1$ sits between two bigger digits.

In every fair one, the digits climb up to $3$ (the largest) and then go down.

Step 2: fair means "up, then down".

If the digits climb to the largest digit and then fall, there is no valley. Every digit before the top has a smaller digit on its left, every digit after the top has a smaller digit on its right, and the top digit is bigger than both of its neighbours.

If the digits ever go down and then later go up again, there is a valley. Follow the digits from where they start going down to where they first turn back up. The digit at that turning point has a bigger digit on its left (the digits were going down) and a bigger digit on its right (they go up again). For example, in $1546$ the digits go down from $5$ to $4$ and then up to $6$ , and $4$ is the valley.

So a number is fair exactly when its digits climb to the largest digit and then fall.

Step 3: count the orders of a fixed set of digits.

Pick a set of $k$ different digits. The largest one has to sit at the top. Each of the other $k - 1$ digits goes either on the left (climbing) side or on the right (falling) side.
Once each digit has picked its side, the order is forced: the left side must be in increasing order and the right side in decreasing order.
Each of the $k - 1$ digits has $2$ choices, so a set of $k$ digits gives $2^{k-1}$ fair numbers. Check with $\{1, 2, 3\}$ : $2^2 = 4$ , matching the four fair numbers above.

Step 4: add up over all digit sets.

The number of ways to choose $k$ digits out of $9$ is $\binom{9}{k}$ . Multiply by $2^{k-1}$ and add:

$k$	ways to choose the digits	orders	fair numbers
1	$9$	$1$	$9$
2	$36$	$2$	$72$
3	$84$	$4$	$336$
4	$126$	$8$	$1008$
5	$126$	$16$	$2016$
6	$84$	$32$	$2688$
7	$36$	$64$	$2304$
8	$9$	$128$	$1152$
9	$1$	$256$	$256$

The total is $9 + 72 + 336 + 1008 + 2016 + 2688 + 2304 + 1152 + 256 = 9841$ .

(Quick check on the $k = 2$ row: every two-digit number with two different nonzero digits is fair, and there are $9 \times 8 = 72$ of them.)

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

Why this works

A rule about neighbours ("no valleys") often turns out to be a rule about the overall shape ("up, then down"). Once you see the shape, counting splits into two easy steps: choose which digits to use, then count the ways to arrange them. The largest digit has no choice about where it goes, and that is why each set gives $2^{k-1}$ and not $2^k$ .

Alternative approach

Here is a way to count everything at once. Give each digit $1$ to $9$ one of three labels: not used, left, or right. That is $3^9 = 19683$ ways to label.

Every labelling except "all not used" builds a fair number: write the left digits in increasing order, then the right digits in decreasing order.
Each fair number gets built exactly twice, because its largest digit can be labelled left or right and the number comes out the same.

So $19683 = 2 \times (\text{number of fair numbers}) + 1$ , and the number of fair numbers is $\dfrac{19683 - 1}{2} = 9841$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Algebra, Chapter 11: Special Factorizations