Find the maximum possible number of kings on a $12\times 12$ chess table so that each king attacks exactly one of the other kings (a king attacks only the squares that have a common point with the square he sits on).
Problem
Source: Romania TST 2 2012, Problem 3
Tags: geometry, floor function, combinatorics proposed, combinatorics
10.05.2012 19:23
OOOPS !! My answer is WRONG ! I didn't read the problem correctly tnx bdejean for your mention
10.05.2012 19:26
alimathematics wrote: The answer is 72. For the example put the kings in the rows $1,3,5,7,9,11$.Each row have $12$ kings. If we divide the chess table to $2 \times 2$ squares and we have more than $72$ kings then we must have at least one square such have at least $3$ kings in $\implies$ contradiction ! I'd like to claim that your scenario is invalid. Each row having 12 kings. The ones on the edges of the rows will only be attacking one king, but the others will be attacking 2: one immediately to the left of them, one immediately to the right.
10.05.2012 20:08
I'd like to prove the answer is $54.$ claim 1: the number will be even proof: each king has common point(s) with one king and in reverse order, so we group them per $2$, so no groups of $1$ king (can't do one) and no groups of more than $2$ or it isn't exactly one. yet to prove: $56$ is imposs.
10.05.2012 22:12
The answer is 56. First, observe that this is obtainable: XX.XX.XX.X.X .........X.X XX.XX.XX.... .........X.X X.X.X.XX.X.X X.X.X....... .......X.X.X X.X.XX.X.X.X X.X......... ....XX.XX.XX X.X......... X.X.XX.XX.XX Now for each pair of kings, either they attack each other diagonally or through adjacent squares. If they attack each other through adjacent squares, add the numbers shown on the left to the surrounding squares. If they attack each other diagonally, add the numbers shown on the right to the surrounding squares. (the 4s are the kings in both cases) 1221..1210 2442..2431 1221..1342 ......0121 It is straightforward to verify that there is no way of placing kings to make the sum of any numbers in a square greater than 4. Furthermore, "squares" just off the edge of the board can have sum at most 2, and "squares" just off the corners of the board can have sum at most 1. (The easiest way to see this is to divide each grid square into four quadrants and imagine that each king takes up a $2 \times 2$ area centered at the square it is placed on. These $2 \times 2$ areas overlap iff the kings attack each other. The numbers above show how many quarters of each square are covered by these $2 \times 2$ areas.) From the above, we can compute that the maximum sum of numbers over all the squares is $676$. Placing kings adjacent to each other gives a sum of 24, and diagonally adjacent ones give a sum of 28. So the maximum number of pairs is $\lfloor \frac{676}{24} \rfloor = 28$. This allows for up to 56 kings. From here, coming up with the construction is not too hard once you realize the above bound is pretty sharp ($24 \cdot 28$ is only 4 below $676$) and so you need to make sure every corner and edge is fully covered.
27.05.2012 12:40
$12 \times 12$ table has $13 \times 13 = 169$ grids, each pair of kings touch at least $6$ grids, and different pairs have not common grids, so the maximum number of pairs is $\left[ {\frac{{169}}{6}} \right] = 28$. Hence the maximum possible number of kings is $2 \times 28=56$.
Attachments:
25.09.2014 23:03
First,lets prove that the answer is $56$.Just see that the $12x12$ table has $13*13=169$ points and that every pair of kings occupies at least 6 points,so we obtain $[169/6]*2=56$.Now,the example:$(1,1),(1,2),(1,4),(2,4),(1,6),(2,6)...(1,12)$ and circle like this round the table.Now,we have a $6*6$ in the middle left and analogisuly to this with that and we are finished.
15.07.2017 03:35
Answer is $\boxed{56}$. First, we will provide a construction for $56$ kings. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \bullet&\bullet& &\bullet&\bullet& &\bullet&\bullet& &\bullet& &\bullet \\\hline & & & & & & & & &\bullet& &\bullet \\\hline \bullet&\bullet& &\bullet&\bullet& &\bullet&\bullet& & & & \\\hline & & & & & & & & &\bullet& &\bullet \\\hline \bullet& &\bullet& &\bullet& &\bullet&\bullet& &\bullet& &\bullet \\\hline \bullet& &\bullet& &\bullet& & & & & & & \\\hline & & & & & & &\bullet& &\bullet& &\bullet \\\hline \bullet& &\bullet& &\bullet&\bullet& &\bullet& &\bullet& &\bullet \\\hline \bullet& &\bullet& & & & & & & & & \\\hline & & & &\bullet&\bullet& &\bullet&\bullet& &\bullet&\bullet \\\hline \bullet& &\bullet& & & & & & & & & \\\hline \bullet& &\bullet& &\bullet&\bullet& &\bullet&\bullet& &\bullet&\bullet \\\hline \end{array} $$ Now we will show that $56$ kings is optimal. Let $S$ denote the entire $12 \times 12$ board. Note that the kings can be split into pairs of attacking kings. For each pair, we will designate its territory based on the relative positions of the two kings: $$ \begin{array}{ccc} \times & \color{red}{\times} & \color{red}{\times} \\ \times & \bullet & \color{red}{\times} \\ \times & \bullet & \color{red}{\times} \\ \times & \times & \times \\ \end{array} $$ $$ \begin{array}{cccc} \times & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} \\ \times & \bullet & \bullet & \color{red}{\times} \\ \times & \times & \times & \times \\ \end{array} $$ $$ \begin{array}{cccc} \times & \color{red}{\times} & \color{red}{\times} & \\ \times & \bullet & \color{red}{\times} & \color{red}{\times} \\ \times & \times & \bullet & \times \\ & \times & \times & \times \\ \end{array} $$ $$ \begin{array}{cccc} & \times & \color{red}{\times} & \color{red}{\times} \\ \times & \color{red}{\times} & \bullet & \color{red}{\times} \\ \times & \bullet & \times & \times \\ \times & \times & \times & \\ \end{array} $$ It's easy to check that no two pairs can have intersecting territory. Furthermore, all the territory is contained in a $13 \times 13$ square that shares its lower left corner with $S$. This means that the kings and the territory combined cannot exceed $13^2 = 169$ squares. Since each pair consists of $2$ kings and $4$ units of territory, we have at most $\frac{169}{6} = 28 + \frac{1}{6}$ pairs. This means that we can have at most $56$ kings, as desired. $\blacksquare$