Олимпиадная задача по алгебраическим методам и принципу Дирихле для 9–11 классов

  Первый способ. Будем выбирать строки "испорченной" нулями таблицы по очереди и следить за суммой  S = S_m  выбранных строк. Первой возьмём "испорченную" строку, которая получилась из  (1, 1,..., 1).  Строка S₁ будет состоять из нулей и единиц (если в ней только нули, то уже одна эта строка дает нужное множество). Второй строкой возьмём "испорченную" строку, полученную из той, в которой стояли минус единицы на тех местах, где в S₁ стоят единицы и , и единицы на тех местах, где в S₁ стоят нули. Тогда S₂ тоже будет стоять из нулей и единиц. Пусть k строк уже выбраны. Если сумма S_k совпадает с некоторой из предыдущих сумм S_m, где  m < k,  то  S_m+1 + S_m+2 + ... + S_k = 0,  и задача решена. Если сумма S_k не совпадает ни с одной из предыдущих строк, то в качестве (k+1)-й берём "испорченную" строку, полученную из той, в которой стояли минус единицы на тех местах, где в S_k стоят единицы, и единицы на тех местах, где в S_k стоят нули. Эта строка еще не была выбрана, так как для разных сумм S_m мы выбираем разные строки, а сумма S_k раньше не встречалась.

  Если на некотором шаге получится сумма, которая уже встречалась раньше, то задача решена (см. выше), если нет, – то, в конце концов, все строки будут выбраны. При этом мы получим 2ⁿ различных сумм S_k. Так как различных наборов из нулей и единиц длины n тоже 2ⁿ, то все строки из нулей и единиц встретятся в качестве сумм S_k. Значит, на каком-то шаге,  S_k = 0,  и нужное множество – первые k выбранных строк.   Второй способ. Обозначим строки исходной таблицы a_i, а строки таблицы, "испорченной" нулями, b_i  (i = 1, 2, ..., 2ⁿ).  Построим также таблицу со строками  c_i = a_i – 2b_i.  Иными словами, строка c_i совпадает с a_i в тех местах, где числа заменялись нулями, и противоположна ей в остальных. В частности, построенная таблица состоит только из единиц и минус единиц. Поэтому для каждого i найдётся такое  j(i), что  c_i = a_j(i).

  Рассмотрим теперь последовательность  i_k, заданную рекуррентным соотношением  i_k+1 = j(i_k).  (Первый член последовательности выбирается произвольно.) Поскольку члены последовательности могут принимать лишь конечное число значений, какие-то из них равны между собой. Пусть  i_k = i_l  для некоторых  k < l,  причём все члены последовательности с номерами, меньшими l, различны. Имеем

b_ik + b_ik+1 + ... + b_il–1 = ½ (a_ik – c_ik) + ½ (a_ik+1 – c_ik+1) + ... + ½ (a_il–1 – c_il–1) = ½ (a_ik – a_ik+1 + a_ik+1 – a_ik+2 + ... + a_il–1 – a_il) = ½ (a_ik – a_il) = 0.

Ответ задачи отсутствует