MathDB

Rearrange the rows and columns to move marked squares above the main diagonal

Source: Tuymaada 2021 Senior P6

July 28, 2021

combinatorics

Problem Statement

In a

n\times n

table (

n>1

)

k

unit squares are marked.One wants to rearrange rows and columns so that all the marked unit squares are above the main diagonal or on it.For what maximum

k

is it always possible?

Back to Problems View on AoPS