What is the maximum number of marked squares on a 10x10 table s.t. every square has at most one marked neighbour?

41 Views Asked by At

There is a $10 \times 10$ table of $100$ unit squares which squares can be marked or unmarked. We want to mark as many squares as possible s.t. every square (marked or unmarked) has at most one marked neighbour. Two squares are adjacent iff they have a common side or vertex.

What is the maximum number of marked squares under these conditions?

1

There are 1 best solutions below

1
On BEST ANSWER

Here is a solution with $16$ marked squares (in blue).

enter image description here

The lines $x=2$, $x=5$, $x=8$, $y=2$, $y=5$, $y=8$ divide the grid into $16$ boxes in each of which at most one square can be marked, so this is best possible.