RU-ALLRUSSIAN 2009 Problem 116

There are $k$ rooks on a $10 \times 10$ chessboard. We mark all the squares that at least one rook can capture (we consider the square where the rook stands as captured by the rook). What is the maximum value of $k$ so that the following holds for some arrangement of $k$ rooks: after removing any rook from the chessboard, there is at least one marked square not captured by any of the remaining rooks.