Разделы 
Дополнительно
Задача по математике - 3528
2019-06-12 
Дана таблица $4 \times 4$ клетки, в некоторых клетках которой расставляются звездочки. Докажите, что можно так расставить семь звездочек, что при вычеркивании любых двух строк и любых двух столбцов этой таблицы в оставшихся клетках всегда будет хотя бы одна звездочка. Докажите, что если звездочек меньше чем семь, то всегда можно так вычеркнуть две строки и два столбца, что все оставшиеся клетки будут пустыми.
Решение:
Ясно, что расположение семи звездочек, показанное на рис., удовлетворяет условию задачи.
Если же звездочек шесть или меньше, то найдутся два столбца, в каждом из которых стоит не более одной звездочки. Вычеркнем оставшиеся два столбца, После этого останется не больше двух звездочек, которые можно вычеркнуть вместе со строками, в которых они стоят.
Было бы интересно исследовать общую аналогичную задачу: какое наименьшее число звездочек можно расставить в таблице $m \times n$ чтобы при вычеркивании любых $k$ столбцов и $l$ строк оставалась хотя бы одна звездочка. (Здесь $k, l, m, n$ - натуральные числа, $k < m$, $l < n$.) Но даже для $m = n, k = l = n - 2$ она очень трудна (см. задачу 208, где $n = 7$ и $n = 13$).
Дана таблица $4 \times 4$ клетки, в некоторых клетках которой расставляются звездочки. Докажите, что можно так расставить семь звездочек, что при вычеркивании любых двух строк и любых двух столбцов этой таблицы в оставшихся клетках всегда будет хотя бы одна звездочка. Докажите, что если звездочек меньше чем семь, то всегда можно так вычеркнуть две строки и два столбца, что все оставшиеся клетки будут пустыми.
Решение:
Ясно, что расположение семи звездочек, показанное на рис., удовлетворяет условию задачи.
Если же звездочек шесть или меньше, то найдутся два столбца, в каждом из которых стоит не более одной звездочки. Вычеркнем оставшиеся два столбца, После этого останется не больше двух звездочек, которые можно вычеркнуть вместе со строками, в которых они стоят.
Было бы интересно исследовать общую аналогичную задачу: какое наименьшее число звездочек можно расставить в таблице $m \times n$ чтобы при вычеркивании любых $k$ столбцов и $l$ строк оставалась хотя бы одна звездочка. (Здесь $k, l, m, n$ - натуральные числа, $k < m$, $l < n$.) Но даже для $m = n, k = l = n - 2$ она очень трудна (см. задачу 208, где $n = 7$ и $n = 13$).
