Difference between revisions of "2021 Fall AMC 12A Problems/Problem 25"
MRENTHUSIASM (talk | contribs) (→Solution) |
MRENTHUSIASM (talk | contribs) m (→Solution 1 (Complete Residue System)) |
||
(24 intermediate revisions by 5 users not shown) | |||
Line 12: | Line 12: | ||
Since <math>\gcd(m,4)=1,</math> we conclude that <cmath>\{k+4(0),k+4(1),k+4(2),\ldots,k+4(m-1)\}</cmath> is the complete residue system modulo <math>m</math> for all integers <math>k.</math> | Since <math>\gcd(m,4)=1,</math> we conclude that <cmath>\{k+4(0),k+4(1),k+4(2),\ldots,k+4(m-1)\}</cmath> is the complete residue system modulo <math>m</math> for all integers <math>k.</math> | ||
− | Given any ordered quadruple <math>(a'_1, a'_2, a'_3, a'_4)</math> in modulo <math>m,</math> it follows that exactly one of these <math>m</math> ordered quadruples | + | Given any ordered quadruple <math>(a'_1, a'_2, a'_3, a'_4)</math> in modulo <math>m,</math> it follows that exactly one of these <math>m</math> ordered quadruples has sum <math>0</math> modulo <math>m:</math> |
<cmath>\begin{array}{c|c} | <cmath>\begin{array}{c|c} | ||
& \\ [-2.5ex] | & \\ [-2.5ex] | ||
Line 18: | Line 18: | ||
\hline | \hline | ||
& \\ [-2ex] | & \\ [-2ex] | ||
− | (a'_1, a'_2, a'_3, a'_4) & S+4(0) \\ [0.5ex] | + | (a'_1, a'_2, a'_3, a'_4) & S'+4(0) \\ [0.5ex] |
− | (a'_1+1, a'_2+1, a'_3+1, a'_4+1) & S+4(1) \\ [0.5ex] | + | (a'_1+1, a'_2+1, a'_3+1, a'_4+1) & S'+4(1) \\ [0.5ex] |
− | (a'_1+2, a'_2+2, a'_3+2, a'_4+2) & S+4(2) \\ [0.5ex] | + | (a'_1+2, a'_2+2, a'_3+2, a'_4+2) & S'+4(2) \\ [0.5ex] |
\cdots & \cdots \\ [0.5ex] | \cdots & \cdots \\ [0.5ex] | ||
− | (a'_1+m-1, a'_2+m-1, a'_3+m-1, a'_4+m-1) & S+4(m-1) \\ [0.5ex] | + | (a'_1+m-1, a'_2+m-1, a'_3+m-1, a'_4+m-1) & S'+4(m-1) \\ [0.5ex] |
\end{array}</cmath> | \end{array}</cmath> | ||
We conclude that <math>q(m)=\frac1m\cdot[m(m-1)(m-2)(m-3)]=(m-1)(m-2)(m-3),</math> so <cmath>q(x)=(x-1)(x-2)(x-3)=c_3x^3+c_2x^2+c_1x+c_0.</cmath> | We conclude that <math>q(m)=\frac1m\cdot[m(m-1)(m-2)(m-3)]=(m-1)(m-2)(m-3),</math> so <cmath>q(x)=(x-1)(x-2)(x-3)=c_3x^3+c_2x^2+c_1x+c_0.</cmath> | ||
Line 29: | Line 29: | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
− | ==Solution 2 ( | + | == Solution 2 (Symmetric Congruent Numbers and Interpolation) == |
− | + | Define | |
+ | <cmath> | ||
+ | \[ | ||
+ | b_i = | ||
+ | \left\{ | ||
+ | \begin{array}{ll} | ||
+ | a_i & \mbox{ if } 1 \leq a_i \leq \frac{m-1}{2} \\ | ||
+ | a_i - m & \mbox{ if } \frac{m-1}{2} + 1 \leq a_i \leq m - 1 \\ | ||
+ | 0 & \mbox{ if } a_i = m | ||
+ | \end{array} | ||
+ | \right.. | ||
+ | \] | ||
+ | </cmath> | ||
− | - | + | Hence, <math>b_i</math> is a one-to-one and onto function of <math>a_i</math>, and the range of <math>b_i</math> is <math>\left\{- \frac{m-1}{2} , \cdots , \frac{m-1}{2} \right\}</math>. |
+ | |||
+ | Therefore, to solve this problem, it is equivalent for us to count the number of tuples <math>\left( b_1 , b_2 , b_3 , b_4 \right)</math> that are all distinct and satisfy <math>m | b_1 + b_2 + b_3 + b_4</math>. | ||
+ | |||
+ | Denote by <math>d \left( m \right)</math> the number of such tuples that are also subject to the constraint <math>b_1 < b_2 < b_3 < b_4</math>. | ||
+ | |||
+ | Hence, <math>D \left( m \right) = 4! d \left( m \right) = 24 d \left( m \right)</math>. | ||
+ | |||
+ | We do the following casework analysis to compute <math>d \left( m \right) </math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math>: There is one <math>0</math> in <math>\left( b_1 , b_2 , b_3 , b_4 \right)</math>. | ||
+ | |||
+ | Denote by <math>d_{1i} \left( m \right)</math> the number of tuples with <math>b_i = 0</math>. | ||
+ | |||
+ | By symmetry, <math>d_{11} \left( m \right)= d_{14} \left( m \right)</math> and <math>d_{12} \left( m \right)= d_{13} \left( m \right)</math>. | ||
+ | |||
+ | <math>\textbf{Case 2}</math>: There is no <math>0</math> in <math>\left( b_1 , b_2 , b_3 , b_4 \right)</math>. | ||
+ | |||
+ | Denote by <math>d_{2i} \left( m \right)</math> the number of tuples with <math>i</math> positive entries. | ||
+ | |||
+ | By symmetry, <math>d_{20} \left( m \right) = d_{24} \left( m \right)</math> and <math>d_{21} \left( m \right) = d_{23} \left( m \right)</math>. | ||
+ | |||
+ | Therefore, | ||
+ | <cmath> | ||
+ | \begin{align*} | ||
+ | D \left( m \right) & = 24 d \left( m \right) \\ | ||
+ | & = 24 \left( \sum_{i=1}^4 d_{1i} \left( m \right) + \sum_{i=0}^4 d_{2i} \left( m \right) \right) \\ | ||
+ | & = 24 \left( 2 d_{11} \left( m \right) + 2 d_{12} \left( m \right) + 2 d_{24} \left( m \right) + 2 d_{23} \left( m \right) + d_{22} \left( m \right) \right) . | ||
+ | \end{align*} | ||
+ | </cmath> | ||
+ | |||
+ | Now, we compute <math>D \left( m \right)</math> for <math>m = 5 , 7 , 9 , 11</math>. | ||
+ | |||
+ | |||
+ | <math>\underline{\textbf{SCENARIO}}</math> <math>m = 5</math>. | ||
+ | |||
+ | We have <math>b_i \in \left\{ - 2 , \cdots , 2 \right\}</math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math> | ||
+ | |||
+ | <math>\textbf{Case 1.1}</math>: <math>b_1 = 0</math> | ||
+ | |||
+ | We cannot have <math>3</math> distinct positive integers. So <math>d_{11} \left( 5 \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 1.2}</math>: <math>b_2 = 0</math> | ||
+ | |||
+ | Because there are <math>2</math> positive integers, we must have <math>b_3 = 1</math>, <math>b_4 = 2</math>. | ||
+ | Hence, <math>b_1 = - 3</math>. However, this is out of the range of <math>b_i</math>. | ||
+ | Thus, <math>d_{12} \left( 5 \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 2}</math> | ||
+ | |||
+ | <math>\textbf{Case 2.1}</math>: <math>b_1 > 0</math> | ||
+ | |||
+ | We cannot have <math>4</math> distinct positive integers. So <math>d_{24} \left( 5 \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.2}</math>: <math>b_1 < 0 < b_2</math> | ||
+ | |||
+ | We cannot have <math>3</math> distinct positive integers. So <math>d_{23} \left( 5 \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.3}</math>: <math>b_2 < 0 < b_3</math> | ||
+ | |||
+ | The only solution is <math>\left( b_1 , b_2 , b_3 , b_4 \right) = \left( - 2 , - 1 , 1 , 2 \right)</math>. So <math>d_{22} \left( 5 \right) = 1</math>. | ||
+ | |||
+ | Therefore, <math>D \left( 5 \right) = 24</math>. | ||
+ | |||
+ | |||
+ | <math>\underline{\textbf{SCENARIO}}</math> <math>m = 7</math>. | ||
+ | |||
+ | We have <math>b_i \in \left\{ - 3 , \cdots , 3 \right\}</math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math> | ||
+ | |||
+ | <math>\textbf{Case 1.1}</math>: <math>b_1 = 0</math> | ||
+ | |||
+ | We have no feasible solution. Thus, <math>d_{11} \left( 7 \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 1.2}</math>: <math>b_2 = 0</math> | ||
+ | |||
+ | The only solution is <math>\left( b_1 , b_3 , b_4 \right) = \left( - 3 , 1 , 2 \right)</math>. | ||
+ | Thus, <math>d_{12} \left( 7 \right) = 1</math>. | ||
+ | |||
+ | <math>\textbf{Case 2}</math> | ||
+ | |||
+ | <math>\textbf{Case 2.1}</math>: <math>b_1 > 0</math> | ||
+ | |||
+ | We cannot have <math>4</math> distinct positive integers. So <math>d_{24} \left( 7 \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.2}</math>: <math>b_1 < 0 < b_2</math> | ||
+ | |||
+ | To get <math>3</math> distinct positive integers, we have <math>\left( b_2 , b_3 , b_4 \right) = \left( 1 , 2 , 3 \right)</math>. This implies <math>b_1 = - 6</math>. However, this is out of the range of <math>b_1</math>. So <math>d_{23} \left( 6 \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.3}</math>: <math>b_2 < 0 < b_3</math> | ||
+ | |||
+ | We have <math>d_{22} \left( 7 \right) = \binom{3}{2} = 3</math>. | ||
+ | |||
+ | Therefore, <math>D \left( 7 \right) = 24 \cdot 5</math>. | ||
+ | |||
+ | |||
+ | <math>\underline{\textbf{SCENARIO}}</math> <math>m = 9</math>. | ||
+ | |||
+ | We have <math>b_i \in \left\{ - 4 , \cdots , 4 \right\}</math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math> | ||
+ | |||
+ | <math>\textbf{Case 1.1}</math>: <math>b_1 = 0</math> | ||
+ | |||
+ | The only solution is <math>\left( b_2 , b_3 , b_4 \right) = \left( 2, 3, 4 \right)</math>. | ||
+ | Thus, <math>d_{11} \left( 9 \right) = 1</math>. | ||
+ | |||
+ | <math>\textbf{Case 1.2}</math>: <math>b_2 = 0</math> | ||
+ | |||
+ | The feasible solutions are <math>\left( b_1 , b_3 , b_4 \right) = \left( - 3 , 1 , 2 \right)</math>, <math>\left( - 4 , 1 , 3 \right)</math>. | ||
+ | Thus, <math>d_{12} \left( 9 \right) = 2</math>. | ||
+ | |||
+ | <math>\textbf{Case 2}</math> | ||
+ | |||
+ | <math>\textbf{Case 2.1}</math>: <math>b_1 > 0</math> | ||
+ | |||
+ | There is no feasible solution. So <math>d_{24} \left( 9 \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.2}</math>: <math>b_1 < 0 < b_2</math> | ||
+ | |||
+ | To get <math>3</math> distinct positive integers, we have <math>b_2 + b_3 + b_4 \geq 1 + 2 + 3 = 6</math>. This implies <math>b_1 = - 6</math>. However, this is out of the range of <math>b_1</math>. So <math>d_{23} \left( 9 \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.3}</math>: <math>b_2 < 0 < b_3</math> | ||
+ | |||
+ | We have <math>d_{22} \left( 9 \right) = 8</math>. | ||
+ | |||
+ | Therefore, <math>D \left( 9 \right) = 24 \cdot 14</math>. | ||
+ | |||
+ | |||
+ | <math>\underline{\textbf{SCENARIO}}</math> <math>m = 11</math>. | ||
+ | |||
+ | We have <math>b_i \in \left\{ - 5 , \cdots , 5 \right\}</math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math> | ||
+ | |||
+ | <math>\textbf{Case 1.1}</math>: <math>b_1 = 0</math> | ||
+ | |||
+ | The only solution is <math>\left( b_2 , b_3 , b_4 \right) = \left( 2, 4, 5 \right)</math>. | ||
+ | Thus, <math>d_{11} \left( 11 \right) = 1</math>. | ||
+ | |||
+ | <math>\textbf{Case 1.2}</math>: <math>b_2 = 0</math> | ||
+ | |||
+ | The feasible solutions are <math>\left( b_1 , b_3 , b_4 \right) = \left( - 3 , 1 , 2 \right)</math>, <math>\left( - 4 , 1 , 3 \right)</math>, <math>\left( - 5 , 1 , 4 \right)</math>, <math>\left( - 5 , 2 , 3 \right)</math>. | ||
+ | Thus, <math>d_{12} \left( 11 \right) = 4</math>. | ||
+ | |||
+ | <math>\textbf{Case 2}</math> | ||
+ | |||
+ | <math>\textbf{Case 2.1}</math>: <math>b_1 > 0</math> | ||
+ | |||
+ | The only feasible solution is <math>\left( b_1 , b_2 , b_3 , b_4 \right) = \left( 1 , 2, 3, 5 \right)</math>. So <math>d_{24} \left( 11 \right) = 1</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.2}</math>: <math>b_1 < 0 < b_2</math> | ||
+ | |||
+ | The only feasible solution is <math>\left( b_1 , b_2 , b_3 , b_4 \right) = \left( -1 , 3, 4, 5 \right)</math>. So <math>d_{23} \left( 11 \right) = 1</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.3}</math>: <math>b_2 < 0 < b_3</math> | ||
+ | |||
+ | We have <math>d_{22} \left( 11 \right) = 16</math>. | ||
+ | |||
+ | Therefore, <math>D \left( 11 \right) = 24 \cdot 30</math>. | ||
+ | |||
+ | We know that <math>q \left( m \right) = D \left( m \right)</math> for odd <math>m \geq 5</math>. | ||
+ | |||
+ | Plugging <math>m = 5, 7, 9, 11</math> into this equation, we get | ||
+ | <cmath> | ||
+ | \begin{align*} | ||
+ | c_3 5^3 + c_2 5^2 + c_1 5 + c_0 & = 24 \cdot 1 && (1.1) \\ | ||
+ | c_3 7^3 + c_2 7^2 + c_1 7 + c_0 & = 24 \cdot 5 && (1.2) \\ | ||
+ | c_3 9^3 + c_2 9^2 + c_1 9 + c_0 & = 24 \cdot 14 && (1.3) \\ | ||
+ | c_3 11^3 + c_2 11^2 + c_1 11 + c_0 & = 24 \cdot 30 && (1.4) | ||
+ | \end{align*} | ||
+ | </cmath> | ||
+ | |||
+ | Now, we solve this system of equations. | ||
+ | Taking <math>\frac{(1.2)-(1.1)}{2}</math>, <math>\frac{(1.3)-(1.2)}{2}</math>, <math>\frac{(1.4)-(1.2)}{2}</math>, we get | ||
+ | <cmath> | ||
+ | \begin{align*} | ||
+ | c_3 109 + c_2 12 + c_1 & = 48 && (2.1) \\ | ||
+ | c_3 193 + c_2 16 + c_1 & = 108 && (2.2) \\ | ||
+ | c_3 301 + c_2 20 + c_1 & = 192 && (2.3) | ||
+ | \end{align*} | ||
+ | </cmath> | ||
+ | |||
+ | Taking <math>\frac{(2.2)-(2.1)}{4}</math>, <math>\frac{(2.3)-(2.2)}{4}</math>, we get | ||
+ | <cmath> | ||
+ | \begin{align*} | ||
+ | c_3 21 + c_2 & = 15 && (3.1) \\ | ||
+ | c_3 27 + c_2 & = 21 && (3.2) | ||
+ | \end{align*} | ||
+ | </cmath> | ||
+ | |||
+ | Taking <math>\frac{(3.2)-(3.1)}{6}</math>, we get <math>c_3 = 1</math>. | ||
+ | |||
+ | Plugging <math>c_3</math> into Equation (3.1), we get <math>c_2 = - 6</math>. | ||
+ | |||
+ | Plugging <math>c_2</math> and <math>c_3</math> into Equation (2.1), we get <math>c_1 = 11</math>. | ||
+ | |||
+ | Therefore, the answer is <math>\boxed{\textbf{(E) }11}</math>. | ||
+ | |||
+ | ~Steven Chen (www.professorchenedu.com) | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | As before, note that we have <math>m(m-1)(m-2)</math> numbers we can choose as <math>a,b,c.</math> From here, there is exactly one possible value of <math>1 \leq d \leq m</math> that could make <math>S=a+b+c+d</math> divisible by <math>m.</math> However, there is a <math>\frac{3}{m}</math> chance that this value of <math>d</math> has already been chosen as <math>a,b</math> or <math>c</math>. Thus our polynomial is <math>m(m-1)(m-2)\left(1-\frac{3}{m}\right)=m(m-1)(m-2)\left(\frac{m-3}{m}\right)=(m-1)(m-2)(m-3)</math>. By Vieta's, <math>c_1 = 2+3+6=\boxed{\textbf{(E) } 11}</math>. | ||
+ | |||
+ | ~Dhillonr25 | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/YExRIOt819Y | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
==See Also== | ==See Also== | ||
{{AMC12 box|year=2021 Fall|ab=A|num-b=24|after=Last Problem}} | {{AMC12 box|year=2021 Fall|ab=A|num-b=24|after=Last Problem}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 23:04, 28 April 2023
Contents
Problem
Let be an odd integer, and let denote the number of quadruples of distinct integers with for all such that divides . There is a polynomial such that for all odd integers . What is
Solution 1 (Complete Residue System)
For a fixed value of there is a total of possible ordered quadruples
Let We claim that exactly of these ordered quadruples satisfy that divides
Since we conclude that is the complete residue system modulo for all integers
Given any ordered quadruple in modulo it follows that exactly one of these ordered quadruples has sum modulo We conclude that so By Vieta's Formulas, we get
~MRENTHUSIASM
Solution 2 (Symmetric Congruent Numbers and Interpolation)
Define
Hence, is a one-to-one and onto function of , and the range of is .
Therefore, to solve this problem, it is equivalent for us to count the number of tuples that are all distinct and satisfy .
Denote by the number of such tuples that are also subject to the constraint .
Hence, .
We do the following casework analysis to compute .
: There is one in .
Denote by the number of tuples with .
By symmetry, and .
: There is no in .
Denote by the number of tuples with positive entries.
By symmetry, and .
Therefore,
Now, we compute for .
.
We have .
:
We cannot have distinct positive integers. So .
:
Because there are positive integers, we must have , . Hence, . However, this is out of the range of . Thus, .
:
We cannot have distinct positive integers. So .
:
We cannot have distinct positive integers. So .
:
The only solution is . So .
Therefore, .
.
We have .
:
We have no feasible solution. Thus, .
:
The only solution is . Thus, .
:
We cannot have distinct positive integers. So .
:
To get distinct positive integers, we have . This implies . However, this is out of the range of . So .
:
We have .
Therefore, .
.
We have .
:
The only solution is . Thus, .
:
The feasible solutions are , . Thus, .
:
There is no feasible solution. So .
:
To get distinct positive integers, we have . This implies . However, this is out of the range of . So .
:
We have .
Therefore, .
.
We have .
:
The only solution is . Thus, .
:
The feasible solutions are , , , . Thus, .
:
The only feasible solution is . So .
:
The only feasible solution is . So .
:
We have .
Therefore, .
We know that for odd .
Plugging into this equation, we get
Now, we solve this system of equations. Taking , , , we get
Taking , , we get
Taking , we get .
Plugging into Equation (3.1), we get .
Plugging and into Equation (2.1), we get .
Therefore, the answer is .
~Steven Chen (www.professorchenedu.com)
Solution 3
As before, note that we have numbers we can choose as From here, there is exactly one possible value of that could make divisible by However, there is a chance that this value of has already been chosen as or . Thus our polynomial is . By Vieta's, .
~Dhillonr25
Video Solution
~MathProblemSolvingSkills.com
See Also
2021 Fall AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last Problem |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.