MathDB

10.5

Part of 2000 Saint Petersburg Mathematical Olympiad

Problems(1)

Can the $2000\times2000$ be colored with certain rules

Source: St. Petersburg MO 2000, 10th grade, P5

4/22/2023
Cells of a 2000×20002000\times2000 board are colored according to the following rules:
1)At any moment a cell can be colored, if none of its neighbors are colored
2)At any moment a 1×21\times2 rectangle can be colored, if exactly two of its neighbors are colored.
3)At any moment a 2×22\times2 squared can be colored, if 8 of its neighbors are colored
(Two cells are considered to be neighboring, if they share a common side). Can the entire 2000×20002000\times2000 board be colored?
[I]Proposed by K. Kohas
combinatoricsgridsColoringtableInvariantsgeometryrectangle