Олимпиада Туймаада по математике. Старшая лига. 2021 год

На доске $n \times n$ $(n > 1)$ отмечено $k$ клеток. Требуется переставить строки и столбцы так, чтобы все отмеченные клетки оказались не ниже главной диагонали. При каком наибольшем $k$ это гарантированно возможно? ( М. Антипов )

Комментарий/решение