Задача на принцип Дирихле

[Thinker]

Здравствуйте!
Вчера мне попалась задача, перед которой я оказался бессилен. Вот ее условие:

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

Я долго думал, но дошел только до следующих соображений:
1. Без потери общности можно заменить числа на их остатки от деления на 2. Получим таблицу из нулей и единиц.
2. Если в таблице есть строка, полностью состоящая из нулей, то доказывать нечего: достаточно вычеркнуть все остальные строки.
3. Если в таблице найдутся 2 одинаковые строки, то и тут все доказано: вычеркнем остальные 9 строк.
4. Рассмотрим таблицу, в которой все строки различны и нет нулевой строки. Каждая строка отличается от любой другой по меньшей мере в одной позиции...
Я пытался развить эту идею, размышлял, что будет, если найдется строка из одних единиц, но больше ни к чему не пришел.

Буду весьма признателен всем, кто даст хоть какую-то подсказку!

[mihaild]

Представьте, что если оставвить 1, 2 и 7 строрку, то получатся нечетные суммы в 3, 6, 7 и 9 столбцах, а если оставить 1, 8 и 9 строки, то получатся нечетные суммы в 3, 4 и 5 столбцах. В каких столбцах получатся нечетные суммы если оставить 2, 7, 8 и 9 строки?

[Thinker]

Я не знаю
Вы уверены, что этот вопрос легче исходной задачи?

[mihaild]

Понимание, как отвечать на такие вопросы - это примерно половина решения задачи. Вторая половина - собственно принцип Дирихле.
Давайте тогда попроще. Пусть мы знаем четность $a + b$ и $a + c$. Можем ли мы узнать четность $b + c$?

[Thinker]

Очевидно! Если a + b и а + с одной четности, то b + c четно, а если разной, то нечетно.

[mihaild]

Правильно. Можете теперь ответить на мой вопрос выше? Скажем для третьего столбца - что нужно взять в качестве $a$, в качестве $b$, в качестве $c$, какие получатся четности сумм?

[Thinker]

Обозначим через $x(n)$ элемент, стоящий в n-й строке, 3-м столбце. Тогда
$a = x(1)$
$b = x(2) + x(7)$
$c = x(8) + x(9)$.
По доказанному выше,
$x(2) + x(7) + x(8) + x(9) $\equiv$0\mod 2$

[mihaild]

Правильно. Пусть у нас теперь есть два множества строк, $A$ и $B$, если оставить строки из $A$, то множество нечетных столбцов будет $C$, если оставить строки из $B$, то множество нечетных столбцов будет $D$. Каким получится множество нечетных столбцов, если оставить строки из $A \triangle B$ (симметрическая разность - строка входит в $A \triangle B$ если она входит ровно в одно из $A$ и $B$)?

[Thinker]

$ C\triangle\ D $ ?

[mihaild]

Да. Доказать можете?
Пусть теперь $C = D$. Какое нам нужно взять подмножество строк, чтобы сумма чисел в каждом столбце была четной?
Может ли быть так, что для любых двух разных подмножеств строк $C \neq D$?

[TOTAL]

Векторы-строки линейно зависимы. Это практически ответ.

[nnosipov]

Thinker в сообщении #1548175 писал(а):

Вчера мне попалась задача

Можно полюбопытствовать, где Вы ее нашли?

[Thinker]

mihaild в сообщении #1548244 писал(а):

Доказать можете?

Если долго помедитировать над всем, что написано выше, то, наверное, смогу.

mihaild в сообщении #1548244 писал(а):

Пусть теперь $C = D$. Какое нам нужно взять подмножество строк, чтобы сумма чисел в каждом столбце была четной?

$C=D \Rightarrow C \triangle D=\varnothing\Rightarrow$ надо взять $A \triangle B$

mihaild в сообщении #1548244 писал(а):

Может ли быть так, что для любых двух разных подмножеств строк $C \neq D$?

Не может, ибо множество строк имеет 2^11 подмножеств, а множество столбцов - 2^10. Значит, по принципу Дирихле, найдутся 2 подмножества множества строк, которым соответствует одно и то же подмножество столбцов.

Ух! Неужели мы это сделали?

-- 08.02.2022, 12:36 --

nnosipov в сообщении #1548253 писал(а):

Thinker в сообщении #1548175 писал(а):

Вчера мне попалась задача

Можно полюбопытствовать, где Вы ее нашли?

https://www.mccme.ru/free-books/57/shen.pdf
Стр. 68, задача 15.

[nnosipov]

Thinker
Спасибо. Обратите внимание на то решение задачи, что дал TOTAL.

[Thinker]

TOTAL в сообщении #1548252 писал(а):

Векторы-строки линейно зависимы. Это практически ответ.

Это задачка для 8 класса. Мы еще не знаем, что такое "векторы-строки" и что значит "линейно зависимы"