Дано n чисел. Доказать, что из них можно выбрать одно или несколько чисел так, что их сумма разделится на n
помогите пожалуйста!:(
Ответы
Для доказательства этого утверждения воспользуемся методом математической индукции.
База индукции: для n = 1 утверждение очевидно, так как любое число делится на 1.
Предположение индукции: пусть утверждение верно для n = k, т.е. из любых k чисел можно выбрать одно или несколько так, что их сумма делится на k.
Шаг индукции: докажем, что утверждение верно для n = k + 1. Рассмотрим любые k + 1 чисел. Если среди них есть число, которое делится на k + 1, то утверждение доказано. В противном случае, рассмотрим остатки от деления каждого числа на k + 1. Если среди остатков есть хотя бы два одинаковых, то разность между соответствующими числами будет делиться на k + 1. Если все остатки различны, то сумма остатков будет равна 0 (так как остатки могут быть только числами от 0 до k), и следовательно, сумма всех чисел будет делиться на k + 1.
Таким образом, утверждение верно для всех натуральных чисел n.