Комбинаторика на ЮМШ

1. Заметим, что при перестановке столбцов и строк в расстановке чисел она всё ещё будет удовлетворять условию. Значит, можно посчитать число способов с в нижнем левом угле и затем умножить его на . Разберём возможные позиции для двойки:

(остальные числа можем поставить как угодно)

(нам нельзя ставить в верхний правый угол. выбираем для неё одно из трёх других мест и расставляем остальные как угодно)

(симметричен предыдущему случаю)

Тогда

2. Будем расставлять числа по возрастанию. Переставим столбцы и строки так, чтобы находилась в левом нижнем углу. Рассмотрим долю мест, на которые мы можем поставить . Эта доля . Для эта доля будет . И в общем случае: с каждым новым числом общее количество свободных мест уменьшается на 1, а количество подходящих увеличивается максимум на . Сравним:

что при верно.

Тогда общее количество мест

Докажем, что

что равносильно

По неравенству о средних:

Тогда

что и требовалось.

3. Докажем, что

что равносильно

Базу легко проверить

По предположению индукции

а для перехода надо доказать

Тогда докажем

что равносильно

а это уже известное неравенство (можно оценить даже не числом 8, а числом Эйлера - числом ), которое тоже легко проверить по индукции для любого натурального

4. Будем расставлять числа по возрастанию. Пусть мы начали с какой-то из двух строк. Нам интересен первый момент, когда мы “перескочим” на другую, так как после этого остальные числа можно расставить как угодно.

Пусть мы “перескочили” на числе . Посчитаем количество таких расстановок: мы выбираем одну из двух строк начальной, затем расставляем числа от до в этой строке, затем выбираем, куда поставить — для этого есть только способов, так как мы должны поставить его в один столбец с любым из чисел. Все остальные числа можем расставить как угодно:

Таким образом,

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

Осталось посчитать эту сумму. Распишем её:

Пусть у нас есть игроков, которые упорядочены по убыванию своей силы. мы выбираем среди них команду из игроков и капитана, который должен быть сильнее всех игроков. С одной стороны, мы можем просто набрать команду из игроков и назначить капитаном самого сильного из них. Это же число способов можно посчитать по-другому: выберем самого сильного после капитана участника команды. Пусть он имеет номер (то есть сильнее него ровно человек). Тогда у нас есть способов выбрать капитана, и потом нам нужно набрать команду из человека из . Получается, что