Let $ m,n\ge 2 $ and consider a rectangle formed by $ m\times n $ unit squares that are colored, either white, or either black. A step is the action of selecting from it a rectangle of dimensions $ 1\times k, $ where $ k $ is an odd number smaller or equal to $ n, $ or a rectangle of dimensions $ l\times 1, $ where $ l $ is and odd number smaller than $ m, $ and coloring all the unit squares of this chosen rectangle with the color that appears the least in it. a) Show that, for any $ m,n\ge 5, $ there exists a succession of steps that make the rectagle to be single-colored. b) What about $ m=n+1=5? $
Problem
Source: Stars of Mathematics 2016, Juniors, Problem 2
Tags: rectangle, discrete maths, Combinatorial games
sarjinius
23.01.2022 20:47
(a) First, we will make all rows monochromatic. If we have an odd number of columns, we can make any row monochromatic in a single move. If the number of columns is even, to make a row monochromatic, we apply the step on all the squares on that row except the first square. If the first square has the same color as the others, the row is monochromatic. If not, we apply the step on the first $3$ squares of the row. After this, the first $3$ squares of the row have a different color than the other squares in the row. We now apply the step on the first $5$ squares of the row, which would finally lead to the row being monochromatic. We do this with all rows. If all rows are monochromatic, then all the columns are identical. Similar to what we did with the rows, we can make all columns monochromatic. By applying the same sequence of steps to each column, the entire rectangle will be monochromatic, and we are done. (b) If $m=5$ and $n=4$ (assume $5$ columns and $4$ rows), we will show that it is possible to make the rectangle monochromatic. In this case, we can make all rows monochromatic as shown in (a). There will be $3$ cases as follows: Case 1: If all these rows are of the same color, then we are done. Case 2: If two of the rows have the same color and the other two are of the other color, then to make a column monochromatic, we apply the step on the first three squares on the column. Apply this to all columns, then we are done. Case 3: If three rows have the same color and the other one is of another color, using the same step as Case 2, we can make the first three rows have the same color (WLOG white) and the last row be black. We apply the steps on the last $3$ squares of column $2$, the last $3$ squares of column $3$, the first $3$ squares of row $3$, the last $3$ squares of column $2$, the last $3$ squares of column $3$, then the entire last row, in that order. Now the rectangle is completely white, and we are done.