Разбиение на множества с одинаковой суммой

[2old]

Целые положительные числа $a_1, a_2, . . . , a_n$ таковы, что $a_k\leq k$ и сумма всех этих чисел четна и равна $2S$. Докажите, что эти числа можно разбить на две группы, сумма по каждой из которых равна $S$.

Для $n=3$ имеем два набора $\{1,1,2\}$, $\{1,2,3\}$ из которых можно сформировать заданные последовательности. Допустим, верно для $n$. Тогда $n+1$ число может быть только четным, иначе сумма будет нечетной. В разбиении на две группы для $n$, отнесем $a_{n+1}$ к той, где элементов больше. Теперь нужно из элементов этой группы выбрать такие элементы, что их сумма равна $a_{n+1}/2$ и "перебросить" в другую группу.

Дальше мысль остановилась. Подскажите, как решать

[svv]

2old в сообщении #1011841 писал(а):

Допустим, верно для $n$. Тогда $n+1$ число может быть только четным, иначе сумма будет нечетной.

Это ошибка (откуда тогда могут взяться в наборах нечетные числа?). Из того, что для $n$ утверждение верно, не следует, что корректный набор из $n+1$ чисел всегда должен получаться из корректного набора $n$ чисел добавлением ещё одного числа. Он может строиться «не опираясь на предшественников».

[gris]

Надо наоборот от $n+1$ переходить к $n-1$. А это сделать можно, выбрав среди чисел два равных. А если нельзя выбрать, то это случай непосредственного указания разбиения. Нет, не сработает из-за неравенств. Например, $1,1,2,3,4,5$ .

[ИСН]

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

[2old]

svv
Да, спасибо

gris
Случай непосредственного указания разбиения это, видимо, когда все $a_k=k$? Честно говоря, ничего не понимаю.
После вашего комментария возникла мысль, что для каждого $S$ можно попытаться рассмотреть самую короткую цепочку, т.е. с $k=1\dots n-1$ заполняем $a_k=k$, а $a_n=S-\sum\limits_{k=1}^{n-1}a_k$ Но ничего хорошего дальше не идет. Да еще они и не единственные :( Может стоит тогда наоборот, самые длинные, т.е. состоящие только из единиц....

Задача все больше похожа на пугающую меня задачу про 15 стаканчиков M655http://kvant.mccme.ru:8080/1981/07/resheniya_zadachnika_kvanta_ma.htm

[svv]

ИСН в сообщении #1011869 писал(а):

и значительно более вялых ограничений по скорости роста хватило бы

Нет, потому что если первые $n-1$ будут единицы, а $n$-е хотя бы $n+1$ — капец.

[svv]

2old
Ваши числа всегда можно отсортировать по возрастанию с сохранением свойства $a_k\leqslant k$. Считаем, что это сделано.
Представьте, что числа Вашего набора — это гири, и $k$-я гиря весит $a_k$.
У Вас есть весы с двумя чашами, которые показывают разность веса грузов на левой и правой чаше.
Начинайте класть на весы гири в порядке убывания индексов. На каждом из $n$ «ходов» Вы должны решить, на какую чашу положить гирю.
Самый простой и естественный алгоритм выбора чаши даёт нужную для доказательства гарантию. Что за алгоритм? Какова гарантия?

[ИСН]

svv в сообщении #1011875 писал(а):

ИСН в сообщении #1011869 писал(а):

и значительно более вялых ограничений по скорости роста хватило бы

Нет, потому что если первые $n-1$ будут единицы, а $n$-е хотя бы $n+1$ — капец.

Ну вот это и есть ограничение по скорости роста. Только оно, как видите, формулируется в относительных терминах: через предыдущие.

[svv]

OK, я Вас понимаю: мы можем взять в набор сначала число 1, а потом каждое следующее $a_k \leqslant $ аж сумме предыдущих плюс 1. Такая свобода, числа могли бы расти в геометрической прогрессии, а я умудрился в примере эту возможность запороть.
Но, с другой-то стороны, я условие $a_k\leqslant k$ нарушил всего-то на единицу, а Вы обещали (или мне показалось), что его можно и больше нарушить. То есть 1) вот в такой форме условие совсем нельзя ослаблять и 2) сильно я в примере вышел за пределы исходного ограничения или нет — вопрос неоднозначный.

[ИСН]

Да, получается, что в абсолютной форме ослаблять нельзя.

[2old]

svv
Понимаю, что вы много подсказали, но я все равно не осилил :(

Пусть весы показывают разницу между правой и левой чашами.
Алгоритм такой: Двигаясь по убыванию индексов кладем гири на чаши, если разница $0$ то кладем на любую, если положительная, то на левую чашу, если отрицательная, то на правую.
Раз мы отсортировали гири по возрастанию, то на каждом ходу разница по абсолютному значению будет уменьшаться.

[svv]

Алгоритм Вы описали совершенно правильно.

2old в сообщении #1013800 писал(а):

на каждом ходу разница по абсолютному значению будет уменьшаться

А здесь надо уточнить.

Давайте номером хода считать номер индекса гири. Номера уменьшаются, да, это непривычно, но привыкаемо. Обратный отсчёт.

Докажите, что если следовать алгоритму, то после $k$-го хода отклонение весов от равновесия (по модулю) не превосходит $k$. Подчёркиваю: реальное отклонение может быть и меньше и после какого-то хода может даже увеличиться, но оценка отклонения сверху неумолимо опускается с каждым ходом на $1$.
Вероятно, следует использовать индукцию.

[2old]

Пусть $i$ номер хода, тогда $a_{n-i+1}$ номер гири в ходу $i$, $\delta_i$ модуль отклонения весов в ходу $i$.
База $i=1$, $\delta_1=|a_n|\leq n$ (по условию)
Пусть $i=k$, $\delta_k\leq n-k+1$

Как устроена $\delta_k$
$\delta_1=|a_n|$
$\delta_2=|a_n-a_{n-1}|$
$\delta_3=|a_n-a_{n-1}-a_{n-2}|$, так как гири отсортированы по возрастанию массы, то за второй ход мы знак точно не поменяем, значит можем кинуть третью гирю на ту же чашу, что и вторую. А как дальше, не понятно. Но может оно и не нужно...Если мы получили на прошлом ходу отрицательное подмодульное выражение, то нужно добавить вес следующей гири, если положительное, то отнять. Но по модулю эти два случая одинаковы. Тогда
$\delta_{k+1}=|X+a_{n-k}|\leq |X|+|a_{n-k}|\leq n-k+1+n-k = 2(n-k)+1$
Но это сильно грубо :(

[svv]

Вот шаг индукции.

Если гиря $a_k$ кладётся на правую чашу, то предыдущее отклонение $-(k+1)\leqslant \delta_{k+1}\leqslant 0$.
Меньше $-(k+1)$ отклонение быть не может по предположению индукции, а если будет больше $0$, гирю положим на левую чашу.
Вес гири $1\leqslant a_k \leqslant k$.
Суммируя эти неравенства, для нового отклонения $\delta_k=\delta_{k+1}+a_k$ получаем
$-k \leqslant \delta_k \leqslant k$.
Аналогично для случая, когда гиря кладётся на левую чашу.