|
|
 |
Условие
Некто расставил в произвольном порядке 10-томное собрание сочинений. Назовём беспорядком пару томов, для которых том с большим номером стоит левее. Для данной расстановки томов посчитано число S всех беспорядков. Какие значения может принимать S?
Подсказка
Если поменять местами два соседних тома, то число беспорядков изменится (уменьшится или увеличится) на 1.
Решение
Ясно, что число S беспорядков не меньше 0 и не больше числа всевозможных пар из 10 томов (число таких пар равно 10·9 : 2 = 45). Покажем, что любое из значений от 0 до 45 может достигаться при некоторой расстановке томов. Расставим вначале тома в обратном порядке. При этом каждая пара томов будет являться беспорядком, и общее число беспорядков S = 45. Пусть у нас уже есть расстановка, для которой S = i > 0; тогда найдём в ней два соседних тома, образующие беспорядок (такие два тома найдутся, иначе расстановка томов будет правильной и S будет равно 0). Поменяв эти два тома местами, получим расстановку, в которой ровно на один беспорядок меньше, то есть S стало равно i – 1. Таким образом, начиная с расстановки томов, для которой S = 45, можно последовательно получать расстановки, для которых S = 44, 43, ..., 1, 0.
Ответ
Любое целое значение от 0 до 45.
Источники и прецеденты использования
| web-сайт | |
| задача |
