\section*{Problem 2 - 061242}

Let \(n \neq 0\) be a natural number. A sequence of numbers will be briefly called a sequence " \(F_{n}\) " if there exist \(n\) distinct numbers \(z_{1}, z_{2}, \ldots, z_{n}\) such that the following conditions are satisfied:

(1) Each term of the sequence is one of the numbers \(z_{1}, z_{2}, \ldots, z_{n}\).

(2) Each of the numbers \(z_{1}, z_{2}, \ldots, z_{n}\) appears at least once in the sequence.

(3) Any two consecutive terms of the sequence are different from each other.

(4) No subsequence of the sequence has the form \(\{a, b, a, b\}\) with \(a \neq b\).

Note: A subsequence of a given sequence \(\left\{x_{1}, x_{2}, x_{3}, \ldots\right\}\) or \(\left\{x_{1}, x_{2}, x_{3}, \ldots, x_{s}\right\}\) is any sequence of the form \(\left\{x_{m 1}, x_{m 2}, x_{m 3}, \ldots\right\}\) or \(\left\{x_{m 1}, x_{m 2}, x_{m 3}, \ldots, x_{m t}\right\}\) with natural numbers \(m_{1}<m_{2}<m_{3}<\ldots\)

Answer the following questions:

a) For a fixed \(n\), are there arbitrarily long sequences \(F_{n}\)?

b) If the answer to question a) is negative for some \(n\):

What is the maximum number of terms that a sequence \(F_{n}\) can have (for a given \(n\))?
}
a) No, because

b) We prove by complete induction that for \(n \geq 1\) there always exists a sequence \(F_{n}\) of length \(2 n-1\) and that this length is maximal. For \(n=1\), this is clear. Let \(n>1\) be arbitrary and the claim proven for \(F_{1}, \ldots, F_{n-1}\).

Consider the sequence

\[
F=z_{1}, S_{1}, z_{1}, S_{2}, \ldots, z_{1}, S_{r}, z_{1}
\]

where \(S_{i} (i \in \{1, \ldots, r\}, 1 \leq r < n)\) denotes the sequence elements of a sequence of numbers from \(\{z_{2}, \ldots, z_{n}\}\) that satisfy conditions (3) and (4) of the problem statement.

It is easy to see that the sequence \(F\) satisfies the conditions of the problem if and only if the \(S_{i}\) are pairwise disjoint and the union of all \(S_{i}\) includes all numbers except \(z_{1}\).

It is clear that the length of \(F\) is maximal if each \(S_{i}\) has maximal length. By the induction hypothesis, the length of \(F\) is then \((r+1) + 2(s_{1} + \ldots + s_{r}) - r\), where \(s_{i}\) denotes the number of different numbers in \(S_{i}\) and \(r+1\) is the number of \(z_{1}\) in \(F\).

It is \(s_{1} + \ldots + s_{r} = n-1\) and thus the length of \(F\) is \(2 n - 1\).

The sequence \(F\) is optimal: Any sequence \(F_{n}\) starts with \(z_{1}\) w.l.o.g. If \(z_{1}\) does not appear again after that, only \(2(n-1)-1\) numbers can follow after \(z_{1}\) (by the induction hypothesis), so the length would only be \(1 + 2(n-1) - 1 = 2 n - 2\).

In a sequence of maximal length, at least two \(z_{1}\) must appear. None of the numbers \(z_{i}\) that stand between two adjacent \(z_{1}\) may appear again, otherwise one would have a subsequence \(\{z_{1}, z_{i}, z_{1}, z_{i}\}\). These conditions are generally satisfied by the sequence \(F\), so the length \(2 n - 1\) is optimal and the claim is proven.

\section*{Solution by Kornkreis}