On a standard chessboard,
What is the number of different arrangements of pawns such that every square has an odd number of pawns on its neighbor (horizontally or vertically) squares?
Note: diagonals and the square itself is not counted
Note 2: you may count symmetrical or mirrored solutions as well.
If this question was asked for $2$x$2$ board, the answer would be $4$ as below:
and $3$ other symmetric solutions.
We can think of this as a linear algebra problem mod $2$. That is, we need to satisfy $Ax=b$ where $A$ is the $64\times 64$ adjacency matrix of the chessboard. The vector $x$ stores a $1$ if a pawn is on that square and a $0$ otherwise. Then $b$ is a vector only containing $1$'s, because we want an odd number of adjacent pawns from each square. Then we can find a solution by solving this system of equations over GF(2).
Using a computer (or a lot of spare time by hand), we find that a solution does in fact exist, for example:
x x x x x x x x
- x x x x x x -
x x - - - - x x
- x x - - x x -
x x - - - - x x
- x x x x x x -
x x x x x x x x
- - - - - - - -
We can also determine that the nullity of $A$ is $8$, so there are
$2^8=256$ solutions in total.
How can we describe the entire solution set, you may ask? Well, just put any number of pawns wherever you want on the top row. These act as our $8$ free variables. Then place whatever pawns you need in the second row so that the oddness property is satisfied on the first row. Then place whatever pawns you need in the third row so that the oddness property is satisfied in the second row. Repeat this until you place pawns on the last row and the whole board is a solution. This works for $8\times 8$ specifically because there are $8$ free variables.
In general, if you only want the number of solutions, there is a very nice formula for any $m\times n$ grid, as shown by K. Sutner in The $\sigma$-Game and Cellular Automata. See theorem on pg. 28.
$2^{\gcd(m + 1, n + 1) - 1}$ if a solution exists, $0$ otherwise.
Start by focusing on the black squares.
• • • A
• • C B
• • E D
• G F •
• I H •
K J • •
M L • •
N • • •
A and B must be different (one has a pawn, the other does not), because the upper right corner touches an odd number of pawns. Looking at the square surrounded by A, B, C and D, this means that C and D must be the same (both have pawns, or both do not). Continuing in this fashion, we get the following pattern:
• • • A
• • B a <-- Lower case letters must the opposite of
• • C B corresponding upper case letter.
• D c L
• E D K
F e J • Two same capital letters must be the same.
G F I •
g H • •
From now on, we use mod 2 arithmetic. Give each square a number so squares without pawns are 0 and squares with pawns are 1. Then the neighbors of any square must add to 1 (mod 2). This means that
H = g + F + 1
I = e + F + H + 1 = e + F + (g + F + 1) + 1 = e + g
J = D + e + I + 1 = D + e + (e + g) + 1 = D + g + 1
K = c + D + J + 1 = c + D + (D + g + 1) + 1 = c + g
L = B + c + K + 1 = B + c + (c + g + 1) + 1 = B + g + 1
Finally, considering the white square surrounded by a, B and L, we must have
a + B + L = 1
∴ a + B + (B + g + 1) = 1
∴ a = g
In other words, we have learned that the H, I, J, K, L diagonal is entirely determined by the numbers above it, and we have learned that a and g are constrained to be equal.
By doing similar work on the other diagonals, you can deduce that the grid must look like this:
• • • A
• • B a
• • C B
• D c •
• C D •
B c • •
A B • •
a • • •
where all of the •'s are forced by the choices of A, B, C and D. However, these four variables can be chosen freely, so there are sixteen ways to place the pawns on the black squares. The white pawns can be chosen independently of the black pawns in the same number of ways, for
16 x 16 = 256
ways total.
I don't know the answer but have at least found an upper bound of
$2^{14} = 16384$
My reasoning:
If we start at one of the corners, say A1, we only one of B1 and A2 has a pawn. Continuing for B2, we know either B3 and C2 are both pawns or neither pawns. This reasoning can continue till H8 where we have 7 pairs of squares that can be in one of two states. Adding in the 7 pairs for the other diagonal we get 14 pairs in total, which give us our 16384 combinations. For each of these combinations we can find a sequence of squares that have one unknown neighbor and fill it with a pawn or not to make numbers odd. The sequence I used was (C1, D2, D1, and their 7 rotations and mirrors for each, D3, C2, B1, and each of their 3 mirrors for each). This will fill the rest of the board, however, there are still 12 squares that do not necessarily have an odd number of neighbors (A2, B3, C4, and their 3 mirrors for each in my case). This might rule out some of the 16384 solutions but will not add any more.
