Задача.
Докажите, что из любых ста натуральных чисел можно выбрать несколько, сумма которых делится на 100.
Решение.
Докажите, что из любых ста натуральных чисел можно выбрать несколько, сумма которых делится на 100.
Решение.
Возьмем любые натуральные числа a1, а2, ..., а100.
Т.к. число сумм, которые можно составить из a1, а2, ...,
а100, вида а1, а1
+ а2, ..., а1+ ...+а100 равно 100, то возможны только два варианта:
1) По крайней мере одна из этих сумм имеет остаток 0 при делении на 100. Тогда это и есть нужный нам набор чисел.
2) Предположим, что сумм вида а1, а1 + а2, ..., а1+ ...+а100 и имеющих остаток 0 при делении на 100 не нашлось. Тогда среди 100 указанных сумм найдутся две, имеющие одинаковые остатки 1, 2, ...., 99 при делении на 100. А значит разность этих сумм с одинаковыми остатками делится на 100, причем она также является суммой некоторого набора чисел из a1, а2, ..., а100.
Ч.т.д.
Ресурсы:
1) http://mmmf.msu.ru/archive/19992000/bugaenko/b2.html
2) Задача 73580
http://www.problems.ru/view_problem_details_new.php?id=73580
1) По крайней мере одна из этих сумм имеет остаток 0 при делении на 100. Тогда это и есть нужный нам набор чисел.
2) Предположим, что сумм вида а1, а1 + а2, ..., а1+ ...+а100 и имеющих остаток 0 при делении на 100 не нашлось. Тогда среди 100 указанных сумм найдутся две, имеющие одинаковые остатки 1, 2, ...., 99 при делении на 100. А значит разность этих сумм с одинаковыми остатками делится на 100, причем она также является суммой некоторого набора чисел из a1, а2, ..., а100.
Ч.т.д.
Ресурсы:
1) http://mmmf.msu.ru/archive/19992000/bugaenko/b2.html
2) Задача 73580
http://www.problems.ru/view_problem_details_new.php?id=73580
Комментариев нет:
Отправить комментарий