Западно-Китайская математическая олимпиада, 2002 год
Пусть S=(a1,a2,…,an) — самая длинная последовательность из нулей и единиц, удовлетворяющая следующему условию: пятиэлементные подпоследовательности S попарно различны, т.е. для любых 1≤i<j≤n−4, (ai,ai+1,ai+2,ai+3,ai+4) и (aj,aj+1,aj+2,aj+3,aj+4) не равны. Докажите, что первые и последние четыре члена последовательности совпадают.
посмотреть в олимпиаде
Комментарий/решение:
Предположим, методом от противного (a1,a2,a3,a4)≠(an−3,an−2,an−1,an).Поскольку n максимальна, то пятиэлементные последовательности (an−3,an−2,an−1,an,0),(an−3,an−2,an−1,an,1) обе встречаются. Также поскольку (a1,a2,a3,a4)≠(an−3,an−2,an−1,an), перед этими двумя пятиэлементными последовательностями должен быть какой-то элемент. По условию это не может быть an−4. Таким образом, 1−an−4 должно быть элементом в S которая находится прямо перед обеими пятиэлементными последовательностями. Но затем последовательность (1−an−4,an−3,an−2,an−1,an) встречается дважды. Противоречие
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.