Задача
Шеренга состоит из N ребят попарно различного роста. Её разбили на наименьшее возможное количество групп стоящих подряд ребят, в каждой из которых ребята стоят по возрастанию роста слева направо (возможны группы из одного человека). Потом в каждой группе переставили ребят по убыванию роста слева направо. Докажите, что после N – 1 такой операции ребята будут стоять по убыванию роста слева направо.
Решение
Выберем любое число h и всех ребят ростом меньше h назовём карликами, а остальных – великанами. Место между соседями, левый из которых карлик, а правый – великан, назовём стыком. Весом стыка назовём количество карликов слева и великанов справа от него (не обязательно подряд). Вес может принимать значения от 2 до N. До операции всякий стык мог быть только внутри группы, причём не более одного в группе. А после операции – только на границе бывшей группы, которая содержала стык. Веса обоих возможных стыков на границах группы будут меньше веса бывшего стыка этой группы. Поэтому максимум весов уменьшается при операции (если, конечно, стыки ещё появляются). Значит, после N – 1 операции стыков не останется. Тем самым все великаны будут стоять левее всех карликов.
Рассматривая нужные h, получим, что первый будет выше всех, первые двое – выше всех остальных, и т.д. Это и значит, что ребята стоят по убыванию роста.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь