Difference between revisions of "User:Crazyvideogamez"
(→AMC) |
|||
(17 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
+ | <!-- Tag: ~[https://artofproblemsolving.com/wiki/index.php/User:Crazyvideogamez CrazyVideoGamez] --> | ||
==AOPS Contributions== | ==AOPS Contributions== | ||
− | + | ||
=== AMC === | === AMC === | ||
# [https://artofproblemsolving.com/wiki/index.php/2019_AMC_10B_Problems/Problem_18#Solution_5_.28rigorous_unlike_all_the_other_solutions.2C_brief_use_of_rudimentary_limits.29 2019 AMC 10B Problems/Problem 18 Solution 5] (Combinatorics) | # [https://artofproblemsolving.com/wiki/index.php/2019_AMC_10B_Problems/Problem_18#Solution_5_.28rigorous_unlike_all_the_other_solutions.2C_brief_use_of_rudimentary_limits.29 2019 AMC 10B Problems/Problem 18 Solution 5] (Combinatorics) | ||
Line 6: | Line 7: | ||
# [https://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10B_Problems/Problem_25#Solution_1_.28Recursion.29 2019 AMC 10B Problems/Problem 25 Solution 1] (Combinatorics) | # [https://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10B_Problems/Problem_25#Solution_1_.28Recursion.29 2019 AMC 10B Problems/Problem 25 Solution 1] (Combinatorics) | ||
# [https://artofproblemsolving.com/wiki/index.php/2021_Fall_AMC_12A_Problems/Problem_20#Solution_2_.28Rigorous_reasoning_on_why_there_cannot_be_any_other_solutions.29 2021 Fall AMC 12A Problems/Problem 20 Solution 2] (Number Theory) | # [https://artofproblemsolving.com/wiki/index.php/2021_Fall_AMC_12A_Problems/Problem_20#Solution_2_.28Rigorous_reasoning_on_why_there_cannot_be_any_other_solutions.29 2021 Fall AMC 12A Problems/Problem 20 Solution 2] (Number Theory) | ||
− | # [https://artofproblemsolving.com/wiki/index.php/2021_Fall_AMC_12A_Problems/Problem_23 2021 Fall AMC 12A Problems/Problem 23 Solution 2.5] (Algebra) | + | # [https://artofproblemsolving.com/wiki/index.php/2021_Fall_AMC_12A_Problems/Problem_23#Solution_2.5_.28Vertex_Form_but_Done_Differently.29 2021 Fall AMC 12A Problems/Problem 23 Solution 2.5] (Algebra) |
=== AIME === | === AIME === | ||
− | # [https://artofproblemsolving.com/wiki/index.php/2011_AIME_II_Problems/Problem_8#Solution_3 2011 AIME II Problems/Problem 8 Solution <math>1.\overline{6}</math>] ( | + | # [https://artofproblemsolving.com/wiki/index.php/2011_AIME_II_Problems/Problem_8#Solution_3 2011 AIME II Problems/Problem 8 Solution <math>1.\overline{6}</math>] (Algebra) |
+ | # [https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_II_Problems/Problem_14#Solution_4 2017 AIME II Problems/Problem 14 Solution 4] (Combinatorics) | ||
+ | # [https://artofproblemsolving.com/wiki/index.php/2000_AIME_I_Problems/Problem_15#Solution_3_.28Recursion_on_number_of_cards_below_1999.29 2000 AIME I Problems/Problem 15 Solution 3] (Combinatorics) | ||
+ | # [https://artofproblemsolving.com/wiki/index.php/2018_AIME_II_Problems/Problem_11#Solution_3_.28Recursion.29 2018 AIME II Problems/Problem 11 Solution 3 (Recursion)] (Combinatorics) | ||
+ | # [https://artofproblemsolving.com/wiki/index.php/2018_AIME_II_Problems/Problem_12#Solution_11 2018 AIME II Problems/Problem 12 Solution 11] (Geometry) | ||
+ | # [https://artofproblemsolving.com/wiki/index.php/2018_AIME_II_Problems/Problem_13#Markov_Chain_Diagram 2018 AIME II Problems/Problem 13 Markov Chain Diagram] (Combinatorics) | ||
+ | # [https://artofproblemsolving.com/wiki/index.php/2018_AIME_I_Problems/Problem_12#Solution_3_.28Triple_Vandermonde.27s.29 2018 AIME I Problems/Problem 12 Solution 3 (Triple Vandermonde's)] (Combinatorics) | ||
+ | # [https://artofproblemsolving.com/wiki/index.php/2018_AIME_I_Problems/Problem_12#Solution_4_.28Symmetry.29 2018 AIME I Problems/Problem 12 Solution 4 (Symmetry)] (Combinatorics) | ||
+ | # [https://artofproblemsolving.com/wiki/index.php/2019_AIME_I_Problems/Problem_15#Solution_8 2019 AIME I Problems/Problem 15 Solution 8] (Geometry) | ||
+ | # [https://artofproblemsolving.com/wiki/index.php/2022_AIME_II_Problems/Problem_11#Solution_5_.28incircle.29 2022 AIME II Problems/Problem 11 Solution 5 (incircle)] (Geometry) | ||
==Problems that I enjoyed solving== | ==Problems that I enjoyed solving== | ||
Line 99: | Line 109: | ||
\end{equation} | \end{equation} | ||
− | Each <math>m^{2k} \cdot 1, m^{2k - 2} \cdot m^2, m^{2k-4} \cdot m^4, \cdots, m^{2} \cdot m^{2k-2}</math> (first power of <math>m</math> originating from the first series, second power of <math>m</math> originating from the infinite geometric series) contribute one factor of <math>m^{2k}</math>. There are <math>k</math> of these factors. | + | Each <math>m^{2k} \cdot 1, m^{2k - 2} \cdot m^2, m^{2k-4} \cdot m^4, \cdots, m^{2} \cdot m^{2k-2}</math> (first power of <math>m</math> originating from the first series, second power of <math>m</math> originating from the infinite geometric series) contribute one factor of <math>m^{2k}</math>. There are <math>k</math> of these factors. Therefore, there are exactly <math>\boxed{k}</math> ordered pairs of <math>(x, y)</math> satisfying any of the equations listed in the problem. |
Latest revision as of 00:26, 6 June 2024
Contents
AOPS Contributions
AMC
- 2019 AMC 10B Problems/Problem 18 Solution 5 (Combinatorics)
- 2020 AMC 10A Problems/Problem 24 Solution 12 (Number Theory)
- 2019 AMC 10B Problems/Problem 25 Solution 1 (Combinatorics)
- 2021 Fall AMC 12A Problems/Problem 20 Solution 2 (Number Theory)
- 2021 Fall AMC 12A Problems/Problem 23 Solution 2.5 (Algebra)
AIME
- 2011 AIME II Problems/Problem 8 Solution
(Algebra)
- 2017 AIME II Problems/Problem 14 Solution 4 (Combinatorics)
- 2000 AIME I Problems/Problem 15 Solution 3 (Combinatorics)
- 2018 AIME II Problems/Problem 11 Solution 3 (Recursion) (Combinatorics)
- 2018 AIME II Problems/Problem 12 Solution 11 (Geometry)
- 2018 AIME II Problems/Problem 13 Markov Chain Diagram (Combinatorics)
- 2018 AIME I Problems/Problem 12 Solution 3 (Triple Vandermonde's) (Combinatorics)
- 2018 AIME I Problems/Problem 12 Solution 4 (Symmetry) (Combinatorics)
- 2019 AIME I Problems/Problem 15 Solution 8 (Geometry)
- 2022 AIME II Problems/Problem 11 Solution 5 (incircle) (Geometry)
Problems that I enjoyed solving
Problem
Let be a positive integer. Prove that there are exactly
ordered pairs
of nonnegative integers that satisfy any one of the following equations:
\begin{align*} x+3y &= 2k-1, \\ 3x + 5y &= 2k - 3, \\ \vdots \\ (2k-1)x + (2k+1)y &= 1. \end{align*}
(Source: Mandelbrot)
My Solution
First, allow us to prove that none of these equations share a solution. Let and
be any integer from
to
. Then, we solve
\begin{align*} (2i - 1)x + (2i + 1)y = 2k - 2i + 1 &\implies (2i - 1)(x+1) + (2i + 1)y = 2k \\ (2j - 1)x + (2j + 1)y = 2k - 2j + 1 &\implies (2j - 1)(x+1) + (2j + 1)y = 2k \\ \text{Subtracting the }&\text{two equations, we get} \\ (2i - 2j)(x+1) + (2i - 2j) y = 0 &\implies x + y + 1 = 0 \implies x + y = -1 \end{align*}
This clearly has no solutions in nonnegative integers. Therefore, each solution each equation provides is guaranteed to be distinct from one another without any overcounting.
Next, let us represent the number of solutions to each equation as a generating function. The equation
\begin{equation} (2i - 1)(x+1) + (2i + 1)y = 2k \end{equation}
represents a sum of multiples of and
equaling
. So, we can represent it as so:
\begin{align*} (m^{2i-1} + m^{2(2i-1)} + m^{3(2i-1)} \ldots)&(1 + m^{2i+1} + m^{2(2i+1)} \ldots) \\ \implies \frac{m^{2i-1}}{1-m^{2i-1}}\cdot&\frac{1}{1 - m^{2i+1}} \end{align*}
where the number of solutions is the coefficient of .
Then, to find the total number of solutions, we sum each of the generating functions corresponding to each equation and derive the coefficient of .
\begin{align*} \sum_{i=1}^{k} \frac{m^{2i-1}}{1-m^{2i-1}}\cdot \frac{1}{1 - m^{2i+1}} &= \sum_{i=1}^{k} m^{2i-1} \Bigl(\frac{1}{1-m^{2i-1}}\cdot\frac{1}{1 - m^{2i+1}}\Bigr) \\ &= \sum_{i=1}^{k} \frac{m^{2i-1}}{1-m^2} \Bigl(\frac{1}{1-m^{2i-1}} - \frac{m^2}{1 - m^{2i+1}}\Bigr) \\ &= \frac{1}{1-m^2} \sum_{i=1}^{k} \frac{m^{2i-1}}{1-m^{2i-1}} - \frac{m^{2i+1}}{1 - m^{2i+1}} \end{align*}
Let . Then, we have
\begin{align*} \frac{1}{1-m^2} \sum_{i=1}^{k} \frac{m^{2i-1}}{1-m^{2i-1}} - \frac{m^{2i+1}}{1 - m^{2i+1}} &= \frac{1}{1-m^2} \sum_{i=1}^{k} \frac{1}{\frac{1}{m^{2i-1}}-1} - \frac{1}{\frac{1}{m^{2i+1}}-1} \\ &= \frac{1}{1-m^2} \sum_{i=1}^{k} \frac{1}{n^{2i-1}-1} - \frac{1}{n^{2i+1}-1} \end{align*}
Notice that
\begin{align*} \sum_{i=1}^{k} \frac{1}{n^{2i-1}-1} - \frac{1}{n^{2i+1}-1} &= \frac{1}{n - 1} - \frac{1}{n^3 - 1} + \frac{1}{n^3 - 1} - \frac{1}{n^5 - 1} + \cdots + \frac{1}{n^{2k-1} - 1} - \frac{1}{n^{2k+1} - 1} \\ &= \frac{1}{n-1} - \frac{1}{n^{2k+1}-1} \end{align*}
Via the factorization , we obtain
\begin{align*} \frac{n^{2k} + n^{2k-1} + \ldots + 1 - 1}{n^{2k+1} - 1} &= \frac{n^{2k} + n^{2k-1} + \ldots + n}{n^{2k+1} - 1} \\ &= \frac{m^{2k+1} (n^{2k} + n^{2k-1} + \ldots + n)}{m^{2k+1}(n^{2k+1}-1)} \\ &= \frac{m + m^2 + \ldots + m^{2k}}{1 - m^{2k+1}} \end{align*}
Returning to our original expression, we have
\begin{align*} \frac{1}{1-m^2} \sum_{i=1}^{k} \frac{1}{n^{2i-1}-1} - \frac{1}{n^{2i+1}-1} &= \frac{1}{1-m^2} \cdot \frac{m + m^2 + \ldots + m^{2k}}{1 - m^{2k+1}} \end{align*}
Expanding the infinite geometric series, we see that
\begin{align*} \frac{1}{1-m^{2k+1}} &= 1 + m^{2k+1} + m^{2(2k+1)} + \ldots \\ \frac{1}{1-m^2} &= 1 + m^2 + m^4 + m^6 + \ldots \end{align*}
To find the coefficient of , we can ignore all the powers of
in
since they are all above
. Thus, we must only find the coefficient of
in the expression
\begin{equation} (m + m^2 + \cdots + m^{2k})(1 + m^2 + m^4 + m^6 + \cdots) \end{equation}
Each (first power of
originating from the first series, second power of
originating from the infinite geometric series) contribute one factor of
. There are
of these factors. Therefore, there are exactly
ordered pairs of
satisfying any of the equations listed in the problem.