Дано: n целых чисел.
Найти: Доказать, что среди них всегда найдётся несколько (или одно) чисел, сумма которых делится на n.
Решение:
а) n = 3:
1. Рассмотрим n целых чисел a_1, a_2, ..., a_3.
2. Найдём остатки этих чисел при делении на 3. Остатки могут быть 0, 1 или 2.
3. По принципу Дирихле, если у нас есть 3 числа (или больше), то хотя бы два из них имеют одинаковый остаток при делении на 3.
4. Пусть a_i и a_j имеют одинаковый остаток r (где r = 0, 1, 2). Тогда:
a_i ≡ a_j (mod 3).
Это означает, что сумма a_i + a_j также делится на 3.
5. Если одно из чисел a_i уже делится на 3 (остаток 0), то это число само по себе удовлетворяет условию.
Ответ: Да, среди n = 3 целых чисел всегда найдётся сумма, делящаяся на 3.
б) n = 100:
1. Рассмотрим n целых чисел a_1, a_2, ..., a_100.
2. Найдём остатки этих чисел при делении на 100. Остатки могут принимать значения от 0 до 99.
3. По принципу Дирихле, если у нас есть 100 чисел, то хотя бы два из них имеют одинаковый остаток при делении на 100.
4. Пусть a_i и a_j имеют одинаковый остаток r. Тогда:
a_i ≡ a_j (mod 100).
Это означает, что сумма a_i + a_j делится на 100.
5. Если одно из чисел делится на 100 (остаток 0), то это число удовлетворяет условию.
Ответ: Да, среди n = 100 целых чисел всегда найдётся сумма, делящаяся на 100.
в) n — любое:
1. Рассмотрим n целых чисел a_1, a_2, ..., a_n.
2. Найдём остатки этих чисел при делении на n. Остатки могут принимать значения от 0 до n-1.
3. По принципу Дирихле, если у нас есть n чисел, то по крайней мере два из них будут иметь одинаковый остаток.
4. Пусть a_i и a_j имеют одинаковый остаток r. Тогда:
a_i ≡ a_j (mod n).
5. Это означает, что сумма a_i + a_j делится на n.
6. Если одно из чисел делится на n (остаток 0), то это число удовлетворяет условию.
Ответ: Да, среди n целых чисел всегда найдётся сумма, делящаяся на n.