C2

Part of 2013 Balkan MO Shortlist

Problems(1)

there exists a rectangle whose vertices are centers of marked squares

Source: Balkan MO Shortlist 2013 C2 BMO

Some squares of an

n \times n

chessboard have been marked (

n \in N^*

). Prove that if the number of marked squares is at least

n\left(\sqrt{n} + \frac12\right)

, then there exists a rectangle whose vertices are centers of marked squares.

SquaresCenterChessboardcombinatoricsrectangle