Is There a Finite Upper Bound for Sequences Without Repeating Subsequences?

[Zurtex]

I have tonight been mulling over a lot of mathematics and I was considering, given a sequence can only be generated from elements 0 and 1, e.g: {1,0,0,1,0,1,1,1} does there exist an upper bound on the longest possible sequence such that you have a sequence:

{a₁, a₂, ..., a_n}

Where there NEVER exists 3 equal subsequences:

{a_i, ..., a_i+j} = {a_i+j+1, ..., a_i+2j+1} = {a_i+2j+2, ..., a_i+3j+2}

Basically a subsequence of elements can not repeat itself 3 times, one after the other e.g {1,1,1} or {0,1,0,1,0,1} would not be allowed, but {1,1,0,1} would be fine.

If there does exist a finite upper bound I wish to extend this to eventually include more elements, but right now I’m quite perplexed about this situation. Is there some mathematics I can learn to help me with this sort of problem?

 

[Tide]

There are $2^n$ possible sequences consisting of n 0s and 1s so that, at most, you could only have $2^n$ subsequences of length n before one of them is repeated.

 

[CRGreathouse]

There are $2^n$ possible sequences consisting of n 0s and 1s so that, at most, you could only have $2^n$ subsequences of length n before one of them is repeated.

Yes, but that doesn't address the original question. Sequences are allowed to repeat, just not immediately afterward. If only 1-subsequences were considered, sequences could be arbitrarily long; consider 101010101...

I think the question is very interesting, but I haven't found an anwer yet.

 

[Tide]

I think I missed the "one after the other" on first reading.

 

[Zurtex]

Let me give a few more examples:

{0,1,1,0,1,0,1,1,0,0,1,1} would be fine, regardless of:

{(0,1,1),0,1,(0,1,1),0,(0,1,1)}

{0,1,1,0,1,1,0,0,1,1,0,0,1,1,0,0} would not be fine because of:

{0,1,1,0,(1,1,0,0),(1,1,0,0),(1,1,0,0)}

 

[LeonhardEuler]

Alright, after many hours, I believe I have a proof that there is no limit the length of such a sequence. The proof works by generating a sequence of arbitrary length with no subsequence repeated three times in a row.
Here's how you make the sequence: start with one of the characters, say 0. Now add its 'inverse' to the end of the sequence, so now you have {0,1}. Now take the 'inverse' of this and add it to the end, so you have:
{0,1,1,0}
continuing:
{0,1,1,0,1,0,0,1}
{0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0}
{0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,1,0,1,1,0,0,1,1,0,1,0,0,1}

For convenience I am going to call sequences that can be generated this way "inversion sequences". Now there are some things to notice about these sequence. Let 'a' be the subsequence {0,1} and b={1,0}. Then the sequence above can be written as a sequence of a's and b's:
{0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,1,0,1,1,0,0,1,1,0,1,0,0,1}
->{a,b,b,a,b,a,a,b,b,a,a,b,a,b,b,a}
Notice that this sequence of a's and b's is also an inversion sequence, as can be seen by replacing the a's with zeros and b's with 1's and comparing to the sequence used to generate the long sequence. All of this can be proven in general by induction: The sequence {0,1} can be represented as {a}, and {a} is an inversion sequence. Now suppose all inversion sequences that are formed by inverting 0<n<N times can be represented in a's and b's, and that these sequences of a's and b's are themselves inversion sequences. Clearly the inverse of a inversion sequence formed by inverting (N-1) times can be represented in a's and b's by replacing the a's with b's and b's with a's, so the total sequence formed by inverting N times can be represented by just adding the new a's and b's to the old (since the original sequence contained an even # of elements). This finishes the proof.

Alright, now to begin proving that these sequences can not contain three repeats of a subsequence in a row: First of all, inversion sequences can not contain a subsequence with an odd number of elements repeated three times. To prove this, first observe that an inversion sequence can not contain three 1's or three 0's in a row. This is because it can be represented as a sequence of a's and b's, and both of these contain one 0 and one 1.

Now to prove that an inversion sequence can not contain a subsequence of an odd number of elements repeated three times in a row: First observe that any subsequence of an inversion sequence containing an odd number of elements(greater than 1) can either be represented as {x,c_1,c_2,...c_k} or {c_1, c_2, c_3, ... c_k, x} where x is 0 or 1 and the c_i are each either 'a' or 'b'. Now consider what the subsequence consisting of one of these subsequences repeated three times looks like:
{x,c_1,c_2,...c_k,x,c_1,c_2,...c_k,x,c_1,c_2,...c_k}
Since this is a subsequence of an inversion sequence containing an odd # of elements, it must be representable in one of the above forms. Suppose it is representable in the form {x,c_1,c_2,...c_k}. This implies that {c_1,c_2,...c_k,x,c_1,c_2,...c_k,x,c_1,c_2,...c_k} is a sequence of a's and b's. By assumption each of the c_i is an 'a' or 'b'. Reading from the beginning of this sequence we would see an a or b at each c_i up to c_k and then read 'x', followed by the first character of c_1. These two characters must be different, so if x=1, then c_1=a, otherwise c_1=b. We would then read the second character of c_1 followed by the first character of c_2. Since this must be a seqence of a's and b's, it follows that these two characters are diferent. This implies that c_1=c_2, which in turn implies that c_2=c_3 and so on. So all the c_i are equal. We would then read the last character of c_k followed by x. These must be different. Therefore, if x=1, then c_k=b, otherwise c_k=a. So we have, if x=1 then c_1=a, c_k=b and c_1=c_k, and otherwise x=0, c_1=b, c_k=a, and c_1=c_k, which is a contradiction. Therefore the subsequence can not be represented in the form {x,c_1,c_2,...c_k}. A nearly identical argument shows that it can not be represented in the form {c_1,c_2,...c_k,x}. This implies that an inversion sequence can not contain a subsequence of odd length repeated three times.

Now to wrap up the argument, it is proven that an inversion sequence can not contain a subsequence of even length repeated three times. First of all the sequences {0,1} and {1,0} are the only inversion sequences formed by inverting once and niether contains such a subsequence. Now suppose that no inversion sequence formed by inverting N times contains such a subsequence. Now, suppose an inversion sequence formed by inverting (N+1) times contains a subsequence of even length repeated three times. This implies that its 'a' 'b' representation contains such a subsequence. But the 'a' 'b' represenntation is an inversion sequence formed by inverting N times, which is known not to contain such a subsequence. Contradiction. Therefore any inversion sequence does not contain a subsequence of even length repeated three times.

Combining these results, we conclude that no inversion sequence contains a subsequence of any length repeated three times. Therefore there is no limit to the length of a sequence of 1's and 0's not containing a subsequence repeated three times.

-edit-
I really should prove the statement

Now, suppose an inversion sequence formed by inverting (N+1) times contains a subsequence of even length repeated three times. This implies that its 'a' 'b' representation contains such a subsequence.

I am working on that now, but it seems to be true.

 

[LeonhardEuler]

Alright, here is the prromised proof of this statement:

Now, suppose an inversion sequence formed by inverting (N+1) times contains a subsequence of even length repeated three times. This implies that its 'a' 'b' representation contains such a subsequence.

Suppose you have an inversion sequence {1,0,0,1,0...} There are two ways to take a subsequence of even length: one way takes only complete a's and b's and the other begins with the last character of an 'a' or 'b' and ends with the first character of another 'a' or 'b'. If the subsequence is of the first type, i.e. {c_1,c_2...c_k}, then obviously the fact that this subsequence is reapeated three times in a row in the inversion sequence implies that the a b representation contains a subsequence repeated three times in a row, since it contains exactly this subsequence three times in a row. Otherwise the subsequence is of the form {x_1, c_1, c_2,...,c_k,x_2}. If this subsequence is repeated three times, then somewhere in the inversion sequence we have {x_1, c_1, c_2,...,c_k,x_2,x_1, c_1, c_2,...,c_k,x_2,x_1, c_1, c_2,...,c_k,x_2} Since the c_i are in the ab representaion of the inversion sequence, {x_2,x_1} must be an 'a' or a 'b'. Call it c*. Also, since the complete inversion sequence has an ab representaion, the charater preceding the first x_1 in the subsequence must be the opposite of x_1, i.e.x_2 and the character that occurs after the final x_2 must be x_1. Now if we add on to the subsequence the character that occurs before it and after it, we obtain this sequence, which is a subsequence of the inversion sequence:
{x_2,x_1, c_1, c_2,...,c_k,x_2,x_1, c_1, c_2,...,c_k,x_2,x_1, c_1, c_2,...,c_k,x_2,x_1}
={c*,c_1, c_2,...,c_k,c*,c_1, c_2,...,c_k,c*,c_1, c_2,...,c_k,c*}
which is a subsequence in the ab representaion repeated three times in a row, completing the proof.

 

[Zurtex]

Wow, that's very odd really, going to have to take some time to sit down and make sure it's all correct.

 

[[Quadratic]]

If this proof is correct, which I believe it is, I applaud you LE. I'm trying to imagine the implications of your result. Zurtex, exactly what did you have in mind when you began asking yourself this question?