N учеников (все — разного роста) образовали очередь в порядке возрастания роста. Любые два человека, стоящие в очереди через одного, могут поменяться местами (например, восьмой и десятый). Могут ли ученики после нескольких обменов образовать очередь в порядке убывания роста, если: а) N четно; б) N нечетно? Если да, то за какое наименьшее число обменов?

Для решения этой задачи рассмотрим поведение учеников в очереди и ограничения на их перемещения. ### Обозначим: - Ученики в очереди имеют рост \( h_1 < h_2 < ... < h_N \) (в порядке возрастания). - Ученики могут меняться местами, если они стоят через одного. ### Задача: Мы хотим узнать, могут ли ученики образовать очередь в порядке убывания \( h_N > h_{N-1} > ... > h_1 \) и за какое минимальное количество обменов. ### a) Если \( N \) четно: 1. **Возможные обмены:** При чётном \( N \) у нас есть \( N/2 \) пар, между которыми можно обменяться. Например, ученики 1 и 3, 2 и 4, ..., (N-1) и N могут поменяться местами. 2. **Обмены для получения убывающей последовательности:** - Можно быстро заметить, что за один обмен мы можем вполне переместить одного ученика из первой половины в позицию во второй половине и наоборот. - Исходная очередь \( h_1, h_2, ..., h_N \) может быть преобразована в очередь \( h_N, h_{N-1}, ..., h_1 \) путём тщательного выбора пар для обменов. 3. **Количество обменов:** В случае четного количества учеников, для полной перестановки понадобится максимум \( N/2 \) обменов, необходимых для перемещения каждого ученика на своё место. ### b) Если \( N \) нечетно: 1. **Возможные обмены:** В этом случае у нас также есть несколько пар, однако в последней позиции окажется один ученик, который не сможет перемещаться через одного (например, если N=5, 1 может обменяться с 3 и 4, но 2 и 5 никогда не могут поменяться местами). 2. **Формулировка задачи:** При нечетном \( N \) возможны блокировки: кто-то в центра может быть раздражитель (например, четный рост будет мешать нечетному). 3. **Перестановка:** Каждый ученик в середине не сможет обойти других учеников. Таким образом, каждый раз это приведёт к ситуации, где мы не сможем поменять два не соседние ученика. 4. **Итог:** Мы не сможем добиться полной упорядоченности в убывающем порядке. ### Ответы: - а) Если \( N \) четное, то возможно. Для полной перестановки может потребоваться **максимум \( N/2 \) обменов**. - б) Если \( N \) нечетное, то невозможно.