Задача 64846
|
|
 |
Условие
Дана квадратная таблица. В каждой её клетке стоит либо плюс, либо минус, причём всего плюсов и минусов поровну.
Докажите, что или в каких-то двух строках, или в каких-то двух столбцах одинаковое количество плюсов.
Решение
Из условия видно, что число клеток в таблице чётно, то есть это таблица 2n×2n, а число плюсов равно 2n2. Предположим, что удалось расставить знаки так, что количества плюсов во всех строках различны. Тогда эти количества равны 0, 1, 2, …, 2n, где один из вариантов отсутствует. Так как общее количество плюсов равно 2n², отсутствует n. Значит, есть строка с 2n плюсами и строка без плюсов. Это означает, что нет столбца без плюсов и нет столбца с 2n плюсами. Следовательно, в каких-то двух столбцах плюсов поровну.
Замечания
4 балла
