9

Part of 2014 Baltic Way

Problems(1)

Marking cells on a board

Source: Baltic Way 2014, Problem 9

What is the least posssible number of cells that can be marked on an

n \times n

board such that for each

m >\frac{ n}{2}

both diagonals of any

m \times m

sub-board contain a marked cell?

combinatorics proposedcombinatorics