Authors: Kanel-Belov A.Ya., Galochkin A.i.

For what largest $n$ can one invent two infinite in both directions sequences $A$ and $B$ such that any segment of sequence $B$ of length $n$ is contained in $A$, $A$ has a period of 1995, and $B$ does not have this property (is non-periodic or has a period of a different length)?

Comment. The sequences can consist of arbitrary symbols. The question is about the minimal period.
An example where the period of sequence $A$ consists of one 1 and 1994 zeros, and $B$ is a non-periodic sequence of zeros and ones, with all ones at least 1994 positions apart, shows that the condition of all segments of length 1994 being identical is not sufficient for the periodicity of $B$.
The sequence is periodic with a period of length 1995.

First, let's prove that 1995 is the length of one of the periods. Suppose this is not the case, then there exists a segment of length 1996 in sequence $B$ where the first and last symbols do not match:

![](https://cdn.mathpix.com/cropped/2024_05_06_ad217c05ea9ced24f8d2g-05.jpg?height=117&width=408&top_left_y=250&top_left_x=825)

where $x$ and $y$ are different symbols. Let the segment of the sequence between $x$ and $y$ be denoted by $Z$. Suppose the symbol $x$ appears in $Z$ exactly $k$ times. Consider two sequences of length 1995: $x Z$ and $Z y$. By assumption, each of these sequences appears in sequence $A$, meaning each of them matches a shifted period of sequence $A$. Therefore, the symbol $x$ must appear the same number of times in each of these sequences. On the other hand, in the sequence $x Z$, it appears $k+1$ times, and in the sequence $Z y$, it appears $k$ times. This is a contradiction.

It remains to prove that 1995 is the length of the minimal period. If the period length of sequence $B$ were less than 1995, then some segment of length 1995 in sequence $B$ would split into several identical segments. By condition, this segment is contained in $A$. Clearly, in this case, the length of the (minimal) period of sequence $A$ would also be less than 1995.

Comment. From the proof, it follows that if $n$ is the length of the minimal period of a sequence, then any two identical segments of length $n-1$ are at a distance that is a multiple of $n$.