Problem

Source: New Zealand MO 2021 Round 1 p8

Tags: combinatorics, board



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?