Розділ 3. КВАДРАТНІ РІВНЯННЯ » 23.29

Доведіть, що з будь–яких ста натуральних чисел можна вибрати кілька (можливо, й одне), сума яких ділитиметься на 100. 1) Нехай x1, ..., x100 — дані числа. Розглянемо суми S1 = x1; S2 = x1 + x2;...; S100 = x1 + x2 + ... + x100. Якщо хоча б одна із сум ділиться на 100, то задача розв’язана. 2) Нехай жодна із сум не ділиться на 100. При цьому остачі від ділення будуть числа 1; 2; 3; ...; 99. За принципом Діріхле, як мінімум дві деякі суми будуть мати одну й ту саму остачу при діленні на 100. 3) Нехай це будуть суми Sk і Sl, де k > l. Тоді Sk – Sl = хl+1 + xl+2 + ... + хk — ділиться на 100. Отже, xl+1 + xl+2 + ... + хk — шукана сума.