Let $m$ and $n$ be positive integers. Determine the number of ways to fill each cell of an $m \times n $ table with a number from $\{-2, -1, 1, 2\}$ so that the product of the numbers written in each row and column is $-2$.
Problem
Source: Thailand Mathematical Olympiad 2015 p6
Tags: combinatorics
16.05.2022 08:02
Case 1: $m\neq n$ The product of each row is $-2$, so the product of the entire table is $(-2)^m$. Similarly, the product of each column is $-2$, so the product of the entire table is $(-2)^n$. Thus, $(-2)^m=(-2)^n$ which means that $m=n$, so if $m\neq n$ then the number of ways to fill is $0$. Case 2: $m=n$ Firstly, we will fill the "sign" in each cell, that is we choose whether each cell is $+$ or $-$. We change the cell into a $m\times m$ metrices with the last column and row are colored red \[\begin{bmatrix} *&*&*&*&*&\textcolor{red}{*}\\ *&*&*&*&*&\textcolor{red}{*}\\ *&*&*&*&*&\textcolor{red}{*}\\ *&*&*&*&*&\textcolor{red}{*}\\ *&*&*&*&*&\textcolor{red}{*}\\ \textcolor{red}{*}&\textcolor{red}{*}&\textcolor{red}{*}&\textcolor{red}{*}&\textcolor{red}{*}&\textcolor{red}{*} \end{bmatrix}_{m\times m}\]The value $a_{i,j}=0$ and $1$ if the sign of that cell is $+$ and $-$, respectively. Note that there must be odd $-$ in each row and column, so the sum of each row and column must be odd. We claim that no matter how the $(m-1)\times (m-1)$ submetrices with black $*$ are labelled with $0,1$, there is exactly one way to label the rest $(m^2-(m-1)^2)-1$ red $\textcolor{red}{*}$ that is not $a_{m,m}$ which is true since the parity of the sum of each row and column must be odd. Also, the parity of the sums $$a_{m,1}+a_{m,2}+\cdots+a_{m,m-1}\quad \text{ and }\quad a_{1,m}+a_{2,m}+\cdots+a_{m-1,m}$$are the same since the parity of them are both equal to the parity of $$m-1\times\text{odd}-\text{sum of all black dots}$$Thus, there is one way to fill $a_{m,m}$. Hence, the number of ways to fill the sign of this table is $2^{(m-1)^2}$. Now that we fill the sign of each cell, we'll proceed by filling the "magnitude" of each cell, that is we choose whether the magnitude of each cell is $1$ or $2$. Obviously, each row and column can have only one $2$ and the rest of them must be $1$. Thus, we have to fill $2$ so that every two of them are not in the same row or column. In row $1$, we can fill $2$ in $m$ ways since we can fill it anywhere. In row $2$, we can fill $2$ in $m-1$ ways since it must not be in the same column as the previous $1 \ 2\text{'s}$. In row $3$, we can fill $2$ in $m-2$ ways since it must not be in the same column as the previous $2 \ 2\text{'s}$. $$\vdots$$In row $n$, we can fill $2$ in $1$ ways since it must not be in the same column as the previous $m-1 \ 2\text{'s}$. Thus, the number of ways to fill magnitude of each cell in this table is $m!$. Hence, the number of ways to fill this table is $2^{(m-1)^2}\cdot m!$. We can now conclude that the number of ways to fill is $= \begin{cases} 0 &\text{ if }m\neq n, \\ 2^{(m-1)^2}\cdot m! &\text{ if }m=n. \end{cases} $ Majority of the part that we fill a sign is from Puntre's solution in 2021 Thailand MO P6 thread.