Problem

Source: 2025 Turkey EGMO TST P1

Tags: combinatorics



A chessboard with some unit squares marked is called a $\textit{good board}$ if for any pair of rows \((s, t)\), a rook placed on a marked square in row \(s\) can reach a marked square in row \(t\) in several moves by only moving to marked squares above, below, or to the right of its current position. Consider a chessboard with 220 rows and 12 columns, where exactly 9 unit squares in each row are marked. Regardless of how the marked squares are chosen, if it is possible to delete \(k\) columns and rearrange the remaining columns to form a $\textit{good board}$ determine the maximum possible value of \(k\).