2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Разбиение на множества с одинаковой суммой
Сообщение06.05.2015, 20:26 


07/04/15
244
Целые положительные числа $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 
Заслуженный участник


23/07/08
10626
Crna Gora
2old в сообщении #1011841 писал(а):
Допустим, верно для $n$. Тогда $n+1$ число может быть только четным, иначе сумма будет нечетной.
Это ошибка (откуда тогда могут взяться в наборах нечетные числа?). Из того, что для $n$ утверждение верно, не следует, что корректный набор из $n+1$ чисел всегда должен получаться из корректного набора $n$ чисел добавлением ещё одного числа. Он может строиться «не опираясь на предшественников».

 Профиль  
                  
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение06.05.2015, 20:42 
Заслуженный участник
Аватара пользователя


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

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


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

 Профиль  
                  
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение06.05.2015, 21:35 


07/04/15
244
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 
Заслуженный участник


23/07/08
10626
Crna Gora
ИСН в сообщении #1011869 писал(а):
и значительно более вялых ограничений по скорости роста хватило бы
Нет, потому что если первые $n-1$ будут единицы, а $n$-е хотя бы $n+1$ — капец.

 Профиль  
                  
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение07.05.2015, 00:50 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение07.05.2015, 01:13 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
svv в сообщении #1011875 писал(а):
ИСН в сообщении #1011869 писал(а):
и значительно более вялых ограничений по скорости роста хватило бы
Нет, потому что если первые $n-1$ будут единицы, а $n$-е хотя бы $n+1$ — капец.
Ну вот это и есть ограничение по скорости роста. Только оно, как видите, формулируется в относительных терминах: через предыдущие.

 Профиль  
                  
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение07.05.2015, 01:42 
Заслуженный участник


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

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


18/05/06
13435
с Территории
Да, получается, что в абсолютной форме ослаблять нельзя.

 Профиль  
                  
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение12.05.2015, 10:45 


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

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

 Профиль  
                  
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение12.05.2015, 16:44 
Заслуженный участник


23/07/08
10626
Crna Gora
Алгоритм Вы описали совершенно правильно.
2old в сообщении #1013800 писал(а):
на каждом ходу разница по абсолютному значению будет уменьшаться
А здесь надо уточнить.

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

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

 Профиль  
                  
 
 Re: Разбиение на множества с одинаковой суммой
Сообщение14.05.2015, 18:55 


07/04/15
244
Пусть $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 
Заслуженный участник


23/07/08
10626
Crna Gora
Вот шаг индукции.

Если гиря $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