Let $r$ be a positive integer, and let $a_0 , a_1 , \cdots $ be an infinite sequence of real numbers. Assume that for all nonnegative integers $m$ and $s$ there exists a positive integer $n \in [m+1, m+r]$ such that \[ a_m + a_{m+1} +\cdots +a_{m+s} = a_n + a_{n+1} +\cdots +a_{n+s} \] Prove that the sequence is periodic, i.e. there exists some $p \ge 1 $ such that $a_{n+p} =a_n $ for all $n \ge 0$.
Problem
Source: IMO Shortlist 2013, Combinatorics #5
Tags: function, combinatorics, Additive combinatorics, Sequence, IMO Shortlist
12.07.2014 12:33
16.07.2014 02:26
A similar (but much shorter, it seems) argument can be found on my blog here EDIT: Actually, I might as well repost it here so people don't have to go through the link:
19.07.2014 17:02
The same idea, but a little bit different point of view and balance. Let's restate the given condition: For each $m,n$ there exists $s, 0\le s < r$, such that \[ a_m+a_{m+1}+\ldots +a_{m+s}=a_n+\ldots + a_{n+s}\,\,\,\,\,\,\,\, \text{(1)} \] We call a pattern every succession of $r-1$ members of the given sequence $a_{i+1},a_{i+2},\ldots, a_{i+r-1} $. Now the key observation. If there exist two equal patterns then the sequence is periodic up to the second one. Indeed if $a_{n+i}=a_{m+i}\,, i=1,2,\ldots,r-1\,,\, n<m$ , by (1) we consecutively get $a_n=a_m,a_{n-1}=a_{m-1},\ldots$ This fact motivates us to check that there are finitely many different values of $a_i$. Indeed if it's true, the number of different patterns will be finite and in every sufficiently big interval there will be two equal patterns. To prove it, note that for each $a_i$ there exists $a_j\,, 0<j-i\le r $ with $a_i=a_j$. It is obvious if we apply (1) to $m=i,n=i+1$. Thus, for each $N$, amongst $a_i, a_{i+1},\ldots, a_{i+N}$ there are at least $\lfloor \frac{N}{r}\rfloor$ terms equal to $a_i$. Now, if we assume there are more than $r$ pairwise different members of the sequence, this argument easily brings us to contradiction, since we could allocate too many terms of the sequence in some sufficiently big interval.
19.07.2014 18:27
dgrozev wrote: Let's restate the given condition: For each $m,n$ there exists $s, 0\le s < r$, such that \[ a_m+a_{m+1}+\ldots +a_{m+s}=a_n+\ldots + a_{n+s}\,\,\,\,\,\,\,\, \text{(1)} \] Sorry, how is this equivalent to the given condition? Are you assuming $n \in [m+1, m+r]$? Even then I don't see why the equivalence is immediate...
19.07.2014 20:09
Well, take $m,n\,, m<n$ and apply the original condition to $a_m+a_{m+1}+\ldots + a_{n-1}$. Depending whether the terms in the second sum intersect with the first one, just remove the repeating ones or add some new ones to both sums to get the second condition.
30.12.2016 22:17
Quote: So we are clearly done from this point. Elaborate?
31.12.2016 02:27
24.03.2017 03:47
Setting $s=0$ yields that for every $m$ there exists $1 \le i \le r$ such that $a_m=a_{m+i}$, so if more than $r$ numbers appeared in the sequence we would have that at some $r$-interval there are $r+1$ numbers, contradiction. Now we proved there are at most $r$ numbers. By taking any $r^r+1$ consecutive $r$-intervals, we see that there must be two which are the same. Also let those intervals begin at $a_k$ and $a_l$, $l>k$. It is trivial that $l-k$ can take only finitely many values, so let $l-k=p$, where difference $p$ appears infinitely many times . Taking $m=k-1$ and $s=k+p-2$ immediately gives $a_{k-1}=a_{l-1}$. By continuing this process we get that our sequence is $p$-periodic up to $a_l$. Since difference $p$ appears infinitely many times, we conclude that our sequence is $p$-periodic too, so we are finished.
02.10.2018 03:26
Does the problem statement still hold when $s$ can only take on values in $\mathbb{N}$?
28.04.2020 05:17
Solution with MathStudent2002 We can rephrase the condition as: For all pairs $(i,j)$, there exists $k\in[0,r)$ such that $a_i+\ldots+a_{i+k}=a_j+\ldots+a_{j+k}$. However, there exists no such $k$ if $a_i\neq a_j$, $a_{i+s}=a_{j+s}\forall 0<s<r$. Thus, we can't have two blocks of $r$ consecutive elements which only differ in the first term. Now, consider $i\neq j$ such that $a_{i+s}=a_{j+s}\forall 0\le s<r$, which is possible since there are only a finite number ($r^r$) of possible blocks of r consecutive elements. By our previous argument, we must have $a_{i-1}=a_{j-1}$, which in turn implies $a_{i-2}=a_{j-2}$, and continuing downwards we get that $a_k=a_{k+(i-j)}\forall k\le j$. So, the sequence is periodic before $\max(i,j)$. However, since we can find arbitrarily large $(i,j)$ with this property, we must have that the sequence is entirely periodic, as desired.
05.05.2020 03:41
23.05.2022 15:32
23.05.2022 15:34
william122 wrote: Solution with MathStudent2002 We can rephrase the condition as: For all pairs $(i,j)$, there exists $k\in[0,r)$ such that $a_i+\ldots+a_{i+k}=a_j+\ldots+a_{j+k}$. However, there exists no such $k$ if $a_i\neq a_j$, $a_{i+s}=a_{j+s}\forall 0<s<r$. Thus, we can't have two blocks of $r$ consecutive elements which only differ in the first term. Now, consider $i\neq j$ such that $a_{i+s}=a_{j+s}\forall 0\le s<r$, which is possible since there are only a finite number ($r^r$) of possible blocks of r consecutive elements. By our previous argument, we must have $a_{i-1}=a_{j-1}$, which in turn implies $a_{i-2}=a_{j-2}$, and continuing downwards we get that $a_k=a_{k+(i-j)}\forall k\le j$. So, the sequence is periodic before $\max(i,j)$. However, since we can find arbitrarily large $(i,j)$ with this property, we must have that the sequence is entirely periodic, as desired. I think that the condition you have proved (there are infinitely many $M$ such for each $M$, there exists $p$ that $a_n=a_{n+p}$ for all $n\leq M$) is not sufficient to imply the entire sequence is periodic (for example, the sequence $a_n=\nu_2(n)$ satisfies the condition you have proven, but is not periodic).
11.10.2022 21:13
Are you kidding me. Let $P_i$ be the set of partial sums of length $i$ sequences. Let $S_i$ be the set of differences of $P_i$. Notice that $S_1 \cup S_2 \cup S_3 \cup \cdots$ is finite since its element's magnitudes are bounded above by $r(\max S_1)$. Hence if each $P_i = \{s_{i_1} < s_{i_2} < \cdots s_{i_k}\}$ for $k \leq r$, then there are finitely many ways to assign $k \leq r$ and $s_{i_2}-s_{i_1}, s_{i_3}-s_{i_2}, \ldots, s_{i_k}-s_{i_{k-1}} \in S_1$, hence by we must have by infinite pigeonhole that there is an infinite set $P'$ where $P_i$ is identical up to a shift for all $i \in P'$. Once again, by infinite pigeonhole, there exist $i, j \in P'$ such that the sequence of partial sums of length i and the sequence of partial sums of length j are identical up to the $r$th element, up to a shift. This means the sequence of partial sums of length $|j - i|$ has a consecutive sequence of $r$ identical values, hence the sequence of partial sums of length $|j - i|$ have constant value everywhere by the condition. Thus, it is obvious by taking differences of consecutive partial sums of length $|j-i|$ that the original sequence has period that at most $|j - i|$, finishing.