Let $n$ be a natural number divisible by $3$. We have a $n \times n$ table and each square is colored either black or white. Suppose that for all $m \times m$ sub-tables from the table ($m > 1$), the number of black squares is not more than white squares. Find the maximum number of black squares.
Problem
Source: Iran National Olympiad 2017, Second Round, Problem 3
Tags: combinatorics
20.04.2017 13:33
We claim that the answer is $\frac{4}{9}n^2$. For each $3\times3$ grids, it can contain at most 4 black squares. So the number of black squares does not exceed $\frac{4}{9}n^2$. The construction is that for each $3\times3$ grids is 010 101 010 where 1 denotes a black square 0 denotes a white square. Consider the part that the $m\times m$ table intersect each $3\times3$ grids, notice that in each part contains black squares not more than white squares. So this construction works.
13.09.2017 06:12
DimensionX wrote: We claim that the answer is $\frac{4}{9}n^2$. For each $3\times3$ grids, it can contain at most 4 black squares. So the number of black squares does not exceed $\frac{4}{9}n^2$. The construction is that for each $3\times3$ grids is 010 101 010 where 1 denotes a black square 0 denotes a white square. Consider the part that the $m\times m$ table intersect each $3\times3$ grids, notice that in each part contains black squares not more than white squares. So this construction works. The construction doesn't work, try a $3\times3$ square at side of the one who pick with the initial coloration.
13.09.2017 06:39
DimensionX wrote: We claim that the answer is $\frac{4}{9}n^2$. For each $3\times3$ grids, it can contain at most 4 black squares. So the number of black squares does not exceed $\frac{4}{9}n^2$. The construction is that for each $3\times3$ grids is 010 101 010 where 1 denotes a black square 0 denotes a white square. Consider the part that the $m\times m$ table intersect each $3\times3$ grids, notice that in each part contains black squares not more than white squares. So this construction works. if we consecutively construct grid like that then we also find 101 010 101 which is apparently a contradiction
13.09.2017 07:05
We use double counting in order to prove this: 1.The condition means that the sum of "squares" by letting black be 1 is smaller than half of that square, so we let: $N\leq\sum_{i=2}^{n} {[\frac{i^2}{2}](n-i+1)^2}$ we then count how many times the each grid is calculated I got to think the solution in this way but I can't make it up more...
13.09.2017 18:52
Skravin wrote: if we consecutively construct grid like that then we also find 101 010 101 which is apparently a contradiction You are misunderstanding the construction. It is not 010101 101010 010101 101010 010101 101010 It is 010010 101101 010010 010010 101101 010010
15.08.2019 08:59
soroush.MG wrote: Let $n$ be a natural number divisible by $3$. We have a $n \times n$ table and each square is colored either black or white. Suppose that for all $m \times m$ sub-tables from the table ($m > 1$), the number of black squares is not more than white squares. Find the maximum number of black squares. We claim the maximum number of black squares is $\frac{4}{9} n^2$. For the upper bound, note that any $3$ x $3$ square cannot have more than $4$ black squares by taking $m = 3$. For a construction, see below:
Attachments:

25.05.2023 11:19
The answer is $\frac{4n^2}{9}$. For the construction, colour all cells with coordinates $(a,b)$ ($1\leq a,b\leq n$) black if and only if $(a,b)$ are $(1,2),(2,1),(3,2),(2,3)$ modulo $3$. To prove this works, notice that any $2\times m$ and $3\times m$ rectangle has at most half of their cells black, and we can write $m=2a+3b$ for non-negative integers $a,b$ for all $m>1$ as needed.