Given a $24 \times 24$ square grid, initially all its unit squares are coloured white. A move consists of choosing a row, or a column, and changing the colours of all its unit squares, from white to black, and from black to white. Is it possible that after finitely many moves, the square grid contains exactly $574$ black unit squares?
Problem
Source: 2023 Hong Kong TST
Tags: combinatorics, TST
08.05.2023 18:10
Answer: No, it is impossible to make the square grid contains exactly 574 black units. Denote the move that changing the colours of all unit squares in row $n$ is $A_n$, the move that changing the colours of all unit squares in column $m$ is $B_m$. For any moves $C_1,C_2,\cdots,C_j\in\{A_1,A_2,\cdots,A_{24},B_{1},B_{2},\cdots,B_{24}\}$, We define $C_1C_2\cdots C_j$ as a series of step-by-step operations that we do the operations $C_1$, $C_2$, $\cdots$, $C_j$ in order. For any $m,n\in\{1,2,\cdots,24\}$, it is easy to know that $A_mA_n=A_nA_m$, $A_mB_n=B_nA_m$, $B_mB_n=B_nB_m$. Hence, for any series of operation $C_1C_2\cdots C_j$, it can be equivalent to $A_{i_1}A_{i_2}\cdots A_{i_p}B_{i_{p+1}}B_{i_{p+2}}\cdots B_{i_{j}}\ (1\leq i_1\leq i_2\leq\cdots\leq i_j)$ . Obviously, we can see that if there is a number $r$ satisfying $i_r=i_{r+1}$, then $A_{i_{r-1}}A_{i_r}A_{i_{r+1}}A_{i_{r+2}}$ can be simplified to $A_{i_{r-1}}A_{i_{r+2}}$ ($B$ also). So, after finitely many times, $A_{i_1}A_{i_2}\cdots A_{i_p}B_{i_{p+1}}B_{i_{p+2}}\cdots B_{i_{j}}$ can be simplified to $A_{i_1'}A_{i_2'}\cdots A_{i_q'}B_{i_{q+1}'}B_{i_{q+2}'}\cdots B_{i_k'}\ (i_1'<i_2'<\cdots<i_k')$. If the series of operations $A_{i_1'}A_{i_2'}\cdots A_{i_q'}B_{i_{q+1}'}B_{i_{q+2}'}\cdots B_{i_k'}$ can make the 576 white square grids become 574 black square grids, then we get \begin{align} 24q+24(k-q)-2q(k-q)&=574\notag\\ q(k-q)-12q-12(k-q)+287&=0\notag\\ (q-12)(k-q-12)&=-143 \end{align} But, $0\leq q,k-q\leq 24 \Leftrightarrow |q-12|,|k-q|\leq 12 \Rightarrow 13\nmid q-12\ \text{and}\ 13\nmid k-q-12\Rightarrow 13\nmid(q-12)(k-q-12)=-143$, contradiction.
08.05.2023 20:06
We have 24×24=576 squares in the 24×24 square grid. We have to colour all squares black or white. Therefore,exactly 574 is not possible.
08.05.2023 20:35
Banglarmanush wrote: We have 24×24=576 squares in the 24×24 square grid. We have to colour all squares black or white. Therefore,exactly 576 is not possible. what. that makes no sense. It is very easy to color all $576$ squares black; we go through each column and color it all black (or each row works too). The goal here is to make $574$ squares black and $2$ white. This adds to $576,$ which is the total number of squares.
19.06.2023 02:43
Ok,I am adding some another things here.Sorry bro I am late. Take, A row and colour it black And repeat it until the last Now,we have 576 black unit squares. Take, A row and colour it white 576-24=552 squares We can see that, it is never possible to have exactly 574 black squares is not possible.