Rooks
Source: Tuymaada 2005, Day 2, Problem 5
July 30, 2005
combinatorics unsolvedcombinatorics
Problem Statement
You have columns of squares in the middle, in the right and in the left you have columns of squares (centered on the ones of squares), then columns of squares. (This is the way it was explained in the original thread, http://www.artofproblemsolving.com/Forum/viewtopic.php?t=44430 ; anyway, i think you can understand how it looks)Several rooks stand on the table and beat all the squares ( a rook beats the square it stands in, too). Prove that one can remove several rooks such that not more than rooks are left and still beat all the table.Proposed by D. Rostovsky, based on folklore