Maths Olympiad Prep

Library / /52 of 53

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Vietnam

A person wants to plant two different kinds of tree on a plot tabular grid size m×nm \times n (each square planted one tree). A planting way is called impressive if two following conditions are satisfied

i) The number of trees in each kind is equal.

ii) The difference between the number of two kinds of tree in each column and each row is at least m2\frac{m}{2} and n2\frac{n}{2} respectively.

a) Find an impressive planting way when m=n=2016m = n = 2016.

b) Prove that if there exists an impressive planting way then m,nm, n is divisible by 4.

Solution

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

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

AAAB
AABA
ABBB
BABB

It is clear that we can merge such 4×44 \times 4 tables to get a 2016×20162016 \times 2016 table satisfying a).
AAABAAAB
AABAAABA
ABBBABBB
BABBBABB
AAABAAAB
AABAAABA
ABBBABBB
BABBBABB

b) Assume that there exists an impressive planting way for a m×nm \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+,mm^+, m^- be the numbers of positive and negative rows; similarly, let n+,nn^+, 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 aija_{ij} bad if it has different sign with the column or the row that contains it. Denote ss to be the number of bad numbers, we have sm+nm+ns \ge m+n-m+n. Denote m0=min{m+,m}m_0 = \min\{m^+, m^-\} and n0=min{n+,n}n_0 = \min\{n^+, n^-\}, we obtain that

sm+n+mn+m+n0+mn0=mn0. s \ge m^+n^- + m^-n^+ \ge m^+n_0 + m^-n_0 = m \cdot n_0.

Similarly, we have snm0s \ge n \cdot m_0. Therefore,

s12(nm0+mn0).(1) 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 34n\frac{3}{4}n numbers +1+1 and not more than 14n\frac{1}{4}n numbers 1-1.

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

s112mn34nm++14nm+=12n(mm+)=12nm. 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 s112mn34nm+14nm=12n(mm)=12nm+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,

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

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

Combining with (1), the inequality s12(nm0+mn0)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 34n\frac{3}{4}n numbers +1+1 and 14n\frac{1}{4}n numbers 1-1 or vice versa.

Thus, nn is the multiple of 4, and the same proof for mm. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.