|
|
 |
Условие
На книжной полке стоят 30 томов энциклопедии в некотором порядке. За одну операцию разрешается менять местами любые два соседних тома. За какое наименьшее число операций можно гарантированно выстроить все тома в правильном порядке (с первого по тридцатый слева направо) независимо от начального положения?
Подсказка
Назовём беспорядком пару томов, в которой том с большим номером стоит левее тома с меньшим номером. За одну операцию число беспорядков меняется не более чем на 1.
Решение
Пусть имеется некоторое расположение томов на полке. Рассмотрим всевозможные пары томов (всего таких пар 30·29 : 2 = 435). Назовем беспорядком пару томов, в которой том с большим номером стоит левее тома с меньшим номером. В конечной ситуации не должно быть ни одного беспорядка. Заметим, что за одну операцию число беспорядков меняется не более, чем на 1. В самом деле, только в паре переставляемых томов может появиться или исчезнуть один беспорядок. Следовательно, при начальном расположении, в котором тома идут в обратном порядке (каждая пара томов образует беспорядок), потребуется сделать не менее 435 операций.
Покажем, что 435 операций всегда достаточно. Если в некотором расположении томов есть беспорядки, то найдётся пара соседних томов, образующая беспорядок. Поменяв местами эту пару томов, мы уменьшаем число беспорядков на 1. Таким образом, каждой операцией мы можем уменьшать число беспорядков на 1 и не более, чем через 435 операций прийти к расположению, в котором нет беспорядков, то есть к правильному порядку томов.
Ответ
За 435 операций.
Источники и прецеденты использования
| web-сайт | |
| задача |
