58-я Международная Математическая Oлимпиада
Бразилия, Рио-де-Жанейро, 2017 год
(1) бойлары ең ұзын екі ойыншының арасында ешкім жоқ,
(2) бойлары үшінші мен төртінші ең ұзын ойыншының арасында ешкім жоқ,
⋮
(N) бойлары ең кіші екі ойыншының арасында ешкім жоқ.
Осыны әрқашан істеуге мүмкіндігі бар екенін дәлелдеңіз.
Комментарий/решение:
Решение. Разделим изначальный ряд на куски p1,...,pN по N+1 подряд идущих футболистов. Пусть pi={ai1>ai2>...>ai(N+1)}. Создадим множество S={s1,...,s2N}. Теперь рассмотрим следующий процесс из N шагов:
(1) Выберем кусок pi, в котором ai2=maxj=1,...,Naj2.
Из данного куска отметим элементы ai1>ai2 и положим их в S: s1=ai1,s2=ai2. Потом уберем из рассмотрения этот кусок полностью.
Для k=2,...,N:
(k) Среди оставшихся кусков выберем кусок с maxaj(k+1). Из него отметим элементы ajk>aj(k+1) и положим их в S: s2k−1=ajk,s2k=aj(k+1). Потом уберем из рассмотрения этот кусок полностью.
После окончания данного процесса получим множество S состоящее из некоторых 2N футболистов, причем из построения следует, что
s1>s2>s3>...>s2N,
а так же элементы s2k−1,s2k лежат в одном куске для k=1,...,N. Оставив только этих футболистов легко убедится, что полученная конфигурация удовлетворяет условию задачи. ◻
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.