Let be a positive integer. Initially, a grid has black cells and the rest white cells. The following two operations are allowed :
(1) If a square has exactly three black cells, the fourth is changed to a black cell;
(2) If there are exactly two black cells in a square, the black cells are changed to white and white to black.
Find the smallest positive integer such that for any configuration of the grid with black cells, all cells can be black after a finite number of operations.
Solution
Let be a positive integer. Initially, a grid has black cells and the rest white cells. The following two operations are allowed:
1. If a square has exactly three black cells, the fourth is changed to a black cell.
2. If there are exactly two black cells in a square, the black cells are changed to white and white to black.
We aim to find the smallest positive integer such that for any configuration of the grid with black cells, all cells can be black after a finite number of operations.
The answer is .
### Proof:
1. **Proof that can fail:**
- Divide the board into squares.
- For squares above the main diagonal of 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 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 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 squares on an 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 , then the total number of black cells is at most .
- 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 black squares.
Final Blow:
- Induct on .
- Show that if , then the number of black squares never increases.
- Use symmetry and inductive hypothesis to handle different cases.
- Conclude that ensures that all cells can be turned black.
Thus, the smallest positive integer such that for any configuration of the grid with black cells, all cells can be black after a finite number of operations is .
The answer is: .