2014 Canadian MO Problems/Problem 2

Problem

Let and be odd positive integers. Each square of an by 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 and .

Solution

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