Завдання 23.29
Цікава задача: сума, кратна 100
Доведіть, що з будь-яких ста натуральних чисел можна вибрати кілька (можливо, одне), сума яких ділиться на 100.
Розв’язання
Складемо 100 сум S1=a1, S2=a1+a2, …, S100.
Якщо якась ділиться на 100 — готово. Інакше 100 сум мають лише 99 можливих ненульових остач, тож дві суми Si і Sj (i<j) дають однакову остачу.
Тоді Sj−Si=ai+1+…+aj ділиться на 100.
Розбір зрозумілий?
§ 23. Квадратне рівняння як математична модель текстових і прикладних задач
Завдання 23.29
с. 190
Цікава задача: сума, кратна 100
Умова
Доведіть, що з будь-яких ста натуральних чисел можна вибрати кілька (можливо, одне), сума яких ділиться на 100.
Що треба знати
Принцип Діріхле.
💡 Підказка — спробуй спершу сам
Розглянь суми Sk=a1+…+ak.
Розв’язання крок за кроком
Складемо 100 сум S1=a1, S2=a1+a2, …, S100.
Якщо якась ділиться на 100 — готово. Інакше 100 сум мають лише 99 можливих ненульових остач, тож дві суми Si і Sj (i<j) дають однакову остачу.
Тоді Sj−Si=ai+1+…+aj ділиться на 100.
Розбір зрозумілий?