Determine all positive integers $N$ for which there exists a strictly increasing sequence of positive integers $s_{0}<s_{1}<s_{2}<\cdots$ satisfying the following properties:
- the sequence $s_{1}-s_{0}, s_{2}-s_{1}, s_{3}-s_{2}, \ldots$ is periodic; and
- $s_{s_{n}}-s_{s_{n-1}} \leq N<s_{1+s_{n}}-s_{s_{n-1}}$ for all positive integers $n$.
■ Answer. All $N$ such that $t^{2} \leq N<t^{2}+t$ for some positive integer $t$.
ब Solution 1 (local). If $t^{2} \leq N<t^{2}+t$ then the sequence $s_{n}=t n+1$ satisfies both conditions. It remains to show that no other values of $N$ work.

Define $a_{n}:=s_{n}-s_{n-1}$, and let $p$ be the minimal period of $\left\{a_{n}\right\}$. For each $k \in \mathbb{Z}_{\geq 0}$, let $f(k)$ be the integer such that
$$
s_{f(k)}-s_{k} \leq N<s_{f(k)+1}-s_{k} .
$$

Note that $f\left(s_{n-1}\right)=s_{n}$ for all $n$. Since $\left\{a_{n}\right\}$ is periodic with period $p, f(k+p)=f(k)+p$ for all $k$, so $k \mapsto f(k)-k$ is periodic with period $p$. We also note that $f$ is nondecreasing: if $k<k^{\prime}$ but $f\left(k^{\prime}\right)<f(k)$ then
$$
N<s_{f\left(k^{\prime}\right)+1}-s_{k^{\prime}}<s_{f(k)}-s_{k} \leq N,
$$
which is absurd. We now claim that
$$
\max _{k}(f(k)-k)<p+\min _{k}(f(k)-k) .
$$

Indeed, if $f\left(k^{\prime}\right)-k^{\prime} \geq p+f(k)-k$ then we can shift $k$ and $k^{\prime}$ so that $0 \leq k-k^{\prime}<p$, and it follows that $k \leq k^{\prime} \leq f\left(k^{\prime}\right)<f(k)$, violating the fact that $f$ is nondecreasing. Therefore $\max _{k}(f(k)-k)<p+\min _{k}(f(k)-k)$, so $f(k)-k$ is uniquely determined by its value modulo $p$. In particular, since $a_{n}=f\left(s_{n-1}\right)-s_{n-1}, a_{n}$ is also uniquely determined by its value modulo $p$, so $\left\{a_{n} \bmod p\right\}$ also has minimal period $p$.
Now work in $\mathbb{Z} / p \mathbb{Z}$ and consider the sequence $s_{0}, f\left(s_{0}\right), f\left(f\left(s_{0}\right)\right), \ldots$. This sequence must be eventually periodic; suppose it has minimal period $p^{\prime}$, which must be at most $p$. Then, since
$$
f^{n}\left(s_{0}\right)-f^{n-1}\left(s_{0}\right)=s_{n}-s_{n-1}=a_{n},
$$
and $\left\{a_{n} \bmod p\right\}$ has minimal period $p$, we must have $p^{\prime}=p$. Therefore the directed graph $G$ on $\mathbb{Z} / p \mathbb{Z}$ given by the edges $k \rightarrow f(k)$ is simply a $p$-cycle, which implies that the map $k \mapsto f(k)$ is a bijection on $\mathbb{Z} / p \mathbb{Z}$. Therefore, $f(k+1) \neq f(k)$ for all $k$ (unless $p=1$, but in this case the following holds anyways), hence
$$
f(k)<f(k+1)<\cdots<f(k+p)=f(k)+p .
$$

This implies $f(k+1)=f(k)+1$ for all $k$, so $f(k)-k$ is constant, therefore $a_{n}=$ $f\left(s_{n-1}\right)-s_{n-1}$ is also constant. Let $a_{n} \equiv t$. It follows that $t^{2} \leq N<t^{2}+t$ as we wanted.

『 Solution 2 (global). Define $\left\{a_{n}\right\}$ and $f$ as in the previous solution. We first show that $s_{i} \not \equiv s_{j}(\bmod p)$ for all $i<j<i+p$. Suppose the contrary, i.e. that $s_{i} \equiv s_{j}$ $(\bmod p)$ for some $i, j$ with $i<j<i+p$. Then $a_{s_{i}+k}=a_{s_{j}+k}$ for all $k \geq 0$, therefore $s_{s_{i}+k}-s_{s_{i}}=s_{s_{j}+k}-s_{s_{j}}$ for all $k \geq 0$, therefore
$$
a_{i+1}=f\left(s_{i}\right)-s_{i}=f\left(s_{j}\right)-s_{j}=a_{j+1} \quad \text { and } \quad s_{i+1}=f\left(s_{i}\right) \equiv f\left(s_{j}\right)=s_{j+1} \quad(\bmod p) .
$$

Continuing this inductively, we obtain $a_{i+k}=a_{j+k}$ for all $k$, so $\left\{a_{n}\right\}$ has period $j-i<p$, which is a contradiction. Therefore $s_{i} \not \equiv s_{j}(\bmod p)$ for all $i<j<i+p$, and this implies that $\left\{s_{i}, \ldots, s_{i+p-1}\right\}$ forms a complete residue system modulo $p$ for all $i$. Consequently we must have $s_{i+p} \equiv s_{i}(\bmod p)$ for all $i$.
Let $T=s_{p}-s_{0}=a_{1}+\cdots+a_{p}$. Since $\left\{a_{n}\right\}$ is periodic with period $p$, and $\{i+1, \ldots, i+k p\}$ contains exactly $k$ values of each residue class modulo $p$,
$$
s_{i+k p}-s_{i}=a_{i+1}+\cdots+a_{i+k p}=k T
$$
for all $i, k$. Since $p \mid T$, it follows that $s_{s_{p}}-s_{s_{0}}=\frac{T}{p} \cdot T=\frac{T^{2}}{p}$. Summing up the inequalities
$$
s_{s_{n}}-s_{s_{n-1}} \leq N<s_{s_{n}+1}-s_{s_{n-1}}=s_{s_{n}}-s_{s_{n-1}}+a_{s_{n}+1}
$$
for $n \in\{1, \ldots, p\}$ then implies
$$
\frac{T^{2}}{p}=s_{s_{p}}-s_{s_{0}} \leq N p<\frac{T^{2}}{p}+a_{s_{1}+1}+a_{s_{2}+1}+\cdots+a_{s_{p}+1}=\frac{T^{2}}{p}+T,
$$
where the last equality holds because $\left\{s_{1}+1, \ldots, s_{p}+1\right\}$ is a complete residue system modulo $p$. Dividing this by $p$ yields $t^{2} \leq N<t^{2}+t$ for $t:=\frac{T}{p} \in \mathbb{Z}^{+}$.
Remark (Author comments). There are some similarities between this problem and IMO 2009/3, mainly that they both involve terms of the form $s_{s_{n}}$ and $s_{s_{n}+1}$ and the sequence $s_{0}, s_{1}, \ldots$ turns out to be an arithmetic progression. Other than this, I don't think knowing about IMO 2009/3 will be that useful on this problem, since in this problem the fact that $\left\{s_{n+1}-s_{n}\right\}$ is periodic is fundamentally important.
The motivation for this problem comes from the following scenario: assume we have boxes that can hold some things of total size $\leq N$, and a sequence of things of size $a_{1}, a_{2}, \ldots$ (where $a_{i}:=s_{i+1}-s_{i}$ ). We then greedily pack the things in a sequence of boxes, 'closing' each box when it cannot fit the next thing. The number of things we put in each box gives a sequence $b_{1}, b_{2}, \ldots$. This problem asks when we can have $\left\{a_{n}\right\}=\left\{b_{n}\right\}$, assuming that we start with a sequence $\left\{a_{n}\right\}$ that is periodic.
(Extra motivation: I first thought about this scenario when I was pasting some text repeatedly into the Notes app and noticed that the word at the end of lines are also (eventually) periodic.)