Claim 1: If $f$ is bounded, then we are done. Proof: Suppose $M$ is the maximal value of $f$. Let $$S=\{ x | f(x)=M\}$$ Key observation: $S$ is an arithmetic sequence with odd common difference. Proof: We can sort the elements of $S$ as $s_1<s_2<\cdots<$. If $s_{i+1}-s_i$ is even, $P(s_i, \frac{s_{i+1}-s_i}{2})$ yields $M=f(\frac{s_{i+1}+s_i}{2})$, contradicting our sorting order. Hence $s_{i+1}-s_i$ is odd for all $i$. Thus, $s_{i+2}-s_i$ is odd for all $i$, and for size reasons, $s_{i+1}=\frac{s_{i+2}+s_i}{2}$. Let $d$ be the common difference of $S$ and $t$ be its starting term. If $d=1$ we are trivially done. Otherwise, note each of the subsequence $$f(a+dz)_{z\ge 0}$$ (Where $d\nmid a-t$) is upper bounded by $M-1$, and we can induct to see that each of the smaller sequences is also eventually periodic because they do obey the condition in the problem, hence $f$ is eventually periodic. It remains to prove $f$ is bounded. By the same argument on $S$ being arithmetic sequence, $$S_d=\{ x| d\mid f(x)\}$$ Is also an arithmetic sequence. Here is a slick method to finish: let $t$ be the minimum value of $\nu_2(f(x))$. We know $S_{2^{t+1}}$ is an arithmetic sequence. If its common difference is 1, then it is of the form $\mathbb{Z}_{\ge c}$, where $c>1$. However, $P(1,m)$ yields $2^{t+1}|a_{2m+k} | a_k+a_{m+k}$ for all $k,c$, so $S_{2^{t+1}}=\mathbb{N}$, absurd! Therefore, its common difference is greater than 1. Let $S_{2^{t+1}}=a+d\mathbb{Z}_{\ge 0}$, where $d>1$ is odd. Then if $t$ satisfies $d\nmid t-a$, then $f(t), f(t+d), \cdots, f(t+kd)$ all have a $\nu_2$ value of $t$. This implies $f(t+kd) \le \frac{f(t+(k-1)d)+f(t+(k-2)d)}{2}$ by $P(t+(k-2)d, d)$, so $f(t+kd)_{k\ge 0}$ is bounded. We also have $f(n)\le f(n-1)+f(n-2)$ if $n\equiv a(\bmod\; d)$, so $f$ is bounded. The conclusion follows.

To prove $f$ bounded, we can also consider any $n$ with $f(n)>f(i)$ for all $i<n$, then $f(n)\mid f(n-i)+f(n-2i)$, so $f(n)=f(n-i)+f(n-2i)$ for all $2i<n$ Then $f(n-1)=f(n-4)$, $f(n-2)=f(n-8)$, and applying the condition again we see that $f(n-1-3i)\equiv 0 \pmod{f(n-1)}$ and $f(n-2-6i)\equiv 0 \pmod{f(n-2)}$, thus both $f(n-1)$ and $f(n-2)$ are bounded by $\max\{f(1),\cdots, f(6)\}$, and so such $f(n)$ are all bounded.

First, we will show that the sequence is bounded. Suppose the contrary. Call $a_i$ ``peak" if $a_i$ is larger than all previous terms in the sequence. At least one of the subsequences $a_1,a_3,a_5,\dots$ and $a_2,a_4,a_6,\dots$ contains infinitely many peaks; suppose it is the former. Consider a peak $a_{2m+1}=M$. By our assumption, we can choose $M$ arbitrary large. Since $M$ divides $a_1+a_{m+1},a_3+a_{m+2},$ and $a_5+a_{m+3}$, this forces $a_{m+1}=M-a_1,a_{m+2}=M-a_3,a_{m+3}=M-a_5$. We have $a_{m+3}\mid a_{m+1}+a_{m+2}$ so $M-a_5\mid 2M-(a_1+a_3)$. Note that $a_5\mid a_1+a_3$. If $a_5<\frac{a_1+a_3}{2}$, $2(M-a_5)>2M-(a_1+a_3)$ so $M-a_5=2M-(a_1+a_3)$, a contradiction for $M$ large enough. If $a_5=a_1+a_3$, $M-(a_1+a_3)\mid a_1+a_3$, a contradiction for $M$ large enough. Hence, $a_5=\frac{a_1+a_3}{2}$. By similar reasoning, we get $a_{2k+1}=\frac{a_{2k-3}+a_{2k-1}}{2}$ for all $k\ge 2$, implying that $a_1,a_3,a_5,\dots$ is actually a constant sequence, a contradiction. Now, we will show that the sequence is eventually periodic. We have shown that the sequence contains finitely many distinct elements. Without loss of generality, let each element appear infinitely many times (otherwise, we can just remove a `few' first terms). Let $m$ be the largest element. Claim: $m$ must appear in a periodic manner, that is, all terms equal to $m$ are exactly $a_{i},a_{i+d},a_{i+2d},\dots$ for some $i,d\in\mathbb{N}$. Proof: Let $a_i, a_{i+d}$ be the first two terms equal to $m$. Observe that if for some $t,u$ we have $a_t=a_{t+2u}=m$, then the maximality of $m$ along with $a_{t+2u}\mid a_{t}+a_{t+u}$ forces $a_{t+u}=m$. Hence, $d$ must be odd. Suppose the first $k\ge 2$ terms equal to $m$ are $a_i,a_{i+d},\dots,a_{i+(k-1)d}$. Let the next $m$ be $a_{i+e}$. If $i+e$ has the same parity as $i+(k-1)d$, then by our previous observation there must be another $m$ between $a_{i+(k-1)d}$ and $a_{i+e}$, a contradiction. Hence, due to $d$ being odd, $i+(k-2)d$ and $i+e$ have the same parity. Since $a_{i+(k-1)d}$ is the only $m$ between $a_{i+(k-2)d}$ and $a_{i+e}$, this forces $(i+(k-2)d)+(i+e)=2(i+(k-1)d)$ so $a_{i+e}=a_{i+kd}$. The claim thus follows by induction. $\blacksquare$ Call the terms between two consecutive $m$s a `gap'. Since there are finitely many possibilities for each gap, there exist two gaps that are identical. But notice that if we fix the choice of one gap, then all terms following it are uniquely determined due to the maximality of $m$. To see this, suppose we fix the values of the gap $a_{i+kd+1},\dots,a_{i+kd+(d-1)}$, then for each $a_{ld+t}$ where $l>k, 1\le t\le d-1$, we have $m\mid a_{(l+1)d}\mid a_{ld+t}+a_{ld+t-(d-t)}$ which forces $a_{ld+t}=m-a_{ld+t-(d-t)}$. This means $a_{i+(k+1)d+1},a_{i+(k+1)d+2},\dots$ are all fixed. Suppose the two identical gaps are $a_{i+k_1d+1},\dots,a_{i+k_1d+(d-1)}$ and $a_{i+k_2d+1},\dots,a_{i+k_2d+(d-1)}$. By our previous argument, $a_{i+(k_1+1)d+1},a_{i+(k_1+1)d+2},\dots$ and $a_{i+(k_2+1)d+1},a_{i+(k_2+1)d+2},\dots$ must be a copy of each other, as desired.

Solved with megarnie and vsamc. Claim: $\{ a_i \}$ is bounded. Assume FTSOC $a_1,a_3, \dots $ or $a_2, a_4, \dots $ is unbounded. Assume WLOG the former. Take any $a_{2m+1}, a_{2m+3}, a_{2m+5}.$ There are arbitrarily large $k$ where $a_{2k+1}$ is larger than anything before, forcing $a_{m+k+1} = a_{2k+1} - a_{2m+1}, a_{m+k+2} = a_{2k+1} - a_{2m+3}, a_{m+k+3} = a_{2k+1} - a_{2m+5},$ so $$a_{m+k+3} \mid a_{m+k+1} + a_{m+k+2} \implies a_{2k+1} - a_{2m+5} \mid 2a_{2k+1} - a_{2m+1} - a_{2m+3}$$forcing $2a_{2m+5} = a_{2m+1}+a_{2m+3}$ by taking $a_{2k+1}$ arbitrarily large. This forces $a_1,a_3, \dots $ bounded, contradiction. $\square$ Let $M$ be the maximal value in $\{a_i\}$. We prove via induction on $M,$ base case trivial. We claim the sequence $S$ of indices in $\{ a_i \}$ evaluating to $M$ is arithmetic. Let $S$ be $i_1 < i_2 < \dots $ and note $a_{n}, a_{n+2m} = M \implies a_{n+m} = M,$ so any two $i_{k}, i_{k+1}$ have different parities. So $\frac{i_k + i_{k+2}}{2}$ must always be in $S$ for any $k,$ implying it is equal to $i_{k+1}$ as desired. If $S$ has difference $d,$ partition $a_1,a_2,a_3,\ldots$ into sequences of the form $a_{i}, a_{i+d}, \dots.$ One of these always evaluates to $M,$ the others are solved by inductive hypothesis. $\blacksquare$

This problem was proposed by Ching Tak Wing, leader of the Hong Kong team; so happy to see his problem here ^_^ (last time a problem from Hong Kong appeared was already 2014!)

I may have overcomplicated the end... Call an index $i$ beautiful if $a_i>a_k$ for all $k<i$. Note that if an integer $n$ is beautiful, then for all $m<\frac{n}{2}$ we have \[a_n\mid a_{n-m}+a_{n-2m}\implies a_n=a_{n-m}+a_{n-2m}\quad (*)\]Claim : There are only finitely many beautiful indices, i.e. the sequence is bounded. Proof : Suppose the contrary, i.e. that there are infinitely many beautiful indices. By pigeonhole, we can find two beautiful indices $\ell>>k>4$ such that $\ell\equiv k\pmod 2$ and $a_{\ell}>3a_k$. If we let $t=\frac{k+\ell}{2}$, we have by applying $(*)$, \[a_{\ell}=a_k+a_{t}=a_{k-2}+a_{t-1}=a_{k-4}+a_{t-2},\]so that $a_t<a_{t-1}<a_{t-2}$ since $k$ is beautiful. However, we have $a_t\mid a_{t-1}+a_{t-2}$, thus it must be the case that \[a_{t-1}+a_{t-2}\ge 3a_t\iff 3a_k-a_{k-2}-a_{k-4}\ge a_{\ell},\]which is obviously a contradiction. $\square$ This claim allows us to consider the greatest positive integer $C$ that appears infinitely many times in the sequence. We can shift the indices of the sequence (which obviously preserves the divisibility condition), so we might as well suppose that $a_0=C$ and that no non-negative integer $a_i$ with $i\ge 0$ is greater than $C$. We then have a second claim : Claim : There exists an odd positive integer $k$ such that $a_i=C$ iff $k\mid i$. Proof : Suppose $k>0$ is the smallest positive integer such that $a_k=C$. If $k$ is even, then \[a_k\mid a_0+a_{\frac{k}{2}}\implies a_k\mid a_{\frac{k}{2}},\]so that $a_{\frac{k}{2}}=C$, which contradicts the minimality of $k$. Similarly, if we let $\ell$ be the smallest positive integer such that $a_{k+\ell}=C$, then $\ell$ must be odd. It follows that $k+\ell$ is even, so $a_{\frac{k+\ell}{2}}=C$. Since $0<\frac{k+\ell}{2}<k+\ell$, we must have $\frac{k+\ell}{2}=k$, so that $\ell=k$. Continuing with a similar reasoning, we get that the indices $i$ such that $a_i=C$ are exactly the multiples of $k$ by induction, as needed. $\square$ We now prove an other claim : Claim : Let $n$ and $t$ be positive integers such that $nk-4t>0$. We have \[a_{nk-t}=a_{nk-4t}\]Proof : If $k\mid t$, then the result is clear since both terms are just $C$. If not, then neither $t$, $2t$ nor $4t$ is divisible by $k$ (here we use $k$ odd). We thus have that $a_{nk-t}, a_{nk-2t}$ and $a_{nk-4t}$ are all strictly smaller than $C$. In particular, iterating a similar relation as in $(*)$ two times yields \[C=a_{nk}=a_{nk-t}+a_{nk-2t}\]\[C=a_{nk}=a_{nk-2t}+a_{nk-4t},\]and the result follows. $\square$ In particular, if we apply the claim inductively, we get that $a_{nk-t}=a_{nk-4^j\cdot t}$ for all $j$, as long as $nk-4^j\cdot t\ge 0$. This motivates our final claim : Claim : For every integer $e\in \{0,1,2,\ldots,k-1\}$, there exists a positive integer $N_e$ such that the subsequence $(a_n)_{n\equiv e\pmod k}$ is periodic with period $N_e$. Proof : Let $t\in \{0,1,2,\ldots,k-1\}$ be such that $t\equiv -e\pmod k$. We claim that $N_e=t\cdot \left(4^{\phi(k)}-1\right)$ works. Indeed, note that if $m>N_e$ is a positive integer such that $m\equiv e\pmod k$, we can write \[m=nk-t,\]with $n$ being a positive integer. We then have, using our previous observation, \[a_m=a_{nk-t}=a_{nk-4^{\phi(k)}\cdot t}=a_{m-N_e}\]This yields the desired result, since we have $N_e\equiv 0\pmod k$ by Euler Fermat. $\square$ To finish off the problem take $N=\prod_{e} N_e$, for which the sequence is periodic with period $N$. $\blacksquare$

Note that our condition is equivelant to $a_i \mid a_{i-j} + a_{i-2j}$ for all positive integers $i, j$ such that $i > 2j$. Claim: The sequence $a_1, a_2, \dots$ is bounded. Suppose for contradiction that our sequence is unbounded. This means there exists an infinite number of positive integers $i$ such that $a_i > a_j$ for all $i>j$. Consider a sufficiently large such $i$. Observe that $a_{i-j}+a_{i-2j}<2a_i \implies a_{i-j}+a_{i-2j} = a_i$. Assume that $a_{i-1} \geq a_{i-2}$ with the other case being treated similarly. Observe that $a_i=a_{i-1}+a_{i-2}=a_{i-2}+a_{i-4} \implies a_{i-1}=a_{i-4}$. We will now prove using induction that $a_{i-1}=a_{i-3k-1}$ for all $i>3k+1$. Suppose that the result is true for $k-1$ and $k-2$. The condition implies that $a_{i-1}=a_{i-3(k-2)-1} \mid a_{i-3(k-1)-1} + a_{i-3k-1}$ so $a_{i-1} \mid a_{i-3k-1} < a_i$. Since $a_{i-1} \geq \frac{a_i}{2}$, this actually means that $a_{i-1}=a_{3k-1}$. Therefore, $a_i \leq 2 \max(a_1, a_2, a_3)$, a contradiction. $\square$. Let $\alpha$ be the maximum value attained by our sequence infinitely many times and let $\alpha=a_{n_1}=a_{n_2}= \dots$ where $n_1 < n_2 < \dots$ be the terms of our sequence equal to $\alpha$. We prove that the sequence $n_1, n_2, \dots$ eventually forms an arithmetic progression. Let $k$ be a sufficiently large positive integer and let $d=n_k-n_{k-1}, s=n_{k+1}-n_k$. It suffices to show that $s=d$. If $d$ is even, we have $a_{n_k} \mid a_{n_k - \frac{d}{2}}+ a_{n_{k-1}} \implies a_{n_k - \frac{d}{2}} = \alpha$, a contradiction. For the same reason, $s$ must also be odd. Therefore, $n_{k+1}$ and $n_{k-1}$ has the same parity. Consequently, we get $a_{n_{k+1}} \mid a_{n_{k+1}-\frac{s+d}{2}} +a _{n_{k-1}}$ and hence $a_{n_{k+1}-\frac{s+d}{2}} =\alpha$. Combined with the fact that $n_{k-1} < n_{k+1} - \frac{s+d}{2}<n_{k+1}$, this implies that $n_{k+1}-\frac{s+d}{2}=n_k \implies s=d$. $\square$ The rest is easy. Our condition implies that $a_{n_{k+2}} \mid a_{n_{k+1}-i} + a_{n_k-2i} < 2 \alpha \implies \alpha = a_{n_{k+1}-i} + a_{n_k-2i}$ and $a_{n_k} \mid a_{n_k-i} + a_{n_k-2i} < 2\alpha \implies \alpha = a_{n_k-i} + a_{n_k-2i}$, which implies $a_{n_{k+1}-i}=a_{n_k-i}$ for all $i<d$. $\blacksquare$

Basically same as 2018 N6

Let $a_n$ be such that for all $i<n$, $a_i<a_n$. Then, $a_n\mid a_{n-j}+a_{n-2j}$ for all $j<\tfrac{n}{2}$ but $a_{n-j}+a_{n-2j}<2a_n$ implies $a_{n-j}+a_{n-2j}<2a_n$ so $a_{n-j}+a_{n-2j}=a_n$. Now, for all $j<\tfrac{n}{4}$ we have \[a_n=a_{n-j}+a_{n-2j}=a_{n-2j}+a_{n-4j}\implies a_{n-j}=a_{n-4j}\]In particular, $a_{n-1}=a_{n-4}$ and $a_{n-2}=a_{n-8}$. We claim that if for some positive integer $k$, $k\mid a_{i+n}$ and $k\mid a_i$ then $k\mid a_{i-n}$. This is obvious, as $k\mid a_{i+n}\mid a_i+a_{i-n}$. Now, we can use induction to get that $a_{n-1}\mid a_x$ and $a_{n-2}\mid a_y$ for some $x\le 3$ and $y\le 6$ so $a_n=a_{n-1}+a_{n-2}$ is bounded. This implies that the entire sequence is bounded. Let $m$ be the maximum value attained infinitely many times by the sequence $a_i$. Let $n_1<n_2<n_3<\dots$ be all the indices such that $a_{n_i}=m$ for all $m$. For sufficiently large $N$, $a_k\le m$ for all $k\ge N$. Let $n_{M-1}>N$. Let $k\ge M$. Note that if $n_k-n_{k-1}$ is even then $a_{\tfrac{n_k+n_{k-1}}{2}}=m$, which is a contradiction. Similarly, $n_{k+1}-n_{k}$ must also be odd. Now, $n_{k+1}-n_{k-1}$ is even, so $a_{\tfrac{n_{k+1}+n_{k-1}}{2}}=m$ which implies $n_{k}=\tfrac{n_{k+1}+n_{k-1}}{2}$ so the sequence $n_1,n_2,n_3,\dots$ is eventually arithmetic. Furthermore, the common difference $d$ it eventually attains is odd. Now, let $0<i<d$ then $n_{k-1}-2i$ is not another term in the sequence $n$, and neither is $n_k-i$. Since $a_{n_{k-1}-2i}+a_{n_k-i}< 2m$ is a multiple of $m$, it equals to $m$. Similarly, $a_{n_{k}-2i}+a_{n_k-i}=m$ so $a_{n_k-2i}=a_{n_{k}-d-2i}$ so the sequence is eventually periodic with period $d$.

Man this is like 99% Algebra not NT.