Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет neklyueva ([info]neklyueva)
@ 2011-01-06 20:18:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Арифметика для взрослых
Есть конечная целочисленная последовательность a(1), a(2),..., a(n).
Доказать что существует участок этой последовательности a(k), a(k+1),..., a(m) (m>=k), такой, что a(k)+a(k+1)+...+a(m) делится на n.

Поразительный результат, кстати. И, на первый взгляд, ему совсем неоткуда следовать:)


(Добавить комментарий)


[info]do_
2011-01-06 21:32 (ссылка)
Допустим, это не так. Рассмотрим последовательность
bm = (Σmi = 1 ai) mod n

Все члены bm должны быть разными.
Допустим, два её члена bk и bl совпадают. Но тогда
Σli = kai mod n = bl - bk = 0.
Значит, все bm разные. Но всего количество возможных остатков от деления
на n равно n, причем один из них - это ноль. Таким образом, получается, что одна
из сумм всё же делится на n.

(Ответить)