Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: How Many Squares Must a Binary Sequence Contain? | How Many Squares Must a Binary Sequence Contain Aviezri S. Fraenkel1 and R. Jamie Simpson2 Submitted November 16 1994 Accepted December 11 1994 Abstract. Let g n be the length of a longest binary string containing at most n distinct squares two identical adjacent substrings . Then g 0 3 010 is such a string g 1 7 0001000 and g 2 18 010011000111001101 . How does the sequence g n behave We give a complete answer. 1. Introduction A binary word or string containing no square a pair of identical adjacent subwords has maximum length 3 in fact the only squarefree words of length 3 are 010 and its 1-complement 101. A computer disclosed that a binary word containing at most 1 square has maximum length 7 the only words of length 7 with only 1 square are 0001000 0100010 0111011 and their 1-complements and the reverse of 0111011 and its 1-complement. Further a binary word containing at most 2 distinct squares has maximum length 18 the only words of length 18 which contain only 2 distinct squares are 010011000111001101 and its 1-complement which is also its reverse . In general let g k denote the length of a longest binary word containing at most k distinct squares. Distinct means that the squares are of different shape not just translates of each other. We have seen that g 0 3 g 1 7 g 2 18. This data raises the following natural questions. 1 Department of Applied Mathematics Computer Science The Weizmann Institute of Science Rehovot 76100 Israel. Email fraenkel@ . Work done while visiting Curtin University. 2 School of Mathematics Curtin University Perth WA 6001 Australia. Email tsimpsonr@ THE ELECTRONIC JOURNAL OF COMBINATORICS 2 1995 R2 2 1. Is the set of values of the sequence S g k k 0 1 . J- inhnite or hnite 2. What s the value of g 3 Regarding the hrst of these questions Entringer Jackson and Schatz 1974 considered the conjecture that S is inhnite citing a reference which. seems to say that this conjecture. is true . They then go on .
