Vietnamese Mathematical Olympiad

For convenience, consider this problem on a $m \times n$ table and write $+1$ or $-1$ in each square to represent the trees.

a) For a $4 \times 4$ table, the table below is satisfied.

It is clear that we can merge such $4 \times 4$ tables to get a $2016 \times 2016$ table satisfying a).

b) Assume that there exists an impressive planting way for a $m \times n$ plot. We will prove that all the equalities in 2) and 3) must attain.

Call a row or a column positive (or negative) if the sum of all of its elements is positive or negative. Let $m^+, m^-$ be the numbers of positive and negative rows; similarly, let $n^+, n^-$ be the numbers of positive and negative columns. Clearly, the number in the square which is the intersection of positive column and negative row or the intersection of negative column and positive row has different sign with its column or its row. Call a number $a_{ij}$ bad if it has different sign with the column or the row that contains it. Denote $s$ to be the number of bad numbers, we have $s \ge m+n-m+n$. Denote $m_0 = \min\{m^+, m^-\}$ and $n_0 = \min\{n^+, n^-\}$, we obtain that

$$s \ge m^+n^- + m^-n^+ \ge m^+n_0 + m^-n_0 = m \cdot n_0.$$

Similarly, we have $s \ge n \cdot m_0$. Therefore,

$$s \ge \frac{1}{2}(n \cdot m_0 + m \cdot n_0). \qquad (1)$$

The second given condition implies that in every positive row, there are at least $\frac{3}{4}n$ numbers $+1$ and not more than $\frac{1}{4}n$ numbers $-1$.

The first condition follows that there are exactly $\frac{1}{2}mn$ numbers $+1$ in this table, thus there are at most $\frac{1}{2}mn - \frac{3}{4}n \cdot m^+$ numbers $+1$ in the negative rows. Let $s_1$ be the numbers of squares that contains the number which has different sign with the row containing it, we obtain that

$$s_1 \le \frac{1}{2}m \cdot n - \frac{3}{4}n m^+ + \frac{1}{4}n \cdot m^+ = \frac{1}{2}n(m - m^+) = \frac{1}{2}n m^-.$$

Similarly, we have $s_1 \le \frac{1}{2}mn - \frac{3}{4}n \cdot m^- + \frac{1}{4}n \cdot m^- = \frac{1}{2}n(m - m^-) = \frac{1}{2}n \cdot m^+$. Hence,

$$s_1 \le \frac{1}{2}n \cdot m_0. \qquad (2)$$

Similarly, denote $s_2$ to be the number of squares that contains the number which has different sign with the column containing it, we also have $s_2 \le \frac{1}{2}m \cdot n_0$. Therefore, $s \le \frac{1}{2}(n \cdot m_0 + m \cdot n_0)$.

Combining with (1), the inequality $s \le \frac{1}{2}(n \cdot m_0 + m \cdot n_0)$ becomes equality. In that case, by the condition (2), it is clear that there are exactly $\frac{3}{4}n$ numbers $+1$ and $\frac{1}{4}n$ numbers $-1$ or vice versa.

Thus, $n$ is the multiple of 4, and the same proof for $m$. $\square$