|
|
 |
Условие
По кругу стоят 10 детей разного роста. Время от времени один из них перебегает на другое место (между какими-то двумя детьми). Дети хотят как можно скорее встать по росту в порядке возрастания по часовой стрелке (от самого низкого к самому высокому). Какого наименьшего количества таких перебежек им заведомо хватит, как бы они ни стояли изначально?
Решение
Занумеруем детей по возрастанию роста – 1, 2, ..., 10.
Оценка. Пусть изначально они стояли в обратном порядке.
Первый способ. Если было меньше восьми перебежек, то какие-то трое детей остались на своих местах, а их порядок противоположен нужному.
Второй способ. Назовём сложностью количество оборотов, которые мы сделаем, проходя против часовой стрелки от 1-го ко 2-му, потом к 3-му, ..., от 10-го к 1-му. Сначала сложность равна 1, а в конце – 9. Нетрудно проверить, что при перебежке одного ребёнка сложность может измениться не больше чем на 1. Поэтому нужно не меньше восьми перебежек.
Пример на восемь перебежек: 1-й и 2-й остаются на своих местах, 3-й перебегает и встаёт за 2-м, потом 4-й – за 3-м и т.д.
Ответ
8 перебежек.
Замечания
5 баллов
