задачка

[avva]

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

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

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

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

Comments

[flaass.livejournal.com]

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

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

[falcao.livejournal.com]

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

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

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

[flaass.livejournal.com]

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

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

[arcbishop.livejournal.com]

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