Let r be a positive integer, and let a0,a1,⋯ be an infinite sequence of real numbers. Assume that for all nonnegative integers m and s there exists a positive integer n∈[m+1,m+r] such that am+am+1+⋯+am+s=an+an+1+⋯+an+s Prove that the sequence is periodic, i.e. there exists some p≥1 such that an+p=an for all n≥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≤s<r, such that am+am+1+…+am+s=an+…+an+s(1) We call a pattern every succession of r−1 members of the given sequence ai+1,ai+2,…,ai+r−1. Now the key observation. If there exist two equal patterns then the sequence is periodic up to the second one. Indeed if an+i=am+i,i=1,2,…,r−1,n<m , by (1) we consecutively get an=am,an−1=am−1,… This fact motivates us to check that there are finitely many different values of ai. 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 ai there exists aj,0<j−i≤r with ai=aj. It is obvious if we apply (1) to m=i,n=i+1. Thus, for each N, amongst ai,ai+1,…,ai+N there are at least ⌊Nr⌋ terms equal to ai. 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≤s<r, such that am+am+1+…+am+s=an+…+an+s(1) Sorry, how is this equivalent to the given condition? Are you assuming n∈[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 am+am+1+…+an−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≤i≤r such that am=am+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 rr+1 consecutive r-intervals, we see that there must be two which are the same. Also let those intervals begin at ak and al, 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 ak−1=al−1. By continuing this process we get that our sequence is p-periodic up to al. 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 N?
28.04.2020 05:17
Solution with MathStudent2002 We can rephrase the condition as: For all pairs (i,j), there exists k∈[0,r) such that ai+…+ai+k=aj+…+aj+k. However, there exists no such k if ai≠aj, ai+s=aj+s∀0<s<r. Thus, we can't have two blocks of r consecutive elements which only differ in the first term. Now, consider i≠j such that ai+s=aj+s∀0≤s<r, which is possible since there are only a finite number (rr) of possible blocks of r consecutive elements. By our previous argument, we must have ai−1=aj−1, which in turn implies ai−2=aj−2, and continuing downwards we get that ak=ak+(i−j)∀k≤j. So, the sequence is periodic before max. 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 rth 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.