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

Проект МЦНМО
при участии
школы 57
Задача 116693
Темы:    [ Упорядочивание по возрастанию (убыванию) ]
[ Задачи с неравенствами. Разбор случаев ]
[ Индукция (прочее) ]
[ Доказательство от противного ]
Сложность: 4+
Классы: 10
В корзину
Прислать комментарий

Условие

По кругу разложено чётное количество груш. Массы любых двух соседних отличаются не более чем на 1 г. Докажите, что можно все груши объединить в пары и разложить по кругу таким образом, чтобы массы любых двух соседних пар тоже отличались не более чем на 1 г.


Решение 1

  Отметим груши с самой маленькой и самой большой массами (в дальнейшем будем называть их X и Y соответственно). Если расположенные между ними груши отсортировать по весу (отдельно по часовой стрелке от X до Y и отдельно – против часовой стрелки от X до Y, деля наши груши таким образом на две части), то массы любых двух соседних по-прежнему будут отличаться не более чем на 1 г (см. решение задачи 116685).
  Рассмотрим произвольную грушу Z, отличную от Y и от второй по массе груши. Существует как минимум две груши, которые тяжелее Z, но не более чем на 1 г. Одна из них – та, которая была соседней с ней лежащей по кругу после сортировки, вторая найдётся, так как (после сортировки) Z можно переложить в другую часть.
  Расположим все груши в ряд по возрастанию веса. По доказанному для каждой из груш в этом ряду две последующие груши (если они существуют), отличаются от неё не более чем на 1 г.
  Опять разложим груши по кругу. Положим X и Y друг напротив друга. По часовой стрелке от X до Y выложим груши с нечётных мест ряда, против часовой стрелки от X аналогичным образом разложим груши с чётных мест ряда. Условие на массы соседних груш сохранилось, что следует из доказанного выше утверждения. После чего будем, начиная с груши X и двигаясь по часовой стрелке, брать грушу, класть в пакет вместе с противоположной ей и выкладывать последовательно по кругу. Несложно проверить, что массы двух соседних пакетов будут отличаться не более чем на 1 г.


Решение 2

  Индукция по числу груш.
  База. Количество груш равно 4. Объединим в одну пару самую лёгкую и самую тяжёлую груши, а в другую – две оставшихся. Очевидно, что массы пар отличаются меньше чем на 1 г.
  Шаг индукции. Из  2n + 2  груш выкинем самую лёгкую и тяжёлую (A и B соответственно). Оставшийся набор по-прежнему удовлетворяет условию, значит, по предположению индукции эти 2n груш можно расположить по кругу в парах правильным образом. Возможны три случая.
  1) Найдутся такие пары  (C1, C2)  и  (D1, D2),  что  m(C1) + m(C2) < m(A) + m(B) < m(D1) + m(D2).
  Тогда на дуге, соединяющей пары  (C1, C2)  и  (D1, D2),  найдётся место для новой пары  (A, B).
  2) Пара  (A, B)  самая лёгкая из  n + 1  пары. Пусть A' и A'' – две самые лёгкие груши среди оставшихся 2n. Ясно, что A' и A'' отличаются от A не более чем на 1 г (это выполнялось для двух соседей груши A). Здесь возможны два варианта.
  2а) A' и A'' попали в разные пары  (A', B')  и  (A'', B'').  Тогда две самые лёгкие пары груш  (X1, Y1),  (X2, Y2)  (m(X1) + m(Y1) ≤ m(X2) + m(Y2))  отличаются от пары  (A, B)  не больше чем на 1 г, так как уже  0 ≤ (m(A') + m(B')) – (m(A) + m(B)) ≤ 1  и  0 ≤ (m(A'') + m(B'')) – (m(A) + m(B)) ≤ 1.
  Если пары  (X1, Y1)  и  (X2, Y2)  не стоят рядом, то вынем пару  (X2, Y2)  и поставим её рядом с  (X1, Y1).  Это не нарушит условия для пар груш. После этого пару  (A, B)  поставим между парами  (X1, Y1)  и  (X2, Y2).
  2б) A' и A'' попали в одну пару. Рассмотрим самую тяжёлую пару  (X1, X2).  Вынем пары  (A', A'')  и  (X1, X2)  из круга (при этом условие не нарушится). Образуем пары  (A', X1)  и  (A'', X2).  Для этих пар на каждой из двух дуг, соединяющих бывшие позиции  (A', A'')  и  (X1, X2),  найдётся место (аналогично случаю 1). Мы свели вариант 2б к 2а.

  3) Пара  (A, B)  самая тяжёлая. Этот случай аналогичен случаю 2.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 75
Год 2012
класс
Класс 10
задача
Номер 4

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

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