Западно-Китайская математическая олимпиада, 2002 год

Пусть $ S=(a_1, a_2, \ldots, a_n)$ — самая длинная последовательность из нулей и единиц, удовлетворяющая следующему условию: пятиэлементные подпоследовательности $ S$ попарно различны, т.е. для любых $ 1\le i < j\le n-4$, $ (a_i, a_{i+1}, a_{i+2}, a_{i+3}, a_{i+4})$ и $ (a_j, a_{j+1}, a_{j+2}, a_{j+3}, a_{j+4})$ не равны. Докажите, что первые и последние четыре члена последовательности совпадают.

Комментарий/решение

Предположим, методом от противного $ (a_1,a_2,a_3,a_4)\ne(a_{n-3},a_{n-2},a_{n-1},a_{n})$.Поскольку $ n$ максимальна, то пятиэлементные последовательности $ (a_{n-3},a_{n-2},a_{n-1},a_{n},0),(a_{n-3},a_{n-2},a_{n-1},a_{n},1)$ обе встречаются. Также поскольку $ (a_1,a_2,a_3,a_4)\ne(a_{n-3},a_{n-2},a_{n-1},a_{n})$, перед этими двумя пятиэлементными последовательностями должен быть какой-то элемент. По условию это не может быть $ a_{n-4}$. Таким образом, $ 1-a_{n-4}$ должно быть элементом в $ S$ которая находится прямо перед обеими пятиэлементными последовательностями. Но затем последовательность $ (1-a_{n-4},a_{n-3},a_{n-2},a_{n-1},a_{n})$ встречается дважды. Противоречие