|
|
 |
Условие
По кругу разложено чётное количество груш. Массы любых двух соседних отличаются не более чем на 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а.
