MathDB
(2n+1) times (2n+1) grid colored white and black

Source: Itamo 2014 - p6

December 1, 2014
functioncombinatorics unsolvedcombinatorics

Problem Statement

A (2n+1)×(2n+1)(2n + 1) \times (2n + 1) grid, with n>0n> 0, is colored in such a way that each of the cell is white or black. A cell is called special if there are at least nn other cells of the same color in its row, and at least another nn cells of the same color in its column.
(a) Prove that there are at least 2n+12n + 1 special boxes. (b) Provide an example where there are at most 4n4n special cells. (c) Determine, as a function of nn, the minimum possible number of special cells.
Back to ProblemsView on AoPS