6
$\begingroup$

Given a finite alphabet $A$ with $|A|=n$, what is the largest $l$ so that a string $s=a_1...a_l$ of length $l$ exists with $a_i\in A$ so that there is no $i,j,d$ with $i\neq j, d > 0$ so that $a_i = a_{i+d}$ and $a_j = a_{j+d}$?

Thanks to @greybeard I now know that such strings are called 2-surprising strings. More information can be found here: http://oeis.org/A008062

This problem has been described by Dennis E. Shasha on page 122 of the December 2003 issue of Scientific American.

Furthermore there exists a proof that $l<3n$: http://aleph0.clarku.edu/~djoyce/mpst/surprising/

These are known strings for small $n$:

n   l quantity  example

1   2   1       00
2   4   3       0010
3   7   4       0012102
4   10  2       0112032310
5   12  212     001232410431
6   15  770     001231452503410
7   18  1630    001231456264035102
8   21  1396    010234563742761154032
9   24  312     012334546785281076142053
$\endgroup$
  • $\begingroup$ The question doesn't strike me as being computer science. Sounds more like math. $\endgroup$ – Yuval Filmus Jan 5 '16 at 16:36
  • 1
    $\begingroup$ @yuval-filmus As long as it is a problem on strings and CNF-SAT is used to solve it, there is at least a bit of CS in it... $\endgroup$ – J.-E. Pin Jan 5 '16 at 17:25
  • $\begingroup$ DId you find out anything more? Is this an open problem? If so, reposting on Theoretical Computer Science or MathOverflow may be appropriate. $\endgroup$ – Raphael May 24 '16 at 9:52

Your Answer

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

Browse other questions tagged or ask your own question.