Числа в таблице

[Busy_Beaver]

Из личного опыта я знаю, что если олимпиадная задача решается слишком легко, то решение, скорее всего, не верно (или "неверно"? Уже забыл, как по-русски писать ).
Именно по этому горю желанием поделиться попыткой решения данной (см. ниже) задачи с уважаемыми участниками этого форума.

А вот и сама задача:
Для квадратной таблицы $(2n + 1)*(2n + 1)$, заполненной числами –1, 0 и 1, вычислили сумму чисел каждого столбца и каждой строки. Доказать, что среди этих сумм хотя бы две будут одинаковыми.
Источник задачи: Всеукраинская олимпиада школьников. 1981, Симферополь.

Я попробовал решить, и вот что вышло:
Всего имеется $4n+2$ строк и столбцов. Сумма всех чисел в строке (столбце) может принимать все целые значения от $-2n-1$ до $2n+1$ (включительно). Итого $4n+3$ значений.
Назовём сумму всех чисел в строке (столбце) зелёненькой, если все числа строки (столбца) равны $1$, или все числа строки (столбца) равны $-1$. Зелёненькая сумма будет равна, разумеется, либо $(2n+1)$, либо $-2n-1$.
Если в таблице зелёненьких сумм нет, то всего имеется $4n+1$ различных значений сумм, а значит, по принципу Дирихле, хотя бы две должны быть равны.
Если же имеется хотя бы одна зелёненькая сумма (без ограничения общности скажем, что все её слагаемые равны единице), то не может встретиться, во-первых, противоположная зелёненькая....

Так, стоп! Вот я и нашёл свою ошибку, пока писал (всё-таки, лучше в уме не решать).
Я почему-то предположил, что если, скажем, в некоторой строке все числа равны 1, то ни в одном столбце все числа не будут равны -1. Оно-то правильно, вот только я не подумал о том, что все числа могут быть равны -1 в другой строке, а не в столбце!
Ладно, шут с ним, пойду дорешивать

[ewert]

Busy_Beaver в сообщении #350044 писал(а):

, заполненной числами –1, 0 и 1,

Что это в точности значит? Допускается ли, например, случай, когда все числа -- это единицы?

А впрочем не важно. Сколько в принципе различных сумм таких чисел может существовать?...

[Busy_Beaver]

Условие задачи не я придумывал, но, полагаю, что каждое из чисел в таблице имеет ровно три (непересекающихся (или (если угодно) неконкурентных)) способа существования, а именно:
1. Быть числом -1.
2. Быть нулём.
3. Быть единицей.

-- Пн сен 06, 2010 10:53:02 --

ewert в сообщении #350048 писал(а):

Сколько в принципе различных сумм таких чисел может существовать?...

Думаю, что $4n+3$.

[ewert]

Ну предположим, что все суммы -- разные.

Сумма вдоль линии может принимать значения от $-(2n+1)$ до $(2n+1)$.

Всего возможных сумм $(4n+3)$, а линий $(4n+2)$, так что отсутствовать в списке может только одна сумма.

Сумма всех вообще мыслимых сумм равна нулю, а сумма фактически присутствующих сумм чётная (т.к. каждый элемент учитывается дважды) -- следовательно, в списке может отсутствовать только чётная сумма.

В частности, обязательно должны присутствовать суммы $-(2n+1)$ и $(2n+1)$. Для определённости считаем, что первая отвечает некоторому столбцу (заполненному минус единичками); тогда вторая отвечает тоже столбцу, но заполненному плюс единичками.

Вычеркнем эти два столбца и какие-либо две строки. Для оставшейся матрицы меньшего размера все суммы тоже будут разными (мы просто удалили из списка две столбцовых суммы и две строчных, а остальные не изменились).

Продолжая этот процесс, доберёмся до матрицы $1\times1$, ну а уж для неё-то "суммы" разными точно быть не могут.

[ИСН]

Когда мы удалили столбцы из сплошных -1 и +1, то строчные суммы не изменились; это ладно. (Столбцовые, понятно, тоже.) Но когда мы удалили две какие-либо строки, то кто знает, как мы при этом повредили столбцы?

[Хорхе]

А зачем вычеркивать строчки, да еще и какие-либо? Ну будем мы получать матрицу с нечетным количеством строк и столбцов, и те жу рассуждения применимы. В конце все равно получим $1\times 1$.

-- Пн сен 06, 2010 16:21:43 --

Ауч, вру, конечно.