MathDB
there exists a rectangle whose vertices are centers of marked squares

Source: Balkan MO Shortlist 2013 C2 BMO

March 8, 2020
SquaresCenterChessboardcombinatoricsrectangle

Problem Statement

Some squares of an n×nn \times n chessboard have been marked (n∈N∗n \in N^*). Prove that if the number of marked squares is at least n(n+12)n\left(\sqrt{n} + \frac12\right), then there exists a rectangle whose vertices are centers of marked squares.
Back to ProblemsView on AoPS