На доске написано n чисел (не обязательно различных) Доказать что из них можно выбрать несколько так, что их сумма будет делиться наn
Любое А число представимо в виде А = n*k+d (d - остаток от деления, не превышает n) Если остаток от деления = 0, то число А и будет числом, делящимся на N Сумма А1+А2 = n*k1 + d1 + n*k2+d2 = n(k1+k2) + d1+d2 Аналогично для трех чисел и т.д. Идея такая: подобрать числа так, чтобы сумма их остатков от деления была кратна n Т.е. задача сводится к доказательству того, что для n чисел меньших n можно отобрать такие, сумма которых будет кратна n
