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 12A Problems/Problem 23: Difference between revisions

← Older editNewer edit →
Silverrush (talk | contribs)
editor
17 edits
Silverrush (talk | contribs)
editor
17 edits
m edited solution title
Line 21: Line 21:
~lprado
~lprado


==Solution 2 (similar to solution 1)==
==Solution 2==


Note every "fair" number will have an increasing string of digit, a maximum digit, then a decreasing string of digits. This is because if it decreases then increases, then the digit in the middle will be less than its adjacent digits.
Note every "fair" number will have an increasing string of digit, a maximum digit, then a decreasing string of digits. This is because if it decreases then increases, then the digit in the middle will be less than its adjacent digits.

Revision as of 16:48, 6 November 2025

Problem

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

To satisfy the conditions, a $\textit{fair}$ integer must have no digit be a local minimum. Let's say we have $n$ distinct digits, with each digit being a number from $1$ to $9$. To create a $\textit{fair}$ integer, we begin by placing the largest digit. For the second-largest digit, we can either place this digit to the right or to the left of the string already created. We have these $2$ options for the third-largest digit, and so on. Therefore, there are $2^{n-1}$ valid permutations to create a $\textit{fair}$ integer.

We must also choose which digits will be in the permutation. If you are creating an $n$-digit long $\textit{fair}$ integer, there are $9\choose{n}$ ways to pick which digits will be in the number.

Therefore, for each $n \in \{1,2,\dots, 9\}$, the number of fair integers of length $n$ is: \[\binom{9}{n} \cdot 2^{n-1}.\] Summing over all $n$: \[\sum_{n=1}^9{\binom{9}{n} \cdot 2^{n-1}}\] \[=\frac{1}{2}\left(\sum_{n=0}^9{\binom{9}{n}}2^n -1\right)\] \[=\frac{1}{2}\left((1+2)^9 -1 \right) = \frac{1}{2}(19682) = \boxed{9841}.\] Note that the Binomial Theorem was used to equate \[\sum_{n=0}^9{\binom{9}{n}}2^n = (1+2)^9.\]

~lprado

Solution 2

Note every "fair" number will have an increasing string of digit, a maximum digit, then a decreasing string of digits. This is because if it decreases then increases, then the digit in the middle will be less than its adjacent digits.

Let $n$ be the maximum digit. For each number $i<n$, we may either place $i$ before $n$, after $n$, or choose not to include it. Note this process will result in a unique number for every case, as the numbers before $n$ must be in increasing order, and the numbers after $n$ must be in decreasing order. Therefore, for each number $n$, we have $3^{n-1}$ cases.

Since $n \in \{1,2,...9\}$, we have: \[\sum_{n=1}^9 3^{n-1}=\frac{3^9-1}{3-1}=\boxed{9841}.\]

~SilverRush

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2025_AMC_12A_Problems/Problem_23&oldid=265920"