Школьная задача про числа

Irbis-S

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

Vlad128

рассмотри остатки от деления на N, их как раз N штук, кому-то должно не хватить места.
2. ?
3. PROFIT!
? — начинаем суммировать все подряд (по модулю N). Получаем N "частичных сумм". Либо среди них есть 0 (тогда ответ — первые несколько чисел либо найдутся две одинаковых. Полуинтервал между ними — как раз искомые числа.

griz_a

три наводящих соображения:
а) заменить все числа на остатки
б) рассмотреть самый часто встречающийся остаток a (пусть он встречается m раз)
в) посчитать сколько чисел блокируют a, 2a, 3a....,ma непосредственно и сколько чисел блокируется при добавлении в набор каждого нового остатка b. Получить противоречие.

Vlad128

Да, я тоже так сначала думал. Но у меня не получилось. Ты уверен, что это доводится до решения?

mtk79

Можно поподробнее: что такое "полуинтервал" и как из него выделить искомую сумму?
Допустим x_1+x_2+x_3 дают тот же остаток, что и x_3+x_4. Из этого следует, что x_1+x_2-x_4 делится на N. А нужна сумма

Lokomotiv59

А не надо рассматривать такие суммы.
Рассматривать надо
x_1, x_1+x_2, x_1+x_2+x_3, ...
Их как раз N штук.

blackout

У него суммы:
x1, x1+x2, x1+x2+x3 и т.д.
Разница между двумя такими всегда даст сумму.

Vlad128

Нет, я рассматриваю только суммы вида [math]$S_k = \sum_{j=1}^k x_j$[/math], где k пробегает от 1 до N.
Если [math]$S_i \equiv S_j \mod N$[/math], то [math]$S_j - S_i = \sum_{k = i+1}^{j} x_k \equiv 0 \mod N$[/math]
"полуинтервал" — потому что i не включается :)

mtk79

усе, вкурил
на первый взгляд казалось, что от противного — проще

incwizitor

рассмотри суммы другого вида:
x_1, x_1+x_2, x_1+x_2+x_3,
и будет тебе счастье :grin:

Vlad128

ты самый непонятливый в треде :lol:

mtk79

боже, как же, оказывается, мало нужно для счастья! а мужики-то не знают!

mtk79

да! а через пару часиков остальная половина форума бросится объяснять мне, что имелось ввиду под "все подряд"

Vlad128

да я пишу сумбурно, но я в этом месте как раз для этого написал, что их N штук :grin:

griz_a

я вроде извратился и довел до похожего на решение, но оно извратное, хотя и на забавной конструкции базируется. но не так как написал
Оставить комментарий
Имя или ник:
Комментарий: