AIME 2025 II · 第 13 题

Solution 1 (complete)

This problem can be split into three parts, listed below:

Part 1: Analyzing Fractions

Let $x_k=\cfrac{a_k}{b_k}$, where $a_k,b_k$ are relatively prime positive integers. First, we analyze the moduli of the problem. Plugging in for $x_2$ yields $x_2=\frac{157}{275}$. Notice that in both $x_1$ and $x_2$, the numerator is equivalent to $1$ and the denominator is equivalent to $2$ modulus $3$. We see that $x_2=\frac{1}{3}\cdot\frac{(a_1-b_1)^2+a_1b_1}{a_1b_1}$. Specifically, we know that

$$(a_1-b_1)^2+a_1b_1\equiv(1-2)^2+1\cdot2\equiv0\hspace{2mm}(\text{mod}\hspace{1mm}3)$$ Then this is always divisible by $3$ for all $x_k$ (it can be shown that for all $x_k$, we have $a_k\equiv1\hspace{2mm}(\text{mod}\hspace{1mm}3)$ and $b_k\equiv2\hspace{2mm}(\text{mod}\hspace{1mm}3)$ by using $\text{mod}\hspace{1mm}9$). Thus, $x_2=\frac{\frac{1}{3}((a_1-b_1)^2+a_1b_1)}{a_1b_1}$, and the numerator and denominator of the right-hand side (RHS) correspond to the numerator and denominator of $x_2$ in simplest form. (To further prove that the top and bottom are relatively prime, consider that $a_k$ and $b_k$ are by definition relatively prime, so $(a_k-b_k)^2$ and $a_kb_k$ share no factors.)

Notice that the above do not just apply to $x_1$; we did not use any specific properties of $x_1$. Then we may generalize the above, finding that:

$$a_k=\frac{1}{3}((a_{k-1}-b_{k-1})^2+a_{k-1}b_{k-1})$$ $$b_k=a_{k-1}b_{k-1}$$ Summing the equations yields $a_k+b_k=\frac{1}{3}(a_{k-1}+b_{k-1})^2$ after some manipulation. Let $z_k=a_k+b_k$; then $z_k=\frac{1}{3}z_{k-1}^2$. We are tasked with finding $z_{2025}$.

Part 2: Recursion

We now need an explicit formula for $z_k$. We can first experiment with the recursive formula:

$z_k=\frac{1}{3}z_{k-1}^2=\frac{1}{3}\left(\frac{1}{3}z_{k-2}^2\right)^2=\frac{1}{3}\left(\frac{1}{3}\left(\frac{1}{3}z_{k-3}^2\right)^2\right)^2$

Notice that the inner $\frac{1}{3}$ is acted upon by two consecutive powers of $2$. This means that it contributes $\left(\left(\frac{1}{3}\right)^2\right)^2=\left(\frac{1}{3}\right)^4$ to the value of $z_k$. The next innermost $\frac{1}{3}$ is acted upon by one power of $2$, so it contributes $\left(\frac{1}{3}\right)^2$ to the value of $z_k$. Finally, the outermost $\frac{1}{3}$ is acted upon by no powers of $2$, so it contributes $\left(\frac{1}{3}\right)^1$ to the value of $z_k$. The overall power of $\frac{1}{3}$ in $z_k$ in terms of $z_{k-3}$ is then $4+2+1=2^2+2^1+2^0=2^3-1$. Then, the overall power of $\frac{1}{3}$ in $z_k$ in terms of $z_{k-a}$ is $2^a-1$ for positive integers $a$.

We also see that the $z_{k-3}$ term is acted upon by $3$ powers of $2$, meaning that its power is $2\cdot2\cdot2=2^3$. We can generalize this, so some $z_{k-a}$ term's power is then $2^a$.

If we combine the above, we obtain the formula $z_k=\left(\frac{1}{3}\right)^{2^a-1}z_{k-a}^{2^a}$. Setting $k=a+1$ results in

$$z_{a+1}=\left(\frac{1}{3}\right)^{2^a-1}z_1^{2^a}=36^{2^a}\cdot\left(\frac{1}{3}\right)^{2^a-1}$$ We can simplify this, noting that $36^{2^a}=12^{2^a}\cdot3^{2^a}$:

$$z_{a+1}=12^{2^a}\cdot3^{2^a}\cdot\left(\frac{1}{3}\right)^{2^a-1}=3\cdot12^{2^a}$$ Finally, decrementing $a+1$ to $a$ gives us our explicit equation:

$$z_a=3\cdot12^{2^{a-1}}$$

Part 3: Mod Bash

Noting that $z_{2025}=3\cdot12^{2^{2024}}$, we are asked to find its value mod $1000$. We can split mod $1000$ into mod $125$ and mod $8$. We know that $z_{2025}\equiv0\hspace{2mm}(\text{mod}\hspace{1mm}8)$, so we must find its value mod $125$.

We find that $\phi(125)=100$, so by Euler's Totient Theorem we know that $12^{100}\equiv1\hspace{2mm}(\text{mod}\hspace{1mm}125)$. Then, since the power of $12$ is $2^{2024}$, we must find this over modulus $100$.

Again, we split mod $100$ into mod $4$ and mod $25$. We know that $2^{2024}\equiv0\hspace{2mm}(\text{mod}\hspace{1mm}4)$. Since $\phi(25)=20$, we can apply Euler again, finding that $2^{20}\equiv1\hspace{2mm}(\text{mod}\hspace{1mm}25)$. Then

$$2^{2024}\equiv(2^{20})^{101}\cdot2^4\equiv2^4\equiv16\hspace{2mm}(\text{mod}\hspace{1mm}25)$$ Combining this with the mod $4$ result yields $2^{2024}\equiv16\hspace{2mm}(\text{mod}\hspace{1mm}100)$.

Going back, $12^{2^{2024}}\equiv12^{16}\hspace{2mm}(\text{mod}\hspace{1mm}125)$. We can then decrement this using a series of simplifications:

$$12^{16}\equiv144^8\equiv19^8\equiv361^4\equiv(-14)^4\equiv196^2\equiv(-54)^2\equiv2916\equiv41\hspace{2mm}(\text{mod}\hspace{1mm}125)$$ Remember that the original value of $z_{2025}$ included a multiplication of $3$; thus,

$$z_{2025}\equiv41\cdot3\equiv123\hspace{2mm}(\text{mod}\hspace{1mm}125)$$ Finally, combining this with the fact that $z_{2025}\equiv0\hspace{2mm}(\text{mod}\hspace{1mm}8)$, we find that the solution to the system of moduli is $z_{2025}\equiv\boxed{248}\hspace{2mm}(\text{mod}\hspace{1mm}1000)$.

~eevee9406

Solution 2 (Faster)

Note that $x_{k+1} = \frac{1}{3}\left( \frac{(x_k)^{2} - x_k + 1}{x_k} \right)$. An astute reader might recognize the top part as one part of a sum of cubes. I multiplied the entire expression by $x_k + 1$, moved things around a bit, simplified, and was left with the following generalization: $x_{k+1} = \frac{(x_k)^{3} + 1}{3x_k(x_k + 1)}$. Now, we do the following: Set $x_k = \frac{m_k}{n_k}$. Therefore, $x_{k+1} = \frac{m_{k+1}}{n_{k+1}}$. We plug these expressions into the $x_k$ and $x_{k+1}$ and simplify to get: $\frac{m_{k+1}}{n_{k+1}} = \frac{(m_k)^{3} + (n_k)^{3}}{3(m_k)(n_k)(m_k + n_k)}$. Now, as we are looking for the sum of the numerators and denominators of $x_{2025}$, this is great! Now, recall that we want the fraction to be simplest. So we have to cancel out anything we can. Canceling out the factor of $m_k + n_k$ from the numerator and denominator leaves us with $\frac{m_{k+1}}{n_{k+1}} = \frac{(m_k)^{2} - (m_k)(n_k) + (n_k)^{2}}{3(m_k)(n_k)}$. Now, adding the numerator and denominator as well as keeping the extra factor of $3$, we get: 3($m_{k+1} + n_{k+1}) = (m_k)^{2} + 2(m_k)(n_k) + (n_k)^{2}$. Nicely, we get the recursion that $m_{k+1} + n_{k+1} = \frac{(m_k + n_k)^{2}}{3}$. Now, by listing out terms using this recursion and doing mod(1000), we get our answer of $\boxed{248}$.

~ilikemath247365

Note: this works, but why are we able to add the numerator and denominator? What if one of the fractions is not fully simplified?

Answer: Because $m_k$ and $n_k$ are coprime, any prime factor $p \mid m_k$ can not be a factor of $(n_k)^{2}$, any prime factor $q \mid n_k$ can not be a factor of $(m_k)^{2}$. The only possible common factor of the numerator and denominator could be 3. However, a simple induction argument shows $n_k \equiv 2 \mod 3$ and $m_k \equiv 1 \mod 3$ for $k > 1$. So this double recursion $\frac{m_{k+1}}{n_{k+1}} = \frac{\frac{1}{3}\big((m_k)^{2} - (m_k)(n_k) + (n_k)^{2}\big)}{(m_k)(n_k)}$ is indeed the most simplified one.

~Rakko12

Video Solution

2025 AIME II #13

MathProblemSolvingSkills.com