2014 IMO problem

Let n >= 2 be an integer. Consider an n x n chessboard consisting of n ^ 2unit squares. A configuration of n rooks on this board is ‘peaceful’ if every row and every column contains exactly one rook. Find the greatest positive integer k such that, for each peaceful configuration of n rooks, there is a k x k square which does not contain a rook on any of its k ^ 2 squares.

Let us suppose that k = [sq.rt(n)] – 1 where [n] is the ceiling function of n.

Each n x n chessboard with a peaceful configuration of n rooks contains a valid k x k square. How do we prove this ? Take a rook and place it at the top most row. This column can be part of k consecutive columns, only one of which contains rook R. The consecutive columns can be chose including those on the left of R or to the right of R or both. There are n-k+1 of such consecutive columns and therefore as many k x k squares.

Now, n-k+1 = n- [sq.rt(n)] +2

=  n-sq.rt(n)+2

> n – sq.rt(n) + 1

= sq.rt(n)(sq.rt(n) -  1)  + 1

                                       > (sq.rt(n)-1)(sq.rt(n)-2)+1

                                   = k(k-1) + 1

From the above expression, from these many in the k x k squares in C, there exists a k x k square not covered by any rook. We say this because we can distribute those many squares above such that we leave the k x k square unoccupied. And so our supposition is a valid choice.

Now we have to mutually exclude this region and show that its still possible to have a chess board as required. Without this (k+1) times (k+1) square, we can still arrange the chess board if we proceed this way. First place a rook at the upper left corner of the board. Next place a rook at one square to the right and k+1 spaces down of the second rook. Repeat until the position is outside the bounds of the chessboard in which case wrap around to the top and continue placing the other rooks. Indeed such a board exists and the arrangement of the rooks is clearly peaceful

Because (k+1)^2 > n, it has the property that any (k+1)x(k+1) square in the board will be occupied by at least one rook. This complete the proof.

 [Lithuania 2010]
Problem: In an m × n rectangular chessboard there is a stone in the lower leftmost square. A and B move the stone alternately, starting with A. In each step one can move the stone upward or rightward any number of squares. The player who moves it into the upper
rightmost square wins. Find all (m, n) such that A has a winning strategy.
Solution: Note that in this problem, the moves possible are either one up or to the right. To move diagonally, you need to exchange turns.
Therefore the winning strategy would be to occupy the diagonals ourselves. Moreover, the diagonal is  only for the square portion of the chessboard of size say m x m not the rectangular portion of the m x n. In the rectangular portion, the moves will be linear since we would have already reached the top row and the squares will be equally and alternatively occupied.