2014 Canadian MO Problems/Problem 2

Problem

Let $m$ and $n$ be odd positive integers. Each square of an $m$ by $n$ board is coloured red or blue. A row is said to be red-dominated if there are more red squares than blue squares in the row. A column is said to be blue-dominated if there are more blue squares than red squares in the column. Determine the maximum possible value of the number of red-dominated rows plus the number of blue-dominated columns. Express your answer in terms of $m$ and $n$ .

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it. Answer: $\frac{2m+n-1}{2}$ . Without losing of generality, $m \geq n$ and $m=2k+1$ , $n=2l+1$ . For a column with m cells to be blue-dominated, at least $k+1$ cells have to be blue. Similarly, for a row with n cells to be red-dominated, at least $l+1$ have to be red. So, we divide $m$ by $n$ rectangle: $k+1$ by $l$ , $k+1$ by $l+1$ , $k$ by $l+1$ and $k$ by $l$ . We look at the rectangle $k+1$ by $l$ , it has most $y$ blue-dominated columns, so we paint the rectangle $k+1$ by $l$ blue. Now, we look at the rectangle $k+1$ by $l+1$ . It has most $k+1$ red-dominated rows $(k \geq l)$ . So, we paint the rectangle $k+1$ by $l+1$ red. If we look at the rectangle $k$ by $l+1$ and paint it in blue, it cannot be blue-dominated, so we paint it red. Now, we have $2k+l+1$ dominated rows and columns. It is not necessary to look at the rectangle $k$ by $l$ , it cannot be dominated no matter how we paint it. We have $2k+l+1= \frac{2m+n-1}{2}$ dominated rows and columns.

Page

Toolbox

Search

2014 Canadian MO Problems/Problem 2

Problem

Solution