2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Разбиение на множества с одинаковой суммой
Сообщение06.05.2015, 20:26 
Целые положительные числа $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$ и "перебросить" в другую группу.

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

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение06.05.2015, 20:36 
Аватара пользователя
2old в сообщении #1011841 писал(а):
Допустим, верно для $n$. Тогда $n+1$ число может быть только четным, иначе сумма будет нечетной.
Это ошибка (откуда тогда могут взяться в наборах нечетные числа?). Из того, что для $n$ утверждение верно, не следует, что корректный набор из $n+1$ чисел всегда должен получаться из корректного набора $n$ чисел добавлением ещё одного числа. Он может строиться «не опираясь на предшественников».

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

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение06.05.2015, 21:32 
Аватара пользователя
По-моему, и значительно более вялых ограничений по скорости роста хватило бы для того, чтобы сформировать из этих чисел любую сумму в пределах досягаемости.

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение06.05.2015, 21:35 
svv
Да, спасибо :facepalm:

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 :cry:

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение06.05.2015, 21:45 
Аватара пользователя
ИСН в сообщении #1011869 писал(а):
и значительно более вялых ограничений по скорости роста хватило бы
Нет, потому что если первые $n-1$ будут единицы, а $n$-е хотя бы $n+1$ — капец.

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

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение07.05.2015, 01:13 
Аватара пользователя
svv в сообщении #1011875 писал(а):
ИСН в сообщении #1011869 писал(а):
и значительно более вялых ограничений по скорости роста хватило бы
Нет, потому что если первые $n-1$ будут единицы, а $n$-е хотя бы $n+1$ — капец.
Ну вот это и есть ограничение по скорости роста. Только оно, как видите, формулируется в относительных терминах: через предыдущие.

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

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение07.05.2015, 02:04 
Аватара пользователя
Да, получается, что в абсолютной форме ослаблять нельзя.

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение12.05.2015, 10:45 
svv
Понимаю, что вы много подсказали, но я все равно не осилил :(

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

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение12.05.2015, 16:44 
Аватара пользователя
Алгоритм Вы описали совершенно правильно.
2old в сообщении #1013800 писал(а):
на каждом ходу разница по абсолютному значению будет уменьшаться
А здесь надо уточнить.

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

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

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение14.05.2015, 18:55 
Пусть $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$
Но это сильно грубо :(

 
 
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение14.05.2015, 23:03 
Аватара пользователя
Вот шаг индукции.

Если гиря $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$.
Аналогично для случая, когда гиря кладётся на левую чашу.

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group