Назад
Задача

Некто расставил в произвольном порядке 10-томное собрание сочинений. Назовём беспорядком пару томов, для которых том с большим номером стоит левее. Для данной расстановки томов посчитано число S всех беспорядков. Какие значения может принимать S?

Решение

Ясно, что число 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.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет