|
|
 |
Условие
В таблице 2n×n были выписаны всевозможные строки длины n из чисел 1 и –1. Затем часть чисел заменили нулями. Докажите, что можно выбрать несколько строк, сумма которых есть строка из нулей. (Суммой строк называется строка, элементы которой являются суммами соответствующих элементов слагаемых.)
Решение
Первый способ. Будем выбирать строки "испорченной" нулями таблицы по очереди и следить за суммой S = Sm выбранных строк. Первой возьмём "испорченную" строку, которая получилась из (1, 1,..., 1). Строка S1 будет состоять из нулей и единиц (если в ней только нули, то уже одна эта строка дает нужное множество). Второй строкой возьмём "испорченную" строку, полученную из той, в которой стояли минус единицы на тех местах, где в S1 стоят единицы и , и единицы на тех местах, где в S1 стоят нули. Тогда S2 тоже будет стоять из нулей и единиц. Пусть k строк уже выбраны. Если сумма Sk совпадает с некоторой из предыдущих сумм Sm, где m < k, то Sm+1 + Sm+2 + ... + Sk = 0, и задача решена. Если сумма Sk не совпадает ни с одной из предыдущих строк, то в качестве (k+1)-й берём "испорченную" строку, полученную из той, в которой стояли минус единицы на тех местах, где в Sk стоят единицы, и единицы на тех местах, где в Sk стоят нули. Эта строка еще не была выбрана, так как для разных сумм Sm мы выбираем разные строки, а сумма Sk раньше не встречалась.
Если на некотором шаге получится сумма, которая уже встречалась раньше, то задача решена (см. выше), если нет, – то, в конце концов, все строки будут выбраны. При этом мы получим 2n различных сумм Sk. Так как различных наборов из нулей и единиц длины n тоже 2n, то все строки из нулей и единиц встретятся в качестве сумм Sk. Значит, на каком-то шаге, Sk = 0, и нужное множество – первые k выбранных строк.
Второй способ. Обозначим строки исходной таблицы ai, а строки таблицы, "испорченной" нулями, bi (i = 1, 2, ..., 2n). Построим также таблицу со строками ci = ai – 2bi. Иными словами, строка ci совпадает с ai в тех местах, где числа заменялись нулями, и противоположна ей в остальных. В частности, построенная таблица состоит только из единиц и минус единиц. Поэтому для каждого i найдётся такое j(i), что ci = aj(i).
Рассмотрим теперь последовательность ik,
заданную рекуррентным соотношением ik+1 = j(ik). (Первый член последовательности выбирается произвольно.) Поскольку члены последовательности могут принимать лишь конечное число значений, какие-то из них равны между собой. Пусть ik = il для некоторых k < l, причём все члены последовательности с номерами, меньшими l, различны. Имеем
bik + bik+1 + ... + bil–1 = ½ (aik – cik) + ½ (aik+1 – cik+1) + ... + ½ (ail–1 – cil–1) = ½ (aik – aik+1 + aik+1 – aik+2 + ... + ail–1 – ail) = ½ (aik – ail) = 0.
Замечания
Второй способ имеет следующую геометрическую интерпретацию.
Рассмотрим n-мерный куб с вершинами (x1, ..., xn) = x, где xi равны 0 и 1. "Большие диагонали" куба – разности векторов x и x' = (1 – x1, ..., 1 – xn) – это векторы с координатами 1 и –1. Назовем d-мерной гранью куба множество вершин, у которых некоторые n – d координат фиксированы, а остальные d принимают все возможные значения (0 и 1); здесь d = 0, 1, ..., n – 1 (0-мерная грань – это просто вершина; 1-мерная – ребро). "Испорченные" нулями строки в нашей задаче – это "диагонали" некоторых d-мерных граней, причем из каждой вершины куба выходит ровно одна такая "отмеченная диагональ" в противоположную вершину этой грани (то есть в вершину, где значения "переменных" координат xi грани заменены на противоположные 1 – xi). Начав с любой вершины куба, будем двигаться по отмеченным диагоналям граней. Тогда наш путь когда-то вернется в вершину, где мы уже побывали. Сумма векторов по замкнутому пути равна нулю!
