Processing math: 100%

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


Пусть S=(a1,a2,,an) — самая длинная последовательность из нулей и единиц, удовлетворяющая следующему условию: пятиэлементные подпоследовательности S попарно различны, т.е. для любых 1i<jn4, (ai,ai+1,ai+2,ai+3,ai+4) и (aj,aj+1,aj+2,aj+3,aj+4) не равны. Докажите, что первые и последние четыре члена последовательности совпадают.
посмотреть в олимпиаде

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

  1
3 года 8 месяца назад #

Предположим, методом от противного (a1,a2,a3,a4)(an3,an2,an1,an).Поскольку n максимальна, то пятиэлементные последовательности (an3,an2,an1,an,0),(an3,an2,an1,an,1) обе встречаются. Также поскольку (a1,a2,a3,a4)(an3,an2,an1,an), перед этими двумя пятиэлементными последовательностями должен быть какой-то элемент. По условию это не может быть an4. Таким образом, 1an4 должно быть элементом в S которая находится прямо перед обеими пятиэлементными последовательностями. Но затем последовательность (1an4,an3,an2,an1,an) встречается дважды. Противоречие