Тема Ломоносов

Ломоносов - задания по годам → .15 Ломоносов 2023

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела ломоносов

Разделы подтемы Ломоносов - задания по годам

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#58009Максимум баллов за задание: 7

Вычислите

[∘ ---√----- ∘ ---√----] 45+ 2022− 45 − 2022 ,

где $[t]$ — это целая часть числа $t$ (т.е. наибольшее целое число, не превосходящее $t$ ).

Источники: Ломоносов-2023, 11.1 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

Давайте обозначим наше выражение внутри скобок за t. Тут какие-то страшные корни, давайте избавимся от них с помощью возведения t в квадрат!

Подсказка 2

t² = 90 - 2√3. Стоит вспомнить, что 1 < √3 < 2, и, получив из этого оценку на t², легко найти целую часть от t!

Показать ответ и решение

Обозначим

∘----√---- ∘----√---- t= 45+ 2022− 45− 2022.

Чтобы не возиться с корнями, попробуем оценить квадрат этого выражения, тем более он довольно симпатичный:

2 √ ---- ∘ ---√-----∘ ---√----- √ ---- t = 45+ 2022− 2⋅ 45 + 2022⋅ 45 − 2022+ 45− 2022=

∘--2----- √ - = 90− 2 45 − 2022= 90− 2 3

Из очевидного $1< √3< 2$ получаем $90− 4< t2 < 90− 2$ . Откуда, конечно, $92 = 81< t2 < 100= 102,$ так что целая часть числа $t$ равна $9.$ Здесь, однако, важно сказать, что $t> 0$ , иначе наше решение не исключало бы, что целая часть могла быть равна $− 10$ . Но в силу $45+√2022> 45− √2022-$ следует очевидность (которую всё же надо упомянуть!) неравенства $t> 0.$

Ответ:

$9$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#67931Максимум баллов за задание: 7

При каком наименьшем по модулю значении параметра $α$ уравнение

20( π ) 23( π ) 1234 sin x −3 − 789cos αx− 4 = 2023

имеет решение на отрезке $[−π,π]?$

Источники: Ломоносов-2023, 11.2 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

Из-за страшного вида уравнения можно понять, что просто преобразованиями это не решить, значит тут какая-то идея! Вот интересное замечание: 1234+789 = 2023. На что это может натолкнуть?

Подсказка 2

Можно из этого понять, что т.к. синус и косинус по модулю не превосходят 1, то максимум левой части как раз равен 2023! Теперь можно приравнять синус к ±1, а косинус к -1, и посмотреть на корни.

Подсказка 3

Выходит системка вида x = 5π/6 + πk и ax = 5π/4 + 2πn. Давайте посмотрим, когда первый корень может быть в этом промежутке.

Подсказка 4

Да, только при k = -1, 0! Осталось разобраться с альфа. Давайте подставим первый корень во второй чтобы выразить альфа через n и k) Останется только понять, при каких n и k модуль этого выражения достигнет минимума, а зная чем может быть k, это не так сложно)

Показать ответ и решение

Так как синус и косинус по модулю не превосходят $1,$ а $1234+ 789= 2023,$ решением уравнения может быть только такой $x,$ при котором входящие в уравнение синус и косинус равны соответственно $± 1$ (при возведении в 20-ю степень даст $1$ ) и $− 1$ (таким же останется при возведении в 23-ю степень).

( ( ) (| 5π { sin x− π3 =±1 |{ x= 6 + πk, k∈ ℤ ( cos(αx − π )=− 1 ⇔ ||( 5π 4 αx= 4 + 2πn, n∈ ℤ

Подставив $x$ из первого выражение во второе, выразим $α$

(5π ) 5π 15+ 24n α -6 +πk = 4-+ 2πn ⇒ α= 10+-12k, k,n∈ ℤ

Найдём возможные целые значения $k,$ подставив $x$ в условие $− π ≤ x≤ π,$

−π ≤ 5π +πk ≤π, k∈ℤ ⇒ k∈ {−1;0} 6

Чтобы найти $α$ с наименьшим модулем, выберем $n,$ минимизирующее модуль числителя, (для приведенных числителей это $0$ или $− 1),$ а также допустимое $k,$ максимизирующее модуль знаменателя. Нетрудно заметить, что это $n= −1$ и $k =0,$ поэтому получаем

α= −9-= −0,9 10

Ответ:

$− 0,9$

Ошибка.
Попробуйте повторить позже

Задача 3#67932Максимум баллов за задание: 7

Решите уравнение

2 3 ∘--4---2--- ∘ -4----2--- log2(|x − 2|+ 1)+ 4x − 3x +5= 2x +5x − 3

Источники: Ломоносов-2023, 11.3 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

Выглядит страшно: и корни, и логарифм по отдельности..может, тут есть какие-то оценочки?)

Подсказка 2

Например, можно обратить внимание, что раз |x-2|³ ≥ 0, то аргумент логарифма ≥ 1, и сам логарифм ≥ 0. А еще в подкоренном выражении слева у старшего члена коэффициент больше, чем в подкоренном выражении справа. Что это может значить?

Подсказка 3

То, что левая часть почти всегда больше правой) А еще сами корни положительные. Поэтому, чтобы решение существовало, нужно чтобы левый корень был не больше, чем правый корень (т.к. логарифм и так ≥ 0). При каких иксах это так?

Подсказка 4

Если написать неравенство на подкоренные выражения, то после нехитрых преобразований, получится, что (x²-2)² ≤ 0! Т.е. x = ±√2. Проверьте, подходят ли они как решение)

Показать ответ и решение

Так как

2 3 2 3 2 3 |x − 2| ≥ 0⇒ |x − 2| +1 ≥1⇒ log2(|x − 2| +1)≥ 0

∘ --4---2--- 4x − 3x + 5≥ 0

∘2x4-+5x2−-3≥ 0

Для существования решения необходимо, чтобы выполнялось неравенство

4x4 − 3x2+ 5≤ 2x4+ 5x2− 3

(x2− 2)2 ≤0

x2 = 2

Проверка показывает, что $√- x= ± 2$ — решение.

Ответ:

$±√2-$

Ошибка.
Попробуйте повторить позже

Задача 4#67940Максимум баллов за задание: 7

Две стороны выпуклого четырёхугольника имеют длину 6, ещё одна — длину 1, а его площадь — наибольшая возможная при таких условиях. Какова длина четвёртой стороны четырёхугольника?

Источники: Ломоносов-2023, 11.4 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

Пусть наши известные стороны это b, b и c, но мы не знаем, в каком порядке они расположены в четырехугольнике: как b, b, c или b, c, b? А вдруг это не важно?)

Подсказка 2

Пусть наш четырехугольник это ABCD, где AB = CD = b, BC = c. Тогда на самом деле площадь четырехугольника AB'CD, где AB' = c, B'C = CD = b будет такой же, потому что треугольник ACD не изменился, а ABC = AB'C, то есть площадь осталась такой же) Давайте теперь мыслить про первый вариант.

Подсказка 3

Можно ли отдельно максимизировать площадь, учитывая наши условия? Например, разбить четырехугольник на какие-то части, и меняя что либо, менять площадь?

Подсказка 4

Давайте отдельно максимизируем площадь ABC и ACD) Начнем с ABC. Мы знаем, что A находится на расстоянии b от точки B. Так давайте будет двигать A по окружности с центром в точке B и радиусом b! Сторона BC как раз не меняется в таком случае. В какой момент площадь ABC будет максимальна?

Подсказка 5

Тогда, когда AB станет перпендикулярна BC! Потому что площадь ABC = 1/2 ⋅ (высота к BC) ⋅ BC, и высота максимальна будет как раз в этом случае. Попробуйте сделать тоже самое с ACD) Какой четырехугольник в таком случае у нас выйдет?

Подсказка 6

Т.к. углы ABC и ADC станут по 90°, то ABCD - вписанный, да и еще у него AB = CD, то есть ABCD - равнобокая трапеция! Осталось посчитать сторону AD, зная все это)

Подсказка 7

Для удобства подсчета, стоит опустить высоты из B и C на AD и воспользоваться формулой высоты в прямоугольном треугольнике)

Показать ответ и решение

$PIC$

Пусть известные длины сторон четырехугольника равны $b,b$ и $c.$ В условии не указан порядок расположения этих сторон: $b,b,c$ или $b,c,b.$ Но вместо четырехугольника $ABCD,$ в котором, скажем $AB = CD =b,BC =c,$ рассмотрим четырехугольник $AB′CD,$ в котором, $B ′C = CD =b,AB′ = c.$ В нем тот же набор известных длин сторон (но в другом порядке), а площади этих четырехугольников равны, так как это суммы $SABC + SACD$ и $SAB′C + SACD,$ причем $△ABC = △AB ′C.$

Поэтому можно считать, что $AB =CD = b,BC =c.$

Заметим, что двигая точку $D$ по дуге окружности радиуса $b$ с центром в точке $C,$ мы будем получать четырехугольник с тем же набором известных длин сторон, с той же частью $ABC,$ а площадь части $ACD$ будет наибольшей тогда, когда $CD ⊥ AC$ (иначе при том же основании $AC$ высота из точки $D$ будет короче, чем $b).$ Двигая аналогично точку $A$ вокруг точки $B,$ получим, что из свойства максимальной площади четырехугольника $ABCD$ вытекает $AB ⊥BD.$

Итак, имеются два прямоугольных треугольника $ABD$ и $ACD$ с общей гипотенузой $AD$ и равными катетами $AB$ и $CD.$ Значит, треугольники равны, как и их высоты на гипотенузу, т.е. $ABCD$ — равнобедренная трапеция с тупыми углами $B$ и $C.$

$PIC$

Пусть $d= AB′ = C′D,$ где $B′$ и $C′$ — проекции точек $B$ и $C$ на $AD.$ Тогда из свойства высоты прямоугольного треугольника получаем

′ ′ ′ 2 2 2 2 2 AB ⋅B D= B B ⇔ d(c+ d)=b − d ⇔ 2d + cd− b = 0

Отсюда, с учётом того, что $d >0,$ получаем

−c+-√c2+-8b2- c+-√c2+-8b2 d= 4 ⇒ a= AD = c+2d= 2

Подставляем $b= 6,c= 1$ и получаем

1+-√1-+8⋅36 a= 2 = 9

Ответ: 9

Ошибка.
Попробуйте повторить позже

Задача 5#67941Максимум баллов за задание: 7

Обозначим через $s(n)$ число цифр в десятичной записи натурального числа $n.$ Найдите сумму

2023 2023 s(2 )+s(5 )

Источники: Ломоносов-2023, 11.5(см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

Понятно, что количество цифр в числе n, это такое k, что 10ᵏ > n > 10ᵏ⁻¹. А какую еще знакомую нам функцию можно связать с k?

Подсказка 2

Логарифм! И правда, ведь получается, что k > log₁₀(n) > k-1. Тогда получается, что k = log₁₀(n) + a, где 0 < a < 1. Как теперь выражается искомая сумма?

Подсказка 3

Получается, что наша сумма это log₁₀(2²⁰²³) + log₁₀(5²⁰²³) + a+b = 2023 + a + b, где 0 < a+b < 2. Остается вспомнить, что количество цифр - это целое число, и станет понятно чему равно a+b!

Показать ответ и решение

Заметим, что

2023 2023 s(2 )= lg(2 )+a =2023lg2+ a, где 0< a< 1

Аналогично,

2023 2023 s(5 ) =lg(5 )+b =2023lg5 +b, где 0< b< 1

Тогда

s(22023)+ s(52023)= 2023(lg2+ lg 5)+ a+ b= 2023+ (a+b)

Значит, число $(a+ b)$ целое, причем $0< a+ b< 2,$ так как $0< a< 1,0 <b <1.$ Отсюда $a +b= 1,$ а ответ равен $2024.$

Ответ:

$2024$

Ошибка.
Попробуйте повторить позже

Задача 6#67942Максимум баллов за задание: 7

Дана последовательность ${a}, n$ в которой $a = 19, 1$ а отношение каждого следующего элемента к предыдущему при всех целых $n≥ 2$ равно

an (n2+ 1)⋅n an−1 = (n−-1)2+-1

Найдите отношение 2023-го члена последовательности к сумме её первых 2022 членов.

Источники: Ломоносов-2023, 11.6 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

Напрямую искать это отношение не хочется. Давайте тогда начнем с aₙ, а там и придумаем. Вспомним, что у нас условие на отношение aₙ/aₙ₋₁. Как им хорошо можно воспользоваться?

Подсказка 2

А давайте перемножим эти условия для n, n-1, ..., 2, 1! Получится, что aₙ/a₁ = aₙ/aₙ₋₁ ⋅ aₙ₋₁}/aₙ₋₂} ⋅ ... ⋅ a₂/a₁ = (n²+1)n/((n-1)²+1) ⋅ ... ⋅ (2²+1)/(1+1) = (n²+1)⋅n!/2. У нас тут есть отношение aₙ к a₁, может тогда легче найти сумму/a₁, ведь отношение получившихся выражений как раз будет отношением aₙ/сумма? Давайте так и поступим)

Подсказка 3

Обозначим сумму первых n-1 члена за Sₙ₋₁. Даже зная aₙ/a₁ для любого n, не очень понятно, как хорошо свернуть сумму. А вдруг можно представить выражение (n²+1)⋅n!/2 как разность двух каких-то выражений, которые зависят от n и n-1? Например как какое-то bₙ - bₙ-₁. Тогда у нас выйдет, что Sₙ₋₁/a₁ будет bₙ₋-b₀, и зная эти b мы легко найдем то, что нам надо!

Подсказка 4

Пошаманим с aₙ/a₁: (n²+1)⋅n!/2 = 1/2 ⋅ (n(n+1) - (n-1)) ⋅ n! = n⋅(n+1)!/2 - (n-1)⋅n!/2. Вот как раз наши bшки! Обозначим тогда bₙ = n⋅(n+1)!/2. Остается найти сумму и посчитать отношение)

Показать ответ и решение

Найдем $an-, a1$ перемножив указанное в условии отношение для различных $n :$

an -an- an−-1 a2 (n2+-1)n-- ((n−-1)2-+1)(n-− 1) (22+-1)2- (n2+-1)n!- a1 =an−1 ⋅an− 2 ⋅⋅⋅a1 = (n − 1)2+1 ⋅ (n− 2)2+ 1 ⋅⋅⋅ 1+ 1 = 2

Представим его в виде разности:

2 an = (n-+-1)n!-= 1(n(n+ 1)− (n− 1))n!= n(n-+1)!− (n-− 1)n!=bn− bn−1, a1 2 2 2 2

где

bn = n(n+-1)! 2

Тогда отношение суммы первых $n$ членов к $a1$ равно

Sn a1+a2+-⋅⋅⋅+-an n(n+-1)! a1 = a1 = (b1 − b0)+(b2− b1)+⋅⋅⋅+(bn− bn−1)= bn− b0 = 2

Стало быть, ответ при $n= 2023$ равен

2 2 2 -an-= -an∕a1-= (n-+-1)n!= n-+-1= n-−-1+-2= n+ 1+ --2-= 2024-1-- Sn−1 Sn−1∕a1 (n − 1)n! n− 1 n− 1 n− 1 1011

Ответ:

$2024-1- 1011$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#67943Максимум баллов за задание: 7

На подвешенном воздухе кубике Рубика, на одном из его $54$ квадратиков, сидит жучок. В какой-то момент он начинает движение по поверхности куба, передвигаясь за каждую секунду на соседний квадратик, т.е. на квадратик, имеющий общую сторону с текущим. Соседний квадратик для первого перемещения был выбран произвольно, а затем жучок следовал таким правилам:

1) при 2-м, 4-м и других чётных перемещениях жучок не менял направления своего движения, т.е. покидал квадратик через сторону, противоположную той, через которую он на этот квадратик попал;

2) при 3-м, 5-м и других нечётных перемещениях жучок поворачивал направо (относительно своего движения).

Через 2023 секунды после начала движения жучок обратил внимание на то, что уже был на этом же квадратике 5 секунд назад. Через какое наименьшее число секунд после 2023-й жучок опять окажется на этом квадратике?

Источники: Ломоносов-2023, 10.7 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

Заметим, что квадратиков ну ооочень много, но ведь многие из них очень похожи?… Если взять конкретный квадратик, то несложно отследить его путь, т.к путь у жучка определяется начальным положением и направлением. Что тогда попробуем сделать?

----—

Подсказка 2

Выделим 9 групп в зависимости от расположения начальной клетки и направления первого шага! Тогда для каждой группы удобно просмотреть пути и отметить, где начинается периодичность.

----—

Подсказка 3

Заметим, что периодичность во всех группах или длины 24, или длины 8. Тогда посмотрим, на какой клетке остановился жучок после 2023 с. и для какой группы это возможно.

----—

Подсказка 4

Оказывается, что такое возможно только для группы, которая начинается с центрального квадратика!

Показать ответ и решение

Для отслеживания движения жучка будем использовать частичную развертку куба, покрывающую $3$ грани. Каждый квадратик будем обозначать двузначным числом, 1-я и 2-я цифры которого являются соответствующими координатами центра квадратика на развертке (единица — ширина квадратика):

$PIC$

Маршрут жучка определяется его начальным положением и направлением его первого перемещения. Хотя всего таких вариантов $54× 4,$ их все можно разбить на $9$ принципиально различных групп:

1) Жучок стартует с центрального квадратика любой грани по направлению к любому ребру

2-3) Старт с углового квадратика любой грани, а первое перемещение в пределах той же грани вдоль ребра, идущего соответственно справа или слева от жучка

4-5) Старт с углового квадратика любой грани, а при первом перемещении жучок переползает на соседнюю грань, причем третья примыкающая грань остается соответственно справа или слева от него

6) Старт с приреберного квадратика любой грани по направлению к центру

7) Старт с приреберного квадратика любой грани с переходом на соседнюю грань при первом перемещении

8-9) Старт с приреберного квадратика любой грани, а первое перемещение в пределах той же грани вдоль ребра, идущего соответственно справа или слева от жучка

Заполним таблицу, в которой для каждой группы приведем пример маршрута в течение того времени, когда обнаруживается его периодичность, т.е. когда на какой-либо четной секунде жучок оказывается на начальном квадратике, а еще через $1$ с — на квадратике, где он был через $1$ с после начала движения.

В случае группы $1$ выберем для старта квадратик $22$ с первым перемещением $22−→ 23$ и проследим весь маршрут, пока не обнаружим, что его период равен $24$ c (1-я колонка таблицы после двойной вертикальной черты).

Заметим, что через $2$ c после начала движения жучок окажется в начальном состоянии группы $8.$ Поэтому для нее маршрут также будет иметь период $24$ с и его можно получить из маршрута группы $1$ сдвигом на $2$ с.

Еще через $2$ с жучок окажется в начальном состоянии группы $4.$ Поэтому и для нее маршрут будет с периодом $24$ с и его можно получить из маршрута группы $1$ сдвигом на $4$ с.

Еще через $2$ с имеем начальное состояние группы $7$ и получаем ее маршрут с периодом $24$ с из маршрута группы $1$ сдвигом на $6$ с.

Для остальных групп получаются кольцевые маршруты с периодом $8$ с, причем в течение одного периода жучок ни на одном квадратике не оказывается дважды.

$PIC$

Так как $2023≡ 7 mod 24$ (остаток от деления $2023$ на $24$ равен $7$ ) и $2023≡ 7 mod 8$ (остаток от деления $2023$ на $8$ равен $7),$ то через $2023$ с после начала движения жучок окажется на том же квадратике, на котором он был через $7$ с после начала, а за $5$ с до этого — на том же квадратике, на котором он был через $2$ с после начала.

Как видно из таблицы, такое совпадение имеет место только для группы $1$ (квадратик $24).$ Так как этот квадратик встречается на маршруте только дважды в течение периода ( $2$ с и $7$ с), следующее попадание на него произойдет через $2+ 24− 7= 19$ (с).

Ответ: 19

Ошибка.
Попробуйте повторить позже

Задача 8#67944Максимум баллов за задание: 7

∙ ∙ ∙ ∙ ∙ ∙

∙ ∙ ∙ ∙ ∙ ∙

Есть два ряда — верхний и нижний, каждый из 6 точек (см. рисунок). Проводят отрезки с концами в противоположных рядах так, чтобы из каждой точки выходил ровно один отрезок. Сколько существует способов провести отрезки, чтобы среди всех пар отрезков было ровно 7 пар пересекающихся отрезков?

Источники: Ломоносов-2023, 10.8 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

В таких задачах полезно посмотреть на случаи поменьше, с меньшим количеством отрезков и необходимых пересечений

Подсказка 2

Когда два отрезка пересекаются? Когда начало первого левее, чем начало второго, а конец первого правее, чем конец второго
Формальнее: Если два отрезка выходят из точек a, b (a < b) и приходят соответственно в точки c, d, то они пересекаются тогда и только тогда, когда (c > d)

Подсказка 3

Давайте посмотрим, что меняется, когда мы добавляем еще один отрезок.
Пусть у нас есть n пар точек и k пересечений отрезков. Добавим одну точку в верхний ряд, и выберем место для её второго конца.
Сколько у нас может получится пересечений в зависимости от её положения?

Подсказка 4

Мы можем поставить второй конец в самую правую точку. Тогда у нас останется k пересечений.
Также мы можем поставить ее в самую левую точку. Тогда у нас добавится n пересечений.
Двигая точку слева направо, мы можем "добавить" к числу пересечений любое число от 0 до n.

Подсказка 5

Давайте подумаем, из каких расстановок отрезков для 5 пар точек мы можем получить необходимую расстановку для 6 пар точек.
Добавляя шестую точку, мы можем увеличить число пересечений на любое число от 0 до 5.
Пусть f(n, k) - количество расстановок отрезков на n парах точек с k пересечениями
Тогда f(6, 7) = f(5, 7) + f(5, 6) + ... + f(5, 2)
Попробуйте обобщить эту формулу, и вычислить ответ ( начиная с f(1, 1) )

Подсказка 6

Общая формула будет иметь вид
f(n, k) = f(n - 1, k) + f(n - 1, k - 1) + ... + f(n - 1, k - n)

Показать ответ и решение

Пусть в каждом ряду по $n$ точек. Способ соединить точки можно задать перестановкой $n$ чисел, ${i ,i ,...,i }: 1 2 n$ первая точка верхнего ряда соединяется с точкой под номером $i1,$ вторая — с $i2,$ и так далее. Значит, всего возможных рисунков будет $n!.$

Теперь берём пару отрезков. Пусть это отрезки с концами $a,ia$ и $b,ib,$ считаем $a< b.$ В каком случае они пересекается? В том, когда $ia > ib.$ Учитывая, что $a,b$ могут быть любой парой, замечаем следующее: общее количество пересечений отрезков равно количеству случаев, когда в перестановке большее число стоит раньше меньшего (не обязательно по соседству). Как сказали бы старшие товарищи, число пересечений равно числу инверсий в перестановке. Так и будем говорить дальше.

Например, $12345$ — нет инверсий и нет пересечений, $21345$ — одна инверсия ( $2$ и $1),$ $43152$ — $6$ инверсий ( $4$ и $3,$ $4$ и $1,$ $4$ и $2,$ $3$ и $1,$ $3$ и $2,$ $5$ и $2).$ Наибольшее количество инверсий будет, если написать числа задом наперёд: $54321,$ какие два числа не выбери — большее будет стоять раньше. То есть инверсий в последнем примере $10,$ а в общем случае — $C2n.$

Как посчитать число перестановок с заданным количеством инверсий? Подойдём к задаче индуктивно. В фигурных скобках будем указывать различные перестановки, а в квадратных перечислим количества перестановок, имеющих соответственно $0,1,...,C2n$ инверсий.

Итак, единственный элемент можно расположить единственным образом, и у нас есть одна перестановка с нулевым числом инверсий.

{1}; [1]

Добавляем двойку — её можно добавить в начало и в конец имеющейся перестановки ${1}.$ Одна из полученных перестановок будет без инверсий, другая — с одной инверсией.

{◟1◝2◜}◞ , {◟2◝1}◜◞ ; [1,1] 0 инверсий1инверсия

Добавляем тройку — её мы можем поставить в любое место каждой из имеющихся перестановок. Тройка больше всех имевшихся ранее чисел, поэтому если поставить её на последнее место — новых инверсий не добавится, если поставить на предпоследнее (на второе) — добавится одна инверсия, а если на первое — будет плюс две инверии. Одна перестановка с нулём инверсий, две перестановки с одной, две перестановки с двумя, одна перестановка с тремя. То есть:

{◟12◝◜3}◞,{◟2 ◝13◜} ◞,{◟13 ◝2◜} ◞,{2◟3 ◝1◜} ◞,{◟31◝◜2}◞,{◟3 ◝21◜} ◞, [1,2,2,1] 0+0 1+0 0+1 1+1 0+2 1+2

Так же будет происходить добавление нового числа $n$ в общем случае: число $n$ можно поставить на любое место, и в зависимости от места к инверсиям добавится $+ 0,+1,+2,...,+(n − 1)$ штук. То есть на новом шаге перестановка с $l$ инверсиями превращается в $n$ перестановок с $l+0,l+1,l+2,...,l+(n− 1)$ инверсиями соответственно.

Посмотрим, какие числа получались в квадратных скобках. Напишем эти последовательности одну под другой:

$pict$

Здесь в $n- й$ строке (нумерация начинается с $1$ ) приводятся числа $Pkn$ для $k =0,1,...,Ckn,$ равные количеству перестановок из $n$ чисел с $k$ инверсиями.

Вспоминая, как происходит добавление нового $n,$ получим

Pnk= Pkn−1 + Pkn−−11 + Pkn−−21+ ⋅⋅⋅+ Pkn−−n1+1 ◟+ ◝0◜и ◞нв. +◟1 ◝◜ин ◞в. +◟2 ◝◜ин◞в. +◟(n−◝1◜)и◞нв.

Действительно, $Pkn− 1$ — количество перестановок из (n-1) чисел, в которых уже есть $k$ инверсий. В них мы вынуждены поставить новое $n$ на последнее место ( $+0$ инверсий). Раз мы ставим $n$ на единственно возможное место, количество перестановок не изменится.

Далее, $Pk−1 n−1$ — количество перестановок с $(k− 1)$ инверсией, и, чтобы добавить недостающую, мы вынуждены ставить $n$ на предпоследнее место ( $+ 1$ инверсия).

Продолжаем так вплоть до $P k− n+1, n−1$ потому что добавить больше $(n− 1)$ инверсии нельзя. Всего получается $n$ слагаемых. Из других перестановок предыдущей строки мы ничего нового получить не сможем.

Заметим, что $P−k =0, n$ так как не бывает перестановок с отрицательным числом инверсий, как и не может быть перестановок со слишком большим (больше чем $C2 n$ ) количеством инверсий.