Let $a_1<a_2$ be two given integers. For any integer $n\ge 3$, let $a_n$ be the smallest integer which is larger than $a_{n-1}$ and can be uniquely represented as $a_i+a_j$, where $1\le i<j\le n-1$. Given that there are only a finite number of even numbers in $\{a_n\}$, prove that the sequence $\{a_{n+1}-a_{n}\}$ is eventually periodic, i.e. that there exist positive integers $T,N$ such that for all integers $n>N$, we have \[a_{T+n+1}-a_{T+n}=a_{n+1}-a_{n}.\]
Problem
Source: 2012 China TST Test 2 p3
Tags: pigeonhole principle, combinatorics proposed, combinatorics
23.04.2012 12:15
This problem is quite similar with Problem 2, VN TST 2000: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=802453&sid=91b6224b033f5c01474d9e3a2a13cd1d#p802453
23.04.2012 12:17
Let $a_n$ is odd when n > N. In that case for sufficiently large n, if $a_n = a_k + a_{\ell},\, k<\ell $ then $k \leq N$, which implies: (1) $k \leq N \, \Rightarrow \, a_{\ell} \geq a_n - N \, \Rightarrow \, \ell \geq n-N $ (1) means that $a_n$ depends only on the preceding $N$ members of the sequence (and on the first $N$ ones). Another observations based on (1) is: (2) if $k<\ell$ are both sufficiently large and $a_{\ell + i} - a_{k+i} = d,\, i=1,2,\ldots,N$ then $a_{\ell + N +1}-a_{k+N+1}=d$. (3) For sufficiently large $n$ we have $a_{n+1}-a_n \leq a_N$ Now it remains only the routine part of the work. Let $f: \mathbb{N}^N \to \mathbb{N}^N:\, (x_1,x_2,\ldots,x_N) \mapsto (0,x_2-x_1,x_3-x_1,\ldots,x_N - x_1) $ If $f(a_n,a_{n+1},\ldots,a_{n+N-1})=(b_1,b_2,\ldots,b_N) \, \Rightarrow \, b_i < (N-1)a_N,\,i=1,2,\ldots, N $ ( from (3) ), so now we apply pigeonhole and get that there exist $n,\, T$ such that $f(a_{n+T},a_{n+T+1},\ldots, a_{n+T+N-1})= f(a_{n},a_{n+1},\ldots, a_{n+N-1})$. Here we can assume $n$ is large enough. This means: $a_{n+T+i}-a_{n+i}=d,\, i=0,1,\ldots,N-1$. Now (2) yields $a_{n+T+N}-a_{n+N}=d$, so step by step we get $a_{m+T}-a_m= d,\, \forall m\geq n \, \Rightarrow \, \forall m \geq n,\, a_{m+1+T}-a_{m+T} = a_{m+1} -a_m$.
23.04.2012 17:05
The sequence $\{a_n\}_{ n \ge 1}$ contains only finitely many even numbers, let them be $a_{i_1} \le a_{i_2} \le ... \le a_{i_m}$. There exists $N$ such that for all $r\ge N$, $a_r$ is odd, but $a_r=a_i+a_j$, so one of $a_i,a_j$ is even and the other is odd. This means that $a_{r+1}-a_r \le a_{i_m}$ for all $r \ge N$. For some large $n \ge N$ consider the set $\mathcal{S}_n=\{a_{n}-a_{n-1},a_n-a_{n-2},a_n-a_{n-3},...a_n-a_{n-k}\}$ where $k$ is the largest integer such that $a_n-a_{n-k} \le a_{i_m}$. Then certainly $k \le a_{i_m}$, and since each $a_{n}-a_{n-j}$ is bounded, there are only finitely many such sets $S_{n}$ The set $\mathcal{S}_n$ can therefore determine the value $i_s$ such that $a_{n+1}=a_{i_s}+a_j$. So $\mathcal{S}_n$ uniquely determines the value $a_{n+1}-a_{n}$, which then uniquely determines $\mathcal{S}_{n+1}$. Since there are only finitely many possible sets that $\mathcal{S}_{n}$ can be, the sequence $\{\mathcal{S}_n\}_{n\ge N}$ eventually repeats and hence $\{a_{n+1}-a_n\}_{n\ge 1}$ is also eventually periodic.
31.01.2022 08:16
The idea is to find one thing that (perhaps eventually) has finitely many possibilities, so that if they repeat, then the entire sequence repeats. Let $b_1<b_2<\cdots<b_k$ be the set of even numbers in $(a_i)$. We know for all sufficiently large $N$, $a_N=b_{x_n}+a_{N-y_n}$ for some $1\le x_n\le k$ and $1\le y_n\le b_k$. However, setting $x_n=x_m$ and $y_n=y_m$ does not immediately solve the problem. Let's think about it. The possible choices are $a_N$ are finite. If $a_N-a_{N-c}=b_j$ and $a_N-a_{N-d}=b_l$ then $a_N\ne a_{N-c}+b_j$. We are basically looking at values $a_N-a_{N-1}, a_N-a_{N-2}, \cdots, a_N-a_{N-t}$ where $t<b_k$ is bounded. We know exactly one of them is $b_j$ for some $j$. Thus, we consider a set $f(N)=\{a_N-a_{N-1}, a_N-a_{N-2}, \cdots, a_N-a_{N-t}\}$, where $|f(N)|$ may change according to $N$ but $f(N)$ contains no elements greater than $b_k$. By pigeonhole there exists $f(M)=f(N)$. I contend that $f(M+1)=f(N+1)$. It suffices to show that $a_{M+1}-a_M=a_{N+1}-a_N$ because $f(M+1) = ((a_{M+1}-a_M) + f(M)) \cup [b_k]$ and $f(N+1) = ((a_{N+1}-a_N) + f(N)) \cup [b_k]$. This is true because suppose $a_{M+1}=a_{(M+1)-t}+b_j$. Let $d_t=a_M-a_{M-t}=a_N-a_{N-t}$. Then $a_{M+1} \ne a_{(M+1)-u}+b_v$ for any $(u,v)\ne (t,j)$ so $d_{t-1}-d_{u-1} \ne b_v-b_j$ for any $(u,v)\ne (t,j)$. Therefore $a_{(N+1)-t}+b_j \ne a_{(N+1)+u}+b_v$ for any $(u,v)\ne (t,j)$, so $a_{M+1}-a_M \le a_{N+1}-a_N$ (i.e. anything smaller failing for $M$ also fails for $N$). Similarly, $a_{N+1}-a_N \le a_{M+1}-a_M$, so it follows that $f(M+1)=f(N+1), f(M+2)=f(N+2),$ etc, and $a_n-a_{n-1}$ is periodic with period $M-N$.