Difference between revisions of "2014 Canadian MO Problems/Problem 2"
(Created page with "== Problem== Let <math>m</math> and <math>n</math> be odd positive integers. Each square of an <math>m</math> by <math>n</math> board is coloured red or blue. A row is said to...") |
|||
(One intermediate revision by the same user not shown) | |||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
{{Solution}} | {{Solution}} | ||
+ | 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. |
Latest revision as of 12:59, 30 June 2024
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.