rook-connected set of 100 cells - All-Russian MO 2001 Regional (R4) 10.7
Source:
September 26, 2024
combinatoricscombinatorial geometry
Problem Statement
We call a set of cells on a checkered plane rook-connected if from any of its cells one can get to any other by moving along the cells of this set by moving the rook (the rook is allowed to fly through fields that do not belong to our set). Prove that a rook-connected set of cells can be divided into pairs of cells, lying in one row or in one column.