|
|
 |
Условие
В ряд стоят 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 баллов.
