Difference between revisions of "User:Crazyvideogamez"
(→AOPS Contributions) |
|||
| Line 43: | Line 43: | ||
represents a sum of multiples of <math>2i-1</math> and <math>2i+1</math> equaling <math>2k</math>. So, we can represent it as so: | represents a sum of multiples of <math>2i-1</math> and <math>2i+1</math> equaling <math>2k</math>. So, we can represent it as so: | ||
| − | \begin{ | + | \begin{align*} |
(m^{2i-1} + m^{2(2i-1)} + m^{3(2i-1)} \ldots)&(1 + m^{2i+1} + m^{2(2i+1)} \ldots) \\ | (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}} & \frac{1}{1 - m^{2i+1}} | + | \implies \frac{m^{2i-1}}{1-m^{2i-1}}\cdot&\frac{1}{1 - m^{2i+1}} |
| − | \end{ | + | \end{align*} |
| − | where the number of solutions | + | where the number of solutions is the coefficient of <math>m^{2k}</math>. |
| + | |||
| + | Then, to find the total number of solutions, we sum each of the generating functions corresponding to each equation and derive the coefficient of <math>m^{2k}</math>. | ||
| + | |||
| + | \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) | ||
| + | \end{align*} | ||
Revision as of 22:11, 14 December 2023
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
(Complex Numbers)
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) \end{align*}
