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$.
Problem
Source: 2014 CMO #2
Tags: floor function, combinatorics proposed, combinatorics, CMO
MellowMelon
12.05.2014 04:14
Fairly similar problem(s) here: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=480479 (The problem in the original post is much easier; the strengthened versions discussed later are much harder. The similarity is that minimizing double-dominant cells mostly involves making lots of rows dominant in one color and lots of columns dominant in the other.)
loopback
02.12.2014 14:51
Can anyone give the answer for this particular question
chaotic_iak
02.12.2014 14:58
First, $m+n-2$ is achievable using the same method: RRRRbbb v RRRRbbb v bbbRbbb bbbRRRR v bbbRRRR v vvv vvv Suppose that $m+n-1$ is achievable. Then either all rows are red-dominated or all columns are blue-dominated (otherwise there are at most $(m-1) + (n-1) = m+n-2 < m+n-1$ dominated lines). WLOG all rows are red-dominated, then there are at least $m \cdot \dfrac{n+1}{2}$ red squares ($\dfrac{n+1}{2}$ red squares in a red-dominated row, times $m$ rows), and thus only $m \cdot \dfrac{n-1}{2}$ blue squares. Since we need $\dfrac{m+1}{2}$ in each column, we have at most $\left\lfloor \dfrac{m(n-1)/2}{(m+1)/2} \right\rfloor = \left\lfloor \dfrac{m}{m+1} \cdot (n-1) \right\rfloor < n-1$ blue-dominated columns. But then we have no more than $n-2$ blue-dominated columns, adding up to $m + (n-2) < m+n-1$ dominated lines, contradiction. So the maximum is indeed $m+n-2$.
CeuAzul
10.10.2016 16:36
Dude you forgot about case $m=n=1$,then your answer will be $0$,not $1$ Your sincerely CeuAzul
Garfield
04.01.2017 14:00
Let's every every red dominate row and blue dominate column call $saved$.Let's prove we can save at most $m+n-2$.Assume opposite
We can save $m+n-1$,let $m=2k+1$ and let $n=2l+1$ so WLOG we save all columns so there are at least $l+1$ blue squares in each column and there are $2k+1$ columns so at least $(2k+1)\cdot (l+1)$ blue squares.Now we must save $2l$ rows so at least $2l\cdot(k+1)$ so we have at least
$2kl+2k+l+1+2lk+2l=4kl+3l+2k+1>(2k+1)\cdot (2l+1)$ painted squares,contradiction.
Construction for $m+n-2$ is trivial we will save $2k$ rows and $2l$ columns:
BBBBBB...BBB
RBRBRB...RRB
BRBRBR...BRR
...
So we hadn't saved only $2k$-th column and $1$-st row.
zephyr7723
24.01.2019 15:28
This is my first solution on AOPS, hence starting with an easy one. We would convert the given problem to graphs. Let the rows and columns denote the vertices of the said graph. Let the set of rows be $R =\{r_1 , r_2 , r_3 ,\cdots , r_m\}$ Let the set of columns be $C =\{c_1, c_2, c_3,\cdots, c_n\}$ If the graph be denoted by $G(E,V)$ Therefore by our definition $E = R \cup C$ Now we define the graph to be bipartite. Here each egde in $R$ is joined to each edge in $C$. An egde that exists between $c_i$ and $r_j$ denotes the box on the $i$th column and $j$th row. Now we direct the graph $G$. An out edge from a vertice $r_i$ that goes to some $c_j$ denotes that the box that is on the $i$th row and $j$th column has red colour. Similarly denote the same for an out edge from a column vertex but just with blue colour. Hence, if we now interpret the question in this new system we see that the question effectively wants us to find the the maximum number of vertices which satisfy the given relation; $$deg^{+}(V)>deg^{-}(V)$$Now my claim is, that the answer is $m+n-2$. First I will prove that the answer is not greater than $m+n-2$. Let the number of such vertices in $G$ be denoted by $k$. Let the set of such vertices be $A$. Now suppose to the contrary that $k>m+n-2$, then by pigeonhole principle we can conclude that one set among $R$ and $C$ must have all its vertices in $A$. Now if the said set is $R$ Therefore, $deg^{+}(r_i)\ge \frac{n}{2}+1$ Therefore, $$\sum_{R}deg^{+}(r_i) \ge \frac{mn}{2}+m$$. Now as $k>m+n-2$ therefore at least $n-1$ vertices of $C$ must be in $A$ Therefore, $$\sum_{C}deg^{-}(c_i)<\frac{m(n-1)}{2} + m= \frac{mn}{2}+\frac{m}{2}$$But as the graph is bipartite $$\sum_{R}deg^{+}(r_i) = \sum_{C}deg^{-}(c_i)$$Hence we have reached a contradiction. A similar contradiction can be achieved by assuming that $C$ has all of its vertices in $A$. Therefore $k\le m+n-2$. Now as for the case when $k=m+n-2$, it is quite easy to construct.
Jupiter123
05.05.2021 20:51
Let $m = 2k + 1$, $n = 2s + 1$. Take $s,t \geq 1$ (cases when $(s,t) = (0,1), (0,0)$ are trivial). Let $c$ and $r$ denote the number of columns and rows for which are blue-dominating and red-dominating, respectively. Let $p,q$ denote the number of red and blue cells, respectively. The problem states that we need to find the maximum of $c + r$. We'll prove that $max(c+r)$ for all such colorings is equal to $m+n-2 = 2s + 2k$. For this, notice that if
$$c,r \leq 2k, 2s$$.
then it's correct. Now assume that one of them $= 2s+1$ (the case when one of them $=2k+1$ is the same). Notice that $(c,r) \neq (2s+1,2k+1)$. WLOG assume that $r = 2s + 1$ and $c \leq 2k$. Since the number of red cells in each red-dominant row has to be $\geq s+1$, we have
$$p \geq (2s + 1)(s+1) = 2s^2 +3s +1$$.
With this we have that
$$q \leq (2k+1)(2s+1) - (2s^2 +3s + 1) = 2s(2k-s) + (2k - s) + 1 - 1 = (2s+1)(2k-s)$$.
Thus, $$c \leq \frac{(2s+1)(2k-s)}{k+1}$$
since we need to have at least $k+1$ blue cells in a column for it to be blue-dominant. We'll prove that,
$$c + r \leq \frac{(2s+1)(2k-s)}{k+1} + (2s + 1) \leq 2s + 2k$$
which simplifies to $4sk + 1 \leq 2s^2 + 2k^2 + s $, which is clearly true. Thus, if one of $c$ or $r$ equals $2s+1$, we have that $c+r \leq 2s +2k$. Thus, we have that $c + r \leq 2s + 2k$, which is what we needed to prove. Constructions are the same as the proofs above.