Разделы 
Дополнительно
Задача по математике - 2847
2019-05-06 
Доказать, что
а) из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100;
б) из любых 100 целых чисел всегда можно выбрать несколько чисел (быть может - одно), сумма которых делится на 100;
в) если числа задачи б) положительны и не превышают 100, а их сумма равна 200, то можно отобрать несколько чисел так, чтобы их сумма равнялась 100;
г) из любых 200 целых чисел можно выбрать 100 чисел, сумма которых делится на 100.
Решение:
а) Рассмотрим наименьшие по абсолютной величине остатки, которые дают наши числа при делении на 100 (т. е. если какое-либо число $a$ дает при делении на 100 остаток, больший 50, то мы будем производить деление с избытком и рассмотрим отрицательный остаток - $r$; $a = 100q - r$, где $0 < r < 50$). Так, как положительных чисел, не превосходящих 50, существует всего 51 (а именно, $0, 1, 2, \cdots, 50$), а остатков мы имеем 52, то два из этих остатков равны по абсолютной величине. Если эти остатки равны и по знаку, то разность соответствующих чисел делится на 100; если они противоположны, то сумма чисел делится на 100.
б) Пусть $a_1, a_2, a_3, \cdots, a_{100}$ - данные числа (расположенные в произвольном порядке). Рассмотрим суммы
$s_1 = a_1, s_2 = a_1 + a_2, s_3 = a_1 + a_2 + a_3, \cdots, s_{100} = a_1 + a_2 + a_3 + \cdots + a_{100}$.
Так как этих сумм имеется 100, то в том случае, когда ни одна из них не делится на 100, по крайней мере две из сумм дают при делении на 100 одинаковые остатки (ибо различных не равных нулю остатков от деления на 100 существует только 99). Вычтя из большей из двух сумм, дающих одинаковые остатки, меньшую, мы получим некоторую сумму вида $a_{k+1} + a_{k+2} + \cdots + a_m$, которая будет делиться на 100.
Примечание. Разумеется, в точности аналогично решению этой задачи можно показать, что из любых $n$ целых чисел (где $n$ - произвольное натуральное число) всегда можно отобрать несколько, сумма которых делится на $n$.
в) Если все рассматриваемые числа равны между собой (и, значит равны 2), то утверждение задачи очевидно: сумма любых 50 чисел равна 100. Если, скажем $a_1 \neq a_2$, то рассмотрим следующие суммы (ср. с решением задачи б)):
$s_1 = a_1, s_2 = a_2, s_3 = a_1 + a_2, s_4 = a_1 + a_2 + a_3 + \cdots, s_{100} = a_1 + a_2 + \cdots + a_{99}$.
Как и выше, заключаем, что либо одна из этих сумм делится на 100, либо две из них дают при делении на 100 одинаковые остатки, а тогда разность $s_i - s_j$, этих двух сумм определяет набор наших чисел, сумма которых делится на 100. (Заметим, что поскольку $a_1 \neq a_2$ и $a_1, a_2 \leq 100$, «суммы» $s_1 = a_1$ и $s_2 = a_2$ не могут давать при делении на 100 одинаковые остатки). Но если сумма некоторых из наших чисел (не всех - в нее наверное не входит число $a_{100}$) делится на 100, то, поскольку эта сумма положительна и меньше 200, она обязательно равна 100.
г) Заметим, прежде всего, что из любых четырех целых чисел можно выбрать два, сумма которых делится на 2, и что из любых десяти целых чисел можно выбрать пять, сумма которых делится на 5; эти утверждения, родственные тому, которое нам требуется доказать, разумеется, проще него (и, кроме того, используются в его доказательстве). Впрочем, все перечисленные оценки (включая и результат настоящей задачи) можно еще и несколько улучшить: два числа, сумма которых делится на 2, можно отобрать из любой совокупности трех чисел; точно так же пять чисел, сумма которых делится на 5, можно отобрать из любой совокупности девяти чисел, а 100 чисел, сумма которых делится на 100, можно отобрать из любой совокупности 199 чисел (см. Примечание в конце решения задачи).
Итак, мы последовательно будем доказывать три факта.
1°. Пусть даны 3 числа $a_1$, $a_2$ и $a_3$; из них можно выбрать 2 числа так, чтобы сумма этих чисел делилась на 2. Это предложение является совершенно очевидным: достаточно выбрать два числа одинаковой четности (оба четные или оба нечетные), а такие числа среди наших трех конечно есть.
Ясно, что основным в этом простом рассуждении является возможность замены самих чисел $a_1$, $a_2$ и $a_3$ их остатками $r_1$, $r_2$ и $r_3$ от деления на 2: ведь если сумма остатков делится на 2, то и сумма самих чисел делится на 2. Но числа $r_1$, $r_2$ и $r_3$ могут иметь лишь значения 0 или 1 - и здесь совсем легко видеть, что среди них всегда есть 2, сумма которых делится на 2.
2°. Рассмотрим теперь 9 чисел $a_1, a_2, \cdots, a_9$; мы утверждаем, что из них можно выбрать 5 чисел так, чтобы сумма этих чисел делилась на 5. Заменим опять сами числа $a_i$ (где $i = 1, 2, \cdots, 9$) их остатками $r_i$; от деления на 5. Все числа $r_i$ имеют одно из пяти значений 0, 1, 2, 3 или 4; с этими маленькими числами удобнее работать, чем с самими числами $A_i$. Но, кроме того, ко всем 9 числам $r_i$ можно прибавить одно и то же (или отнять от них одно и то же) произвольно выбранное число $с$ - ведь при этом остаток от деления cуммы произвольных 5 наших чисел на 5 не изменится. [Разумеется, после этой операции «сдвига» остатков мы снова заменим полученные числа $r_i^{ \prime} = r_i \pm c$ их остатками от деления на 5; эти новые остатки мы по-прежнему будем обозначать через $r$.] Это замечание позволяет считать, что среди 9 чисел $r_i$, (каждое из которых равно 0, 1, 2, 3 или 4) число 0 встречается реже, чем остальные остатки: ведь если бы среди наших чисел было больше всего чисел $k > 0$, то мы просто отняли бы от всех чисел по $k$.
При этом ясно, что число $t$ нулей может заключаться в пределах $2 \leq t \leq 9$ ($t > 1$, так как среди 9 чисел хоть один остаток повторяется дважды!); при этом, если $t \geq 5$, то доказывать нечего: в этом случае мы имеем 5 делящихся на 5 чисел, сумма которых тоже, конечно, делится на 5.
Дальнейшие рассуждения несложны, но несколько кропотливы. Если $t = 2$, то в нашей совокупности девяти остатков $r_i$ ни одно число не повторяется более чем 2 раза; другими словами, 4 остатка повторяются в этой совокупности дважды, и лишь один встречается однократно. Но тогда с помощью того же приема «сдвига» всех остатков на одно и то же число $с$ мы можем добиться равенства этого «непарного» остатка числу 4. Но если совокупность чисел представляет собой набор чисел 0, 0, 1, 1, 2, 2, 3, 3, 4 (мы считаем, что здесь последовательно выписаны числа $r_1, r_2, r_3, \cdots, r_9$), то, например, сумма $r_1 + r_2 + r_3 + r_4 + r_7$ делится на 5 (равна 5). Если же $t = 3$ или 4, то условимся считать, что $r_1 = r_2 = r_3 = 0$ и что все числа $r_5, r_6, \cdots, r_9$ отличны от нуля; при этом число $r_4$ может равняться 0 или быть больше 0 - это нам безразлично. Далее, из совокупности 5 (отличных от 0) чисел $r_5, r_6, r_7, r_8$ и $r_9$ всегда можно отобрать несколько (больше одного!) чисел так, чтобы их сумма делилась на 5 - доказать это можно аналогично решению задачи б) (ср. с Примечанием в конце решения задачи б)). Дополнив же затем полученную совокупность чисел нужным числом нулей из числа чисел $r_1$, $r_2$ и $r_3$ до пяти чисел (возможно, впрочем, что нам не придется эти числа дополнять), мы и придем к совокупности пяти чисел, сумма которых делится на 5.
3°. Теперь мы можем установить, что из совокупности произвольных 199 чисел $a_1, a_2, \cdots, a_{199}$ всегда можно выбрать 100 чисел, сумма которых делится на 100. Ясно, что из этих 199 чисел можно выбрать 99 пар чисел одинаковой четности: будем выделять такие пары последовательно; после того как мы отберем 98 пар, у нас останутся 3 числа, из которых, в силу п. 1°, последние 2 требуемых числа выбрать можно. Перенумеруем наши числа, считая, что $a_1$ и $a_2$, $a_3$ и $a_4, \cdots, a_{197}$ и $a_{198}$ - числа одинаковой четности; затем заменим каждые два числа $a_{2i-1}$ и $a_2i$ (где $i = 1, 2, \cdots, 99$) их полусуммой $b_i = \frac {a_{2i-1} + a_{2i}}{2}$. Ясно, что если среди 99 (целых) чисел $b_i$ мы сможем выбрать 50, сумма которых делится на 50, то (в два раза большая) сумма всех чисел $a_i$, отвечающих 60 отобранным числам $b_i$ будет делиться на 100. Таким образом, нам достаточно установить, что из каждых 99 целых чисел можно выбрать 50, сумма которых делится на 50. Далее, в точности, как и выше, отберем из 99 чисел $b_i$ 49 пар чисел одинаковой четности. Считая, что $b_1$ и $b_2$, $b_3$ и $b_4, \cdots, b_{97}$, и $b_{98}$ - числа одинаковой четности, заменим каждые два числа $b_{2k-1}$ и $b_{2k}$ (где $k = 1, 2, \cdots, 49$) одним числом - их полусуммой $c_k = \frac {b_{2k-1} + b_{2k}}{2}$; при этом, если сумма каких-то 25 чисел $с_k$ будет делиться на 25, то сумма 50 отвечающих им чисел $b_i$ будет делиться на 50. Однако далее этот прием уже отказывается работать, так как 25 - число нечетное; поэтому теперь нам придется объединять числа $с_k$ не в пары, а в пятерки чисел.
Из каждых 9 чисел, как мы знаем, можно выбрать 5 чисел, сумма которых делится на 5; тем более из числа наших 49 чисел $c_k$, можно выбрать 5 таких чисел - назовем их $с_1$ $c_2$, $с_3$, $с_4$, $с_5$. После этого у нас останется $49-5=44$ числа, из которых можно выбрать еще 5 чисел, сумма которых делится на 5, - и затем продолжать этот процесс далее. Выделив таким образом 8 пятерок чисел, таких, что сумма чисел в каждой пятерке делится на 5, мы придем к оставшейся совокупности $49 - 8 \cdot 5 = 9$ чисел, из которых, в силу п. 2°, нам удастся выбрать последнюю, девятую пятерку. Теперь заменим каждую пятерку чисел $c_{5l-4}, c_{5l-3}, c_{5l-2}, c_{5l-1}, c_{5l}$ их средним арифметическим $d_l = \frac {c_{5l-4} + c_{5l-3} + \cdots + c_5l}{5}$. Ясно, что если мы найдем 5 чисел $d_l$:, сумма которых делится на 5, то (в 5 раз большая этой суммы!) сумма отвечающих им чисел $c_k$ будет делиться на 25, - а возможность выбора таких чисел $c_k$ нам как раз и требуется доказать. Но (здесь мы снова апеллируем к п. 2°!) из 9 чисел $d_1$, $d_2$, $d_3$, $d_4$, $d_5$, $d_6$, $d_7$, $d_8$ и $d_9$, пять чисел, сумма которых делится на 5, выбрать можно, чем и завершается доказательство.
Доказать, что
а) из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100;
б) из любых 100 целых чисел всегда можно выбрать несколько чисел (быть может - одно), сумма которых делится на 100;
в) если числа задачи б) положительны и не превышают 100, а их сумма равна 200, то можно отобрать несколько чисел так, чтобы их сумма равнялась 100;
г) из любых 200 целых чисел можно выбрать 100 чисел, сумма которых делится на 100.
Решение:
а) Рассмотрим наименьшие по абсолютной величине остатки, которые дают наши числа при делении на 100 (т. е. если какое-либо число $a$ дает при делении на 100 остаток, больший 50, то мы будем производить деление с избытком и рассмотрим отрицательный остаток - $r$; $a = 100q - r$, где $0 < r < 50$). Так, как положительных чисел, не превосходящих 50, существует всего 51 (а именно, $0, 1, 2, \cdots, 50$), а остатков мы имеем 52, то два из этих остатков равны по абсолютной величине. Если эти остатки равны и по знаку, то разность соответствующих чисел делится на 100; если они противоположны, то сумма чисел делится на 100.
б) Пусть $a_1, a_2, a_3, \cdots, a_{100}$ - данные числа (расположенные в произвольном порядке). Рассмотрим суммы
$s_1 = a_1, s_2 = a_1 + a_2, s_3 = a_1 + a_2 + a_3, \cdots, s_{100} = a_1 + a_2 + a_3 + \cdots + a_{100}$.
Так как этих сумм имеется 100, то в том случае, когда ни одна из них не делится на 100, по крайней мере две из сумм дают при делении на 100 одинаковые остатки (ибо различных не равных нулю остатков от деления на 100 существует только 99). Вычтя из большей из двух сумм, дающих одинаковые остатки, меньшую, мы получим некоторую сумму вида $a_{k+1} + a_{k+2} + \cdots + a_m$, которая будет делиться на 100.
Примечание. Разумеется, в точности аналогично решению этой задачи можно показать, что из любых $n$ целых чисел (где $n$ - произвольное натуральное число) всегда можно отобрать несколько, сумма которых делится на $n$.
в) Если все рассматриваемые числа равны между собой (и, значит равны 2), то утверждение задачи очевидно: сумма любых 50 чисел равна 100. Если, скажем $a_1 \neq a_2$, то рассмотрим следующие суммы (ср. с решением задачи б)):
$s_1 = a_1, s_2 = a_2, s_3 = a_1 + a_2, s_4 = a_1 + a_2 + a_3 + \cdots, s_{100} = a_1 + a_2 + \cdots + a_{99}$.
Как и выше, заключаем, что либо одна из этих сумм делится на 100, либо две из них дают при делении на 100 одинаковые остатки, а тогда разность $s_i - s_j$, этих двух сумм определяет набор наших чисел, сумма которых делится на 100. (Заметим, что поскольку $a_1 \neq a_2$ и $a_1, a_2 \leq 100$, «суммы» $s_1 = a_1$ и $s_2 = a_2$ не могут давать при делении на 100 одинаковые остатки). Но если сумма некоторых из наших чисел (не всех - в нее наверное не входит число $a_{100}$) делится на 100, то, поскольку эта сумма положительна и меньше 200, она обязательно равна 100.
г) Заметим, прежде всего, что из любых четырех целых чисел можно выбрать два, сумма которых делится на 2, и что из любых десяти целых чисел можно выбрать пять, сумма которых делится на 5; эти утверждения, родственные тому, которое нам требуется доказать, разумеется, проще него (и, кроме того, используются в его доказательстве). Впрочем, все перечисленные оценки (включая и результат настоящей задачи) можно еще и несколько улучшить: два числа, сумма которых делится на 2, можно отобрать из любой совокупности трех чисел; точно так же пять чисел, сумма которых делится на 5, можно отобрать из любой совокупности девяти чисел, а 100 чисел, сумма которых делится на 100, можно отобрать из любой совокупности 199 чисел (см. Примечание в конце решения задачи).
Итак, мы последовательно будем доказывать три факта.
1°. Пусть даны 3 числа $a_1$, $a_2$ и $a_3$; из них можно выбрать 2 числа так, чтобы сумма этих чисел делилась на 2. Это предложение является совершенно очевидным: достаточно выбрать два числа одинаковой четности (оба четные или оба нечетные), а такие числа среди наших трех конечно есть.
Ясно, что основным в этом простом рассуждении является возможность замены самих чисел $a_1$, $a_2$ и $a_3$ их остатками $r_1$, $r_2$ и $r_3$ от деления на 2: ведь если сумма остатков делится на 2, то и сумма самих чисел делится на 2. Но числа $r_1$, $r_2$ и $r_3$ могут иметь лишь значения 0 или 1 - и здесь совсем легко видеть, что среди них всегда есть 2, сумма которых делится на 2.
2°. Рассмотрим теперь 9 чисел $a_1, a_2, \cdots, a_9$; мы утверждаем, что из них можно выбрать 5 чисел так, чтобы сумма этих чисел делилась на 5. Заменим опять сами числа $a_i$ (где $i = 1, 2, \cdots, 9$) их остатками $r_i$; от деления на 5. Все числа $r_i$ имеют одно из пяти значений 0, 1, 2, 3 или 4; с этими маленькими числами удобнее работать, чем с самими числами $A_i$. Но, кроме того, ко всем 9 числам $r_i$ можно прибавить одно и то же (или отнять от них одно и то же) произвольно выбранное число $с$ - ведь при этом остаток от деления cуммы произвольных 5 наших чисел на 5 не изменится. [Разумеется, после этой операции «сдвига» остатков мы снова заменим полученные числа $r_i^{ \prime} = r_i \pm c$ их остатками от деления на 5; эти новые остатки мы по-прежнему будем обозначать через $r$.] Это замечание позволяет считать, что среди 9 чисел $r_i$, (каждое из которых равно 0, 1, 2, 3 или 4) число 0 встречается реже, чем остальные остатки: ведь если бы среди наших чисел было больше всего чисел $k > 0$, то мы просто отняли бы от всех чисел по $k$.
При этом ясно, что число $t$ нулей может заключаться в пределах $2 \leq t \leq 9$ ($t > 1$, так как среди 9 чисел хоть один остаток повторяется дважды!); при этом, если $t \geq 5$, то доказывать нечего: в этом случае мы имеем 5 делящихся на 5 чисел, сумма которых тоже, конечно, делится на 5.
Дальнейшие рассуждения несложны, но несколько кропотливы. Если $t = 2$, то в нашей совокупности девяти остатков $r_i$ ни одно число не повторяется более чем 2 раза; другими словами, 4 остатка повторяются в этой совокупности дважды, и лишь один встречается однократно. Но тогда с помощью того же приема «сдвига» всех остатков на одно и то же число $с$ мы можем добиться равенства этого «непарного» остатка числу 4. Но если совокупность чисел представляет собой набор чисел 0, 0, 1, 1, 2, 2, 3, 3, 4 (мы считаем, что здесь последовательно выписаны числа $r_1, r_2, r_3, \cdots, r_9$), то, например, сумма $r_1 + r_2 + r_3 + r_4 + r_7$ делится на 5 (равна 5). Если же $t = 3$ или 4, то условимся считать, что $r_1 = r_2 = r_3 = 0$ и что все числа $r_5, r_6, \cdots, r_9$ отличны от нуля; при этом число $r_4$ может равняться 0 или быть больше 0 - это нам безразлично. Далее, из совокупности 5 (отличных от 0) чисел $r_5, r_6, r_7, r_8$ и $r_9$ всегда можно отобрать несколько (больше одного!) чисел так, чтобы их сумма делилась на 5 - доказать это можно аналогично решению задачи б) (ср. с Примечанием в конце решения задачи б)). Дополнив же затем полученную совокупность чисел нужным числом нулей из числа чисел $r_1$, $r_2$ и $r_3$ до пяти чисел (возможно, впрочем, что нам не придется эти числа дополнять), мы и придем к совокупности пяти чисел, сумма которых делится на 5.
3°. Теперь мы можем установить, что из совокупности произвольных 199 чисел $a_1, a_2, \cdots, a_{199}$ всегда можно выбрать 100 чисел, сумма которых делится на 100. Ясно, что из этих 199 чисел можно выбрать 99 пар чисел одинаковой четности: будем выделять такие пары последовательно; после того как мы отберем 98 пар, у нас останутся 3 числа, из которых, в силу п. 1°, последние 2 требуемых числа выбрать можно. Перенумеруем наши числа, считая, что $a_1$ и $a_2$, $a_3$ и $a_4, \cdots, a_{197}$ и $a_{198}$ - числа одинаковой четности; затем заменим каждые два числа $a_{2i-1}$ и $a_2i$ (где $i = 1, 2, \cdots, 99$) их полусуммой $b_i = \frac {a_{2i-1} + a_{2i}}{2}$. Ясно, что если среди 99 (целых) чисел $b_i$ мы сможем выбрать 50, сумма которых делится на 50, то (в два раза большая) сумма всех чисел $a_i$, отвечающих 60 отобранным числам $b_i$ будет делиться на 100. Таким образом, нам достаточно установить, что из каждых 99 целых чисел можно выбрать 50, сумма которых делится на 50. Далее, в точности, как и выше, отберем из 99 чисел $b_i$ 49 пар чисел одинаковой четности. Считая, что $b_1$ и $b_2$, $b_3$ и $b_4, \cdots, b_{97}$, и $b_{98}$ - числа одинаковой четности, заменим каждые два числа $b_{2k-1}$ и $b_{2k}$ (где $k = 1, 2, \cdots, 49$) одним числом - их полусуммой $c_k = \frac {b_{2k-1} + b_{2k}}{2}$; при этом, если сумма каких-то 25 чисел $с_k$ будет делиться на 25, то сумма 50 отвечающих им чисел $b_i$ будет делиться на 50. Однако далее этот прием уже отказывается работать, так как 25 - число нечетное; поэтому теперь нам придется объединять числа $с_k$ не в пары, а в пятерки чисел.
Из каждых 9 чисел, как мы знаем, можно выбрать 5 чисел, сумма которых делится на 5; тем более из числа наших 49 чисел $c_k$, можно выбрать 5 таких чисел - назовем их $с_1$ $c_2$, $с_3$, $с_4$, $с_5$. После этого у нас останется $49-5=44$ числа, из которых можно выбрать еще 5 чисел, сумма которых делится на 5, - и затем продолжать этот процесс далее. Выделив таким образом 8 пятерок чисел, таких, что сумма чисел в каждой пятерке делится на 5, мы придем к оставшейся совокупности $49 - 8 \cdot 5 = 9$ чисел, из которых, в силу п. 2°, нам удастся выбрать последнюю, девятую пятерку. Теперь заменим каждую пятерку чисел $c_{5l-4}, c_{5l-3}, c_{5l-2}, c_{5l-1}, c_{5l}$ их средним арифметическим $d_l = \frac {c_{5l-4} + c_{5l-3} + \cdots + c_5l}{5}$. Ясно, что если мы найдем 5 чисел $d_l$:, сумма которых делится на 5, то (в 5 раз большая этой суммы!) сумма отвечающих им чисел $c_k$ будет делиться на 25, - а возможность выбора таких чисел $c_k$ нам как раз и требуется доказать. Но (здесь мы снова апеллируем к п. 2°!) из 9 чисел $d_1$, $d_2$, $d_3$, $d_4$, $d_5$, $d_6$, $d_7$, $d_8$ и $d_9$, пять чисел, сумма которых делится на 5, выбрать можно, чем и завершается доказательство.
