Maths Olympiad Prep

Library / /6 of 106

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

Let nn be an even positive integer. We say that two different cells of a n×nn \times n board are [b]neighboring[/b] if they have a common side. Find the minimal number of cells on the n×nn \times n board that must be marked so that any cell (marked or not marked) has a marked neighboring cell.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let n n be an even positive integer, representing the dimensions of an n×n n \times n 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 (i,j) (i, j) , its potential neighbors are located at (i1,j) (i-1, j) , (i+1,j) (i+1, j) , (i,j1) (i, j-1) , and (i,j+1) (i, j+1) , 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 n n is even, we can split the board into two equal halves: cells are alternately marked on checkerboard patterns across the n n 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 n2 n^2 . In a checkerboard pattern:
- Each row has n2 \frac{n}{2} cells marked.
- There are n n such rows.

Thus, the total number of marked cells necessary is:
(n2)×n=n22. \left( \frac{n}{2} \right) \times n = \frac{n^2}{2}.

We further optimize this by observing that marking every alternate row reduces the number of marked rows by half:
- Only n2 \frac{n}{2} rows need to be entirely marked.

Therefore, we adjust the board:
- Mark n2\frac{n}{2} rows, each with n2+1\frac{n}{2} + 1 marked cells due to boundary considerations.

The number of marked cells in these rows can be calculated as:
(n2)×(n2+1)=n24+n2. \left( \frac{n}{2} \right) \times \left( \frac{n}{2} + 1 \right) = \frac{n^2}{4} + \frac{n}{2}.

Thus, the minimal number of cells required to be marked on an n×n n \times n board, where n n is even, ensuring that every cell has a marked neighbor is:
n24+n2. \boxed{\frac{n^2}{4} + \frac{n}{2}}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.