Відповіді до вправ § 20 - § 26: 23.29

23.29 Доведіть, що з будь–яких ста натуральних чисел можна вибрати кілька (можливо, й одне), сума яких ділитиметься на 100.

1) Нехай x₁, ..., x₁₀₀ — дані числа. Розглянемо суми S₁ = x₁;

S₂ = x₁ + x₂;...; S₁₀₀ = x₁ + x₂ + ... + x₁₀₀. Якщо хоча б одна із сум ділиться на 100, то задача розв’язана.

2) Нехай жодна із сум не ділиться на 100. При цьому остачі від ділення будуть числа 1; 2; 3; ...; 99. За принципом Діріхле, як мінімум дві деякі суми будуть мати одну й ту саму остачу при діленні на 100.

3) Нехай це будуть суми S_k і S_l, де k > l.

Тоді S_k – S_l = х_l+1 + x_l+2 + ... + х_k — ділиться на 100.

Отже, x_l+1 + x_l+2 + ... + х_k — шукана сума.