?

Log in

No account? Create an account
задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [май. 29, 2008|10:07 pm]
Anatoly Vorobey
Второй день очень раздражает, что не могу доказать:

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

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

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

Comments:
[User Picture]From: rruben
2008-05-30 05:14 am
Боюсь представить практическую задачу, в которой это может понадобиться :)
(Ответить) (Thread)
[User Picture]From: flaass
2008-05-30 05:47 am
Если N простое, то знаю и использую активно, уча детишек.
А для степени двойки - подумаю.
(Ответить) (Thread)
[User Picture]From: falcao
2008-05-30 10:07 am

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

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

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

С учётом справедливости утверждения для простых N, получается, что оно верно всегда.
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2008-05-30 02:40 pm
Классно! Спасибо!
Жаль, что я сам в этом направлении ни разу не подумал. Придумал бы сам - протащился бы еще больше.
(Ответить) (Parent) (Thread)
From: arcbishop
2008-06-01 12:39 pm

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

Возьми N подряд идущих чисел. Если N четное (ага. степень двойки) то сумма будет делится на N.
(Ответить) (Parent) (Thread)
[User Picture]From: castasat
2008-05-30 06:01 am
Докажем, что:
1+3+5+7+...+(2n-1)=n2

Tk=2k-1
Tk-1=2(k-1)-1=2k-3
Tk-2=2(k-2)-1=2k-5
...
Tk-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))=2n2
1+3+5+7+...+(2n-1)=n2
чтд.

Можно взять любую непрерывную подпоследовательность этой последовательности, начиная с первого числа и заканчивая произвольным N-м, так что сумма этих N чисел даст N2, что всегда делится на N.
(Ответить) (Thread)
[User Picture]From: castasat
2008-05-30 06:04 am
Кажется, не так прочитал условие
(Ответить) (Parent) (Thread)
[User Picture]From: uemoe
2008-05-30 06:06 am
Степень двойки важна. Нужно рассматривать делимость чисел на два, доказывается индукцией. Очевидно, что из трех чисел всегда можно выбрать два, сумма которых будет делиться на два.
(Ответить) (Thread)
From: barbarys_ka
2008-05-30 06:12 am
Очень подозреваю, что идея доказательства для степени двойки будет аналогична идее доказательства в общем случае, т.е. если утверждение задачи верно для m и n, то оно верно и для mn.

Интересно, а это доказательство 1960-го года первое?
www.math-inst.hu/~p_erdos/1961-25.pdf
(Ответить) (Parent) (Thread)
From: u1ik
2008-05-30 06:14 am
Оригинал, думаю, находится здесь
10164 - Number Game .

Совсем недавно использовал ее я тренировок местной 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.
(Ответить) (Thread)
From: marknn
2008-05-30 03:45 pm
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.

(Ответить) (Parent) (Thread)
From: u1ik
2008-05-30 04:15 pm
Nice solution, indeed. :)
(Ответить) (Parent) (Thread)
[User Picture]From: alll
2008-05-30 07:06 am
Э... Отчего-то вспомнилась формула Гаусса для арифметической прогрессии. ;)
(Ответить) (Thread)
[User Picture]From: spartach
2008-05-30 12:01 pm
Это замечательная теорема Эрдеша-Гинзбурга-Зива, доказана в 1961 году.

Сначала доказывается (не слишком просто) для простых N, затем переносится на все натуральные N.
(Ответить) (Thread)
From: dizzy57
2008-05-30 02:46 pm

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

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

А теорема, действительно, замечательная.
(Ответить) (Parent) (Thread)
[User Picture]From: uuner
2008-05-30 12:16 pm
Вообще, если нужно доказать что-то с натуральным параметром, первое, что стоит попробовать - рассуждение по индукции.
(Ответить) (Thread)
From: dizzy57
2008-05-30 02:49 pm
В теории чисел индукция проходит лучше по разложению на просты множители, это нам ещё Мощевитин объяснял. =)
(Ответить) (Parent) (Thread)
[User Picture]From: uuner
2008-05-30 02:58 pm
Ага, просто в данном случае попытка индуктивного рассуждения по степени двойки сразу приводит к вот этому доказательству.
(Ответить) (Parent) (Thread)
From: ex_juan_gan
2008-05-30 05:31 pm
Различных целых чисел?
(Ответить) (Thread)
[User Picture]From: yury_lifshits
2008-05-30 08:41 pm
По индукции.
Для N=1 верно (любое целое число делится на 1)

Переход от N-1 к N:
Пока остается хотя бы три числа всегда можно найти пару, которая дает четную сумму. Нашли - отложили. Итого можно отложить N-1 пару с четными суммами. Делим каждую сумму на два, применяем ндукционное предположение. Значит, можно найти N/2 пар, полусуммы которых в сумме делятся на N/2. А значит сумма этих парных сумм делится на N. То есть сумма N участников этих пар делится на N. Что и требовалось доказать.
(Ответить) (Thread)
[User Picture]From: rsc_gai
2008-05-31 05:21 am
Со степенью двойки вроде легко решается индукцией.
(Ответить) (Thread)
[User Picture]From: tea_with_milk
2008-05-31 06:43 am
Мат индукция, вроде как, достаточно просто--для степени двойки... Верно ли в общем случае--не знаю...
(Ответить) (Thread)