2025 AMC 10A Problem 24

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,

23,

196,

and

12463

are fair, but

1546,

320,

and

34321

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

Show solution

Solution

A fair number’s digits must increase up to its largest digit

m

and then decrease. Indeed, the first ascent after any descent would begin at a digit smaller than both of its neighbors. For

k

digits, choose the digit set from

1

9

\binom{9}{k}

ways. Each of the

k-1

digits below

m

independently goes on the increasing left side or the decreasing right side, after which its position is forced. Hence the total is

\sum_{k=1}^{9}\binom{9}{k}2^{k-1}

= \tfrac12\big((1+2)^9-1\big)

= \tfrac{3^9-1}{2}

=9841.

Therefore, the answer is C.