Kings all over the game

2500 chess kings have to be placed on a 100 × 100 100 \times 100 chessboard so that

(i) no king can capture any other one (i.e., no 2 kings are placed in two squares sharing a common vertex);

(ii) each row and each column consists exactly 25 kings.

Find the number of such arrangements. (Two arrangements differing by rotation or symmetry are supposed to be different.)


Image Credit: Flickr Darwyn


The answer is 2.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Piyush Palawat
Dec 29, 2015

There are 2 such arrangements. Suppose that we have an arrangement satisfying the problem conditions. Divide the board into 2 x 2 pieces; we call these pieces blocks. Each block can contain not more than one king (otherwise the 2 kings would attack each other); hence, by the pigeonhole principle each block must contain exactly one king. Now assign to each block a letter T or B if a king is placed in its top or bottom half, respectively. Similarly, assign to each block a letter L or R if a king stands in its left or right half. So we define T-blocks, B-blocks, L-blocks and R-blocks. We also combine the letters; we call a block a TL-block if it is simultaneously T-block and L-block. Similarly we define TR-blocks, BL-blocks, BR-blocks. The arrangement of blocks determines uniquely the arrangement of kings; so in the rest of the solution we consider the 50 x 50 system of blocks (see Fig. 1). We identify the blocks by their coordinate pairs; the pair (i, j), where 1 ≤ i, j ≤ 50, refers to the jth block in the ith row (or the ith block in the jth column). The upper-left block is (1, 1). The system of blocks has the following properties : (i) If (i, j) is a B-block the (i+1, j) is a B-block: otherwise the kings in these 2 blocks can take each other.
Similarly: if (i, j) is a T-block then (i-1, j) is a T-block; if (i,j) is a L-block the (i, j-1) is a L-block; if (i, j) is a R-
block then (i, j+1) is a R-block. (ii)Each column contains exactly 25 L-blocks and 25 R-blocks, and each row contains exactly 25 T-blocks and
25 R-blocks. In particular, the total number of L-blocks (or R-blocks, or T-blocks, or B-blocks) is equal to 25 . 50=1250. Consider any B-blocks of the form (i, j). By (i), all blocks in the jth column are B-blocks; so we call such a column B-column. By (ii), we have 25 B-blocks in the first row, so we obtain 25 B-columns. These 25 B-columns contains 1250 B-blocks, hence all blocks in the remaining columns arwe T-blocks, and we obtain 25 T-columns. Similarly, there are exactly 25 L-rows and exactly 25 R-rows. Now consider an arbitrary pair of a T-column and a neighbouring B-column (columns with numbers j and j+1). Case 1: Suppose that the jth column is a T-column, and the (j+1)th column is a B-column. Consider some index i such that the ith row is an L-row; then (i, j+1) is a BL-block. Therefore, (i+1, j) cannot be a TR-block, hence (i+1, J) is a TL-block, thus the (i+1)th row is a L-row. Now, choosing the ith row to be the topmost L-row, we successively obtain that all rows from the ith row to the 50th row are L-rows. Since we have exactly 25 L-rows, it follows that the rows from the 1st to the 25th are R-rows, and the rows from the 26th to the 50th are L-rows. Now consider the neighbouring R-row and L-row (that are the rows with numbers 25 and 26). Replacing in the previous reasoning rows by columns and vice versa, the columns from the 1st to the 25th are T-columns, and the columns from the 26th to the 50th are B-columns. So we have a unique arrangement of blocks that leads to the arrangement of kings satisfying the condition of the problem. Case 2: Suppose that the jth column is a B-column, and the (j+1)th column is a T-column. Repeating the arguments from Case 1, we obtain that the rows from the 1st to the 25th are B-columns (and all columns are T-columns), so we find exactly one more arrangement of kings.

Supreme answer...What an idea.?

Sachin Anand - 5 years, 5 months ago

Log in to reply

Did you understand the solution , i mean was it proper??

Piyush Palawat - 5 years, 5 months ago

Log in to reply

Nearly understood.....I think the solution is alright.

Sachin Anand - 5 years, 5 months ago

Did you even solve it yourself ? Question and solution both copied from some olympiad book.
Given question : IMO 2010, C3 Shortlist

A Former Brilliant Member - 5 years, 5 months ago

Log in to reply

Nice one....

Piyush Palawat - 5 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...