Maths Olympiad Prep

Library / /45 of 97

Combinatorics Difficulty 7.9 National olympiad, round 2 Find the answer

Let nn be a positive integer. Initially, a 2n×2n2n \times 2n grid has kk black cells and the rest white cells. The following two operations are allowed :
(1) If a 2×22\times 2 square has exactly three black cells, the fourth is changed to a black cell;
(2) If there are exactly two black cells in a 2×22 \times 2 square, the black cells are changed to white and white to black.
Find the smallest positive integer kk such that for any configuration of the 2n×2n2n \times 2n grid with kk black cells, all cells can be black after a finite number of operations.

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

Solution

Let n n be a positive integer. Initially, a 2n×2n 2n \times 2n grid has k k black cells and the rest white cells. The following two operations are allowed:
1. If a 2×2 2 \times 2 square has exactly three black cells, the fourth is changed to a black cell.
2. If there are exactly two black cells in a 2×2 2 \times 2 square, the black cells are changed to white and white to black.

We aim to find the smallest positive integer k k such that for any configuration of the 2n×2n 2n \times 2n grid with k k black cells, all cells can be black after a finite number of operations.

The answer is n2+n+1 n^2 + n + 1 .

### Proof:
1. **Proof that n2+n n^2 + n can fail:**
- Divide the board into n2 n^2 2×2 2 \times 2 squares.
- For squares above the main diagonal of 2×2 2 \times 2 squares, paint the upper right square black.
- For squares below the main diagonal, paint only the lower left square black.
- This configuration ensures that no 2×2 2 \times 2 square has exactly three black cells, preventing the first operation from being applied. Thus, it is possible that not all cells can be turned black.

2. **Proof that kn2+n+1 k \geq n^2 + n + 1 works:**
- If we can somehow get the number of black cells to increase, we clearly win. The objective is to get two black cells to share an edge.
- We will prove a lemma: If k>(m+1)(n1)4 k > \frac{(m+1)(n-1)}{4} squares on an m×n m \times n grid are painted black, then we can get two squares to be adjacent.

Lemma Proof:
- Perform smoothing operations to rearrange black and white cells.
- Consider a diagonal of black cells and assign coordinates to them.
- Show that by smoothing operations, the assigned squares must be white.
- Calculate the number of black cells that are not on the leftmost row or bottom column.
- If a(m1)(n1)4 a \leq \frac{(m-1)(n-1)}{4} , then the total number of black cells is at most mn+m+n+14 \frac{mn + m + n + 1}{4} .
- Otherwise, show that the number of black squares on the leftmost column and bottom row is limited, leading to a contradiction if there are more than (m+1)(n+1)4 \frac{(m+1)(n+1)}{4} black squares.

Final Blow:
- Induct on m+n m + n .
- Show that if k(m+1)(n+1)4 k \leq \frac{(m+1)(n+1)}{4} , then the number of black squares never increases.
- Use symmetry and inductive hypothesis to handle different cases.
- Conclude that kn2+n+1 k \geq n^2 + n + 1 ensures that all cells can be turned black.

Thus, the smallest positive integer k k such that for any configuration of the 2n×2n 2n \times 2n grid with k k black cells, all cells can be black after a finite number of operations is n2+n+1 n^2 + n + 1 .

The answer is: n2+n+1\boxed{n^2 + n + 1}.

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.