MathDB

In an

n\times n

table, it is allowed to rearrange rows, as well as rearrange columns. Asterisks are placed in some

k{}

cells of the table. What maximum

k{}

for which it is always possible to ensure that all the asterisks are on the same side of the main diagonal (and that there are no asterisks on the main diagonal itself)?
Proposed by P. Kozhevnikov

Problem Statement