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

Пункт 1, подсказка 1

Для начала попробуйте подобрать такие наборы, у нас 2 карточки, на каждой по 2 числа.

Пункт 1, подсказка 2

Убедитесь, что наборы (1; 1/4) и (3/4; 1/2) подходят. Попробуйте провести оценку. Например, обязательна ли нам единица в одной из пар?

Пункт 1, подсказка 3

Набор с единицей должен быть, поскольку нам надо мажорировать (1; 0). Какой еще набор нам надо мажорировать и какие тогда карточки должны быть?

Пункт 1, подсказка 4

Нам также надо мажорировать (1/2; 1/2). Для этого на одной из карточек должны быть числа, большие 1/2. Что будет, если рассмотренные пары чисел с карточек совпадают?

Пункт 1, подсказка 5

Тогда их сумма — 3/2. Если это разные пары, посмотрите на набор (3/4; 1/4).

Пункт 1, подсказка 6

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

Пункт 2, подсказка 1

Попробуйте посмотреть, как можно записать число 1 + 10⁻¹⁰⁰ в виде суммы дробей.

Пункт 2, подсказка 2

Давайте добавим, что дроби у нас будут положительные и со знаменателем 10²⁰⁰. Что можно сказать о количестве таких записей?

Пункт 2, подсказка 3

Оно будет конечно. Тогда давайте обозначим его за n и запишем на карточки все соответствующие наборы. Подойдут ли нам такие карточки?

Пункт 2, подсказка 4

Рассмотрите произвольный набор с суммой 1 и замените в нем каждое число на ближайшую сверху дробь со знаменателем 10²⁰⁰. На сколько при округлении увеличится сумма?

Пункт 2, подсказка 5

Сумма увеличится не более, чем на 10¹⁰⁰ ⋅ (1 / 10²⁰⁰) = (1 / 10¹⁰⁰). Что мы тогда получим?

Пункт 2, подсказка 6

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

Пункт 2, подсказка 7

Можем увеличить числители некоторых дробей, чтобы сумма стала равной 1 + 10⁻¹⁰⁰. Осталось сделать вывод про мажорируемость.

Пункт 3, подсказка 1

Давайте сначала придумаем какой-то пример и прикинем возможные значения a(2,4).

Пункт 3, подсказка 2

Рассмотрите наборы (21/34; 1/2; 1/3; 1/4) и (1; 13/24; 13/68; 13/102). Чему равны их суммы? А чему равен √3?

Пункт 3, подсказка 3

Сумма в каждом наборе меньше 1,71, а √3 = 1,73... . Попробуйте проверить, что эта пара наборов мажорирует все четверки.

Пункт 3, подсказка 4

Пусть у нас есть упорядоченная тройка с суммой x. Что можно сказать про её среднее и меньшее числа?

Пункт 3, подсказка 5

Среднее число будет не больше x/2, а малое — не больше x/3. Распространите это наблюдение на четвёрки. Посмотрите на наборы, которые мы привели ранее.

Пункт 3, подсказка 6

На самом деле, аналогичное верно для четвёрок. Если максимальное число в четверке больше 21/34, то второе по величине будет не больше 13/34. Продолжите оценки на числа четвёрки и докажите, что приведённые 2 набора действительно мажорируют все четвёрки.

Пункт 4, подсказка 1

Нам нужно найти разность между двумя значениями функции a. Давайте для начала попробуем посчитать a(1,k). Вспомните, что мы знаем из прошлых пунктов о числах l≤k.

Пункт 4, подсказка 2

Для каждого такого l должна быть карточка, на которой l-ое по величине число не меньше, чем 1/l. Предположим, что такая карточка одна. Что можно сказать о сумме её чисел?

Пункт 4, подсказка 3

Сумма ее чисел будет не меньше 1 + 1/2 + ... + 1/k. А подойдет ли нам такая карточка?

Пункт 4, подсказка 4

Заметим, что в наборе с единичной суммой l-ое по величине число не больше 1/l, следовательно, карточка подойдет. А чему тогда будет равно a(1,k)?

Пункт 4, подсказка 5

a(1,k) = 1 + 1/2 + ... + 1/k. Давайте теперь рассмотрим произвольную пару натуральных чисел l < k и попробуем предъявить 2 набора, которые будут зависеть от k и l и мажорировать все наборы с единичной суммой.

Пункт 4, подсказка 6

Рассмотрим произвольный набор a₁ > a₂ > ... > aₖ с единичной суммой. Заметим, что для любого i aᵢ ≤ 1/i. Какой набор тогда будет мажорировать любой набор с единичной суммой, при условии, что все числа не превосходят 1/l?

Пункт 4, подсказка 7

Можно взять такой набор: в нем l раз встретится дробь 1/l, а также будут числа 1/(l + 1), 1/(l + 2), ... , 1/k. Осталось рассмотреть случай, когда a₁ > l. Попробуйте оценить сумму остальных aᵢ.

Пункт 4, подсказка 8

Это единичный набор, следовательно, a₂ + a₃ + ... + aₗ₊ᵢ < 1 - 1/l. Оцените aₗ₊ᵢ.

Пункт 4, подсказка 9

aₗ₊ᵢ ≤ (l - 1) / (l(l + i - 1)). Как, пользуясь этим соотношением, можно задать второй набор?

Пункт 4, подсказка 10

Второй набор будет следующего вида: (1; 1/2; ... ; 1/l; (l - 1) / l²; (l - 1) / (l(l + 1)); ... ; (l - 1) / (l(k - 1)). Попробуйте доказать, что разность между a(1,k) и наибольшей суммой одного из этих наборов может быть сколь угодно большой при правильном выборе l и k.

Пункт 4, подсказка 11

Посчитайте разницу между суммой с первой карточки и a(1,k).

Пункт 4, подсказка 12

Получим 1 + 1/2 + ... + 1/(l - 1) - (l - 1)/l. Заметьте, что эта сумма больше 1/2 + ... + 1/(l - 1).

Пункт 4, подсказка 13

При достаточно больших l эта сумма будет сколь угодно большой. Осталось посмотреть на вторую карточку.

Пункт 4, подсказка 14

У Вас должно получиться, что разность между a(1,k) и суммой чисел со второй карточки больше (1/l) ⋅ (1/(l+1) + 1/(l+2) + ... + 1/(k-1)) - 1. Осталось понять, ограниченно ли это число, и сделать соответствующие выводы.