MathDB

M2748

Part of Kvant 2023

Problems(1)

Blue and red cells on a board

Source: Kvant Magazine No. 5 2023 M2748

1/9/2024
In a 44×4444\times 44 board, some of the cells are blue, and the rest are red. No blue cells borders another blue cell on the side. The red cells, on the other hand, form a connected component (one may get from any red cell to any other red cell only by traversing edge-adjacent red cells). Prove that less than one third of the cells on the board are blue.
Proposed by B. Frenkin
boardcombinatorics