Mongolian Mathematical Olympiad

Let $N$ be the number of green cells. Let's construct a bipartite graph $G$ on $n$ rows and $n$ columns that $i$-th row connects $j$-th column iff the cell at the intersection of $i$-th row and $j$-th column is colored green. This graph has $N$ edges and contains no cycles of length greater than six. Now let's prove that $N<2n(1+\sqrt[3]{n})$.

Let $t=\frac{N}{2n}$. The average degree of the vertices of graph $G$ is $2t$. Let us first prove the following lemma.

Lemma. A graph with average degree $2t$ contains a subgraph with minimum degree at least $t$.

Proof. If there exists a vertex in the graph with a degree less than $t$, we delete that vertex. This operation increases the average degree of the remaining subgraph. As the nominator and the denominator decrease, the algorithm is guaranteed to terminate. The resulting subgraph will satisfy the desired property. □

The lemma guarantees the existence of a subgraph $G^{\prime }$ such that its minimum degree is at least $t$. Now let $u$ be an arbitrary vertex of $G^{\prime }$ and $A_k$ be the set of all the vertices of $G^{\prime }$ whose distance to $u$ equals $k$, then $|A_1|\ge t$. $G^{\prime }$ contains no cycles of length four and six implies that $|A_2|\ge |A_1|(t-1)$ and $|A_3|\ge |A_2|(t-1)$. The vertices of $A_1$ and $A_3$ are in the same pole, so $t(t-1{)}^2+t\le n$. It follows that $t-1<\sqrt[3]{n}$ which is equivalent to $N<2n(1+\sqrt[3]{n})$.