Архив задач олимпиады по математике и криптографии

Теория чисел

Докажите, что из любых пяти различных натуральных чисел всегда можно выбрать три различных числа так, что их сумма будет делиться на три. Докажите, что из любых двадцати пяти различных натуральных чисел всегда можно выбрать девять различных чисел так, что их сумма будет делиться на девять.

  • Подсказка

    • Подсказка

    Рассмотрите вначале остатки от деления на три 5 чисел.
  • Решение

    • Решение

    Решим сначала первую часть задачи. Пусть {a_1, a_2, a_3, a_4, a_5} - различные пять натуральных чисел и {r_1, r_2, r_3, r_4, r_5 \in \{0,1,2\}} - их остатки от деления на 3 соответственно. Возможны следующие два случая: а) среди чисел {r_1, r_2, r_3, r_4, r_5 есть хотя бы три одинаковых, тогда сумма этих трех чисел делится на три; б) среди чисел {r_1, r_2, r_3, r_4, r_5 нет трех одинаковых, а значит, найдутся три различных числа, имеющие остатки 0, 1 и 2 и тогда их сумма делится на три. Докажем теперь второе утверждение задачи. Пусть {a_1, ..., a_{25}} - любые двадцать пять натуральных чисел. Будем считать, что они упорядочены по возрастанию. Сгруппируем их последовательно по 5 штук: {a_1,a_2,a_3,a_4,a_5; a_6,a_7,a_8,a_9,a_{10}; \dots ;a_{21},a_{22},a_{23},a_{24},a_{25}.} 
    В каждой пятерке по первой части задачи найдется три различных числа, сумма которых делится на три, выпишем их: {v_1,c_2,v_3, w_1, w_2, w_3, \dots, z_1,z_2,z_3.} 
    Рассмотрим пять различных натуральных чисел:{\bar v = \frac{1}{3}(v_1+v_2+v_3), \bar w = \frac{1}{3}(w_1+w_2+w_3), \dots, \bar z = \frac{1}{3}(z_1+z_2+z_3).} Среди этих пяти чисел по доказанной первой части задачи найдутся три различных числа, пусть a, b, c, сумма которых делится на три. Каждое из чисел a, b, c есть {\frac{1}{3}} от суммы трех некоторых различных чисел из набора {a_1, ..., a_{25}} тогда a + b + c есть {\frac{1}{3}} от суммы некоторых девяти различных чисел из этого же набора. Отсюда из свойств делимости целых чисел следует, что сумма этих девяти чисел делится на 9.