A board is divided into 144 unit squares by drawing lines parallel to the sides. Two rooks placed on two unit squares are said to be non-attacking if they are not in the same column or same row. Find the least number such that if rooks are placed on the board, one rook per square, we can always find 7 rooks such that no two are attacking each other.
Hint 1: Think about the worst-case scenario: how many rooks can we place such that we can select at most 6 pairwise non-attacking ones?
Hint 2: If we completely fill 6 rows of the board with rooks, we place rooks. Can we find 7 non-attacking rooks here?
Hint 3: Adding one more rook (making 73) forces us to occupy a new row and column, guaranteeing a matching of size 7.
We have a board. Rooks are non-attacking if no two are in the same row or column.
We want the minimum number such that placing rooks guarantees a set of 7 pairwise non-attacking rooks.
By Dilworth's Theorem or the bipartite matching version of the Pigeonhole Principle, the maximum number of rooks we can place without having 7 pairwise non-attacking rooks is achieved by completely filling rows (or columns) with rooks.
If we fill 6 rows, we place rooks. In this configuration, we can choose at most 6 pairwise non-attacking rooks (since we can choose at most one rook from each of the 6 filled rows).
If we place rooks, by the Pigeonhole Principle and Hall's Marriage Theorem, we are guaranteed to find at least 7 pairwise non-attacking rooks.
Thus, the minimum number is .
Ready to track your progress and master these topics?
Create a free account