Kings' Standoff

Probability Level 5

Determine the maximum number of kings that can be placed on a 12 × 12 12\times12 chessboard so that each king threatens exactly one other king.

Note: Each cell contains at most 1 king. Two kings threaten each other if they inhabit adjacent or diagonally adjacent cells.


The answer is 56.

View wiki
Zk Lin by ZK LIn , 24, Malaysia

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.

3 solutions

I maximized the value by separating the grid into paths and maximizing the no. of kings in each path. Firstly, the Kings will come in pairs.

Let us name grid as in chess board: A-L (Columns) and 1-12 (Rows)

Now, let us take the 2-square wide path between the 12X12 grid and the inner 8X8.

Let us start with columns A and B:

  1. We have to put king in pairs, so we can put kings in (A1, B1)

  2. next leaving a row (A3, B3) and continuing upto (A9, B9)

  3. Now, we have two options: (A11, B11) or (A11, A12)

If, we put (A11, B11), then the Column C is completely inaccessible. That will definitely not maximize our solution

So, we put Kings in (A11, A12).

Continuing with the 11th and the 12th row, we put kings at:

  1. (C11, C12)

  2. (E11, E12)

  3. (G11, G12)

  4. (i11, i12)

Again, instead of putting at (K11, K12), we put kings at (K12, L12)

We continue this throughout the path between the 12X12 and the 8X8 grid

Now, we have 2 rows and 2 columns in the path. If we consider any row/column, we find that there are ( 12 / 2 = ) (12/2 =) 6 small grids of size 2X2. Each of these grids have 2 Kings.

So, in any row/column in the path there are 6 × 2 = 12 6 \times 2 = 12 Kings. But, there are 4 of these small grids to any adjacent row-column.

So, a total of 12 × 4 − 4 × 2 = 40 12 \times 4 - 4 \times 2 = 40 Kings in this path.

Now, a simple observation can show us that dude to the arrangement, the 1-square wide path between 8X8 grid and 6X6 grid.

In a similar way we will maximize the no. of Kings in the 2-square wide path between 6X6 grid and the 2X2 grid.

With a similar logic, this will have ( 6 / 2 = ) (6/2 =) 3 small grids of size 2X2 per row/column. so 6 Kings per row/column.

And the number of kings will be: 6 × 4 − 4 × 2 = 16 6 \times 4 - 4 \times 2 = 16 Kings in this path.

Obviously the inner most 2X2 grid will not have any Kings.

Total Kings = 40 + 16 = 56 \boxed{56}

4 Helpful 0 Interesting 0 Brilliant 0 Confused

I had a somewhat different approach. I like your arrangement, but I'm just not sure how, with your method, you would know that 56 is maximal.

Peter Byers - 7 years, 3 months ago

Log in to reply

I actually tried another approach in which this pattern emerged.

I first tried this on an 8X8 chessboard.

First thing: To maximize the no. of kings, we have to initially place the Kings at the four corners.

Now, we are placing 2 Kings together. So, if we have to maximize the Kings, if we place the first two kings at say ( A 1 , B 1 ) (A1, B1) , the next 2 ( at the bottom right corner ) should be ideally placed as ( H 1 , H 2 ) (H1, H2) ... To maximize the gaps

The next two ( at the top right corner ) placed as ( G 8 , H 8 ) (G8, H8)

And, the next two ( at the top left corner ) placed as ( A 8 , A 7 ) (A8, A7)

Now, I stroke-off the unreachable cells, viz. ( A 2 , B 2 , C 2 , C 1 ) , ( G 1 , G 2 , G 3 , H 3 ) , ( F 8 , F 7 , G 7 , H 7 ) , ( B 8 , B 7 , B 6 , A 6 ) (A2,B2,C2,C1), (G1,G2,G3,H3), (F8,F7,G7,H7), (B8,B7,B6,A6)

While Placing the next two Kings, what I noticed was:

Firstly, C1 & C2 are both inaccessible. So, I can place two Kings just beside these two squares, viz. D1 & D2

Also, A2 & B2 are also inaccessible. So, we can place two Kings just beside these two squares, viz. A3 & B3

The reason I was placing Kings beside already inaccessible squares is pretty obvious in itself: To Minimize the number the of Inaccessible squares, and thus Maximizing the no. of Kings

Only, after completing the arrangement in the 8X8 grid, I observed this pattern.

And, applied the same in our problem. Hope that clarifies how I was certain how this arrangement would definitely maximize the no. of Kings.

Soumya Chakraborty - 7 years, 3 months ago

Log in to reply

Thanks, Soumya.

For myself, I start with a 13 by 13 board. First cover all of it except one square with 2 by 3 rectangles. (For example, one way to do this is to first cover all but the center square with four 6 by 7 rectangles. Then cut each 6 by 7 into a 6 by 3 and two 6 by 2 rectangles, and so on.)

Now place two kings in each 2 by 3 rectangle, such that they are not in the bottom-most row or the right-most column (i.e. either like this:

XX0

000

or like this:

XO

XO

OO)

Then none of the 56 kings are in the bottom-most row or the right-most column of the 13 by 13 board, which is to say they are on the required 12 by 12 board, and each threatens exactly one other king.

With this approach, I found it easy to also show that 56 is maximal.

Peter Byers - 7 years, 3 months ago
Adhish Agarwal
Feb 21, 2014

1 0 1 0 1 1 0 1 0 1 0 1

1 0 1 0 0 0 0 1 0 1 0 1

0 0 0 0 1 1 0 0 0 0 0 0

1 1 0 0 0 0 0 1 1 0 1 1

0 0 0 1 0 1 0 0 0 0 0 0

1 1 0 1 0 1 0 1 1 0 1 1

0 0 0 0 0 0 0 0 0 0 0 0

1 0 1 0 1 1 0 1 0 1 0 1

1 0 1 0 0 0 0 1 0 1 0 1

0 0 0 0 1 1 0 0 0 0 0 0

1 0 1 0 0 0 0 1 0 1 0 1

1 0 1 0 1 1 0 1 0 1 0 1

4 Helpful 2 Interesting 2 Brilliant 1 Confused
Rama Devi
May 21, 2015

I think 56 is the answer, I've tried to come up with some way to measure the whole arrangement, but I could only do that for kings on the boundary (in corners and edges)--see note at the end. I've noticed that every empty square in the solutions below is next to at least 2 kings, which was not the case when there were only 54.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...