задачка

[avva]

Второй день очень раздражает, что не могу доказать:

N - степень двойки (возможно, это условие лишнее, не уверен). Даны 2N-1 целых чисел. Доказать, что можно выбрать ровно N из них так, что сумма выбранных делится на N.

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

Комментарии читать не буду, а буду пытаться решать.

Comments

[rruben.livejournal.com]

Боюсь представить практическую задачу, в которой это может понадобиться :)

[flaass.livejournal.com]

Если N простое, то знаю и использую активно, уча детишек.
А для степени двойки - подумаю.

[castasat.livejournal.com]

Докажем, что:
1+3+5+7+...+(2n-1)=n²

T_k=2k-1
T_k-1=2(k-1)-1=2k-3
T_k-2=2(k-2)-1=2k-5
...
T_k-n=2(k-n)-1=2k-2n-1

1+3+5+7+...+(2n-7)+(2n-5)+(2n-3)+(2n-1)=
/поскольку в последовательности ровно n чисел/
=2n*n-(1+3+5+7+...+(2n-1))
/переносим сумму в левую часть равенства/
2*(1+3+5+7+...+(2n-1))=2n²
1+3+5+7+...+(2n-1)=n²
чтд.

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

[castasat.livejournal.com]

Кажется, не так прочитал условие

[uemoe.livejournal.com]

Степень двойки важна. Нужно рассматривать делимость чисел на два, доказывается индукцией. Очевидно, что из трех чисел всегда можно выбрать два, сумма которых будет делиться на два.

[barbarys-ka.livejournal.com]

Очень подозреваю, что идея доказательства для степени двойки будет аналогична идее доказательства в общем случае, т.е. если утверждение задачи верно для m и n, то оно верно и для mn.

Интересно, а это доказательство 1960-го года первое?
www.math-inst.hu/~p_erdos/1961-25.pdf

[u1ik.livejournal.com]

Оригинал, думаю, находится здесь
10164 - Number Game (http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1105).

Совсем недавно использовал ее я тренировок местной ACM ICPC команды.
Вот отрывок из моего разбора:

The correct solution exploits the fact that N = 2^k. The idea is to reduce the original problem (of size 2*N-1) into a smaller problem (of size 2*N/2-1).

The base case is easy, when N = 2, then we have to select two number out of three such that their sum is even. For this we just select two numbers of the same parity.

For general case, we assume that we can solve problems of size N/2.
We divide our initial set of numbers (of size 2*N-1) into two subsets (of size 2*N/2-1). By induction, we can select N/2 numbers from each subset such that their sum divides N/2. So the sums of the selected numbers are:
sum1 = k1 * (N/2)
sum2 = k2 * (N/2)
where k1 and k2 some positive integers.

Now if we combine the selected numbers we get N numbers. But unfortunately their sum does not necessarily divide N. For this we need that k1 and k2 have the same parity. If we would have three subsets instead of only two, we could always find ki and kj of the same parity (as in the base case). But we can build the third subset from the numbers that were rejected in the first two subsets.

[alll]

Э... Отчего-то вспомнилась формула Гаусса для арифметической прогрессии. ;)

мультипликативность

[falcao.livejournal.com]

Условие из задачи (зависящее от N) обладает свойством мультипликативности. Пусть N=km, и для каждой из задач с параметром k или m утверждение верно. Тогда будем из 2N-1 числа отбирать группы из k чисел, суммы которых делятся на k. Это можно сделать 2m-1 раз, после чего останется k-1 число.

В каждой из 2m-1 групп найдём суммы и разделим их на k. А потом применим предположение индукции для параметра m к этим новым числам. Это в итоге приведёт к km числам с суммой, делящейся на km.

С учётом справедливости утверждения для простых N, получается, что оно верно всегда.

[spartach.livejournal.com]

Это замечательная теорема Эрдеша-Гинзбурга-Зива, доказана в 1961 году.

Сначала доказывается (не слишком просто) для простых N, затем переносится на все натуральные N.

[uuner.livejournal.com]

Вообще, если нужно доказать что-то с натуральным параметром, первое, что стоит попробовать - рассуждение по индукции.

[flaass.livejournal.com]

Классно! Спасибо!
Жаль, что я сам в этом направлении ни разу не подумал. Придумал бы сам - протащился бы еще больше.

я, пожалуй, приложу ссылку

[dizzy57.livejournal.com]

http://en.wikipedia.org/wiki/Zero-sum_problems

А теорема, действительно, замечательная.

[dizzy57.livejournal.com]

В теории чисел индукция проходит лучше по разложению на просты множители, это нам ещё Мощевитин объяснял. =)

[uuner.livejournal.com]

Ага, просто в данном случае попытка индуктивного рассуждения по степени двойки сразу приводит к вот этому (http://avva.livejournal.com/1924897.html?thread=51593505#t51593505) доказательству.

[marknn.livejournal.com]

There is even simpler solution:

Suppose there A even values and B odd ones, where A+B = 2N-1. Thus either A or B is odd.

Now partition all even numbers into pairs (among themselves) and partition all odd numbers into pairs (leaving one number behind). Thus we have N-1 pairs
and sum of each pair is even. Consider the sequence of sums {S_i} and since they are all even, apply induction to {S_i / 2}. We will have that we could choose (N/2) pairs that will divide N/2. Since the original sum sequence was twice of that thus the corresponding subset in {S_i} will divide N.

[u1ik.livejournal.com]

Nice solution, indeed. :)

[ivan-gandhi.livejournal.com]

Различных целых чисел?

[yury-lifshits.livejournal.com]

По индукции.
Для N=1 верно (любое целое число делится на 1)

Переход от N-1 к N:
Пока остается хотя бы три числа всегда можно найти пару, которая дает четную сумму. Нашли - отложили. Итого можно отложить N-1 пару с четными суммами. Делим каждую сумму на два, применяем ндукционное предположение. Значит, можно найти N/2 пар, полусуммы которых в сумме делятся на N/2. А значит сумма этих парных сумм делится на N. То есть сумма N участников этих пар делится на N. Что и требовалось доказать.

[rsc-gai.livejournal.com]

Со степенью двойки вроде легко решается индукцией.

[tea-with-milk.livejournal.com]

Мат индукция, вроде как, достаточно просто--для степени двойки... Верно ли в общем случае--не знаю...

Re: мультипликативность

[arcbishop.livejournal.com]

Возьми N подряд идущих чисел. Если N четное (ага. степень двойки) то сумма будет делится на N.