Задача 66102

Темы:    [ Перестановки и подстановки (прочее) ] [ Упорядочивание по возрастанию (убыванию) ] [ Теория алгоритмов (прочее) ]

Сложность: 3+ Классы: 7,8,9

Условие

Автор: Богданов И.И.

В ряд стоят 100 детей разного роста. Разрешается выбрать любых 50 детей, стоящих подряд, и переставить их между собой как угодно (остальные остаются на своих местах). Как всего за шесть таких перестановок гарантированно построить всех детей по убыванию роста слева направо?

Решение

Обозначим первые слева 25 мест в ряду буквой A, вторые 25 – B, третьи и четвёртые – C и D. Каждый раз, выбирая 50 детей, будем выстраивать их по убыванию роста. Сделаем это сначала с AB, затем с BC и, наконец, с CD. После первой перестановки 25 самых низких детей окажутся в куске BCD, после второй – в CD, после третьей – в D. Таким образом, 25 самых низких детей уже расставлены правильно. Снова выполним перестановки AB и BC. Они расставят в нужном порядке следующих по росту 25 детей в куске C. Последняя перестановка AB расставит правильно 50 самых высоких.

Замечания

1. Набор перестановок AB, CD, BC, AB, CD, BC тоже подходит.

2. За пять перестановок обратный порядок детей перестроить нельзя.

3. 5 баллов.

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

олимпиада
Название	Турнир городов
номер/год
Дата	2016/17
Номер	38
вариант
Вариант	весенний тур, базовый вариант, 8-9 класс
задача
Номер	4