, 2016

For each row consider all pairs of squares from this row such that both squares are the same colour. From the condition of the problem it follows that no two rows can have any of these pairs in common. So, each pair can occur in at most one row. There are $\binom{m}{2} = \frac{m(m-1)}{2}$ pairs altogether and the squares in each pair are either both red or both blue. So there are $2 \cdot \frac{m(m-1)}{2} = m(m-1)$ possible pairs.

On the other hand we can estimate the lowest possible number of same-colour pairs in each row. Suppose that a row contains $k$ red and $m-k$ blue squares. Then the number of same-colour pairs is equal to $\binom{k}{2} + \binom{m-k}{2}$. This number can be bounded below by using the Quadratic-Arithmetic Means Inequality
$$\begin{aligned} \binom{k}{2} + \binom{m-k}{2} &= \frac{k(k-1)}{2} + \frac{(m-k)(m-k-1)}{2} \\ &= \frac{k^2 + (m-k)^2}{2} - \frac{m}{2} \\ &\ge \left( \frac{k+(m-k)}{2} \right)^2 - \frac{m}{2} = \frac{m(m-2)}{4}. \end{aligned}$$
Since the number of possible same-coloured pairs is at least as large as the total number of same-colour pairs in all the rows combined and we have bounded the number of same-colour pairs from below, we have
$$\begin{aligned} m(m-1) &\ge m \cdot \left( \frac{m(m-2)}{4} \right) \\ \Rightarrow 0 &\ge m^2 - 6m + 4. \end{aligned}$$
Solving the quadratic equation we see that $m \le 3 + \sqrt{5} < 6$. So, $m \le 5$.

When $m = 5$ the lower bound from above has the value of $\frac{m(m-2)}{4} = \frac{15}{4} > 3$. This means that any colouring will create at least 4 same-colour pairs in each row. Since the number of possible pairs is $m(m-1) = 20$ and there are 5 rows, each row has to contain exactly 4 same-colour pairs. This can only happen when the row contains 3 squares of one colour and 2 squares of the other colour. Altogether we have to use all of the 10 red pairs and all of the 10 blue pairs. But the number of rows is odd. So, the number of squares of one colour will have to be greater than the number of squares of the other colour and the same will be true for the number of red pairs and the number of blue pairs. Hence, the $5 \times 5$ array cannot be coloured as desired.

We have shown that the greatest positive integer with the desired property is $m = 4$.