Difference between revisions of "2014 Canadian MO Problems/Problem 2"
m |
|||
| Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
| − | |||
Answer: <math>\frac{2m+n-1}{2}</math>. | Answer: <math>\frac{2m+n-1}{2}</math>. | ||
Without losing of generality, <math>m \geq n</math> and <math>m=2k+1</math>, <math>n=2l+1</math>. For a column with m cells to be blue-dominated, at least <math>k+1</math> cells have to be blue. Similarly, for a row with n cells to be red-dominated, at least <math>l+1</math> have to be red. So, we divide <math>m</math> by <math>n</math> rectangle: <math>k+1</math> by <math>l</math>, <math>k+1</math> by <math>l+1</math>, <math>k</math> by <math>l+1</math> and <math>k</math> by <math>l</math>. We look at the rectangle <math>k+1</math> by <math>l</math>, it has most <math>y</math> blue-dominated columns, so we paint the rectangle <math>k+1</math> by <math>l</math> blue. Now, we look at the rectangle <math>k+1</math> by <math>l+1</math>. It has most <math>k+1</math> red-dominated rows <math>(k \geq l)</math>. So, we paint the rectangle <math>k+1</math> by <math>l+1</math> red. If we look at the rectangle <math>k</math> by <math>l+1</math> and paint it in blue, it cannot be blue-dominated, so we paint it red. Now, we have <math>2k+l+1</math> dominated rows and columns. It is not necessary to look at the rectangle <math>k</math> by <math>l</math>, it cannot be dominated no matter how we paint it. We have <math>2k+l+1= \frac{2m+n-1}{2}</math> dominated rows and columns. | Without losing of generality, <math>m \geq n</math> and <math>m=2k+1</math>, <math>n=2l+1</math>. For a column with m cells to be blue-dominated, at least <math>k+1</math> cells have to be blue. Similarly, for a row with n cells to be red-dominated, at least <math>l+1</math> have to be red. So, we divide <math>m</math> by <math>n</math> rectangle: <math>k+1</math> by <math>l</math>, <math>k+1</math> by <math>l+1</math>, <math>k</math> by <math>l+1</math> and <math>k</math> by <math>l</math>. We look at the rectangle <math>k+1</math> by <math>l</math>, it has most <math>y</math> blue-dominated columns, so we paint the rectangle <math>k+1</math> by <math>l</math> blue. Now, we look at the rectangle <math>k+1</math> by <math>l+1</math>. It has most <math>k+1</math> red-dominated rows <math>(k \geq l)</math>. So, we paint the rectangle <math>k+1</math> by <math>l+1</math> red. If we look at the rectangle <math>k</math> by <math>l+1</math> and paint it in blue, it cannot be blue-dominated, so we paint it red. Now, we have <math>2k+l+1</math> dominated rows and columns. It is not necessary to look at the rectangle <math>k</math> by <math>l</math>, it cannot be dominated no matter how we paint it. We have <math>2k+l+1= \frac{2m+n-1}{2}</math> dominated rows and columns. | ||
Latest revision as of 22:54, 22 March 2025
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
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.
