|
COMMENT
|
Also, maximal length of a 2-surprising sequence in n symbols. (A sequence of symbols is 2-surprising if, for every pair of symbols X and Y, not necessarily distinct, and every distance D, there is at most one position in t he sequence where X precedes Y by distance D.) - John W. Layman (layman(AT)math.vt.edu), Nov 17 2003
Dan Hoey (Jan 13 2006) points out that the equivalence of the two definitions is a consequence of the equivalence (for any sequence s_1,s_2,...) of "Exists i,j,k,l : s_i = s_j, s_k = s_l and i-k = j-l" and "Exists i,j,k,l : s_i = s_j, s_k = s_l and i-j = k-l".
|
|
REFERENCES
|
J. Hamkins and K. Zeger, Improved bounds on maximum size binary radar arrays, IEEE Trans. Inform. Theory, 43 (1997), 997-1000.
Dennis E. Shasha, Puzzling Adventures, Scientific American 289 (#12, 2003), 22.
|
|
EXAMPLE
|
{0,1,1,2,0,3,2,3,1,0}, {0,0,1,2,3,2,4,1,0,4,3,1}, and {0,0,1,2,3,1,4,5,2,5,0,3,4,1,0} are 2-surprising sequences of 4, 5 and 6 symbols, respectively, and no longer sequences of 4,5, or 6 symbols exist, so a(4)=10, a(5)=12, and a(6)=15.
a(7) = 18: example: AABCDBEFGCGEADFBAC and there are no longer strings. - Jeffrey Shallit (shallit(AT)graceland.math.uwaterloo.ca), Dec 03 2003
a(8) = 21: example: ABACDEFGDHECHGBBFEADC and there are no longer strings.
a(9) = 24: example: ABCDDEFEGHIFCIBAHGBECAFD and there are no longer strings.
a(10) = 26: example: AABCBDEFGHEIJCDJGAIDFHBACE and there are no longer strings.
a(11) = 29; example: AABCDECFGHIHJDKBEIJKGFACEBAHD and there are no longer strings.
a(12) = 32; example: AABCDEFGHGIJKELFCLKBDJIHBAFDGACE and there are no longer strings. - Dan M. Shaw (dan(AT)aloha.com), Dec 14 2003 and Jan 11, 2004
|
