ISL 2023 N5 wrote: Let $a_1 < a_2 < a_3 < \dots$ be positive integers such that $a_{k + 1}$ divides $2(a_1 + a_2 + \dots + a_k)$ for every $k \ge 1$. Suppose that for infinitely many primes $p$, there exists $k$ such that $p$ divides $a_k$. Prove that for every positive integer $n$, there exists $k$ such that $n$ divides $a_k$. Neat problem. We'll first define $x_k = \frac{2(a_1 + \dots + a_k)}{a_{k + 1}}$ for all $k \ge 1$. By the condition of the problem, $x_k \in \mathbb{N}$ for all $k \ge 1$. Now, we have \[ x_{k + 1} a_{k + 2} = 2(a_1 + \dots + a_{k + 1}) = 2(a_1 + \dots + a_k) + 2a_{k + 1} = (x_k + 2)a_{k + 1} \]and as $a_{k + 1} < a_{k + 2}$ from the condition, for any $k \ge 1$, we thus obtain $x_{k + 1} a_{k + 2} = (x_k + 2)a_{k + 1} < (x_k + 2)a_{k + 2}$ and thus $x_{k + 1} < x_k + 2$ and as $x_{k + 2}, x_k \in \mathbb{N}$, we conclude that $x_{k + 1} \le x_{k} + 1$ for all $k \ge 1$. Let us now suppose that $(x_n)_{n \ge 1}$ is a bounded sequence, i.e. $x_k \le L$ for some positive integer $L$ for all $k \ge 1$. The condition of the problem states that there are infinitely many primes $p$ such that there exists $k$ for which $p \mid a_k$. Take one such prime $p > \max(a_2, L + 2)$. By our assumption, there exists a smallest positive integer $\ell > 2$ such that $p \mid a_{\ell}$, but $p \nmid a_{\ell - 1}$. As we have $x_{k + 1} a_{k + 2} = (x_k + 2)a_{k + 1}$ for all $k \ge 1$, we also have \[ x_{\ell - 1} a_{\ell} = (x_{\ell - 2} + 2)a_{\ell - 1} \implies p \mid x_{\ell - 2} + 2\]and thus $x_{\ell - 2} + 2 \ge p > L + 2 \implies x_{\ell - 2} > L$, which is a contradiction. Therefore, $(x_n)_{n \ge 1}$ is unbounded. We first note that $x_1 = \frac{2a_1}{a_2} < 2 \implies x_1 = 1$. Now, as $(x_n)_{n \ge 1}$ is unbounded, we have that for all $j \ge 1$, there exists $\ell$ such that $x_{\ell + 1} = x_{\ell} + 1 = j + 1$. For such value of $\ell$, we note that \[ a_{\ell + 2}x_{\ell + 1} = a_{\ell + 1}(x_{\ell} + 2) \]and since $\gcd(x_{\ell + 1}, x_{\ell} + 2) = 1$, we obtain that $\frac{a_{\ell + 2}}{x_{\ell} +2} = \frac{a_{\ell + 1}}{x_{\ell} + 1} \in \mathbb{N}$, which implies that $j + 1 \mid a_{\ell + 1}$. Therefore, we have proven that for any $n \ge 2$, there exists $\ell$ for which $n \mid a_{\ell}$, and note that the statement is trivial for $n = 1$ and hence we are done. Motivational Remark. The key idea should be pretty standard: if we have such a strange divisibility condition, writing the quotient and get some inequality about the new sequence, from which we get $x_{k + 1} \le x_k + 1$ for all $k$, and we would like if such sequence $(x_n)_{n \ge 1}$ is unbounded.

Let $S $ be the infinite set of primes dividing some term of the sequence. Also let $a_{k+1} b_k = 2(a_1 + a_2 + \cdots + a_k)$ for $k \ge 1$, and $b_0 = 0$ (clearly $b_k$ is always a nonnegative integer). Since $2(a_1 + a_2 + \cdots + a_k) < k a_{k+1} $, we have $b_k < 2k$. Additionally, by comparing $k=n$ and $k = n + 1$, we also have \[a_{n+2} b_{n + 1} = a_{n+1} (b_n + 2) \ \ \ \ \ \ \ \ \ \ (1) \]for any nonnegative integer $n$. Now we see that $0 < b_1 < 2$, so $b_1 = 1$. Now, since $(a_i)$ is strictly increasing, $(1)$ implies that $b_{n+1} < b_n + 2$ so $b_{n+1} \le b_n + 1$. Case 1: $(b_i)$ is bounded Suppose $b_i \le M$ for some constant $M$. Looking at $(1)$, if $a_{n+2}$ contains a prime factor greater than $M + 2$, it cannot divide $b_n + 2$, so it must divide $a_{n+1}$. Hence for any positive integer $a_x$ and prime greater than $M + 2$ dividing $a_x$ satisfies that the prime also divides $a_{x-1}$. Repeatedly applying this gives that the prime divides $a_1$. Since $S$ is infinite, we get infinitely many primes greater than $M + 2$ dividing values in $(a_i)$, so $a_1$ has infinitely many prime divisors, absurd since $a_1 > 0$. Case 2: $(b_i)$ is unbounded. Claim: $(b_i)$ is surjective and the first occurrence of any positive integer $c$ in $(b_i)$ comes right after $c - 1$. Proof: First we show $(b_i)$ is surjective. Suppose $(b_i)$ never hit $c$. Since $b_1 = 1$ and $(b_i)$ gets arbitrarily large, there exists $n$ with $b_n < c$ and $b_{n+1} > c$, contradiction since $b_{n+1} \le b_n + 1$. Thus, $(b_i)$ is surjective. If the first occurrence of $c$ didn't come right after $c - 1$, then since $b_{n+1} \le b_n + 1$, it must come right after something greater than $c$, implying again that there exists $n$ with $b_n < c$ and $b_{n+1} > c$, absurd. $\square$ Now let $m$ be any positive integer greater than $1$. Setting $n$ to be the smallest $n$ such that $b_{n+1} = m$ gives that $b_n = m - 1$, so $b_n + 2 = m + 1$. Hence $m \mid a_{n+1} (m + 1)\implies m \mid a_{n+1}$, so every positive integer greater than $1$ has a multiple in the sequence (this is trivially true for $1$ also), so we are done.

We set $$b_1 = 0, \hspace{0.5cm} b_{k+1}= \frac{2(a_1 + \cdots + a_k)}{a_{k+1}}.$$ So we get that $a_{k+1}b_{k+1} = a_k(b_k + 2)$. Note that this means $b_{k+1} < b_k + 2$ so the sequence increases by at most $1$ each time. We have that $$a_k = \frac{\prod_{i = 1}^{k}(b_i + 2)}{\prod_{j = 2}^{k+2}b_j}a_1.$$If $(b_i)$ is bounded by some constant $M$, then we get that only primes $p \le M+2$ and $p\mid a_1$ divide some term of the sequence $(a_i)$. Since there are only finitely many of these primes, we get a contradiction. Since the sequence increases by at most $1$ at each step and is unbounded, we can find an index $t$ such that $b_t = n$ and $b_{t-1} = n-1$. However, we get that $a_{t} = \frac{n+1}{n} a_{t-1}$. But since $n$ and $n+1$ are relatively prime, we get that $n \mid a_{t-1}$, so we are done.

Seems like this is also true? Let $a_1<a_2<a_3<\dots$ be positive integers such that there exists a positive integer $N$ such that $a_{k+1}$ divides $2(a_1+a_2+\dots+a_k)$ for every $k\geqslant N$. Suppose that for infinitely many primes $p$, there exists $k$ such that $p$ divides $a_k$. Prove that for every positive integer $n$, there exists infinitely many $k$ such that $n$ divides $a_k$.

Consider the sequence \[b_i=\frac{2(a_1+a_2+\dots+a_i)}{a_i}\in\mathbb{Z}.\]Note that \[b_i=\frac{2(a_1+a_2+\dots+a_i)}{a_i}>\frac{2(a_1+a_2+\dots+a_i)}{a_{i+1}}=\frac{2(a_1+a_2+\dots+a_{i+1})}{a_{i+1}}-2=b_{i+1}-2.\]Therefore, $b_{i+1}\le b_i+1$. Let $p$ be one of the guaranteed infinitely many primes such that $p\nmid a_1$. Let $i$ be the first index for which $p\mid a_i$. Note that $p\mid a_i\Longrightarrow p\mid 2(a_1+a_2+\dots+a_{i-1})$. Since $p\nmid a_{i-1}$, we have $p\mid b_{i-1}$. Thus $b_i$ contains arbitrarily large terms, so since $b_{i+1}\le b_i+1$, $b_i$ contains every sufficiently large positive integer. So let $n$ be sufficiently large and let $i$ be the first index for which $b_i=n$ and $b_{i+1}=n+1$. Then \[\frac{2(a_1+a_2+\dots+a_i)}{a_{i+1}}=n-1.\]If $x=2(a_1+a_2+\dots+a_i)$, we have \[x=na_i=(n-1)a_{i+1}.\]Since $\gcd(n,n-1)=1$, we indeed have $n\mid a_{i+1}$. For the small $n$, just choose a sufficiently large multiple of it, which will divide one of the terms in the sequence. $\blacksquare$

For all positive integers $i$, let $s_i = a_1 + \cdots + a_i$. By the divisibility condition, there is a sequence of positive integers $m_1, m_2, \dots$ such that $a_{i+1} = \frac{2s_i}{m_i}$ for all $i$. Since $a_2$, being divisible by $2a_1$ yet greater than $a_1$, must equal $2a_1$, we must have $m_1 = \frac{2a_1}{a_2} = 1$. Now, for all $i \ge 2$, we may compute \begin{align*} \frac{a_{i+1}}{a_i} &= \frac{2s_i}{m_i a_i} \\ &= \frac{2(s_{i-1} + a_i)}{m_i a_i} \\ &= \frac{2s_{i-1}}{m_i a_i} + \frac{2}{m_i} \\ &= \frac{2s_{i-1} m_{i-1}}{2s_{i-1} m_i} + \frac{2}{m_i} \\ &= \frac{m_{i-1} + 2}{m_i}. \end{align*}Since $a_{i+1} > a_i$, this ratio is greater than $1$, so $m_{i-1} + 2 > m_i$. Since $m$ consists of integers, this implies $m_i \le m_{i-1} + 1$. We now claim that $m$ is unbounded; suppose not. Then, since for all $i \ge 2$, \[ a_i = a_2 \prod_{j=3}^i \frac{m_{j-2} + 2}{m_{j-1}} \]and the numerator of the fractions in the product is bounded, the prime factors of $a_i$ are bounded as well, contradicting the fact that the $a_i$ collectively have infinitely many distinct prime factors. Suppose that for some $n > 1$, there exists $i$ such that $m_i = n$. Consider the smallest $j$ such that $m_j \ge n$; since $m_1 = 1$, we must have $j \ge 2$. Then $m_{j-1} \ge m_j - 1 \ge n-1$, but if $m_{j-1} \ge n$ then $j$ would not be minimal. Therefore $m_{j-1} = n-1$ and $m_j = n$, and $n-1$ occurs in $m$ as well. Since $m$ is unbounded, this implies that all $n$ occurs in $m$, and moreover, for all $n > 1$, there exists $j > 1$ such that $m_{j-1} = n-1$ and $m_j = n$. Then \[\frac{a_{j+1}}{a_j} = \frac{m_{j-1} + 2}{m_j} = \frac{n+1}{n},\]and since $\frac{n+1}{n}$ is in lowest terms, $a_j$ must be a multiple of $n$. This is exactly what the problem asks for.

Define \[b_k := \frac{2(a_1 + \dots + a_k)}{a_{k+1}}.\]We have \[2 + \frac{2(a_1 + \dots + a_k)}{a_{k+1}} = \frac{2(a_1 + \dots + a_{k+1})}{a_{k+1}} > \frac{2(a_1 + \dots + a_{k+1})}{a_{k+2}}, \]so $b_k \leq b_{k-1} + 1$. We can rewrite the equation relating $a_i$ and $b_i$ as \[a_{k+1} = \tfrac{2}{b_k} \cdot (a_1 + \dots + a_k) = a_k \cdot \left( \frac{b_{k-1} + 2}{b_k} \right).\]The fact that infinitely many primes divide some value in $a_i$ tells us that $b_i$ is unbounded. So, for each integer $n$, there exists some $i$ such that $b_{i-1} = n-2$ and $b_i = n-1$. When we plug this $i$ into our recurrence, we get $a_{i+1} = a_i \cdot \tfrac{n}{n-1}$, so $a_{i+1}$ is a multiple of $n$.

Nice problem, same solution as everyone else, worth noticing that this looks like this Tournament Of Towns problem where a similar logic is used Tournament Of Towns wrote: Let $a_1<a_2<a_3<\dots$ be positive integers such that $a_{k+1}$ divides $a_1+a_2+\dots+a_k$ for every $k\geqslant N$. Show that $a_{n+1} = a_1+a_2+\dots+a_k$ for all $n > N_0$ for some $N_0$.

kingu wrote: Nice problem, same solution as everyone else, worth noticing that this looks like this Tournament Of Towns problem where a similar logic is used Tournament Of Towns wrote: Let $a_1<a_2<a_3<\dots$ be positive integers such that $a_{k+1}$ divides $a_1+a_2+\dots+a_k$ for every $k\geqslant N$. Show that $a_{n+1} = a_1+a_2+\dots+a_k$ for all $n > N_0$ for some $N_0$. And this problem is the same as was on Malaysia contest.

This problem is quite nice, and I could see it standing as an IMO 2/5 (the only problem for which I could confidently say so in the N1-N7 range). We may assume that $a_1 = 1$. We assign a positive integer $x_k \geq 1$ for each $k$ such that \[x_k a_k = 2(a_1+a_2+\cdots+a_{k-1}).\]For a prime $p$, let $k$ be the smallest index such that $p \mid a_1+a_2+\cdots+a_k$. Observe that this is equivalent to \[\left(\frac{x_k+2}{x_k}\right)(a_1+a_2+\cdots+a_{k-1}) = a_1+a_2+\cdots+a_{k-1} + a_k \equiv 0 \pmod p.\]By minimality of $k$, we must have $x_k \equiv -2 \pmod p$. The main claim is the following: Claim: The sequence $\{x_i\}$ does not ``jump"; i.e. if $x_k = N$ for some positive integer $N$, for any $n < N$ there is an index $r$ such that $x_r = n$. Proof: The proof requires the following sub-lemma: Lemma: If $x_k \geq m$ for some index $m$, then $x_{k-1} \geq m-1$. Proof: If $x_k \geq m$, it follows that $ma_k \leq 2(a_1+a_2+\cdots+a_{k-1})$. So \[ma_{k-1} < ma_k \leq 2(a_1+a_2+\cdots+a_{k-1})\]i.e. $(m-2) a_{k-1} < 2(a_1+a_2+\cdots+a_{k-2})$, or $x_{k-1} \geq m-1$. $\blacksquare$ Suppose for the sake of contradiction now that there is no index $r$ with $x_r = n$. The lemma applied inductively implies $x_{k-N+n} \geq n$, thus $x_{k-N+n} \geq n+1$. Then $x_{k-N+n-1} \geq n$, so $x_{k-N+n-1} \geq n+1$, and so on. Inductively, $x_{k-N+n-i} \geq n+1$ for all $i$, which is impossible as $x_1 = 1 < n+1$. $\blacksquare$ Now for any positive integer $N$, pick a $p$ such that $p > 2N$ and some $a_k$ is divisible by $p$. It follows that $p \mid a_1+a_2+\cdots+a_{k-1}$, so $x_k \geq p-2 > N$; thus the lemma implies there is an $r$ with $x_r = N - 2$ and $x_{r+1} = N-1$. Thus, \[a_1+a_2+\cdots+a_r =\left(\frac N{N-2}\right)(a_1+a_2+\cdots+a_{r-1}) \equiv 0 \pmod N\]as $x_r \mid a_1+a_2+\cdots+a_{r-1}$. But \[a_1+a_2+\cdots+a_{r+1} = \left(\frac{N+1}{N-1}\right) (a_1+a_2+\cdots+a_r) \equiv 0 \pmod N\]still, so $N$ divides $a_{r+1}$, as needed.

Let \[b_{k+1}=\frac{2(a_1+\dots+a_k)}{a_{k+1}}\]And see that we have \[a_{k+1}b_{k+1}=a_k(b_k+2) \iff \frac{b_k+2}{b_{k+1}}=\frac{a_{k+1}}{a_k}>1 \implies b_k+1 \geq b_{k+1}\]This is the crucial claim. Claim: The sequence $(b_k)_{k \geq 1}$ takes all positive integer values except some finite number of them. Proof: Let $k=i+1$ be the smallest index for which a prime $p$ divides $a_k$. And so \[p \mid a_{i+1}b_{i+1}=a_i(b_i+2) \implies p \mid b_i+2 \implies b_i \geq p-2\]Since there are infinite such primes we are done, by discrete IVT. $\square$ Let $N$ be a large enough number and let $k=K+1$ be the smallest index for which $b_k=N$ and so we have $b_{K+1}=b_K+1$; and also \[b_{K+1}a_{K+1}=(b_{K+1}+1)a_K \implies N \mid a_K\]And so we are done. Remark: Similar idea to Chinese National Olympiad 2020/5.