13
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ math.stackexchange.com/questions/1846722/… seems awfully similar. $\endgroup$ Jun 6, 2020 at 9:39
  • 1
    $\begingroup$ @mypronounismonicareinstate I did not notice this was a duplicate of another site. $\endgroup$ Jun 6, 2020 at 10:07
  • 1
    $\begingroup$ One lateral-thinking answer could involve noting that chess pieces of the same colour are not conventionally considered to be attacking each other... but that would miss the elegance of the intended (and already given) solution! $\endgroup$
    – Steve
    Nov 30, 2021 at 8:12

1 Answer 1

17
$\begingroup$

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:
enter image description here
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.

enter image description here
So these are the only two solutions.

$\endgroup$
1
  • 1
    $\begingroup$ Correct! This is IMO shortlist 14C3 $\endgroup$ Jun 6, 2020 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.