Когда "послезавтра" станет "вчера", то "сегодня" будет так же далеко от воскресенья, как тот день, который был "сегодня", когда "вчера" было "завтра". Как вы думаете, какой сегодня день недели?

   Решение

Темы:    [ Отношение порядка ] [ Соображения непрерывности ] [ Перестановки и подстановки (прочее) ]

Сложность: 3+ Классы: 9,10

Прислать комментарий

Условие

Некто расставил в произвольном порядке 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.

Источники и прецеденты использования