Архив задач

Трансверсали

В каждую из k ячеек квадратной таблицы n×n записана единица, а в остальные ячейки – ноль. Найдите максимальное значение k, при котором, независимо от исходного расположения единиц, меняя местами строки между собой и столбцы между собой, можно добиться того, что все единицы окажутся выше побочной диагонали или на ней. (Побочной называется диагональ, идущая из левого нижнего угла в правый верхний угол. На рисунке приведен пример: содержимое ячеек, лежащих выше побочной диагонали или на ней, отмечено жирным.)
2019-12-1.jpg