Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2014 Canadian MO Problems/Problem 2"

(In a \(m \times n\) rectangle, with \(m=2k+1\) and \(n=2l+1\), paint \(k+1 \times l\) blue and \(k+1 \times l+1\) red. For blue-dominated columns and red-dominated rows, this results in \(\frac{2m+n-1}{2}\) dominated)
 
Line 5: Line 5:
 
{{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>x+1</math> red-dominated rows <math>(x \geq y)</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 11:59, 30 June 2024

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_Canadian_MO_Problems/Problem_2&oldid=221347"