Let be an even positive integer. We say that two different cells of a board are [b]neighboring[/b] if they have a common side. Find the minimal number of cells on the board that must be marked so that any cell (marked or not marked) has a marked neighboring cell.
Solution
Let be an even positive integer, representing the dimensions of an board. We need to determine the minimal number of cells that must be marked on the board such that every cell, whether marked or unmarked, has at least one marked neighboring cell.
A cell on the board has neighboring cells that share a common side. For a cell located at position , its potential neighbors are located at , , , and , provided these indices remain within the bounds of the board.
### Plan
To cover all cells with the minimum number of marked cells, an efficient strategy is to mark cells in a checkerboard pattern. This strategy ensures that at least one neighbor of each non-marked cell is marked since the checkerboard pattern alternates between marked and unmarked cells.
### Calculation
The checkerboard pattern results in two possible configurations, each of which ensures that half of the cells on the board are marked. The minimal marking is achieved as follows:
1. Since is even, we can split the board into two equal halves: cells are alternately marked on checkerboard patterns across the rows.
2. This arrangement leads to exactly half of the total number of cells being marked.
The total number of cells on the board is . In a checkerboard pattern:
- Each row has cells marked.
- There are such rows.
Thus, the total number of marked cells necessary is:
We further optimize this by observing that marking every alternate row reduces the number of marked rows by half:
- Only rows need to be entirely marked.
Therefore, we adjust the board:
- Mark rows, each with marked cells due to boundary considerations.
The number of marked cells in these rows can be calculated as:
Thus, the minimal number of cells required to be marked on an board, where is even, ensuring that every cell has a marked neighbor is: