1
$\begingroup$

An answer of mine disagrees with an answer in a math book I'm reading, and so I wanted to sanity check it to see if there's something obvious I'm missing.

The book Foundations of Mathematical Analysis by Paul J. Sally Jr. defines a subsequence avoiding sequence to be a sequence $x_1, x_2, ..., x_n$ such that, for any indices $0 < i < j \leq n/2,$ $$x_i, x_{i+1}, ..., x_{2i}$$ is not a subsequence of $$x_j, x_{j+1}, ..., x_{2j}.$$

He defines $n(k)$ to be the length of the longest subsequence avoiding sequence whose terms lie in $\{1, 2, ..., k\}.$ He states that $n(1) = 3, n(2) = 11.$

I agree that $n(1) = 3,$ but I believe that the sequence

$$1,1,2,2,2,2,1,2,1,2,1,2$$

is subsequence avoiding and of length 12, contradicting his claim that $n(2) = 11.$

Now, the subsequences of that sequence of the form $$x_i, ..., x_{2i}$$ for $i\leq n/2$ are, respectively, $$1, 1,$$ $$1,2,2,$$ $$2,2,2,2,$$ $$2,2,2,1,2,$$ $$2,2,1,2,1,2$$ $$2,1,2,1,2,1,2.$$

It's clear that none of them contain each other. So, have I made some silly mistake? Or was there a typo in the entry $n(2) = 11$?

$\endgroup$
  • 1
    $\begingroup$ What is the definition of subsequence in this context? Normally, in subsequences you can skip elements, so that $2,2,2,2$ is a subsequence of $2,2,2,1,2.$ If you can't skip elements, I think this is usually called a sublist (at least in computer science.) If one can't skip elements, your example looks right. If one can skip elements, I'd like to see the example with $11$ terms. $\endgroup$ – saulspatz May 26 at 13:54
  • $\begingroup$ Ah! I think you may be right--you can skip elements. The book does not provide an example with 11 terms, although now I know what to start looking for! $\endgroup$ – Michael Barz May 26 at 14:13
  • $\begingroup$ @saulspatz - Here's the example with $11$ terms: $1222111111x.$ There are only $5$ candidates: $12, 222, 2211, 21111, 111111$ and none is a subseq of another. The last letter $x$ is not part of any candidate and can be either symbol. (This also means all $n(k)$ must be odd, as the last symbol is not part of any candidate if total length is odd.) $\endgroup$ – antkam May 26 at 14:54
  • $\begingroup$ @antkam I think you should make that an answer, since the OP didn't have an example. $\endgroup$ – saulspatz May 26 at 14:56
1
$\begingroup$

Using the definition from @saulspatz that a subsequence allows skipping terms, here is an example with $11$ terms: $1222111111x$

There are only $5$ candidates: $12, 222, 2211, 21111, 111111$ and none is a subsequence of another. The last letter $x$ is not part of any candidate and can be either symbol. (This also means all $n(k)$ must be odd, as the last symbol is not part of any candidate if the total length is odd.)

BTW I found this by "manual backtracking" :) - it turns out starting with $11$ limits you to a shorter length. And starting with $12$ means once another $1$ appears the rest must be all $1$s (except for the last $x$) so it's just a matter of how many $2$s you can fit in before the reappearance of $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.