Let $ a_1 = 11^{11}, \, a_2 = 12^{12}, \, a_3 = 13^{13}$, and $ a_n = |a_{n - 1} - a_{n - 2}| + |a_{n - 2} - a_{n - 3}|, n \geq 4.$ Determine $ a_{14^{14}}$.
Problem
Source: IMO ShortList 2001, number theory problem 3
Tags: modular arithmetic, IMO Shortlist, number theory, Integer sequence, recurrence relation
mathangel
03.10.2008 17:44
* Notice that the numbers $ 11^{11}, 12^{12}, 13^{13}, 14^{14}$ are not of importance. They could be replace by any other number. Hence, we do not concentrate on the value of $ a_{14^{14}}$ itself but look for a different representation of it. * Treat every element $ a_i$ as a vector with 3 weight $ a_1, a_2, a_3$. It means: rewrite $ a_i \rightarrow (\alpha_i , \beta_i, \gamma_i)$ with the property: $ a_i = (\alpha_i , \beta_i, \gamma_i) \cdot (a_1, a_2, a_3)$ (the dot product of 2 real vectors) Enumerating the sequence of vectors, we observe that: $ a_{7k+6} = (-1, 1, 0)$ for all $ k \in \mathbb{N}$. Proving this is just a routine. * Also of interest is the sequence $ a_{7k}$: (0,-1,1) (2,-3,1) (4,-5,1) ... One easily get the pattern: $ a_{7k} = (2k-2 , - 2k+1 , 1)$ and the answer for the IMO shortlist problem is: $ a_{14^{14}} = (4\times 14^{13} - 2)\times 11^{11} - (4\times 14^{13} - 1)\times 12^{12} + 13^{13}$ Final Remark: Generalization could be made to obtain the formula for all $ a_n$.
Zhero
16.05.2010 22:51
mathangel wrote: * Treat every element $ a_i$ as a vector with 3 weight $ a_1, a_2, a_3$. It means: rewrite $ a_i \rightarrow (\alpha_i , \beta_i, \gamma_i)$ with the property: $ a_i = (\alpha_i , \beta_i, \gamma_i) \cdot (a_1, a_2, a_3)$ (the dot product of 2 real vectors) Enumerating the sequence of vectors, we observe that: $ a_{7k+6} = (-1, 1, 0)$ for all $ k \in \mathbb{N}$. Proving this is just a routine. This claim is completely false.
Let $c_n = |a_{n+1} - a_n|$. Then $c_1 = 12^{12} - 11^{11}$, $c_2 = 13^{13} - 12^{12}$, $c_3 = 11^{11}$, and $c_4 = 12^{12} - 2 \cdot 11^{11}$. Since $a_n = |a_{n-1} - a_{n-2}| + |a_{n-2} - a_{n-3}| = c_{n-2} + c_{n-3}$, $a_{n+1} = c_{n-1} + c_{n-2}$. Subtracting these two yields $c_n = |c_{n-1} - c_{n-3}|$ for all $n \geq 3$.
Lemma: For any positive integer $i$, $\gcd(c_i, c_{i+1}, c_{i+2}) = 1$.
Proof: Suppose that there exists some positive $i$ for which $\gcd(c_i, c_{i+1}, c_{i+2}) > 1$; consider the minimal such $i$. If $i > 1$, since $c_{i+2} = |c_{i+1} - c_{i-1}|$, $\gcd(c_i, c_{i+1}, c_{i+2}) | c_{i-1}$ as well, so $\gcd(c_{i-1}, c_i, c_{i+1}) > 1$, contradicting the minimality of $i$. Hence, $i = 1$; but it is clear that $\gcd(c_1, c_2, c_3) = 1$, so we have a contradiction.
Define a sharp peak of $\{c_n\}$ to be some term $c_i$ such that $c_i > c_{i+1}, c_{i+2}$. We claim that for every sharp peak $c_p$, if $c_p > 2$, there exists some integer $i \leq 5$ such that $c_{p+i}$ is a smaller sharp peak. First, we will suppose that neither $c_{p+1}$ nor $c_{p+2}$ are 0, and show that we can find some $i \leq 3$ such that $c_{p+i}$ is a smaller sharp peak when $c_{p+1}, c_{p+2}$ are both nonzero.
If $c_{p+1} > c_{p+2}$, let $c_p = a + b + c$, $c_{p+1} = a + b$, and $c_{p+2} = a$, where $a$, $b$, and $c$ are nonnegative integers (with $a, b \neq 0.$) Then $c_{p+3} = b + c$. If $a > c$, then $a+b > a, b + c$. Since $a \neq 0$, $c_{p+1}$ is a sharp peak. If $a < c$, then $c_{p+3} = b + c$, $c_{p+4} = c - a$, and $c_{p+5} = |c - 2a|$. Since $0 \leq a < c < c + 2a$, $-c < -a < c - 2a < c$, giving $|c - 2a| < c < b + c$. In addition, $c - a < c < b + c$, so we have that $b + c > c - a, |c - 2a|$, so $c_{p+3}$ is a sharp peak. If $a = c$, then $a_{p+3} = a + b$, $a_{p+4} = 0$, and $a_{p+5} = a$; since $a + b > 0, a$, $a_{p+3}$ is a sharp peak.
If $c_{p+1} < c_{p+2}$, let $c_p = a + b + c$, $c_{p+1} = a$, and $c_{p+2} = a + b$, where $a$, $b$, and $c$ are nonnegative integers (with $a,b \neq 0$). It follows easily that $c_{p+3} = c$. If $a > c$, then $c_{p+4} = a - c$; since $a > c, a - c$, we have that $c_{p+1}$ is a sharp peak. If $a < c$, then $c_{p+4} = c - a$. If $a + b > c$, then $a + b > c > c - a$, so $c_{p+2}$ is a sharp peak. If $a + b \leq c$, then $c_{p+5} = |(c - a - b) - a| \leq a$, making $c_{p+3}$ a sharp peak. Finally, if $a = c$, then $c_{p+3} = a$ and $c_{p+4} = 0$; as $a + b > a, 0$, we have that $c_{p+2}$ is a sharp peak.
Finally, we consider the case in which $c_{p+1} = c_{p+2}$; here, let $c_p = a + b$ and $c_{p+1} = c_{p+2} = a$. Then $c_{p+3} = b$ and $c_{p+4} = |a - b|$. If $a > b$, then $a > b, |a - b|$, making $c_{p+2}$ a sharp peak. If $a < b$, then $c_{p+5} = |b - 2a|$. Also, $a < b < b + 2a$, so $-b < -a < b - 2a < b$, giving $|b - 2a| < b$. Hence, $c_{p+3} > c_{p+4}, c_{p+5}$, making $c_{p+3}$ a sharp peak. If $a = b$, then by our lemma, $\gcd(c_p, c_{p+1}, c_{p+2}) = \gcd(2a,a, a) = 1$, giving $a = 1$ and hence $c_p = 2$, which is a contradiction.
We now consider the case in which $c_{p+2}$ or $c_{p+1}$ is 0. In the former case, let $c_p = a$ and $c_{p+1} = b$. Then $c_{p+2} = a$, and $c_{p+3} = c_{p+4} = |a - b|$. If $a = b$ or if $b = 0$, then our lemma tells us that $\gcd(c_p, c_{p+1}, c_{p+2}) = a = 1$, contradicting our assumption that $c_p > 2$. Hence, from what we have shown before, we can find some $i \leq 3$ such that $c_{p+2+i}$ is a sharp peak smaller than $a$ (since $c_{p+2} > c_{p+3}, c_{p+4}.)$ As $2 + i \leq 5$, our proof of this case is done.
If $c_{p+1}$ is 0, let $c_p = a$ and let $c_{p+2} = b$ (because of the above case, we may assume $b \neq 0$.) Then $c_3 = c_4 = a - b$. If $a - b < b$, then $c_{p+2} > c_{p+3}, c_{p+4}$, making $c_{p+2}$ a sharp peak. If $a \geq 2b$, $c_5 = a - 2b$ and $c_6 = b$. $a - b > a - 2b, b$, so $c_4 > c_5, c_6$, making $c_4$ a sharp peak.
$c_2$ is a sharp peak, so it follows from what we have shown that for some $M \leq 5(13^{13} - 12^{12}) < 14^{14} - 11$, we have that there is some sharp peak $c_M$ such that $c_M \leq 2$. By simply going through all possible cases, it can easily be shown that no matter what the values of $c_{M+1}$ and $c_{M+2}$ are, there will be some $M_0$ with $0 < M_0 - M < 10$ such that $c_{i+k}, c_{i+k+1}$, and $c_{i+k+2}$ are all 1. It follows trivially from here that whenever $m > M_0$, $c_m$ is either 1 or 0.
In particular, since $M_0 < 14^{14} - 3$, we have that $a_{14^{14}} = c_{14^{14}-2} + c_{14^{14}-3}$ is either 0, 1, or 2.
We will now show that $a_{14^{14}} = 1$. Taking the recurrence formula of $\{a_n\}$ mod 2 gives $a_n \equiv a_{n-1} + a_{n-3} \pmod{2}$. Simple computations reveal that $a_n \equiv a_{n+7} \pmod{2}$, giving $a_{14^{14}} \equiv a_7 \equiv 1 \pmod{2}$, from which it follows that $a_{14^{14}} = 1$.
james digol
17.05.2010 03:45
From IMO shortlist booklet: Fro $n \ge 2$, define $s_n=\left | a_n-a_{n-1} \right |$. Then for $n\ge 5$, $a_n=s_{n-1}+s_{n-2}$ and $a_{n-1}=s_{n-2}+s_{n-3}$, and hence $s_n=\left | s_{n-1}-s_{n-3} \right |$. Because $s_n\ge 0$, it follows that if $\max\left \{ s_n,s_{n+1},s_{n+2} \right \}\le T$, then $s_m\le T$ for all $m\ge n$. In particular, the sequence $(s_n)$ is bounded. We now prove the following claim. Claim. If $\max\left \{ s_i,s_{i+1},s_{i+2} \right \}=T\ge 2$ for some $i$, then $\max\left \{ s_{i+6},s_{i+7},s_{i+8} \right \}\le T-1$. Proof. If this were not the case, then $\max\left \{ s_{j},s_{j+1},s_{j+2} \right \}=T\ge 2$ for $j=i,i+1,i+2,\ldots,i+6$. We show by contradiction that this cannot happen. If the claim were false, then for $j=i,i+1$, or $i+2$ the sequence $s_j,s_{j+1},s_{j+2},\ldots$would have the form \[ T,x,y,T-y,\ldots, \] with $0\le x,y\le T$, and $\max\left \{ x,y,T-y \right \}=T$. Hence either $x=T$ or $y=T$ or $y=0$. We consider each case: (a) If $x=T$, then the sequence has the form $T,T,y,T-y,y,\ldots$ Because $\max\left \{ x,y,T-y \right \}=T$ we must have $y=0$ or $y=T$. (b) If $y=0$, then the sequence takes the form $T,x,0,T,T-x,T-x,x,\ldots$ Hence $\max\left \{ x,T-x \right \}=T$, so $x=0$ or $x=T$. (c) If $y=T$, then the sequence is $T,x,T,0,x,T-x,\ldots$ We then have $\max\left \{ x,T-x \right \}=T$, so $x=0$ or $x=T$. In each case we find that both $x$ and $y$ must be either $0$ or $T$. In particular, $T$ must divide each of $s_i,s_{i+1}$ and $s_{i+2}$, which implies that $T$ divides $s_n$ for all $n\ge 2$. However, because $s_2=12^{12}-11^{11}$ and $s_4=11^{11}$ are relatively prime we have a contradiction. This establishes the claim. Now let $M=14^{14}$ and $N=13^{13}$. From the bound $\max\left \{ s_2,s_3,s_4 \right \}\le N$, we use the claim to deduce inductively that $\max\left \{ s_{6N+2},s_{6N+3},s_{6N+4} \right \}=1$. In particular $s_n=0$ or $1$ for $n\ge 6N+2$. Hence $a_n=s_{n-1}+s_{n-2}$ may only take on the values $0, 1$ or $2$ when $n\ge M>6N+4$. In particular, $a_m=0,1$ or $2$. Now the recursion for $a_n$ implies that \[ a_n \equiv (a_{n-1}-a_{n-2})+(a_{n-2}-a_{n-3}) \pmod 2. \] From the initial values for $a_1,a_2$, and $a_3$ it can easiliy shown that modulo $2$, the sequence $(a_n)$ is periodic with period $7$, and that $a_$ is odd. Because $14^{14}$ is a multiple of $7$, we conclude that $a_M=1$.
TheUltimate123
30.08.2020 02:52
Solved with eisirrational, goodbear, Th3Numb3rThr33. The answer is 1. Instead consider the sequence \(x_n=|a_n-a_{n-1}|\), with the property that \(a_n=x_{n-1}+x_{n-2}\). Claim: \(x_n=|x_{n-1}-x_{n-3}|\). Proof. We have \(a_n=x_{n-1}+x_{n-2}\) and \(a_{n-1}=x_{n-2}+x_{n-3}\), so \[x_n=|a_n-a_{n-1}|=\big\lvert(x_{n-1}+x_{n-2})-(x_{n-2}+x_{n-3})\big\rvert=|x_{n-1}-x_{n-3}|.\]\(\blacksquare\) Claim: No three consecutive elements of \((x_n)\) share a common divisor. Proof. If \(x_n\equiv x_{n+1}\equiv x_{n+2}\equiv0\pmod p\), we can verify via \(x_{n+2}=|x_{n-1}+x_{n-1}|\) that \(x_{n-1}\equiv0\pmod p\). Continuing backwards, the entire sequence is divisible by \(p\). However, \(x_2=12^{12}-11^{11}\) and \(x_4=11^{11}\) are relatively prime, contradiction. \(\blacksquare\) Claim: \(\max(x_n,x_{n+1},x_{n+2})\) is nonincreasing, and if \(\max(x_n,x_{n+1},x_{n+2})=A\ge2\), then \(\max(x_{n+6},x_{n+7},x_{n+8})\le A-1\). Proof. The sequence is obviously nonincreasing, since \(x_{n+3}\le\max(x_n,x_{n+2})\). Let \(x_n=A\), \(x_{n+1}=B\), \(x_{n+2}=C\). We will show that if \(x_n=A\ge\max(B,C)\), then \(\max(x_{n+4},x_{n+5},x_{n+6})\le A-1\). Assume \(\max(x_{n+4},x_{n+5},x_{n+6})=A\), so \(\max(B,C,x_{n+3})=A\) as well. This is only possible if \(A=B\), \(A=C\), or \(C=0\). Let's take the three cases: If \(A=B\), then the sequence runs \(A\), \(A\), \(C\), \(A-C\), \(C\), 0, \ldots. For \(\max(x_{n+3},x_{n+4},x_{n+5})=A\) to hold, either \(C=0\) or \(C=A\). By Claim 2, \(A=1\). If \(A=C\), then the sequence runs \(A\), \(B\), \(A\), 0, \(B\), \(A-B\), \ldots. For \(\max(x_{n+3},x_{n+4},x_{n+5})=A\) to hold, either \(B=0\) or \(B=A\). By Claim 2, \(A=1\). If \(C=0\), then the sequence runs \(A\), \(B\), 0, \(A\), \(A-B\), \(A-B\), \(B\), \ldots. In order for \(\max(x_{n+4},x_{n+5},x_{n+6})=A\) to hold, either \(B=0\) or \(B=A\). By claim 2, \(A=1\). \(\blacksquare\) Let \(N=14^{14}\). Observe that \(\max(x_2,x_3,x_4)<13^{13}\), so for \(n>13^{13}/6\), we have \(x_n\in\{0,1\}\). Therefore \(a_N=x_{N-1}+x_{N-2}\in\{0,1,2\}\). It will suffice to show \(a_N\) is odd. Indeed, the sequence \((a_n)\) modulo 2 begins 1, 0, 1, 0, 0, 1, 1, \(\ldots\) and repeats with period 7. Since \(7\mid N\), we have \(a_N\equiv a_7\equiv0\pmod2\). The end.
lorodane
17.05.2021 01:19
TheUltimate123 wrote: Solved with eisirrational, goodbear, Th3Numb3rThr33. The answer is 1. Instead consider the sequence \(x_n=|a_n-a_{n-1}|\), with the property that \(a_n=x_{n-1}+x_{n-2}\). Claim: \(x_n=|x_{n-1}-x_{n-3}|\). Proof. We have \(a_n=x_{n-1}+x_{n-2}\) and \(a_{n-1}=x_{n-2}+x_{n-3}\), so \[x_n=|a_n-a_{n-1}|=\big\lvert(x_{n-1}+x_{n-2})-(x_{n-2}+x_{n-3})\big\rvert=|x_{n-1}-x_{n-3}|.\]\(\blacksquare\) Claim: No three consecutive elements of \((x_n)\) share a common divisor. Proof. If \(x_n\equiv x_{n+1}\equiv x_{n+2}\equiv0\pmod p\), we can verify via \(x_{n+2}=|x_{n-1}+x_{n-1}|\) that \(x_{n-1}\equiv0\pmod p\). Continuing backwards, the entire sequence is divisible by \(p\). However, \(x_2=12^{12}-11^{11}\) and \(x_4=11^{11}\) are relatively prime, contradiction. \(\blacksquare\) Claim: \(\max(x_n,x_{n+1},x_{n+2})\) is nonincreasing, and if \(\max(x_n,x_{n+1},x_{n+2})=A\ge2\), then \(\max(x_{n+6},x_{n+7},x_{n+8})\le A-1\). Proof. The sequence is obviously nonincreasing, since \(x_{n+3}\le\max(x_n,x_{n+2})\). Let \(x_n=A\), \(x_{n+1}=B\), \(x_{n+2}=C\). We will show that if \(x_n=A\ge\max(B,C)\), then \(\max(x_{n+4},x_{n+5},x_{n+6})\le A-1\). Assume \(\max(x_{n+4},x_{n+5},x_{n+6})=A\), so \(\max(B,C,x_{n+3})=A\) as well. This is only possible if \(A=B\), \(A=C\), or \(C=0\). Let's take the three cases: If \(A=B\), then the sequence runs \(A\), \(A\), \(C\), \(A-C\), \(C\), 0, \ldots. For \(\max(x_{n+3},x_{n+4},x_{n+5})=A\) to hold, either \(C=0\) or \(C=A\). By Claim 2, \(A=1\). If \(A=C\), then the sequence runs \(A\), \(B\), \(A\), 0, \(B\), \(A-B\), \ldots. For \(\max(x_{n+3},x_{n+4},x_{n+5})=A\) to hold, either \(B=0\) or \(B=A\). By Claim 2, \(A=1\). If \(C=0\), then the sequence runs \(A\), \(B\), 0, \(A\), \(A-B\), \(A-B\), \(B\), \ldots. In order for \(\max(x_{n+4},x_{n+5},x_{n+6})=A\) to hold, either \(B=0\) or \(B=A\). By claim 2, \(A=1\). \(\blacksquare\) Let \(N=14^{14}\). Observe that \(\max(x_2,x_3,x_4)<13^{13}\), so for \(n>13^{13}/6\), we have \(x_n\in\{0,1\}\). Therefore \(a_N=x_{N-1}+x_{N-2}\in\{0,1,2\}\). It will suffice to show \(a_N\) is odd. Indeed, the sequence \((a_n)\) modulo 2 begins 1, 0, 1, 0, 0, 1, 1, \(\ldots\) and repeats with period 7. Since \(7\mid N\), we have \(a_N\equiv a_7\equiv0\pmod2\). The end. Really cool proof, TheUltimate123, just wanted to note there is a typo at the end, I'm pretty certain it should be $a_{N}\equiv a_{7} \equiv 1\pmod2$.
megarnie
23.06.2023 04:55
Let $ a_1 = 11^{11}, \, a_2 = 12^{12}, \, a_3 = 13^{13}$, and $ a_n = |a_{n - 1} - a_{n - 2}| + |a_{n - 2} - a_{n - 3}|, n \geq 4.$ Determine $ a_{14^{14}}$. We claim that $\boxed{a_{14^{14}} =1}$. Let $x_n = | a_n - a_{n-1} | $ for each $n>1$. The condition becomes \[ a_n = x_{n-1}+ x_{n-2}\] We see that \[x_n = |x_{n-1} - x_{n-3}| \]because $x_n = |a_n - a_{n-1}| = |x_{n-1} - x_{n-3}|$. Now let $y_n = \max(x_n, x_{n+1}, x_{n+2})$. Claim 1: $y_n \ge y_{n+1}$ for all positive integers $n$ (i.e. the sequence $(y_i)$ is nonincreasing). Proof: Suppose $y_{n+1} > y_n$ for some $n$. This implies that $x_{n+3}$ is greater than $x_n, x_{n+1}, x_{n+2}$. Now, $x_{n+3} = |x_n - x_{n+2}|$ is either less than or equal to $x_n$ or less than or equal to $x_{n+2}$, which is a contradiction. $\square$ Claim 2: $x_n, x_{n+1}, x_{n+2}$ cannot share a common integer factor greater than $1$ for $n\ge 2$. Proof: If they did share a common factor of $d$, then $0\equiv x_{n+2} = |x_{n+1} + x_{n-1}|\pmod d$, so $d\mid x_{n-1}$. We may repeat such a process and get $d\mid x_2, x_3, x_4$. We can now compute that $a_4 = 13^{13} - 11^{11}$, so $x_4 = 11^{11}$. Therefore $d$ must be a multiple of $11$, so $d$ cannot divide $12^{12} - 11^{11}$, absurd. $\square$ Claim 3: For any positive integer $m>2$, if $y_m = y_{m+1}$, then either $\max(x_m, x_{m+1}, x_{m+2}) = x_{m+1}, x_{m+2} $, or $x_{m+2} =0$. Proof: Suppose we have $x_m$ is the max (and $x_{m+1}, x_{m+2}$ are less than $x_m$), and $x_{m+2} \ne 0$. Then $x_{m+3} = |x_{m+2} - x_m|$ is less than $x_m$, so the $x_{m+1}, x_{m+2}, x_{m+3}$ are all less than $x_m$, absurd. $\square$ Claim 4: For any positive integer $n\ge 5$, if $y_{n-3} > 1$, then $y_{n-3} > y_{n+3}$. Proof: Suppose we had $y_{n-3} = y_{n+3}$. Then \[y_{n-3} = y_{n-2} = \cdots = y_{n+2} = y_{n+3} = M\]for some $M>1$. Since $y_{n-3} = y_{n-2}$, by claim 3, we have $x_{n-1} = 0, x_{n-2} = M, $ or $x_{n-1} = M$. Case 1: $x_{n-1} = 0$. If $x_{n-3} = M$ and $x_{n-2} = a \le M$, then the sequence starting from $x_{n-3}$ is as follows: \[\left(M, a, 0, M, |a-M|, |a-M|, ||a-M| - M|, \ldots, \right)\]By claim 2, $a$ cannot be equal to $0$ or $M$, so $0<|a-M| < M$. Since $y_{n+1} = M$, we must have $||a-M| - M| = M$, so $|a-M| \in \{0,2M\}$. If $x_{n-3} = a\le M$ and $x_{n-2} = M$, then the sequence starting from $x_{n-3}$ is as follows: \[\left( a, M, 0, a, |a-M|, |a-M| , \ldots, \right) \]By claim 2, $a$ cannot be equal to $0$ or $M$ . Since $y_n = M$, we must have $|a-M| = M$, so $a = 0$ or $2M$, both of which are clearly absurd. Henceforth $x_{n-1} \ne 0$. Case 2: $x_{n-2} = M$. Let $a= x_{n-3}, b = x_{n-1}$ . If $a = M$, then the sequence starting from $x_{n-3}$ is as follows (using the fact that $M > b$): \[(M,M,b, M-b,b, \ldots, ),\]which is absurd since it implies $y_{n-1} =\max(b, M-b, b) < M$. If $b = M$, then the sequence starting from $x_{n-3}$ is as follows (using the fact that $M > a$): \[(a, M, M, M-a, a, M-a, \ldots, ),\]which is absurd since it implies $y_n = \max(M-a, a, M-a) < M$. Now assume $a,b<M$. Note that $b>0$. The sequence is as follows: \[(a, M, b, |a-b|, M - |a-b|, \ldots, ) ,\]since $y_{n-1}= M$, we have $a = b$. However, then the sequence is \[(a, M, a, 0, M, M-a, M-a,\]however by claim 3, since $y_{n+1} = y_{n + 2}$, we have $M-a = 0$ or $a=0$. However, if $a = 0$, we have an obvious contradiction by claim 2, so $a = M$, which is absurd. Case 3: $x_{n-1} = M$. Let $a = x_{n-3}, b = x_{n-2}$. If $a =0 $, the sequence is \[(0, b, M, M, M-b, b, M-b, \ldots ),\]however since $y_{n+1} = M$, we have $\max(M-b, b, M-b) = 0$, so $M\mid b$, which is absurd because then $M$ divides $x_{n-3}, x_{n-2}, x_{n-1}$. If $b=0$, the sequence is $(a, 0, M, M-a, M-a, \ldots, )$, however by claim three we get $a=0$ or $M - a = 0$, both of which are absurd by claim 2. Hence forth we assume that $a,b > 0$ and $b < M$. Then the sequence starting from $x_{n-3}$ is as follows: \[ (a, b, M, M-a, |M-a-b| \ldots, ) \]However, by claim 3, since $y_{n-1} = y_n$, we have $|M - a - b| = 0$ or $M - a = M$, the latter is impossible so $a + b = M$. Now replacing $b$ with $M-a$ we get the sequence is \[(a, M-a, M, M-a, 0, M, a, a, M-a, \ldots, ),\]however then $y_{n+3} = \max(a, a, M-a) < M$, absurd. We have exhausted all cases, so the claim is proven $\square$. So $y_{n+6} \le y_n - 1$, and repeating this iteratively gives that $y_{n + 6k} \le y_n - k$ for $k\le y_n - 1$ and $y_{n + 6k} = 1$ for larger $k$. Now, fix a $11^{11} < c<14^{14} - 2$ such that $y_c = 1$ (this is doable since $y_{2 + 6\cdot (11^{11} - 1) } = 1$) . This means that each of $x_c, x_{c+1}, x_{c+2}$ are all either zero or one, but by claim 2, they cannot all be zero. Therefore using the fact that $x_n = |x_{n-1} - x_{n-3} |$, we have $x_i \in \{0,1\}\forall i\ge c$, so then $a_n = x_{n-1} + x_{n-2}\in \{0,1,2\}$ for all $n>c + 2$. Thus $a_{14^{14}}\in \{0,1,2\}$. However the parity of the sequence $(a_i)$ goes Odd, Even, Odd, Even, Even, Odd, Odd, and then repeats from there, so it has a period of $7$. Therefore $a_{14^{14}} \equiv a_7\pmod 2$, which is odd, therefore $a_{14^{14}} = 1$.
asdf334
20.02.2024 07:06
ding a ling $a_{14^{14}} = 1$ $c_n=|a_{n+1}-a_n|$ $c_n=|c_{n-1}-c_{n-3}|$ Notice that it's bounded above and therefore there is some $N$ where $N$ appears arbitrarily many times in $\{c\}$ and is actually the maximum after a point $c_i$. So take $c_j=N$ which has $j$ arbitrarily large. The idea is that $c_{k}\in \{0,N\}$ for $k>i+O(1)$ (im too lazy to work out the intricacies of the constant factor, it's irrelevant) In any case, working backwards we find $c_i\equiv a_i\equiv 0\pmod N$ always. That means $N=1$. We can also find that $1110100$ is the eventual repeating string for $\{c\}$ by casework, thus $2211101$ is the repeating string for $\{a\}$. Now notice that $a_i\equiv 1\pmod 2$ where $7\mid i$, therefore the answer is $1$.
asdf334
19.05.2024 02:20
just lost whole solution to computer freeze, ill post a sketch Let $d_n=|a_{n+1}-a_n|$. Notice $d_n=|d_{n-1}-d_{n-3}|$. Let $M_n=\max\{d_n,d_{n+1},d_{n+2}\}$. Notice $M_n$ is nonincreasing. Thus it is eventually constant at a value $M$. Now let $d_N=M$ for large $N$. By casework prove that all of $d_{N-1}$, $d_{N-2}$, and $d_{N-3}$ are divisible by $M$. Working backwards we find that $M$ divides any $d_i$. Thus $M\mid \gcd\{d_1,d_2,d_3\}$ and so $M=1$. (Also, we have to show that $N$ is less than $14^{14}$. This is not hard as each decrease of $M_n$ has to occur within some $O(1)$ amount of indices.) Now take modulo $2$, noting that $d_n\equiv d_{n-1}+d_{n-3}\pmod 2$ and each of $d_1$, $d_2$, and $d_3$ is odd. The parity repeats every seven indices, thus \[a_{14^{14}}=d_{7i+4}+d_{7i+5}=0+1=1\]and we are done.
awesomeming327.
09.06.2024 22:18
Let $b_n=|a_n-a_{n-1}|$. Then, $a_n=b_{n-1}-b_{b-2}$ for all $n\ge 4$. Thus, \[b_n=|a_n-a_{n-1}|=|b_{n-1}-b_{n-3}|\]We claim that it is impossible for $b_n$, $b_{n-1}$, $b_{n-2}$ to all be divisible by $p$. If this is possible, then let $k$ be the smallest index for which this is true. Clearly, $k\ge 5$. Then $p\mid b_{k},p\mid b_{k-1}\implies p\mid b_{k-3}$ so $k$ is not minimal, contradiction. Now, note that $c_n=\max{b_n,b_{n-1},b_{n-2}}$ for $n\ge 4$ is an non-increasing sequence. Suppose $c_n=b_{n-2}\ge 2$. If $b_{n-1}<c_n$ and $0<b_n<c_n$ then $b_{n+1}=b_{n-2}-b_{n}$ so $b_{n-1},b_n,b_{n+1}$ are all less than $c_n$, so $c_{n+1}<c_n$. If $b_{n-1}=c_n$ then $0<b_n<c_n$, otherwise our claim is violated. Then, $b_{n+1}=c_n-b_n$ and $b_{n+2}=b_n$ so $c_{n+2}<c_n$. If $b_n=0$ then $b_{n+1}=c_n$, $b_{n+2}=c_n-b_{n-1}$, $b_{n+3}=c_n-b_{n-1}$, and $b_{n+4}=b_{n-1}$ so $c_{n+4}<c_n$. If $b_n=c_n$ then $b_{n+1}=0$, $b_{n+2}=b_{n-1}$, $b_{n+3}=c_n-b_{n-1}$ so $c_{n+3}<c_n$. Therefore, $c_{n+4}<c_{n-2}$ for all $n$ if $c_{n-2}\ge 2$. Thus, $b_{14^{14}-2},b_{14^{14}-1}\in \{0,1\}$ so $a_{14^{14}}\le 2$ so it suffices to show it is odd which is obvious.