Question

Какое наибольшее количество чисел от 1500 до 2200(крайние числа включительно) можно выбрать так, что сумма никаких двух из них не делится на 5?

Answer 1

- Чисел, делящихся на 5, может быть не более одного, иначе сумма двух чисел, делящихся на 5, будет делиться на 5.
- Если выбрано хоть одно число, дающее остаток 1 при делении на 5, то не должны быть выбраны числа, дающие остаток 4 при делении на 5, и наоборот.
- Если выбрано хоть одно число, дающее остаток 2 при делении на 5, то не должны быть выбраны числа, дающие остаток 3 при делении на 5, и наоборот.

Чисел, дающих остаток 0 при делении на 5:  2200/5 - 1500/5 + 1 = 440 - 300 + 1 = 141, и их на 1 больше, чем с каждым ненулевым остатком.

Итак, можно взять неболее 1 числа, делящегося на 5, не более половины из 280 с остатками 1 или 4, не более половины из 280 с остатками 2 или 3. Тогда можно выбрать не больше, чем 1 + 140 + 140 = 281 число.

Оценка достигается, например, если выбрать все числа с остатками 1 и 3 и число 2010.

ответ. 281