Let $m$ and $n$ be natural numbers with $mn$ even. Jetze is going to cover an $m \times n$ board (consisting of $m$ rows and $n$ columns) with dominoes, so that every domino covers exactly two squares, dominos do not protrude or overlap, and all squares are covered by a domino. Merlin then moves all the dominoe color red or blue on the board. Find the smallest non-negative integer $V$ (in terms of $m$ and $n$) so that Merlin can always ensure that in each row the number squares covered by a red domino and the number of squares covered by a blue one dominoes are not more than $V$, no matter how Jetze covers the board.
Problem
Source: 2021 Dutch IMO TST 3.1
Tags: combinatorics, game, game strategy, winning strategy, dominos
FIREDRAGONMATH16
01.01.2022 04:41
parmenides51 wrote: Merlin then moves all the dominoe color red or blue on the board. Do you mean that "Merlin then colors all the dominoes red or blue on the board."? A more gramatically correct problem statement would be parmenides51 wrote: Let $m$ and $n$ be natural numbers with $mn$ even. Jetze is going to cover an $m \times n$ board (consisting of $m$ rows and $n$ columns) with dominoes, so that every domino covers exactly two squares, dominos do not protrude or overlap, and all squares are covered by a domino. Merlin then colors all the dominoes red or blue on the board. Find the smallest non-negative integer $V$ (in terms of $m$ and $n$) so that Merlin can always ensure that in each row the number of squares covered by a red domino and the number of squares covered by a blue domino are not more than $V$, no matter how Jetze covers the board. Just FTFY
FIREDRAGONMATH16
01.01.2022 05:03
The answer is trivially $\boxed{V=n}$.
Our construction goes as follows: in order for there to exist a nonnegative integer $V$ such that each row has $r$ and $b$ squares colored red and black respectively with $r,b \le V$, we must find the most extreme case for equality to occur. Because $r+b = n$ implies $r,b \le n$, it suffices to find a row such that $(r,b) = (0,n)$ or $(n,0)$. In fact, this is trivially possible; even if he does not color all square blue or red, we may first select an arbitrary $r$th row $1 \le w \le m$ and have Merlin not color that those dominos that contain at least one square in that row. Any further colorings of the other dominos will still result in an optimal coloring. Hence because this is the extreme case, we must have $V = n$ as our minimum $V$.
Remarks. Again, is it just me? I think I read the problem carefully enough, but this seems a bit too trivial for a Dutch TST problem, considering that I haven't even started doing many USAJMO/USAMO problems yet. I need someone to tell me where I'm wrong with the construction... or is it correct?