Kings on a chessboard

Question

Let $n$ be a positive integer. You are given $4n^2$ kings and a $4n\times4n$ chessboard. You have to place the kings on the chessboard such that each row and column contains exactly $n$ kings, and no kings attack each other. How many ways can you do it?

---

Source: IMO shortlist 2010 C3

Answer 1

There are

two ways to do this.

Here's why:

Every 2x2 space can contain exactly one king. You need (2n×2n) stars, so if you divide the grid into 2×2 blocks, each one has exactly one king.

Call a block "right-weighted" if the king is in the right side, and "left-weighted" if the king is in the left side. In a row, you can never have a right-weighted block immediately left of a left-weighted block because their kings would touch.
Look at the weightings of a row of blocks. Can the edge blocks both be weighted inwards? No: it would cause that condition above to happen somewhere in that row. If you have "R....L", then that row has to have RL in it somewhere.

Can you have the opposite situation, where both end blocks are weighted towards the edge? Also no: a different row would have to have both edge blocks weighted inwards, because both the left and right columns of blocks have to have half of their blocks weighted out and half weighted in. If you have a double-out row, you'll have to have a double-in row somewhere else.

This shows that every row of blocks is all weighted the same direction: left or right. Similarly, every column of blocks is either all top-weighted or all bottom-weighted. (And in both of these cases, they have to be split half and half: half of the rows are left-weighted, and the other half are right-weighted.)


Now, note that you can never have this scenario with your weightings:

Here, the center blocks would have kings touching.
This means that, reading your column weightings from left to right, you can never have both "down-up" and "up-down". If you did, one of those two would cause a problem at any place where the rows change weightings.
So, the left half of the columns all have the same weight, and the right half of the columns all have the same weight. (And the same holds for the rows.)

This leaves only four options. Columns' weightings will either be ↓↓↓↓↑↑↑↑ or ↑↑↑↑↓↓↓↓; similarly, rows' weightings will be either →→→→←←←← or ←←←←→→→→. As shown by the image above, we can't have the first column option with the first row option, because it would cause a contradiction in the center. Similarly, we can't have the second with the second. But the other two options do produce solutions: the below and its mirror image.


So these are the only two solutions.