8. Problem: Two cells in a $20 \times 20$ board are adjacent if they have a common edge (a cell is not considered adjacent to itself). What is the maximum number of cells that can be marked in a $20 \times 20$ board such that every cell is adjacent to at most one marked cell?
Solution: In the following diagram, there are 110 cells containing an o symbol. Notice that each cell is adjacent to exactly one $\circ$ (including the cells containing a $\circ$ ). Now partition all 400 cells into 110 pigeon-holes based on which $\circ$ the cell is adjacent to.

Two cells are in the same pigeon-hole if and only iff they are adjacent to the same $\circ$.
For example the four coloured cells are in the same pigeon-hole. By the constraint given in the problem, we cannot mark two cells (or more) in the same pigeon-hole. Since there are 110 pigeon-holes, this means we can mark at most 110 cells. Therefore it is impossible to mark more than 110 cells.

In order to demonstrate that it is possible to mark 110 cells, we provide a construction. One suitable construction is to simply mark each of the cells in the previous diagram containing a $\circ$.