IMO 2014 Shortlist C3
Let n ě 2 be an integer. Consider an n ˆ n chessboard divided into n2 unit squares. We call a configuration of n rooks o...
Category: Combinatorics
Problem
Let n ě 2 be an integer. Consider an n ˆ n chessboard divided into n2 unit squares. We call a configuration of n rooks on this board happy if every row and every column contains exactly one rook. Find the greatest positive integer k such that for every happy configuration of rooks, we can find a k ˆ k square without a rook on any of its k2 unit squares. (Croatia)