## T-3 C

A tract of land in the shape of an $8 \times 8$ square, whose sides are oriented north-south and east-west, consists of 64 smaller $1 \times 1$ square plots. There can be at most one house on each of the individual plots. A house can only occupy a single $1 \times 1$ square plot.

A house is said to be blocked from sunlight if there are three houses on the plots immediately to its east, west and south.

What is the maximum number of houses that can simultaneously exist, such that none of them is blocked from sunlight?

Remark: By definition, houses on the east, west and south borders are never blocked from sunlight.

Answer. The maximal number of houses is 50 .


Solution. Let us represent the tract as an $8 \times 8$-chessboard, with cells colored black if the corresponding parcel is occupied, and white otherwise. We denote by $(i, j)$ the cell in the $i-$ th row and $j$-th column (with the first row being the northernmost and the first column being the westernmost). We start by showing that an optimal configuration can be obtained by coloring all the cells along the east, south, and west borders.

Assume that there is an optimal configuration in which one of those cells, for example $(i, 1)$, is left white. Since we have an optimal configuration, this cell cannot be colored black. This means that by coloring $(i, 1)$, we would block the cell $(i, 2)$. In other words, we know that the cells $(i, 2),(i, 3)$ and $(i+1,2)$ are all colored black in this optimal configuration. However, we now see that we can color $(i, 1)$ instead of $(i, 2)$, keeping the same number of black cells and coloring $(i, 1)$, without disturbing any of the other cells.

We can apply the same reasoning to any of the cells $(1,1)-(8,1),(8,1)-(8,8)$ and, similarly, to $(8,8)-(1,8)$, thus showing that there is an optimal configuration in which all the cells along the E, S, W borders are colored black.

Those cells being colored, we are left with a $7 \times 6$ area of the board. We can now show that no more than 28 cells in this area can be colored black. In order to obtain 28 , the average number of black cells per row has to be 4 . However, if any row contains six black cells, the next row down cannot contain any black cells, since such a black cell would block the cell immediately north of it. Similarly, if a row were to contain 5 black cells, the next row down would be able to contain at most 3 black cells (namely in the cell immediately below the single white one and the two next to it). This shows that the average number of black cells per row in our $7 \times 6$ area cannot be greater than 4 .

![](https://cdn.mathpix.com/cropped/2024_06_05_ef0be42837b45243f854g-23.jpg?height=374&width=375&top_left_y=204&top_left_x=652)

(a)

![](https://cdn.mathpix.com/cropped/2024_06_05_ef0be42837b45243f854g-23.jpg?height=369&width=388&top_left_y=204&top_left_x=1025)

(b)

Figure 1: Alternative Solution

This gives us an upper bound on the total number of black cells: the 22 border cells plus 28 cells in the remaining $7 \times 6$ area, i.e., 50 cells in total.

An example to show that 50 can indeed be achieved is the following. We color the columns $1,2,4,5,7,8$ and row 8 black, leaving the other cells white. This coloring clearly satisfies the conditions and contains exactly 50 black cells, completing the proof.
