26

An infinite sequence ($a_0$, $a_1$, ...) is such that the absolute value of the difference between any 2 consecutive terms is equal to $1$. Is there a length-8 subsequence such that the terms are equally spaced on the original sequence and the terms form an arithmetic sequence from left to right?

Clarifications: 1. The Common difference can be negative or 0

Example: the sequence 1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 10

works because the 3rd term is 3, 6th term is 4, 9th term is 5, ..., 24th term is 10.

and 3rd, 6th, ..., 24th terms are equally spaced. They also form an arithmetic sequence.

I am thinking about Szekeres theorem but idk if that would work

EDIT: I was able to show it for $n=$. I am actually more interested in indefinitely long ones. But hey, it could be that one can construct something that an indefinitely long one will never happen.

Alex Ravsky
  • 90,434
  • By "subsequence such that the terms are equally spaced on the original sequence" do you mean that the subsequence is of the form $\displaystyle b_n = a_{xn+y}$ where $x,y$ are integers? – Regret Dec 09 '14 at 07:44
  • Yes. That's the definition. –  Dec 09 '14 at 07:46
  • For example, such a subsequence is a_2, a_6, a_10, ..., a_30 –  Dec 09 '14 at 07:48
  • Alright. Just to be clear, you want to know does such a subsequence exist for all sequences where $|a_{n+1}-a_n|=1$ for all $n$? – Regret Dec 09 '14 at 07:50
  • Yeah, I am trying to prove that such a subsequence occurs regardless what values you put (as long as it satisfies that absolute value condition) –  Dec 09 '14 at 07:52
  • Any particular reason you chose to ask about arithmetic progressions of length 8? (I can't even resolve whether AP of length 4 must exist, and it wouldn't surprise me if the stronger condition of arbitrarily long AP existing were true) – Milo Brandt Dec 14 '14 at 02:58
  • 1.) length 8 is pretty arbitrary. 2.) I was able to prove it for length 4. 3.) Induction seems promising. –  Dec 15 '14 at 01:51
  • 2
    @TheMathTroll: You could append the proof for $n=4$ to the question, or post it as a (partial) answer. Either way, it would be interesting to see. – Regret Dec 15 '14 at 07:07
  • I’m sure the proof for n = 4, if exists, is a fine result. Cases of n > 4 are hopeless and I expect (counter)examples constructed by elementary tools. – Incnis Mrsi Dec 18 '14 at 21:05
  • You might be interested in looking at 2009 IMO problem 3 proposed by Gabriel Carroll. This is A6 in the shortlist and the solution can be found on page 24 of this document: https://www.imo-official.org/problems/IMO2009SL.pdf – Faraz Masroor Dec 19 '14 at 00:38
  • For some time I tried to show that each appropriate sequence contains an arbitrary long equally spaced arithmetic progression. I tried to use generalizations of van der Waerden theorem (which works when the sequence is bounded) and ultrafilter technique (which is a powerful tool for proving the theorems of this kind), but I have failed. Also I tried to build a counterexample, but I failed too. But it is easy to construct an appropriate sequence, which should contain no infinite equally spaced arithmetic progression. – Alex Ravsky Dec 19 '14 at 10:15
  • A nice question. :-) I just shared it with our powerful mathematicians, which deals with similar subjects. :-) – Alex Ravsky Dec 19 '14 at 10:26
  • @Alex Ravsky: I do not think this is a very clever thing. Expect a n = 5 fractal-based counterexample in hour or so. – Incnis Mrsi Dec 19 '14 at 10:28
  • @IncnisMrsi Maybe I shall write a program for this case. – Alex Ravsky Dec 19 '14 at 10:56
  • @Alex Ravsky: astonishingly, fractal sequences of differences generated with such rules as “+”⇒some_string, “−”⇒some_string failed my expectations. I tried several of these – they all lead to rather long AP subsequences in {a}, as computations show. – Incnis Mrsi Dec 19 '14 at 11:42
  • @IncnisMrsi: Why do you think cases $n>4$ are hopeless? – Regret Dec 19 '14 at 12:38
  • @IncnisMrsi You are not the first. :-) After I recalled Thue-Morse sequence, I am rather sceptical to such approaches. – Alex Ravsky Dec 19 '14 at 14:23
  • 2
    For many problems like this the number of terms explodes rapidly. $11$ terms guarantee a sequence of $4$, but it might be something enormous for $5$. It looks similar to the Ramsey numbers to me. – Ross Millikan Dec 19 '14 at 18:14
  • @regret: I thought so, but not so sure after experiments with pencil and, especially, computer. We have a curve on two-dimensional lattice. Let D be its fractal dimension. A lattice of arithmetical progressions have 4 dimensions, and condition for each term of it to lie on the curve subtracts 2 − D (codimension of the curve) from it. So, subsequences of 4 terms have critical value D = 1, but subsequences of 5 terms should have negative dimension for any D < 6/5. – Incnis Mrsi Dec 20 '14 at 11:10
  • The "$n=$" in your edit is puzzling because (1) the equality sign is followed by a period, and (2) the variable $n$ does not appear anywhere else in the question. – bof Dec 21 '14 at 12:55
  • I wonder if the related problem of "Suppose the difference between consecutive terms is constrained in $S$. Must there be an AP of length $4$?" where $|S|=n$ and $S$ is affinely independent (over the rationals - though we might as well be in a vector space). It might be possible, for instance, to reduce looking for AP of length $5$ to looking for those of length $4$ in a set with a larger $S$. (Though I see no obvious solution to that problem, aside from computational methods, so this comment could be in vain) – Milo Brandt Dec 21 '14 at 17:00
  • @RossMillikan Agreed - fusible numbers are another and possibly even more pertinent example that springs to mind, where the hugeness comes about in the interplay between some König-style lemma guaranteeing solutions of all lengths and certain 'large countable ordinal' properties of the core problem itself. I wonder if Harvey Friedman would know anything... – Steven Stadnicki Dec 21 '14 at 17:45
  • This problem has certainly been solved by someone, since it appeared in a competition. But I suppose the solver does not want to share it with us :( See http://www.komal.hu/verseny/feladat.cgi?a=honap&h=201411&t=mat&l=en – Dongryul Kim Dec 24 '14 at 02:50
  • 1
    yeah... I am still thinking about it; no progress. Btw, are you the 40-point scorer at IMO 2012 or is that just a confusion in name? –  Dec 24 '14 at 17:15
  • My name is not a common one. My friend just said he's found a counterexample for 40, so let's wait till he posts it. – Dongryul Kim Dec 25 '14 at 05:32

3 Answers3

8

Far from a full answer, but I have some (hopefully) new information. Length $4$ equally spaced, AP subsequences can be found from all finite $(a_n)_{n=1}^N$ with $N>10$ and $\forall n(|a_{n+1}-a_n|=1)$. This can very easily be brute forced, as there exist only $2^N$ distinct length $N$ sequences which obey the absolute value condition. That comes out to only $2048$ distinct sequences which require checking.

Here is an example of a length $10$ sequence which does not contain any length $4$, equally spaced, AP subsequences. However, appending either $a_{10}+1$ or $a_{10}-1$ to it will negate this.

| /\
|/  \/\  /
|      \/
|

So I thought that there is probably some finite length $N$ after which every such sequence will contain length $8$, equally spaced, AP subsequences. Turns out that even for length $5$, $N$ would have to be greater than $32$. There are $2^{32}$ distinct sequences, and filtering out those sequences where length $5$ APs have already been found, over $3$ million sequences are left. This was when I got a memory error.

Perhaps some of you out there with better hardware and/or programming prowess (or just more time) could brute force the solution, if there is indeed such a finite $N$. Of course, a positive answer for $k$ will beg the same question for $k+1$ and eventually you will run out of processing power or memory, which is why this is a rather inelegant method of doing it.

Regret
  • 3,817
  • How you checked subsequences isn’t very interesting, but where is a counterexample? We must construct an infinite sequence, and can’t use periodic sequences since any of them contains an (infinite) equally spaced constant subsequence. – Incnis Mrsi Dec 19 '14 at 07:58
  • @Incnis: I think you may have misinterpreted the aim of my post. If there exists an $N$ such that all $(a_n)_{n=1}^N$ contain equally spaced, length 8 subsequences of arithmetic progression, then that $N$ may be found computationally. If $N$ is found, then the answer to OP's question is yes. – Regret Dec 19 '14 at 08:41
  • 1
    @Incnis: In addition, an easy "proof" for AP length $4$ is readily available, you just need to confirm that all $2048$ length $11$ sequences contain one. – Regret Dec 19 '14 at 08:45
7

So, I wrote a program too. For natural $n$ as $f(n)$ I denote the least number $m$ such that each appropriate sequence of length $m$ contains an equally spaced arithmetic progression of length $m$. So, regret calculated $f(4)=11$ and $f(5)>32$. My program confirmed these results. Moreover, It claims that f(5)>4200 (this sounds somewhat strange for me. Maybe, there is a bug in my program) as shows the following sequence of signs of $a_{i+1}-a_i$:

oooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxoooxooxxxoooxooxoxxxoxoooxxoxxxooxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxxxoxxxoooxoxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoxxxoxoooxoooxoxxoxxoooxoooxoooxoxxoooxoooxoxxoxxoooxoooxoooxoxxoxxoooxoooxoxxoxxoxxoooxoxoxxxoooxxxoxoxoooxoxoxxxoxxoooxoooxxoxoooxoooxoooxoxxoooxoooxoxxoxxoooxoxxxoxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxoxxxoooxoxoxxxoooxxoxxxoxxoooxxoooxooxxoxxoxoxxoooxoxxxoxxxoxxxoooxxoooxxoooxooxxxooxoooxoxoxxxooxooxxoooxxoooxxoxxxoxooxxxoxxoxxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoxxoxxoxxoooxoooxxxooxxoooxoxxxoxoooxxxoooxooxxxoxxxoxxxoooxooxoxxxoooxxxoxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoxxoxxoooxxoxoxxxoxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxxoooxoxoxxxooxxoooxooxxoxxoooxoxxxoxxxooxoxoooxoxxoooxoxxoxxxoooxxxoxxoooxooxoxxxoxxxoxxxooxoooxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxxoooxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxooxxxoxooxxxoxxxoxxxoooxoooxoooxxoxoxxoooxoxoxxxooxoxooxxxoxxoooxoooxoxxoooxoooxoxxoxxoooxoxxoxxxooxoxxxoxxxoxooxxxoooxoooxoxxoxxxoooxxxooxooxxxoxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoxxoooxoooxoooxoxxoooxoxxxoxoooxooxxoxxooxoooxoxxoooxoxxxoxoooxoxxxoxxxooxooxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoxxoooxooxxoxxoooxoxxxoxooxxxoxxxoxxxoooxoooxoxxoooxoooxoooxoxxoxxxoooxoxoxxxooxxxoooxxoxoooxoooxoooxoxxoxxoooxoxoxxxoxoooxoxxxoxxxoxxxooxoooxooxxoxxoooxooxxxooxoxxxoxxxoxxxoooxooxoxxxoxoxoooxooxxxoooxxoxoooxoooxoooxoxxoooxoxoxxxoxoooxooxoxxxoooxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxxoxxxooxxoooxoxoxxxooxxxooxooxoooxxoxoooxooxxxooxoxxxoxoxxoooxooxxxoxxxoxxxooxoxxxooxoooxooxxoxxoooxooxxoxxoooxooxxoxxxoxxoooxxxoxooxxxoxxxoxxxoooxooxxxoooxooxxoxxxooxoxxxoxxxoxxxoooxooxoxxxooxxxooxxxoxooxooxxoooxxooxxxoooxoooxxxoxxoooxoooxoooxoxxxooxooxxoxxoxoxxoooxoxoxxxooxxxooxoxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxxoooxoooxxxooxooxoxxxooxoxxxoxoooxoxooxxxoxxoxoooxoooxoxxoooxxooxxxoxxooxooxoxxxoxxxoxxxoooxoooxoxxxoooxxooxoooxxxoxxxoxooxxxooxoxxxoxxxooxoxoooxoxxxoxxxoxxxooxoxxxoooxooxxxooxxoooxooxxoooxxoxxooxxxooxooxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxxxoxoxoxxxooxxoooxooxxoooxxoxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxxoxxooxxxooxxoooxxxoxoooxoooxoooxoxxoooxxooxxxoooxxooxxxoooxoxxxoxxxoxxxooxoooxooxxoxxoooxooxxoxxoooxooxxoxxoxxxoooxxxoxxxoxxxoxoooxoxooxxxoooxooxxoooxxoooxxxoxxoooxoooxxoxxxoooxoooxoooxoxxoxxoxxoooxoxoxxxoxxoooxoxxxoxxxoxxxooxoooxooxxoxxoooxoxxxoxooxxxoooxoooxoooxoxxoooxoooxoxxoooxoxxoxxooxxxooxxoooxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoxxoooxooxxoxxoooxoxoxxxooxoxxxoxxoooxoooxoooxoxxoooxoooxoxxxoooxoxoxxxooxxoooxooxxoxxoxxxoooxxxoxxxoxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoxxoxxoooxxoxoxxxoxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxoxxxoxoooxoxooxxxoooxooxxxooxxxoxxoooxxoxoxxxoxoooxoooxoooxoxxoooxoooxxoxxxooxoxxxoooxoooxoxxoxxxooxoxxxoxxxoxoooxoooxoooxoxxxooxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxooxoxxxoxxxoxxxooxooxxxoooxxxoxxxoxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxxoxxoxxxooxooxoxxxoxxxoxxxoooxoooxoooxoxxxoooxooxxoxxoxxoxoooxoxxoxxxooxoxxxoxxxoxooxxxoooxoooxoooxoxxoooxoooxoxxoooxxxooxxoxxoooxoooxoooxoxxoooxxoxxooxoooxxxoxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxxoxxxoxxoooxoooxxoxoooxoooxoxxoxxoooxooxoxxxoxxxoooxooxoxxxoxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoxxoxxoooxxoxoxxxoxooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxxxoxxxoooxoxxxoxxxoxxxoooxoooxxoxoxxoooxoxoxxxoooxoxxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoxxoooxoooxoooxoxxoooxoooxoxxoxxoooxoxxoxxoooxoooxoooxoxxoxxoxxoooxxoxxxoooxooxoxxxoxxxoxxxooxoooxooxxoxxoooxooxxoxxooxoooxoxxoxxxoxooxxxoxxxoxooxxxoxooxooxxoooxxooxxxoooxoooxxxoxxoooxoooxoooxoxxxooxooxxoxxoxxoxoooxoxxoooxxxoxxxoxxxoxooxoooxoxxoooxoxxoxxoooxxxoxxooxoooxxxoxxxoxxxooxoxxxoxxxoxxxoooxxooxooxxoxxoooxoooxoooxoxxoooxxoxxooxxxoooxoxoooxxoxxoxoooxoxooxxxoxxxoooxxxoxoxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxoooxooxxxoooxooxoxxxoxoooxxoxxxooxxxoooxoooxoooxoxxoooxxxoxxxoooxxoxxoooxooxoxxxoxxxooxoxoooxxoxxxoxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxxoxoooxoxxoooxoxxoxxoooxoooxoooxoxxoooxoooxoxxoxxxoxooxxxoooxoooxxoxxxoxooxoooxoxxxooxoooxoxxoooxxxoxxxoxxxoxoooxooxxoxxoooxooxxoooxxoxxxoooxoooxxoxxxooxoxxxoxxxoxooxxxoooxoooxoxxoxxxoooxooxxoxxxoxooxxxooxoooxxoooxxoooxooxxxooxxxoxxoooxxoooxxoxoooxoooxoooxoxxoooxoooxoooxxxooxxoooxoxoxxxoooxoxoooxxoxxoxxxoooxxxoxoxxxoooxoooxoooxoxxoooxooxooxxxoxxoooxxooxxxoxxoooxxoooxooxxxooxoxxxoxxxooxoxxxoxxoooxoxoooxxoxoxxoooxoooxoooxoxxxoooxoxoxxxoooxoxxxoxxxoxxxoooxoooxoooxoxxoxxoooxooxxoxxoooxoxxxoxxxoxxxoooxxoooxoxoxxxooxxxoooxoxoxxxoooxoooxoooxoxxoooxxoxxxoooxoxoxxxooxxxoooxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoooxoooxoxxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxoxxoooxoooxoooxoxxoooxooxoxxxoxxxoooxxoooxoxoxxxoxxoooxxoxxooxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxoxxoooxoxoxxxoooxoooxoxxoxxxoooxxoxxxoxxoooxooxooxxxoooxoooxoooxoxxoooxoxxoxxooxxxooxxoooxxxoxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxoooxxxoxxxoxxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxoxxxoxxxooxoxooxxxoxxxoxxxooxoxooxxxooxooxoooxxoxoooxooxxxooxxxooxxoxxoooxoooxoooxoxxoooxoooxoooxoxxoooxooxoxxxooxxxooxxoooxooxxoooxxxooxoxxxoxxxooxoxxxoxxoooxooxooxxxoooxooxoxxxoooxxooxoo

The graph of the respective sequence $\{a_i\}$:

enter image description here

The calculating block of my Delphi program:

procedure TForm1.Button1Click(Sender: TObject); 
label
 0,1;
const
 prLen0=4; // Length of Progression -1
 seqLen0=7000; // Length of Sequence -1
var
 prLen,l:Byte;
 i,j,k,d,d0,imin,seqLen:Word;
 l1:Integer;
 b:array[0..seqLen0-1]of Byte; // b[i]=a[i+1]-a[i]
 SOut:String;
begin
Memo1.Lines.Add('Seq.Length='+IntToStr(seqLen0+1));
Memo1.Lines.Add('Prog.Length='+IntToStr(prLen0+1));
FillChar(b,SizeOf(b),0);
imin:=seqLen0-prLen0;
prLen:=prLen0-1;
seqLen:=seqLen0-1;
repeat
for i:=imin downto 0 do for j:=1 to (seqLen0-i) div prLen0 do begin
 d0:=b[i];for k:=i+1 to i+j-1 do inc(d0,b[k]);
 for l:=1 to prLen do begin
  d:=b[i+j*l];for k:=i+j*l+1 to i+j*(l+1)-1 do inc(d,b[k]);
  if d<>d0 then goto 1; // Search for next progression
 end;
 // Progression found, go to the next sequence
 for l1:=i-1 downto 0 do b[l1]:=0;
 l1:=i; while b[l1]=1 do begin b[l1]:=0;inc(l1) end;
 b[l1]:=1;
 goto 0;
1:
end;
// No progessions found
SOut:='';
for i:=seqLen downto 0 do if b[i]=1 then SOut:=SOut+'x' else SOut:=SOut+'o';
Memo1.Lines.Add(SOut);
Break;
0:
until b[seqLen]=1; // by the symmetry , without loss of genearily we can assume b[0]=0
Memo1.Lines.Add('Done');
end;
Alex Ravsky
  • 90,434
6

There exist a sequence that has no length $54$ equally spaced arithmetic subsequence. This is a modified counterexample from this link.

Let $$u(x)=\frac{3}{2\pi}\sum_{n=1}^\infty 18^n\sin(\frac{2\pi x}{3(36)^n})$$ and put $a_n$ to be an even number in the interval $[u(x)-1,u(x)+1)$ when $n$ is even and an odd number when $n$ is odd.

Then we have \begin{align}|a_k-a_{k+1}|\leq|u(k)-u(k+1)|+2&\leq\frac{3}{2\pi}\sum_{n=1}^\infty 18^n\left|\sin(\frac{2\pi k}{3(36)^n})-\sin(\frac{2\pi(k+1)}{3(36)^n})\right|+2\\&<\frac{3}{2\pi}\sum_{n=1}^\infty18^n\frac{2\pi}{3}\frac1{36^n}+2=3\end{align}

Since $a_k-a_{k+1}$ is odd, we see that $|a_k-a_{k+1}|=1$

Now let $k_1, k_2,\ldots,k_{54}$ be an arithmetic sequence with common difference $d>0$. Define $m$ to be $36^{m-1}\le d<36^{m}$ and $h\le18$ as the smallest integer that $36^m/2\le hd\le 36^m$. Then $\frac{2\pi k_{19}}{3(36)^m},\frac{2\pi k_{20}}{3(36)^m},\ldots,\frac{2\pi k_{36}}{3(36)^m}$ is an arithmetic sequence with common difference at least $\pi/54$ but less than $2\pi/3$. So one of $\frac{2\pi k_{19}}{3(36)^m},\frac{2\pi k_{20}}{3(36)^m},\ldots,\frac{2\pi k_{36}}{3(36)^m}$ must be in the interval $[\pi/6,5\pi/6]$ or $[7\pi/6,11\pi/6]$ in $\pmod{2\pi}$. Let $\frac{2\pi k_i}{3(36)^m}$ be one of it.

We now show that $a_{k_i-h},a_{k_i},a_{k_i+h}$ is not an arithmetic sequence.

Let $K=2\pi k_i/3$, $D=2\pi hd/3$. First we have $$\sin\frac{D}{2(36)^m},\left|\sin\frac{K}{36^m}\right|\geq\sin\frac\pi6$$

Now \begin{align} &|a_{k_i-h}-2a_{k_i}+a_{k_i+h}|\\&\ge |u(k_i-h)-2u(k_i)+u(k_i+h)|-4\\&\ge\frac{3(18)^m}{2\pi}\left|\sin\frac{K-D}{36^m}-2\sin \frac{K}{36^m}+\sin\frac{K+D}{36^m}\right|-\sum_{n=1}^{m-1}\frac{3(18)^n}{2\pi}\left|\sin\frac{K-D}{36^n}-2\sin\frac{K}{36^n}+\sin\frac{K+D}{36^n}\right|-\sum_{n=m+1}^\infty\frac{3(18)^n}{2\pi} \left|\sin\frac{K-D}{36^n}-2\sin\frac{K}{36^n}+\sin\frac{K+D}{36^n}\right|-4\\&\geq \frac{3(18)^m}{2\pi}4\sin^2\frac{D}{2(36)^m}\left|\sin\frac{K}{36^m}\right|-\sum_{n=1}^{m-1}\frac{3(18)^n}{2\pi}4-\sum_{n=m+1}^\infty \frac{3(18)^n}{2\pi} 4\sin^2\frac{D}{2(36)^n}\left|\sin\frac{K}{36^n}\right|-4\\&\geq\frac{3(18)^m}{2\pi}4\sin^2\frac\pi6\sin\frac\pi6-\frac{3}{2\pi}\frac{4(18)^m}{17}-\sum_{n=m+1}^\infty \frac{3(18)^n}{2\pi}4\left(\frac{36^m}{2(36)^n}\right)^2-4\\&=\frac{3(18)^m}{2\pi}\left(\frac12-\frac4{17}-\frac1{71}\right)-4 \end{align} So if $m\ge2$, $$|a_{k_i-h}-2a_{k_i}+a_{k_i+h}|\geq\frac{3(18)^2}{2\pi}\left(\frac12-\frac4{17}-\frac1{71}\right)-4>0$$

If $m=1$, we can actually have $$|a_{k_i-h}-2a_{k_i}+a_{k_i+h}|\geq\frac{3(18)^1}{2\pi}\left(\frac12-\frac1{71}\right)-4>0$$ as the term $$\sum_{n=1}^{m-1}\frac{3(18)^n}{2\pi}\left|\sin\frac{K-D}{36^n}-2\sin\frac{K}{36^n}+\sin\frac{K+D}{36^n}\right|$$ doesn't occur.

Therefore we always have $a_{k_i-h}-2a_{k_i}+a_{k_i+h}\ne0$ which proves the assertion.


Remark

The argument can be improved a bit more to prove for $36$ using the same equation. As shown in the argument, it is easy to prove for arithmetic sequences whose common difference is large(compare the cases $m=1$ and $m=2$). This post will be updated soon with some more tweaks attached to it.

karvens
  • 3,745
  • Congrats! May be better and more easily provable bounds can be obtained if we take another periodical function instead of the sinus. For instance, a “saw” $f(x)=g(x-\lfloor x\rfloor)$, where $g(x)=x$, if $0\le x\le 1/2$ and $g(x)=1-x$, if $1/2\le x\le 1$. – Alex Ravsky Dec 25 '14 at 16:32
  • 2
    @AlexRavsky Yes I tried that(the same function...) but it didn't turn out well. The part where sine function becomes a good use is, interestingly $$f(x-y)-2f(x)+f(x+y)=-4f(x)f(y/2)^2$$where $f(x)=\sin x$. I could not think of any other function satisfying this kind of 'separating' equation and could not modify that part. – karvens Dec 25 '14 at 16:45
  • This does look like the kind of answer that could be fiddled with to get tighter bounds; it looks like we might be able to replace the intervals $[\pi/6,5\pi/6]$ and $[7\pi/6,11\pi 6]$ with some larger intervals (i.e. whatever values still force a positive result at the end) or that we might be able to require less terms to ensure one in those bounds (since currently, a rather primitive bound is used). – Milo Brandt Dec 25 '14 at 16:55
  • @karvens Maybe this functional equation has no essentially different (bounded) solutions (see, for instance, this first page. Nevertheless, the situation may be not so bad, because, as I understand, we don’t need exact equalities for the function but only some bounds. Can you formulate the needed conditions for the function as inequalities (or equalities)? – Alex Ravsky Dec 25 '14 at 17:31