IMO2024 Shortlisted Problems

Solution 1. We will show that the eventual period of sequence $\left(b_n\right)$ consists of any fixed number of occurrences of $G$ (possibly zero) followed by a single $A$. We look at the ratios of consecutive terms of the sequence $\left(a_n\right)$. Let $C$ and $D$ be coprime positive integers such that $a_1/a_0=(C+D)/C$. If $b_n=G$ then $a_n/a_{n-1}=a_{n+1}/a_n$. If $b_n=A$ and $a_n/a_{n-1}=(C+kD)/(C+(k-1)D)$ for some positive integer $k$ then $$\frac{a_{n+1}}{a_n}=\frac{2a_n-a_{n-1}}{a_n}=\frac{C+(k+1)D}{C+kD}$$ Thus, by induction, there is a sequence of positive integers $\left(k_n\right)$ for $n⩾1$ which satisfies $a_n/a_{n-1}=\left(C+k_{n}D\right)/\left(C+\left(k_n-1\right)D\right)$ for all positive integers $n$. Moreover, we have $k_1=1$ and $$k_{n+1}=\{\begin{array}{ll}{k}_n,& \text{ if }{b}_n=G\\ k_n+1,& \text{ if }{b}_n=A\end{array}$$ If there are only finitely many values of $n$ such that $b_n=A$ then the problem statement obviously holds (we can choose $d=1$ ). Thus, we may assume that $b_n=A$ for infinitely many $n$. This means that the sequence ( $k_n$ ) attains all positive integer values. Given a value $q⩾1$, denote by $m_q$ the last index where value $q$ occurs, that is, the index such that $k_{m_q}=q$ and $k_{m_q+1}=q+1$. Our aim is to prove that the sequence of differences $\left(m_{q+1}-m_q\right)$ is eventually constant. We first show that it is bounded above. To that end, fix $t⩾1$ (we will choose a suitably large $t$ later on) and consider a sequence $s(t{)}_0,s(t{)}_1,\dots$ defined for $q⩾1$ by $s(t{)}_q=a_{m_q}/(C+qD{)}^t$. We note two properties of $s(t{)}_q$. First, simple algebra gives $$\begin{array}{c}s(t{)}_{q+1}=\frac{a_{m_{q+1}}}{(C+(q+1)D{)}^t}=\frac{a_{m_q}}{(C+(q+1)D{)}^t}{\left(\frac{C+(q+1)D}{C+qD}\right)}^{m_{q+1}-m_q}\\ =\frac{a_{m_q}}{(C+qD{)}^t}{\left(\frac{C+(q+1)D}{C+qD}\right)}^{m_{q+1}-m_q-t}=s(t{)}_q{\left(\frac{C+(q+1)D}{C+qD}\right)}^{m_{q+1}-m_q-t}\end{array}$$ It follows that $$\begin{array}{l}s(t{)}_q>s(t{)}_{q+1}\\ s(t{)}_q=s(t{)}_{q+1}\\ s(t{)}_q<s(t{)}_{q+1}\end{array}\}\text{ if and only if }\{\begin{array}{l}{m}_{q+1}-m_q<t\\ m_{q+1}-m_q=t\\ m_{q+1}-m_q>t\end{array}$$ Second, suppose that $m_{q+1}-m_q⩾t$ for some positive integer $q$. We claim that in that case $s(t{)}_q$ is a positive integer. Indeed, we have $$a_{m_q+t}=a_{m_q}{\left(\frac{C+(q+1)D}{C+qD}\right)}^t,$$ because $k_{m_q+1}=k_{m_q+2}=\cdots =k_{m_q+t}=q+1$. Since $C+(q+1)D$ and $C+qD$ are coprime we have that $$s(t{)}_q=\frac{a_{m_q}}{(C+qD{)}^t}$$ is an integer. We choose $T⩾1$ such that $s(T{)}_1<1$ (which exists since $C+D>1$ ). Then, by induction we can show that $s(T{)}_q<1$ for all $q$. Indeed, since $s(T{)}_q<1$, it is not a positive integer; this means that $m_{q+1}-m_q<T$ by the second property above. Hence by the first property above we have $s(T{)}_{q+1}<s(T{)}_q<1$, as needed. This means that $m_{q+1}-m_q<T$ for all $q$. Thus there is a largest integer $T^{\prime }⩽T$ with the property that an equality $m_{q+1}-m_q=T^{\prime }$ holds for infinitely many values of $q$. Therefore, for all sufficiently large values of $q$ we have the inequality $m_{q+1}-m_q⩽T^{\prime }$, which by the first property implies that the sequence $s\left(T^{\prime }\right)$ is decreasing from some point on. Moreover, we know that the sequence attains infinitely many integer values since there are infinitely many values of $q$ for which we have the equality $m_{q+1}-m_q=T^{\prime }$. As a consequence, the sequence $s\left(T^{\prime }\right)$ is constant from some sufficiently large index $Q$ onwards. This in turn means that the equality $m_{q+1}-m_q=T^{\prime }$ holds for all $q⩾Q$. Note that $b_n=A$ is equivalent to the fact that $n=m_q$ for some integer $q$. Thus, the sequence ( $b_n$ ) is periodic for $n⩾Q$ with period $T^{\prime }$, and the proof is complete.

Solution 2. First, observe that the statement holds immediately if $b_n=G$ for all $n$; otherwise, there must be some $n$ for which $b_n=A$. Without loss of generality, we may assume that $n=1$, as we can translate the sequence without affecting the statement. We define an arithmetic sequence $\left(p_n\right)$ by taking $p_0=a_0/\gcd \left(a_0,a_1\right)$ and $p_1=a_1/\gcd \left(a_0,a_1\right)$. Note that $p_0<p_1$, and hence that $\left(p_n\right)$ is an increasing sequence of positive integers, and also that $p_2=a_2/\gcd \left(a_0,a_1\right)$. We also define a sequence of positive integers $d_n=a_n-a_{n-1}$ and a sequence of positive rational numbers $q_n=a_n/a_{n-1}$. Then the following facts are immediate consequences of the definitions: - if $b_n=G$, then $q_{n+1}=q_n$ and $d_{n+1}=d_n{q}_n$; - if $b_n=A$, then $d_{n+1}=d_n$; - $q_1=p_1/p_0$; - if $b_n=A$ and $q_n=p_i/p_{i-1}$, then $q_{n+1}=p_{i+1}/p_i$. Now, let $k_i$ be the number of integers $n$ for which $b_n=G$ and $q_n=p_i/p_{i-1}$. If some $k_i$ is infinite then $b_n$ is eventually always $G$; otherwise, all values of $k_i$ are nonnegative integers. The sequence of values for $d_n$ can be written as $$d_0,d_0\frac{p_1}{p_0},\dots ,d_0{\left(\frac{p_1}{p_0}\right)}^{k_1},d_0{\left(\frac{p_1}{p_0}\right)}^{k_1}\frac{p_2}{p_1},\dots ,d_0{\left(\frac{p_1}{p_0}\right)}^{k_1}{\left(\frac{p_2}{p_1}\right)}^{k_2},\dots$$ and in particular all terms in this sequence are positive integers. Furthermore, $p_i$ and $p_{i+1}$ are coprime for all $i$, so the following sequence consists entirely of positive integers: $$\begin{array}{rl}{u}_0& =d_0{p}_0^{-k_1}\\ u_1& =d_0{p}_0^{-k_1}{p}_1^{k_1-k_2}\\ u_2& =d_0{p}_0^{-k_1}{p}_1^{k_1-k_2}{p}_2^{k_2-k_3}\\ & ⋮\end{array}$$ We will prove that $k_i$ is eventually constant, which implies that the sequence of $b_n$ is eventually periodic with period consisting of $k$ copies of $G$ followed by an $A$ (where $k$ is that constant value). Observe that either $k_i$ is unbounded, or is bounded with eventual maximum $k$ for some constant $k$. In the second case, let $r_0$ be minimal such that $k_{r_0}=k$; in the first case let $r_0=0$. We will construct an infinite sequence of integers as follows: - If $k_{r_i+1}⩾k_{r_i}$, then $r_{i+1}=r_i+1$ - If $k_{r_i+1}<k_{r_i}$, then $r_{i+1}$ is the minimal positive integer greater than $r_i$ such that $k_{r_{i+1}}⩾k_{r_i}$. Observe that in the second case, such an $r_{i+1}$ must exist by our construction of $r_0$. We claim that $u_{r_{i+1}}⩽u_{r_i}$ with equality only if $k_{r_i+1}=k_{r_i}$ (so $r_{i+1}=r_i+1$ ). Indeed, if $k_{r_i+1}⩾k_{r_i}$ then $$u_{r_{i+1}}=u_{r_i+1}=u_{r_i}{p}_{r_i}^{k_{r_i}-k_{r_i+1}}⩽u_{r_i}$$ with equality if and only if $k_{r_i}=k_{r_i+1}$. Otherwise, we have $$\frac{u_{r_{i+1}}}{u_{r_i}}=p_{r_i}^{k_{r_i}-k_{r_i+1}}{p}_{r_i+1}^{k_{r_i+1}-k_{r_i+2}}\cdots p_{r_{i+1}-1}^{k_{r_{i+1}-1}-k_{r_{i+1}}}$$ so we just need to show that the right hand side is strictly less than 1 . But this follows because $$\begin{array}{rl}{p}_{r_i}^{k_{r_i}-k_{r_i+1}}{p}_{r_i+1}^{k_{r_i+1}-k_{r_i+2}}\cdots p_{r_{i+1}-1}^{k_{r_{i+1}-1}-k_{r_{i+1}}}& <p_{r_i+1}^{k_{r_i}-k_{r_i+2}}{p}_{r_i+2}^{k_{r_i+2}-k_{r_i+3}}\cdots p_{r_{i+1}-1}^{k_{r_{i+1}-1}-k_{r_{i+1}}}\\ & <p_{r_i+2}^{k_{r_i}-k_{r_i+3}}{p}_{r_i+3}^{k_{r_i+3}-k_{r_i+4}}\cdots p_{r_{i+1}-1}^{k_{r_{i+1}-1}-k_{r_{i+1}}}\\ & ⋮\\ & <p_{r_{i+1}-1}^{k_{r_i-k_{r_{i+1}}}}\\ & ⩽1\end{array}$$ where each inequality besides the last follows from the fact that $p_j<p_{j+1}$ and $k_{r_i}>k_j$ for $j<r_{i+1}$, and the last follows from the fact that $k_{r_i}⩽k_{r_{i+1}}$. Finally, the sequence $u_{r_i}$ is an infinite nonincreasing sequence of positive integers so must eventually be constant, yielding the claim.