ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109814
Темы:    [ Перестановки и подстановки (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
[ Принцип крайнего (прочее) ]
Сложность: 5
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Смирнов А.

Натуральные числа от 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 хорошая пара.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2004
Этап
Вариант 5
Класс
Класс 9
задача
Номер 04.5.9.7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .