Question

Какое наименьшее количество любых натуральных чисел следует взять, чтобы среди них всегда нашлась такая пара чисел, разность которых делилась бы на 5?

Answer 1

Разность двух натуральных чисел a и b делится на число n, если a и b дают одинаковые остатки при делении на n.

Допустим обратное. Пусть числа дают разный остатки: a дает остаток k, b дает остаток l, k≠l, a>b. Тогда

1) |k-l|<n, (т.к. максимальный остаток равен n-1, минимальный равен 0)

2) a-b=x₁n+k-x₂n-l=(x₁-x₂)n+k-l

Тогда, т.к. a-b делится на n, k-l тоже делится на n. Но |k-l|<n. А значит |k-l|=0. Тогда k=l. Противоречие.

___________________________

Всего остатков при делении на 5 ровно 5: 0,1,2,3,4.

Т.е. в наборе обязательно должна присутствовать хотя бы одна пара чисел с одинаковыми остатками при делении на 5. По принципу Дирихле минимальное кол-во чисел в таком наборе равно 5+1=6