IMO2024 Shortlisted Problems

Answer: The only such sequences are $a_n=n+C$, where $C$ is a nonnegative integer.

## Common remarks. - Denote by $a_{[i,j]}$ the subsequence $a_i,a_{i+1},\dots ,a_j$. - Without loss of generality, in each solution we suppose $p<q$. It can be convenient to treat the case where $p=1$ separately. - The problem can also be posed for sequences of arbitrary integers (rather than positive). Refer to the comment after Solution 1 for a proof.

Solution 1. Let $k=\lceil \frac{q}{p}\rceil$. Note that $k⩾2$.

Lemma 1. If $i,j$ and $m$ are positive integers such that $|i-j|⩽mp$ then $\left|a_i-a_j\right|⩽mp$.

Proof. By the given condition, if $|i-j|⩽p$ then $\left|a_i-a_j\right|⩽p$. So the lemma follows from induction on $m$ and the triangle inequality.

Lemma 2. For a fixed $n$, suppose that $a_i$ is minimal over $i⩾n$. Then $i⩽n+p-1$.

Proof. Suppose for contradiction that $i⩾n+p$. Then $\min \left(a_{[i-p,i+q-p]}\right)=a_i$. Since $q-p⩽(k-1)p$, it follows from Lemma 1 that $\max \left(a_{[i-p,i+q-p]}\right)⩽a_i+(k-1)p<a_i+q$, which is a contradiction.

Lemma 3. For a fixed $n>q$, suppose that $a_i$ is maximal over $i⩽n$. Then $i⩾n-p+1$.

Proof. Suppose $a_j$ is minimal over $j⩾n-q$. Then by Lemma $2,j⩽n-q+p-1$. So $\min \left(a_{[n-q,n]}\right)=a_j$ and $a_i⩾\max \left(a_{[n-q,n]}\right)$, which implies that $a_i⩾a_j+q$.

Lemma 2 also implies that if $j⩾n$ then $a_j⩾\min \left(a_{[n,n+p]}\right)$. So if $i<j$, then we have $a_j⩾a_i-p$, which contradicts $a_i⩾a_j+q$. Hence we must have $i>j$.

The above inequality also gives $\left|a_i-a_j\right|⩾q>(k-1)p$, so by Lemma 1 it follows that $|i-j|>(k-1)p$. Therefore $i>j+(k-1)p⩾n-q+(k-1)p⩾n-p+1$.

Let $b_n$ be the minimal value of $a_i$ for $i⩾n$. By Lemma 2, $b_{n+p}>b_n$ for all $n$. Hence $b_n=\min \left(a_{[n,n+p]}\right)=\min \left(a_{[n,n+q]}\right)$. Let $c_n$ be the maximal value of $a_i$ for $i⩽n$. By Lemma 3, $c_{n-p}>c_n$ for all $n>q$. Hence $c_n=\max \left(a_{[n-p,n]}\right)=\max \left(a_{[n-q,n]}\right)$ for $n>q$.

So if $n>q$ then $b_n=c_{n+p}-p=c_{n+q}-q$. So for $n>q$ we get $b_{n+q-p}+p=c_{n+q}=b_n+q$, and hence $b_{n+q-p}=b_n+q-p$.

Next note that $b_{n+p}⩽a_{n+p}⩽b_n+p$. So $b_{n+p}-b_n⩽p$ for all $n>q$, and iterating this ($q-p$) times gives $b_{n+p(q-p)}-b_n⩽p(q-p)$. But using $b_{n+q-p}=b_n+q-p$ gives $b_{n+p(q-p)}-b_n=p(q-p)$. Since equality occurs, we must have $b_{n+p}=b_n+p$.

So for $n>q,b_{n+p}=b_n+p$ and $b_{n+q-p}=b_n+q-p$. Since $p$ and $q-p$ are coprime, $b_{n+1}=b_n+1$ for all $n>q$. The only way for $b_n$ and $b_{n+1}$ to be different is if $b_n=a_n$, so we deduce that $a_{n+1}=a_n+1$ and there is a constant $C$ such that $a_n=n+C$ for all $n>q$.

Finally, suppose $a_n=n+C$ for all $n⩾N$. Then $p=\max \left(a_{N-1},N+C+p-1\right)-\min \left(a_{N-1},N+C\right)$. So $a_{N-1}=N+C+p$ or $N+C-1$. Similarly, $a_{N-1}=N+C+q$ or $N+C-1$. Hence $a_{N-1}=N+C-1$. So, by induction, we have $a_n=n+C$ for all positive integers $n$. Since $a_1⩾1,C$ is a nonnegative integer.

It is trivial to check that $a_n=n+C$ satisfies the given condition.

---

Alternative solution.

For $n,x⩾1$, let the $x$-width of $n$ be $\max \left(a_{[n,n+x]}\right)-\min \left(a_{[n,n+x]}\right)$. We call a positive integer $x$ good if the $x$-width of $n$ is less than or equal to $x$ for all sufficiently large $n$, and we call $x$ very good if the $x$-width of $n$ is equal to $x$ for sufficiently large $n$.

Lemma 1. If $p^{\prime }$ is good and $q^{\prime }$ is very good with $p^{\prime }<q^{\prime }<2p^{\prime }$, then $2p^{\prime }-q^{\prime }$ is also good.

Proof. Note that $0<q^{\prime }-p^{\prime }<p^{\prime }<q^{\prime }$. Let $n$ be a sufficiently large positive integer. Then for $k\in [n+q^{\prime }-p^{\prime },n+p^{\prime }]$, we have $a_k⩾\max \left(a_{[n,n+p^{\prime }]}\right)-p^{\prime }$ and $a_k⩾\max \left(a_{[n+q^{\prime }-p^{\prime },n+q^{\prime }]}\right)-p^{\prime }$ since $p^{\prime }$ is good, which shows $a_k⩾\max \left(a_{[n,n+q^{\prime }]}\right)-p^{\prime }$. Similarly we get $a_k⩽\min \left(a_{[n,n+q^{\prime }]}\right)+p^{\prime }$.

Therefore, for all $k\in [n+q^{\prime }-p^{\prime },n+p^{\prime }]$ we have $a_k\in [\max \left(a_{[n,n+q^{\prime }]}\right)-p^{\prime },\min \left(a_{[n,n+q^{\prime }]}\right)+p^{\prime }]$. Thus, the $(2p^{\prime }-q^{\prime })$-width of $n+q^{\prime }-p^{\prime }$ is at most $(\min \left(a_{[n,n+q^{\prime }]}\right)+p^{\prime })-(\max \left(a_{[n,n+q^{\prime }]}\right)-p^{\prime })=2p^{\prime }-q^{\prime }$. The lemma follows.

Lemma 2. Let $p^{\prime }$ be a good number and $q^{\prime }$ a very good number with $p^{\prime }<q^{\prime }$. For sufficiently large $n$, take $s,t\in [n,n+q^{\prime }]$ such that $\min \left(a_{[n,n+q^{\prime }]}\right)=a_s$ and $\max \left(a_{[n,n+q^{\prime }]}\right)=a_t$. Then $s\in [n,n+p^{\prime }]$ and $t\in [n+q^{\prime }-p^{\prime },n+q^{\prime }]$.

Proof. Lemma 2 and Lemma 3 from Solution 1 hold with $p$ and $q$ replaced by $p^{\prime }$ and $q^{\prime }$ by similar arguments. We can deduce the statement about $s$ from Lemma 2 of Solution 1. We can deduce the statement about $t$ from Lemma 3 of Solution 1.

Lemma 3. If $p^{\prime }$ is good and $q^{\prime }$ is very good with $2p^{\prime }<q^{\prime }$, then there exists a positive integer $r$ such that for all sufficiently large $n$, we have $a_{n+r}-a_n⩾r$.

Proof. Let $r=q^{\prime }-2p^{\prime }$, and let $s$ and $t$ be as defined in Lemma 2. Then consider the identity $$\left(a_t-a_{n+q^{\prime }-p^{\prime }}\right)+\left(a_{n+p^{\prime }+r}-a_{n+p^{\prime }}\right)+\left(a_{n+p^{\prime }}-a_s\right)=a_t-a_s=q^{\prime }$$ By Lemma 2, we have $s\in [n,n+p^{\prime }]$ and $t\in [n+q^{\prime }-p^{\prime },n+q^{\prime }]$, so $a_{n+p^{\prime }}-s⩽p^{\prime }$ and $a_t-a_{n+q^{\prime }-p^{\prime }}⩽p^{\prime }$. Combining these, we get $a_{n+p^{\prime }+r}-a_{n+p^{\prime }}⩾q^{\prime }-2p^{\prime }=r$. This proves that $a_{n+r}-a_n⩾r$ for sufficiently large $n$.

Lemma 4. Suppose $(p,q)\ne (1,2)$. Then there exists a good number $p^{\prime }$ such that $2p^{\prime }<q$.

Proof. Let $p^{\prime }$ be the smallest good positive integer. Note that $p$ is good, so $p^{\prime }$ exists and is less than $q$.

Suppose for contradiction that $2p^{\prime }⩾q$. If $2p^{\prime }>q$, then by Lemma 1, $2p^{\prime }-q$ is a good number strictly less than $p^{\prime }$, which contradicts minimality of $p^{\prime }$. If $2p^{\prime }=q$, then $p^{\prime }<p<2p^{\prime }$. So we can apply Lemma 1 with $q_0=p$ to get that $2p^{\prime }-p$ is a good number that is strictly less than $p^{\prime }$, which again contradicts minimality.

If $(p,q)=(1,2)$ then the problem is easily solved. Otherwise, Lemmas 3 and 4 combined give us some $r>0$ such that $a_{n+r}-a_n⩾r$ for $n$ sufficiently large.

By iterating, we get $a_{n+pr}-a_n⩾pr$ for all sufficiently large $n$, and hence it follows that $a_{n+p}-a_n=p$. Similarly we get $a_{n+q}-a_n=q$. As $p$ and $q$ are coprime, we deduce that $a_{n+1}-a_n=1$ for sufficiently large $n$. Thus we get $a_n=n+C$ for sufficiently large $n$, and we can conclude by the same argument as Solution 1.