4
$\begingroup$

Let n be a natural number. We put $4n^2$ kings on a chessboard with the size $4n \times 4n$, in such a way no two kings attack each other, and there should be exactly $n$ kings in every row and column. In how many ways can this be done?

Edit: For n=1 there is only one solution with it's mirror. For n=2 I've found one way to do it, and I've had some trouble finding it in the first place. I haven't tried to find a combination for larger chessboards. Here's the picture of both: Picture

I think there is a nice formula, this was one of the problems in IMO qualification for my country, and those tend to have nice solutions, at least the ones from combinatorics.

$\endgroup$
  • 1
    $\begingroup$ For n=1 there is only one solution with it's mirror. For n=2 I've found one way to do it, and I've had some trouble finding it in the first place. I haven't tried to find a combination for larger chessboards. Here's the picture of both: imgur.com/qco0XFE. I think there is a nice formula, this was one of the problems in IMO qualification for my country, and those tend to have nice solutions, at least the ones from combinatorics. $\endgroup$ – TAJD Jul 2 '16 at 11:30
  • 1
    $\begingroup$ Good observations. Adding this context to the body of your Question would improve it. $\endgroup$ – hardmath Jul 2 '16 at 11:40
  • $\begingroup$ Hint: Given your solutions of the $4\times 4$ case, apply a pigeonhole argument to the $4n\times 4n$ case. $\endgroup$ – hardmath Jul 2 '16 at 12:31
0
$\begingroup$

This is a really enjoyable question! I'm going to try and work through it without pictures.

Let's divide the board into $2\times{2}$ tiles - so there will be $2n$ tiles across and $2n$ tiles down.

It is obvious that each tile can contain only one king. Let's label the tile T if he is in the top row of the tile and B if he is in the bottom row; similarly L if he is in the left-hand column and R if he is in the right-hand one. In your left-hand picture this makes the first row of tiles TR BR, and in your right-hand picture this makes the first row of tiles BL BL TL TL.

In each row of tiles, there have to be $n$ Ts and $n$ Bs. This is to ensure that the total number of kings in each row of the board is $n$.

Looking at the second row of tiles, you cannot have a T underneath a B from the first row, because the top-row king of the second tile would attack the bottom-row king of the first. So (reading downwards) a B has to be followed by a B. As far as non-attacking goes, a T could be followed by a B; but then there would be more Bs than Ts, which violates the condition of "total kings per row = $n$". So the pattern of Ts and Bs has to be identical in the second row.

Thus, for "T versus B", we know that there have to be $n$ Ts and $n$ Bs, labelling each successive column of tiles.

Similar reasoning shows that there have to be $n$ Ls and $n$ Rs, labelling each successive row of tiles.

This would appear to indicate that there are $\binom{2n}{n}$ arrangements of Ts and Bs, and of Ls and Rs. But there is another constraint!

Consider a pair of columns where T becomes B, and a pair of rows where L becomes R, and look at everything from the point of view of the point in the middle of the intersection. In the lower left quadrant, the tile will be TR. In the upper right quadrant, the tile will be BL. The top-right and bottom-left kings will attack each other, which is not allowed. So

  • You cannot have both a transition from T to B and a transition from L to R.

Now consider a pair of columns where B becomes T, and a pair of rows where R becomes L, and look at everything from the point of view of the point in the middle of the intersection. In the upper left quadrant, the tile will be BR. In the lower right quadrant, the tile will be TL. The bottom-right and top-left kings will attack each other, which is not allowed. So

  • You cannot have both a transition from B to T and a transition from R to L.

Since we need a mixture of T and B columns, and a mixture of L and R rows, transitions are needed. Thus there are only two possible ways of having transitions without falling foul of either of the prohibitions.

  1. T to B and R to L.

  2. B to T and L to R.

In your left-hand picture, the tiles in your first row are T, B and the tiles in your first column are R, L. In your right-hand picture, the tiles in your first row are B, B, T, T and the tiles in your first column are L, L, R, R.

So in general, for any $4n\times{4n}$ board, there is the following solution:

  1. Consider the board as a $2n\times{2n}$ grid of $2\times{2}$ tiles.

  2. Label all the tiles in the first $n$ columns with a T, and the rest with a B.

  3. Label all the tiles in the first $n$ rows with an R, and the rest with an L.

  4. In each tile, inspect the label, and put a king into the {T=top / B=bottom} {L=left / R=right} cell.

The "other" solution (B-to-T and L-to-R) is a mirror image of this one.

So the answer to your question

In how many ways can this be done?

is

One.

$\endgroup$
  • $\begingroup$ Thanks a lot man, really nice solution. $\endgroup$ – TAJD Jul 2 '16 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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