Question

Докажите что из любых 11 случайных числа можно выбрать 2 числа разность или сумма которых делится на 19! Помогите с решением!

Answer 1

Разность чисел A и B делится на 19 только если они дают одинаковый остаток при делении на 19.
Предположим, что среди 11 чисел нет двух чисел, дающих одинаковый остаток при делении на 19 (иначе мы выбираем данные два числа, и тогда разность этих чисел делится на 19).
Всего при делении на 19 ровно 19 различных остатков (от 0 до 19). Кроме того, остатки можно разбить на 10 групп:

0
1 - 18
2 - 17
3 - 16
4 - 15
5 - 14
6 - 13
7 - 12
8 - 11
9 - 10

(в каждой строке выписана одна группа)
В группах со 2 по 10 (там, где по два числа) сумма чисел внутри группы делится на 19 (в точности равна 19), а значит и числа, дающие данные остатки в сумме будут давать число кратное 19. Значит чтобы сумма любых 2 чисел из данных 11 не делилась на 19 нужно, чтобы среди остатков не было 2 из одной группы. Групп всего 10

Значит либо два числа дают равные остатки, либо эти остатки находятся в одной группе. Первое означает, что разность чисел делится на 19, а второе, что сумма этих чисел делится на 19.
Что и требовалось доказать.