Сюжет 1
На n карточках написали по k чисел, сумма на каждой карточке равна m. Оказалось, что любой набор из k неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть a(n, k) — наименьшее m, при котором это возможно.
1.3 Докажите, что
Рассмотрим, например, следующую пару наборов:
Сумма в каждом равна это даже меньше, чем 1,71, а
Проверим, что эта пара наборов мажорирует все нужные четвёрки. Ясно (*), что в упорядоченной тройке с суммой x среднее число — не больше, чем а малое — не больше, чем аналогичное верно для четвёрок. Действительно, если максимальное число в четвёрке больше то второе по величине — не больше, чем третье не больше а самое маленькое не
Как прийти к этому решению?
Рассмотрим ситуацию, в которой в первой четверке максимальное число равно 1, а во второй Заметим, что для
получим, что третье число в первой четверке не меньше, чем а рассмотрев для четверки вида
что четвертое число первой четверки — это хотя бы Значит, сумма в первой четверке хотя бы
Далее разберем случай, в котором четверки
накрываются второй суммой. Тогда четверка также накрывается второй суммой (если мы, конечно, не хотим сумму в первой четверке, большую 1,75). В такой ситуации второе число во второй четверке хотя бы третье — хотя бы четвертое — хотя бы Значит, сумма во второй четверке хотя бы третье — хотя бы четвертое — хотя бы Значит, сумма во второй четверке хотя бы
Теперь заметим, что все пары вида
подходят. Действительно (*), если наибольшее число попадает в полуинтервал то тогда следующее по размеру не больше, чем третье — не больше, чем а четвертое — не больше, чем Аналогично разбирается случай, когда наибольшее число в четверке попадает в интервал Значит, любой подходящий вариант может быть сведен к парам такого вида без увеличения суммы. Если
то, очевидно, можно изменить a так, чтобы эти выражения стали равны и ближе друг к другу, максимальное из них, соответственно, уменьшится. Если же
то а значит Сумма в четверках в этом случае равна