Разделы 
Дополнительно
Задача по математике - 2892
2019-05-06 
В некоторых клетках шахматной доски размером $n \times n$ стоят звездочки; известно, что если вычеркнуть любой набор строк доски (только, разумеется, не все!), то найдется столбец, в котором имеется ровно одна незачеркнугая звездочка. (В частности, если вовсе никакие строки не вычеркивать, то тоже найдется столбец, в котором имеется ровно одна звездочка.) Доказать, что если вычеркнуть любой набор столбцов (но не все), то найдется строка, в которой имеется ровно одна незачеркнутая звездочка.
Решение:
Ясно, что для «доски» размером $1 \times 1$ (состоящей из одной единственной клетки) утверждение задачи выполняется (здесь оно бессодержательно: ведь наша «доска» состоит из единственной клетки, в которой стоит звездочка); это делает возможным использование метода математической индукции. При $n = 2$, очевидно, доска будет содержать столбец ($а$ следовательно, и строку), в котором имеется точно одна звездочка; переставив, если это понадобится, Строки и столбцы так, чтобы свободное место оказалось правым верхним, мы придем к таблице, имеющей «треугольное» строение (см. рис. а, где знак «+» означает, что в соответствующей клетке звездочка может как стоять, так и не стоять). Докажем, что и при произвольном $n$ строки и столбцы таблицы можно переставить так, чтобы таблица приняла «треугольный» вид, т. е. чтобы все звездочки в таблице стояли на идущей сверху вниз направо диагонали и, быть может, под ней, - однако все клетки над диагональю обязательно были пустыми. В самом деле, предположим, что это уже доказано для удовлетворяющих нашим условиям таблиц размером $(n-1) \times (n-1)$, и рассмотрим таблицу размером $n \times n$. Эта таблица содержит столбец, в котором имеется ровно одна звездочка; переставим этот столбец на последнее место, а затем переставим строки так, чтобы звездочка в нем оказалась внизу рис. б, и вычеркнем содержащую эту звездочку строку и последний столбец. При этом мы придем к таблице размером $(n-1) \times (n-1)$, также удовлетворяющей условиям задачи; по предположению индукции строки и столбцы этой таблицы можно переставить так, чтобы она имела «треугольный» вид, после чего примет «треугольный» вид и исходная таблица.
«Треугольное» строение рассматриваемых таблиц (его можно считать «треугольным», ибо с точки зрения интересующих нас свойств таблиц допустимы любые перестановки строк и столбцов) доказывает равноправность строк и столбцов таблицы, а значит и справедливость утверждения задачи (наглядно очевидного для «треугольных» таблиц).
В некоторых клетках шахматной доски размером $n \times n$ стоят звездочки; известно, что если вычеркнуть любой набор строк доски (только, разумеется, не все!), то найдется столбец, в котором имеется ровно одна незачеркнугая звездочка. (В частности, если вовсе никакие строки не вычеркивать, то тоже найдется столбец, в котором имеется ровно одна звездочка.) Доказать, что если вычеркнуть любой набор столбцов (но не все), то найдется строка, в которой имеется ровно одна незачеркнутая звездочка.
Решение:
Ясно, что для «доски» размером $1 \times 1$ (состоящей из одной единственной клетки) утверждение задачи выполняется (здесь оно бессодержательно: ведь наша «доска» состоит из единственной клетки, в которой стоит звездочка); это делает возможным использование метода математической индукции. При $n = 2$, очевидно, доска будет содержать столбец ($а$ следовательно, и строку), в котором имеется точно одна звездочка; переставив, если это понадобится, Строки и столбцы так, чтобы свободное место оказалось правым верхним, мы придем к таблице, имеющей «треугольное» строение (см. рис. а, где знак «+» означает, что в соответствующей клетке звездочка может как стоять, так и не стоять). Докажем, что и при произвольном $n$ строки и столбцы таблицы можно переставить так, чтобы таблица приняла «треугольный» вид, т. е. чтобы все звездочки в таблице стояли на идущей сверху вниз направо диагонали и, быть может, под ней, - однако все клетки над диагональю обязательно были пустыми. В самом деле, предположим, что это уже доказано для удовлетворяющих нашим условиям таблиц размером $(n-1) \times (n-1)$, и рассмотрим таблицу размером $n \times n$. Эта таблица содержит столбец, в котором имеется ровно одна звездочка; переставим этот столбец на последнее место, а затем переставим строки так, чтобы звездочка в нем оказалась внизу рис. б, и вычеркнем содержащую эту звездочку строку и последний столбец. При этом мы придем к таблице размером $(n-1) \times (n-1)$, также удовлетворяющей условиям задачи; по предположению индукции строки и столбцы этой таблицы можно переставить так, чтобы она имела «треугольный» вид, после чего примет «треугольный» вид и исходная таблица.
«Треугольное» строение рассматриваемых таблиц (его можно считать «треугольным», ибо с точки зрения интересующих нас свойств таблиц допустимы любые перестановки строк и столбцов) доказывает равноправность строк и столбцов таблицы, а значит и справедливость утверждения задачи (наглядно очевидного для «треугольных» таблиц).
