A chessboard Combinatorics Problem

chessboardcombinatorics

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

  1. When $n=1$, there is no way to satisfy the question. (Trivial)
  2. When $n=2$, there is no way to satisfy the question. (Brute force)
  3. When $n=3$, there is no way to satisfy the question. (Brute force)
  4. 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

  1. I hope this is not a duplication. If there are any mistakes in my question, I will edit it.
  2. 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):

$n$ $4$ $6$ $8$ $10$
# matrices $246$ $8784000$ $111869178489670$ $384868991272320758246400$

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)$.

Related Question