3
$\begingroup$

In Lecture Notes on Enormous integers Harvey M. Friedman introduces

"... longest finite sequence $x_1,...,x_n$ from $\{1,...,k\}$ such that for no i < j <= n/2 is $x_i,...,x_{2i}$ a subsequence of $x_j,...,x_{2j}$. For k ≥ 1, let n(k) be the length of this longest finite sequence."

Then, the author evaluates this function

"Paul Sally runs a program for gifted high school students at the University of Chicago. He asked them to find n(1), n(2), n(3). They all got n(1) = 3. One got n(2) = 11. Nobody reported much on n(3)."

which I fail to confirm. Consider 12 character word

001011111101 

neither of its starting subsequences

00  010   1011 

is contained in "doubled" subsequences and suggest n(2) = 13. Am I missing anything?

  • 2
    Hmm... I recall proving that $n(2)=11$ for Dr. Sally earlier this year. Let me see if I can dig up the proof.2012-07-31

1 Answers 1

5

$00$ is a subsequence of $010$. You seem to be thinking of substring/subword.