AoPS - Problem

Source: CWMO 2002 P8

Tags: combinatorics proposed, combinatorics

April

27.12.2008 18:51

Assume that $ S=(a_1, a_2, \cdots, a_n)$ consists of $ 0$ and $ 1$ and is the longest sequence of number, which satisfies the following condition: Every two sections of successive $ 5$ terms in the sequence of numbers $ S$ are different, i.e., for arbitrary $ 1\le i<j\le n-4$, $ (a_i, a_{i+1}, a_{i+2}, a_{i+3}, a_{i+4})$ and $ (a_j, a_{j+1}, a_{j+2}, a_{j+3}, a_{j+4})$ are different. Prove that the first four terms and the last four terms in the sequence are the same.

Suppose, for the sake of contradiction, that $ (a_1,a_2,a_3,a_4)\ne(a_{n-3},a_{n-2},a_{n-1},a_{n})$. Since $ n$ is maximal, the 5-sequences $ (a_{n-3},a_{n-2},a_{n-1},a_{n},0),(a_{n-3},a_{n-2},a_{n-1},a_{n},1)$ have both occured. Since $ (a_1,a_2,a_3,a_4)\ne(a_{n-3},a_{n-2},a_{n-1},a_{n})$, there must be some element before these two 5-sequences. By definition, it cannot be $ a_{n-4}$. Thus, $ 1-a_{n-4}$ must be the element in $ S$ that is right before both 5-sequences. But then the sequence $ (1-a_{n-4},a_{n-3},a_{n-2},a_{n-1},a_{n})$ occurs twice. Contradiction!