|
|
 |
Условие
Натуральные числа от 1 до 100 расставлены по кругу в таком порядке, что каждое число либо больше обоих соседей, либо меньше обоих соседей. Пара соседних чисел называется хорошей, если при выкидывании этой пары вышеописанное свойство сохраняется. Какое минимальное количество хороших пар может быть?
Решение
Пример. Сначала расставим числа подряд, а затем поменяем местами числа 2 и 3, 4 и 5, ..., 98 и 99. В полученной расстановке
(1, 3, 2, 5, 4, ..., 99, 98, 100) есть ровно 51 хорошая пара – это пары (1, 3), (3, 2), (5, 4), (7, 6), ..., (97, 96), (99, 98), (98, 100).
Докажем, что хороших пар не менее 51. Заметим, что среди любых двух пересекающихся пар хотя бы одна – хорошая. Действительно, пусть a1, a2, a3, a4, a5 – подряд стоящие числа. Не умаляя общности, можно считать, что a1 > a2 < a3 > a4 < a5. Пусть пара (a3, a4) не является хорошей. Тогда a1 > a2 > a5 > a4, то есть a1 > a4 < a5. Значит, пара (a2, a3) является хорошей.
Поэтому хороших пар уже не менее 50, причём ровно 50 их может быть, только если хорошие и нехорошие пары чередуются. Но пара, следующая за числом 100, – хорошая: 100 > (ak < ak+1) > ak+2 < ak+3. Хорошей также является и пара, предшествующая числу 100, а значит, чередование невозможно.
Ответ
51 хорошая пара.
