Разделы 
Дополнительно
Задача по математике - 3659
2019-06-13 
Докажите, что из любых двухсот целых чисел можно выбрать сто чисел, сумма которых делится на сто.
Решение:
Мы докажем, что из любых 199 (целых) чисел можно выбрать 100, сумма которых делится на 100. При этом понадобятся лишь такие факты: из любых 3 чисел можно выбрать 2 одинаковой четности (это очевидно); из любых 9 чисел можно выбрать 5, сумма которых делится на 5.
Обозначим через $P_m$ следующее общее утверждение: из любых $2m - 1$ целых чисел можно выбрать $m$ чисел, сумма которых делится на $m$ (другими словами, можно выбрать $m$ чисел, среднее арифметическое которых - целое число). Наше доказательство основано на такой лемме.
Лемма 1, Если верны утверждения $P_k$, и $P_m$, то верно и $P_{km}$.
Докажем это. Пусть дано $2km - 1$ чисел. Выберем из них, согласно $P_m$, группу из $m$ чисел с целым средним арифметическим, из оставшихся $2km - m - 1$ - еще одну такую группу, из оставшихся $2km - 2m - 1$ - еще одну и т. д. - 1 раз, после чего останется $2km -(2 к - l)m - 1 = m - 1$ число, так что $2k - 1$ раз мы действительно могли использовать $P_m$. Рассмотрим (целые) средние арифметические чисел в $2k - 1$ выбранных группах. Из них согласно $P_k$ можно выбрать $k$ чисел, сумма которых делится на $k$. Тогда сумма $km$ исходных чисел, входящих в соответствующие к групп, очевидно, делится на $km$. Лемма 1 доказана.
Поскольку $100 = 2 \cdot 2 \cdot 5 \cdot 5$, то из $P_2$ и $P_5$ трехкратным применением леммы 1 мы можем вывести $P_{100}$. Осталось лишь проверить $P_5$.
Сделать это можно сравнительно простым перебором всех возможных наборов $0 \leq r_1 \leq r_2 \leq \cdots \leq r_9 \leq 4$ из 9 остатков при делении на 5, которые могут давать данные 9 чисел. Случаи, когда среди $r_i (1 \leq i \leq 9)$ есть 5 одинаковых или когда среди них нет трех одинаковых (и, следовательно, встречаются все остатки 1, 2, 3, 4 и 0), очевидны. Остается рассмотреть случай, когда некоторый остаток $r$ встречается среди $r_i$ либо 3, либо 4 раза. При этом можно считать, что $r = 0$; в противном случае можно добавить ко всем 9 числам $5 - r$ (условие «сумма 5 чисел делится на 5» при таком добавлении сохраняется). Дальше можно избавиться от перебора, вспомнив такую полезную лемму.
Лемма 2. Из любых $q$ целых чисел можно выбрать несколько чисел, сумма которых делится на $q$.
(Чтобы доказать лемму для чисел $a_1, a_2, \cdots, a_q$, достаточно рассмотреть $q$ чисел $a_1, a_1 + a_2, a_1 + a_2 + a_3, \cdots, a_1 + a_2 + \cdots + a_q$: либо они дают все различные остатки при делении на $q$, либо среди них есть два, дающих одинаковые остатки, тогда их разность делится на $q$.)
По лемме 2 из 5 ненулевых остатков $r_i$ можно выбрать несколько (от 2 до 5), сумма которых делится на 5, и добавить к ним недостающее до 5 количество нулевых.
Можно доказать, что утверждение $P_n$ верно для любого натурального $n$. Интересно выяснить следующий вопрос: для какого наименьшего натурального числа $F_d(n)$ из любых $F_d(n)$ векторов с целочисленными координатами можно выбрать несколько векторов, у суммы которых все координаты делятся на $n$? (Здесь $n$ - натуральное, $d$ - «размерность»: $d = 2$ для векторов на плоскости, $d = 3$ - в пространстве.)
Докажите, что из любых двухсот целых чисел можно выбрать сто чисел, сумма которых делится на сто.
Решение:
Мы докажем, что из любых 199 (целых) чисел можно выбрать 100, сумма которых делится на 100. При этом понадобятся лишь такие факты: из любых 3 чисел можно выбрать 2 одинаковой четности (это очевидно); из любых 9 чисел можно выбрать 5, сумма которых делится на 5.
Обозначим через $P_m$ следующее общее утверждение: из любых $2m - 1$ целых чисел можно выбрать $m$ чисел, сумма которых делится на $m$ (другими словами, можно выбрать $m$ чисел, среднее арифметическое которых - целое число). Наше доказательство основано на такой лемме.
Лемма 1, Если верны утверждения $P_k$, и $P_m$, то верно и $P_{km}$.
Докажем это. Пусть дано $2km - 1$ чисел. Выберем из них, согласно $P_m$, группу из $m$ чисел с целым средним арифметическим, из оставшихся $2km - m - 1$ - еще одну такую группу, из оставшихся $2km - 2m - 1$ - еще одну и т. д. - 1 раз, после чего останется $2km -(2 к - l)m - 1 = m - 1$ число, так что $2k - 1$ раз мы действительно могли использовать $P_m$. Рассмотрим (целые) средние арифметические чисел в $2k - 1$ выбранных группах. Из них согласно $P_k$ можно выбрать $k$ чисел, сумма которых делится на $k$. Тогда сумма $km$ исходных чисел, входящих в соответствующие к групп, очевидно, делится на $km$. Лемма 1 доказана.
Поскольку $100 = 2 \cdot 2 \cdot 5 \cdot 5$, то из $P_2$ и $P_5$ трехкратным применением леммы 1 мы можем вывести $P_{100}$. Осталось лишь проверить $P_5$.
Сделать это можно сравнительно простым перебором всех возможных наборов $0 \leq r_1 \leq r_2 \leq \cdots \leq r_9 \leq 4$ из 9 остатков при делении на 5, которые могут давать данные 9 чисел. Случаи, когда среди $r_i (1 \leq i \leq 9)$ есть 5 одинаковых или когда среди них нет трех одинаковых (и, следовательно, встречаются все остатки 1, 2, 3, 4 и 0), очевидны. Остается рассмотреть случай, когда некоторый остаток $r$ встречается среди $r_i$ либо 3, либо 4 раза. При этом можно считать, что $r = 0$; в противном случае можно добавить ко всем 9 числам $5 - r$ (условие «сумма 5 чисел делится на 5» при таком добавлении сохраняется). Дальше можно избавиться от перебора, вспомнив такую полезную лемму.
Лемма 2. Из любых $q$ целых чисел можно выбрать несколько чисел, сумма которых делится на $q$.
(Чтобы доказать лемму для чисел $a_1, a_2, \cdots, a_q$, достаточно рассмотреть $q$ чисел $a_1, a_1 + a_2, a_1 + a_2 + a_3, \cdots, a_1 + a_2 + \cdots + a_q$: либо они дают все различные остатки при делении на $q$, либо среди них есть два, дающих одинаковые остатки, тогда их разность делится на $q$.)
По лемме 2 из 5 ненулевых остатков $r_i$ можно выбрать несколько (от 2 до 5), сумма которых делится на 5, и добавить к ним недостающее до 5 количество нулевых.
Можно доказать, что утверждение $P_n$ верно для любого натурального $n$. Интересно выяснить следующий вопрос: для какого наименьшего натурального числа $F_d(n)$ из любых $F_d(n)$ векторов с целочисленными координатами можно выбрать несколько векторов, у суммы которых все координаты делятся на $n$? (Здесь $n$ - натуральное, $d$ - «размерность»: $d = 2$ для векторов на плоскости, $d = 3$ - в пространстве.)
