An odd chessboard

Probability Level 1

Can you rearrange the 64 squares on a chess board so that every row and column has an odd number of black squares?

Yes No

2 solutions

Chris Lewis
Apr 17, 2019

I started this problem firmly believing it wasn't possible to arrange the chessboard this way, then failing to prove it.

My next attempt was to simply try out arrangements on an 8x8 board. This eventually worked, but almost immediately led to another idea: what about a 4x4 board? Clearly this is a much simpler problem: if a valid arrangement exists, the numbers of black squares in each row must be $\{1,1,3,3\}$ in some order (no other set of four odd numbers each less than $4$ would total $8$ ), so it's easy to look for a valid arrangement by hand.

Let's label a rearranged chessboard whose rows and columns all have an odd number of black squares "odd", and one whose rows and columns all have an even number of black squares "even". (There are some arrangements that don't fall into these categories, but I won't be using them in this discussion).

Here are two example odd 4x4 chessboards:

And here are two even ones:

The reason this helps is we can combine two odd 4x4 chessboards with two even ones two make an odd 8x8, as below:

Examples based on the above boards:

There are, of course, various operations we can perform on the board that don't change the parity of its rows and columns, for example swapping two columns, swapping two rows, rotating, reflecting; by using combinations of these a variety of different solutions can be found.

David Vreken
Apr 14, 2019

If you start with a regular checkerboard, and pick $4$ vertical $2 \times 1$ tiles and $4$ horizontal $2 \times 1$ tiles so that there is one vertical tile in each row and one horizontal tile in each column, and flip the colors in those tiles, you will end up with $4$ rows with $3$ black squares, $4$ rows with $5$ black squares, $4$ columns with $3$ black squares, and $4$ columns with $5$ black squares, which fulfills the requirement that every row and column has an odd number of black squares.

Here are some other possible checkerboards:

I got the problem wrong but ended up working out a solution that is kinda similar.

Let the checkerboard be denoted as an array

$\begin{aligned}[a_{ij}]&=\begin{cases}\text{Red} &: \text{ if } i+j\equiv0\pmod{2}\\ \text{Black} &: \text{ if } i+j\equiv1\pmod{2} \end{cases}\end{aligned}$

Now choose $8$ elements such that ,

$i \in \{1,2,3,4,5,6,7,8\}$

$j \in \{1,2,3,4,5,6,7,8\}$

$i$ and $j$ are chosen without repetition

This will ensure that each element will have a unique row and column corresponding to it.

also there are $4$ even and $4$ odd choices for both $i$ and $j$ .If i and j are chosen as shown below

$\text{Element No:}$	$\hspace{3mm}$ i	$\hspace{3mm}$ j
1	even	odd
2	even	odd
3	odd	even
4	odd	even
5	even	even
6	even	even
7	odd	odd
8	odd	odd

The first $4$ elements will be $\text{Black}$ as $i+j\equiv1\pmod{2}$

The next $4$ elements will be $\text{Red}$ as $i+j\equiv0\pmod{2}$

Pair them up so that each pair has a black and red square,

now interchange the position of the black and red square within each pair.

Now each row and column will have an odd number of black and red squares.

Also, swapping the black and red tiles in every solution of the 8 queens puzzle will also satisfy the problem.

Anirudh Sreekumar - 2 years, 1 month ago

An odd chessboard

2 solutions

0 pending reports