When the unit squares at the four corners are removed from a three by three squares, the resulting shape is called a cross. What is the maximum number of non-overlapping crosses placed within the boundary of a $ 10\times 11$ chessboard? (Each cross covers exactly five unit squares on the board.)
Problem
Source: CGMO 2004 P8
Tags: pigeonhole principle, geometry, rectangle, combinatorics unsolved, combinatorics
28.12.2008 20:11
It is at least $ 15$. We can put the centers of the crosses in: $ (2, 4)$ $ (2, 9)$ $ (3, 2)$ $ (3, 7)$ $ (4, 5)$ $ (5, 3)$ $ (5, 8)$ $ (6, 6)$ $ (7, 4)$ $ (7, 9)$ $ (8, 2)$ $ (8, 7)$ $ (9, 5)$ $ (10, 3)$ $ (10, 8)$ Who gives more?
28.12.2008 22:03
Yes, it is 15. I'll be concise... Any problem, tell me. The centers of the crosses are clearly in the "main" $ 8 \times 9$ sub-board, which can be partitioned in three $ 8 \times 3$ sub-board. Now, supposes there are $ 16$ crosses. At least $ 6$ of their centers are in a same $ 8 \times 3$ sub-board (pigeonhole principle). To better understanding, we are going to say the squares in this $ 8 \times 3$ board are ordered pairs $ (a, b)$, with $ 1 \le a \le 3$ and $ 1 \le b \le 8$. It is easy to see the rectangle $ R = {(a, b)|b = 4 \text{ or } b = 5\}}$ must contain at most two centers, as the $ 3 \times 3$ squares above and under it, which gives at most $ 2 + 2 + 2 = 6$ centers. To attain the equality, we must have two centers in each of these figures ($ R$ and the squares). Now, supposing there are centers in $ R$ are $ (1, 4)$ and $ (3, 5)$ (the other case is symmetric), it is easy to check that the centers are $ (1, 1), (3, 2), (1, 4), (3, 5), (1,7)$ and $ (3, 8)$. This $ 8 \times 3$ rectangle may have one or two ajacent $ 8 \times 3$ rectangles. In the first case, its neighbor rectangle can have at most $ 4$ crosses centers (this is just case analisis). Until now, we have $ 10$ crosses. To get $ 16$, we must have $ 6$ crosess centers in the last rectangle. But, in this case, any configuration of the crosses is going to limit the number of centers in the second rectangle to at most $ 3$. Case the $ 8 \times 3$ rectangle is the rectangle in the "middle" of the $ 8 \times 9$ rectangle, as I said above, we are going to have at most $ 4$ centers in each of its neighbors, which limits us to at most $ 6 + 4 + 4 = 14$ crosses.
01.06.2018 12:15
Another solution: For the sake of contradiction suppose we can place on the table $16$ crosses. It is obvious that we can’t put more than $3$ crosses to touch one of the first column, last column, first row and the last row. Hence we must have at most $110 -10 +3 -10 +3 -11 +4 -11+4 = 82$ occupied squares. But $16$ crosses need $80$ squares. Now focus on the following squares: $(1,3)$, $(2,3)$, $(2,2)$, $(3,2)$, $(3,1)$, $(2,0)$, $(0,2)$. It is not hard to see that at least three of these squares will be unocuppied by squares, while at most 2 were not in the 82. Consider the same region for each of the $4$ corners of the table. Hence, at most $82-4 =78\leq 80$ squares can be covered. Hence the assumption made is false!
04.12.2019 20:08
MK4J wrote: Another solution: Now focus on the following squares: $(1,3)$, $(2,3)$, $(2,2)$, $(3,2)$, $(3,1)$, $(2,0)$, $(0,2)$. It is not hard to see that at least three of these squares will be unocuppied by squares, while at most 2 were not in the 82. What happens if you put the crosses with center $(1,3)$ , $(2,1)$ , $(4,2)$, $(5,3)$? There is just one square unoccupied, and that could not be in the 82
20.09.2020 09:59
April wrote: When the unit squares at the four corners are removed from a three by three squares, the resulting shape is called a cross. What is the maximum number of non-overlapping crosses placed within the boundary of a $ 10\times 11$ chessboard? (Each cross covers exactly five unit squares on the board.) Keep the board horizontally so that there are $10$ rows and $11$ columns. Color the columns black and white alternatingly ( first column should be black). Now there are $6$ black columns and $5$ white columns. A centre refers to the central cell of a cross. Its clear that a centre either is either white or black . Let the number of white centres be $a$ and the number of black centres be $b$. Note that the first and last columns can't have any centre at all and the maximum number of cross in a particular column is $3$ since $\lfloor \frac{10}{3} \rfloor = 3$ . Now note that $a \leq 15$ whereas $b \leq 12$. Therefore can have atleast $15$ crosses. However note that in configuration for $15$ crosses, there cannot be any more crosses ($a$ is already max and black column cells are alternately covered with a cross-cell). Also note that whenever there is a black-cross Since it covers $3$ black squares and $2$ white squares, so it takes up the space for exactly $2$ two white-crosses (the cells in white column take up center space and the cells in the black column take up other cell space). Even if the black-cross is centered in the second row (i.e its topmost cell touches the border), the number of white cells left in the adjacent columns is $8$ (the cross clearly can't be centred in the first or second row of these columns anymore), implying that atmost $2$ white-crosses can be placed in each of these columns. This observation however implies that whenever there is a black-cross, we can always remove it and instead add $2$ more white-crosses ( with slight re-arrangements ofcourse). But since the maximum number of white-crosses can be $15$, we conclude that our final answer is 15 and we are done . For those wondering about the actual construction for 15, simply take the top $3$ consecutive white-crosses in the odd white columns and the bottom three consecutive white-crosses in the even white columns. It is clear that this works . Sincerely, Aayam