How many ways are there to put numbers $1,2,3,\cdots, n^2$ into a $n\times n$ chessboard s.t. the sum of the numbers on every row and every column is even.
My approach to this problem (Ideas)
I want to use parity to solve the problem. First, see all odd numbers as $1$, and all even numbers as $2$. Using the addition principle, we can figure out how many $0,1$ arrangements are there. After that, for each arrangement, using the multiplication principle, we can solve for all the arrangements.
Observations
- When $n=1$, there is no way to satisfy the question. (Trivial)
- When $n=2$, there is no way to satisfy the question. (Brute force)
- When $n=3$, there is no way to satisfy the question. (Brute force)
- When $n=4$?
When I got to $n=4$, I got stuck because the are way to many cases to write down if I brute force the problem.
Trying to solve the general formula
I GUESS there exists more than $0$ ways only for $4\mid n$. I already turned the original problem into an equivalent problem s.t. the numbers are all $0$ s and $1$ s. Now I may have to solve for the general formula for all $4m\times 4m\;(m\in \mathbb{N})$ chessboards, and prove that for all $n$ s.t. $4\nmid n$, there are $0$ possible arrangements.
Note
- I hope this is not a duplication. If there are any mistakes in my question, I will edit it.
- If two or more arrangements can be turned into one another by rotations and flips, these arrangements are still different arrangements.
Edit
The GUESS above is wrong. I should prove $\forall m\in \mathbb{N}$ s.t. $2\mid m$ and $m>2$, there exists at least one possible arrangement for a $m\times m$ chessboard. Then, I should find the general formula for the $m\times m$ chessboard.
Best Answer
I do not think there is any formula to count the number of matrices. You can use dynamic programming to count the number of matrices for $n\le 10$, but the time required is $O(n^32^{2n})$, so this quickly becomes infeasible. Here is the data I found (not in OEIS):
Here is a sketch of how the program works. Let $N(n,m,k,v)$ be the number of $m\times n$ matrices with elements in $\mathbb Z/2\Bbb Z$ which have exactly $k$ ones, where every row has an even number of ones, and for which the sum of the row vectors is $v$. By considering all possible choices for the last row of the matrix, we have $$ N(n,m,k,v)= \begin{cases} \sum_r N(n,m-1,k-|r|,v\oplus r) & m \ge 1 \\ 1 & m=0, k=0,v=\vec 0 \\ 0 & \text{otherwise} \end{cases} $$ where the sum ranges over all vectors $r\in (\Bbb Z/2\Bbb Z)^n$ with an even number of ones, $|r|$ is the number of ones in $r$, and $\oplus$ is the usual vector addition in $(\mathbb Z/2\mathbb Z)^n$. Your problem calls for $N(n,n,n^2/2, \vec 0)$.