Kings on a chessboard
What is the maximum number of kings you can place on a 12 by 12 chessboard such that each king threatens to attack exactly one other king?
The answer is 56.
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
Great solution!
For finding the construction , for equality to hold we must have a = 2 8 , b = 0 , so the problem becomes "Tile a 1 3 × 1 3 square using 28 2 × 3 tiles with 1 3 × 1 3 − 2 8 × 6 = 1 tile left over".
Note that 1 3 = 5 × 2 + 1 × 3 = 2 × 2 + 4 × 3 are the only way to perfectly tile a side, so that provides very strong motivation for what any side without a empty square looks like. In your construction, this gives us the 1 0 × 9 block that you have in the upper right corner, and then the left column (from top to bottom) and bottom row (from right to left) are uniquely determined, and then it's easy to figure out how the bottom right corner looks like with the 1 tile left over.
In a certain sense, this is the "Structure avoider and finder" approach, with a bit of greedy algorithm thrown in.
Log in to reply
Also, what was the point of making it a 13x13?
Log in to reply
To ensure the kingdoms of any king on the board will stay completely on the board.
Log in to reply
@Sharky Kesa – This goes back to what I was saying about how best to present such solutions where we have a "alternative interpretation" of the problem. It is best to set it up initially, and then explain the implications (IE we now have a 1 3 × 1 3 board), and then work through the rest of the solution.
Otherwise, it is confusing to the reader why we have a 1 3 × 1 3 board in the very first paragraph. IE What was the point of adding a border to make it 1 3 × 1 3 ?
This is brilliant !! Any links to few more problems of this type?
To solve this question, we will first create a bound.
We will try and create an upper bound on the number of kings possible that can be placed on the board.
Note that since each king threatens to attack exactly one other king, the kings must interact in pairs, so each king is in exactly one pair of kings. There are 2 different ways each king in a pair can threaten each other:
The kings either share a side or share a vertex. Now, consider a 2x2 square around each king, and call this their kingdom . To ensure that these kingdoms remain completely on the board, we expand the board by adding half a square on each edge, such that the chessboard is now ( 1 2 + 2 1 + 2 1 ) × ( 1 2 + 2 1 + 2 1 ) = 1 3 × 1 3 . These half-squares won't have any kings on them. Here is a diagram:
If two kings don't threaten each other, their kingdoms do not intersect. Thus the combined kingdom area can be counted as the disjoint union of king pairs. If two kings threaten each other, then their kingdoms must intersect: If two threatening kings are sharing a side, their combined area is 6, and if two threatening kings are sharing a vertex, their combined area is 7. Here are some images showing each king's kingdoms, as well as their combined kingdom area (shaded in blue):
Let there be a kings sharing a side and b kings sharing a vertex, and a total of n kings. Note n = 2 a + 2 b and the total area of the chessboard is 169. Thus, 3 n = 6 a + 6 b ≤ 6 a + 7 b ≤ 1 3 2 = 1 6 9 , so n ≤ 5 6 . The construction for this takes some time to find (at least for me, since I was looking for symmetry), but if you play around enough, you get
Therefore, the answer is 56.