|
|
| Line 1: |
Line 1: |
| Call a positive integer fair if no digit is used more than once, it has no <imath>0</imath>s, and no digit is adjacent to two greater digits. For example, <imath>196, 23</imath> and <imath>12463</imath> are fair, but <imath>1546, 320,</imath> and <imath>34321</imath> are not. How many fair positive integers are there?
| | #redirect [[2025 AMC 12A Problems/Problem 23]] |
| | |
| <imath>\textbf{(A) } 511 \qquad \textbf{(B) } 2584 \qquad \textbf{(C) } 9841 \qquad \textbf{(D) } 17711 \qquad \textbf{(E) } 19682</imath>
| |
| | |
| ==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 <imath>1-9</imath> among these parts. For each such digit, it can either be in the ascending part, descending part, or not be in the number, giving <imath>3</imath> possibilities per digit for a total of <imath>3^9</imath> 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, <imath>136|742=1367|42.</imath> Therefore, we divide by <imath>2</imath> to get <imath>(3^9-1)/2=19682/2=\boxed{\textbf{(C) } 9841}</imath>
| |
| ~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 <imath>k</imath> 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 <imath>k</imath> integers, they are either in the increasing sequence or not. This gives <imath>2^k</imath> possible increasing sequences, and the decreasing sequence is decided from the remaining integers. But, we must divide this count by <imath>2,</imath> 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 <imath>k</imath> is <imath>2^{k-1}.</imath>
| |
| | |
| Therefore, for the number of <imath>d-</imath>digit fair positive integers, there are <imath>\dbinom{9}{d}</imath> ways to choose the <imath>d-</imath>digits, and <imath>2^{d-1}</imath> ways to make a unimodal permutation with those digits. Our total count is then
| |
| <cmath>\sum_{i=1}^{9}\dbinom{9}{i}2^{i-1}=\dfrac{1}{2}\sum_{i=1}^{9}\dbinom{9}{i}2^{i}=\dfrac{1}{2}((1+2)^9-1)=\boxed{\text{(C) }9841}.</cmath>
| |
| | |
| ~Tacos_are_yummy_1
| |
| | |
| ===Alternate Counting Method===
| |
| Or, to calculate <cmath>\sum_{i=1}^{9}\dbinom{9}{i}2^{i-1},</cmath> we can double it and then half it to create a more symmetric structure, giving us <cmath>\frac{1}{2} \sum_{i=1}^{9}\dbinom{9}{i}2^{i}.</cmath> Consider a counting argument in which there are <imath>9</imath> people, and you choose a nonempty group of them to respond, and they can say either vote yes or no to a prompt. Equivalently, this would be identical to giving each person three choices, to not vote, to vote yes, or to vote no. Therefore, the aforementioned sum is equivalent to <cmath>\sum_{i=1}^{9}\dbinom{9}{i}2^{i} = 3^i - 1</cmath> where the -1 comes from when no one votes. Halving that yields <imath>\dfrac{3^9 - 1}{2} = 9841.</imath>
| |
| | |
| - [https://artofproblemsolving.com/wiki/index.php/User:Spectraldragon8 spectraldragon8]
| |
| | |
| == Solution 3 (Easily Motivated)==
| |
| Similar to Solution 1, observe that the digits of all "fair" numbers go up and go down. We simply do casework on the peak digit; if it is <imath>6</imath>, for example, each of the digits <imath>1\sim 5</imath> can either be to the left of <imath>6</imath>, to the right of <imath>6</imath>, or don't appear in the number at all. This would yield <imath>3^5</imath> such numbers. Sweeping through all possible values of the peak digit from 1 through 9, we get <cmath>3^0+3^1+...+3^8=\dfrac{3^9-1}{2}=\boxed{\text{(C) }9841}</cmath>
| |
| ~Mathkiddie
| |
| | |
| == Solution 4 (Cheese 🧀)==
| |
| | |
| Notice that answer choices A and B are way too small, and answer choices D and E are way too big. This leaves us with <cmath>\boxed{\text{(C) } 9841}</cmath>.
| |
| | |
| Note: Do not try this on an actual test unless you have to. This is a really risky solution.
| |
| | |
| ~Aeioujyot
| |
| | |
| ===Alternate Cheese Method===
| |
| | |
| For answer choices C and E, notice that E is a multiple of C. Since E is way too big, we will choose <imath>\boxed{\text{(C) } 9841}</imath> from these options.
| |
| | |
| Note: Also do not try this on the actual test. This is another risky solution that is not recommended if you have time.
| |
| | |
| Note #2: From my experience, the MAA usually adds an answer choice that is a multiple of another answer choice, and usually one of these choices are correct.
| |
| | |
| ~mathcantcount1plus1is3
| |
| | |
| == Video Solution (In 2 Mins) ==
| |
| https://youtu.be/hYZkrBtIFvI?si=dMOaGsXSpxYV17PO ~ Pi Academy
| |
| | |
| ==Video Solution by SpreadTheMathLove==
| |
| https://www.youtube.com/watch?v=dAeyV60Hu5c
| |
| | |
| ==See Also==
| |
| {{AMC10 box|year=2025|ab=A|num-b=23|num-a=25}}
| |
| * [[AMC 10]]
| |
| * [[AMC 10 Problems and Solutions]]
| |
| * [[Mathematics competitions]]
| |
| * [[Mathematics competition resources]]
| |
| {{MAA Notice}}
| |
