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

1. Пример: наборы ( ) и ( ).

Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать ( ), и набор, в котором оба числа больше , чтобы мажорировать . Если это одна и та же пара, то сумма уже . Если разные, то посмотрим на набор : чтобы набор мажорировал его, должно быть , а чтобы набор с парой чисел, больших мажорировал — это должен быть набор, как минимум . Легко видеть также, что указанный набор подходит.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

3. Рассмотрим, например, следующую пару наборов:

Сумма в каждом равна , это даже меньше,чем 1,71 , а . Проверим, что эта пара наборов мажорирует все нужные четвёрки. Ясно (*), что в упорядоченной тройке с суммой среднее число - не больше, чем , а малое - не больше, чем ; аналогичное верно для четвёрок. Действительно, если максимальное число в четвёрке больше , то второе по величине - не больше,чем , третье не больше а самое маленькое не больше , значит такая четверка мажорируется вторым набором. Аналогично, если максимальное число не больше, чем , то оно мажорируется первым набором.

_________________________________________________________________________________________________________________________________________________________________________________

4. Вычислим . Как уже отмечалось, для всякого должна быть карточка, в которой -ое по величине число не меньше, чем . Если карточка всего одна, то сумма на этой карточке, таким образом, не меньше . С другой стороны, карточка , очевидно, подходит, т.к. в наборе с единичной суммой -ое по величине число не больше , так что . Теперь рассмотрим произвольную пару натуральных чисел , соотношение между которыми мы уточним позднее, и предъявим два набора, вдвоём мажорирующих все наборы с единичной суммой: а именно

и

Действительно, рассмотрим любой упорядоченный по убыванию набор ( ) с единичной суммой. Ясно, что при любом и поэтому первая карточка мажорирует любой набор с единичной суммой, в котором все числа не превосходят .

Пусть, напротив, . Тогда для любого имеем

Поэтому любой набор с мажорируется второй из наших карточек.

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

и эта величина при достаточно больших может быть сделана, как известно, сколь угодно большой. Теперь зафиксируем произвольное и посмотрим на вторую карточку: сумма чисел на ней меньше, чем , на

Поскольку выражение в скобках при фиксированном и неограниченном может быть сделано сколь угодно большим, то можно выбрать так, что эта разность будет больше разности между и первой суммой, которая одним лишь выбором может быть сделана сколь угодно большой для произвольного . Утверждение доказано, последовательность из условия не ограничена.