Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2025 AMC 10A Problems/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, $196, 23$ and $12463$ are fair, but $1546, 320,$ and $34321$ are not. How many fair positive integers are there?

$\textbf{(A) } 511 \qquad \textbf{(B) } 2584 \qquad \textbf{(C) } 9841 \qquad \textbf{(D) } 17711 \qquad \textbf{(E) } 19682$

Solution 1

Note that the condition that no digit is adjacent to two greater digits means that the digits must be in ascending order up to some largest digit, when they then switch to descending order. To find the number of such numbers, consider two "parts" of the number: the ascending part and the descending part. Note that since each of these has a unique ordering, we just need to divide the digits $1-9$ among these parts. For each such digit, it can either be in the ascending part, descending part, or not be in the number, giving $3$ possibilities per digit for a total of $3^9$ possibilities. However, we can see that the number cannot be "empty", so we have to subtract 1. Furthermore, the largest digit can be on either part, as it will not make a difference. For example, $136|742=1367|42.$ Therefore, we divide by $2$ to get $(3^9-1)/2=19682/2=\boxed{\textbf{(C) } 9841}$ ~krithikrokcs

Solution 2

There is one very interesting detail about fair positive integers: The second a digit becomes less than its preceding one, the rest of the digits following must also be in decreasing order. This implies that every fair positive integer increases, reaches a maximum digit, and then decreases. This type of permutation of numbers is called a unimodal permutation.

Let's say we have a set of $k$ distinct integers. We want to find the number of unimodal permutations of the set. First, we choose the integers to be in the increasing part of the permutation. For each of the $k$ integers, they are either in the increasing sequence or not. This gives $2^k$ possible increasing sequences, and the decreasing sequence is decided from the remaining integers. But, we must divide this count by $2,$ as we do not need to count the choices for our vertex (the vertex is in both the increasing and decreasing sequence). Hence, the number of unimodal permutations of a set of length $k$ is $2^{k-1}.$

Therefore, for the number of $d-$digit fair positive integers, there are $\dbinom{9}{d}$ ways to choose the $d-$digits, and $2^{d-1}$ ways to make a unimodal permutation with those digits. Our total count is then \[\sum_{i=1}^{9}\dbinom{9}{i}2^{i-1}=\boxed{\text{(C) }9841}.\]

  • Note: I have no idea how to simplify the above sum to make it easier to compute, so Solution 1 would be easier computation-wise.

~Tacos_are_yummy_1 ~ChatGPT for the term "unimodal" cuz I didn't feel like saying "up then vertex then down" twenty times .-.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2025_AMC_10A_Problems/Problem_24&oldid=265861"