A $8 \times 8$ board is given, with sides directed north-south and east-west. It is divided into $1 \times 1$ cells in the usual manner. In each cell, there is most one house. A house occupies only one cell. A house is in the shade if there is a house in each of the cells in the south, east and west sides of its cell. In particular, no house placed on the south, east or west side of the board is in the shade. Find the maximal number of houses that can be placed on the board such that no house is in the shade.
Problem
Source: MEMO 2016 T3
Tags: combinatorics, combinatorics proposed, board
30.08.2016 20:32
Hm, no solutions on AoPS yet, weird, seeing that every team on the MEMO has solved this one. My - kind of weird - solution follows. It'd be better with pictures. We'll prove that the maximal number of houses is $64-14=50$. It is easy to find an example to verify that it is possible. Now look at each row and especially look at the number of cells without houses. We'll call those cells empty. Call the rows $R_1,R_2,\dots,R_8$ from the top to the bottom and let the number of empty cells in those rows be $r_1,r_2,\dots,r_8$. Now if $r_i=0$, then it's easy to see that $r_{i+1} \geq 6$, you'd have to let the middle $6$ cells of $R_{i+1}$ be empty, else a house in $R_i$ would be in the shade. If $r_i=1$, then it's easy to check that $r_{i+1} \geq 3$. Again, it is easier to visualise this with a picture. Consider two cases. CASE 1: Let $r_7=0$ or $r_7=1$. Observe that for $r_n = 0$ or $r_n = 1$ for $1 \leq n \leq 7$, we can take the pair $r_n+r_{n+1} \geq 4$. For $r_m=2$ or $r_m=3$ for $1 \leq m \leq 8$, we automatically get $r_m \geq 2$. So we can bundle those numbers in pairs and single numbers with each averaging $2$ per term. Basically we look at $r_1$. If it was $0$ or $1$, then we'd pair up $r_1$ and $r_2$, their sum would be at least $4$. Then we'd look at $r_3$. If it were $0$ or $1$, then again, we'd pair up $r_3$ and $r_4$. Else $r_3 \geq 2$ and we'd immediately go to $r_4$, and so on. So \[ r_1+r_2+r_3+\dots+r_8 \geq 16. \]Up to case 2. CASE 2: Let $r_7 \geq 2$. By the same procedure as above, we get \[ r_1+r_2+r_3+\dots+r_7+r_8 \geq 14+r_8 \geq 14. \]And $14$ can be reached. So it is indeed the minimum of empty cells and thus $50$ is indeed the maximal number of houses.
04.09.2016 17:31
Rather count the minimal number of empty cells, i.e. those with no house in it. One can reach $14$ of those when leaving the $3$rd and $6$th columns empty except for the bottom row, it remains to find a way to show that a construction like this is tight. To do this, we split the $8\times 8$ board into two $8\times 4$ boards and apply the following lemma: Claim. In an $n\times 4$ (sub)board (so $n$ rows and $4$ columns), you can have at most $n-1$ empty cells. Proof. This is clear by induction: $n=1$ is trivial, and for $n>1$, either the top row has an empty cell, and we can remove it and apply the inductive hypothesis, or the top row is full, and so the middle two cells of the row beneath it must be empty, in which case we remove the top two rows and apply the hypothesis. $\blacksquare$