Математическая задача про суммы с одинаковым остатком для 2n чисел
Все целые числа от 1 до 2n выписаны в строчку. Затем к каждому числу прибавили номер того места, на котором оно стоит.
Доказать, что среди полученных сумм найдутся хотя бы две, дающие при делении на 2n одинаковый остаток.
Разобрать решение
Пусть в строчку выписаны числа a1, a2, ..., a2n. Предположим, что все числа a1 + 1, a2 + 2, ..., a2n + 2n дают разные остатки при делении на 2n. Тогда эти остатки равны 1, 2, ..., 2n. Поэтому (a1 + 1) + (a2 + 2) + ... + (a2n + 2n) = 2(1 + 2 + ... + 2n) ≡ 1 + 2 + ... + 2n (mod 2n). Противоречие, поскольку
1 + 2 + ... + 2n = n(2n + 1) ≡ n (mod 2n).
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.