Riddles, brain puzzles and mathematical problems

[BAndrew]

Let x be the number of rooks on the board.

If x = 0, then the claim is true trivially

If x > 0, then we are going to show that the claim is also true.

Let S be the largest possible set of mutually non-attacking rooks.
or S = {R1, R2, ..., Rk} where Ri (1≤i≤k) is a rook on the board.

The rooks selected are mutually non-attacking. The order the rooks are selected is random. Also, R1 ≠ R2 ≠ ... ≠ Rk.

|S| = k and this is the largest number of mutually non-attacking rooks.

We choose the rows/columns where these rooks ∈ S are located. By this choice we are going to show that all the rooks on the board are contained.

Assume to the contrary that there exists a rook (let it be r) on the board that isn't contained with the choice we made. Then this rook is by definition mutually non-attacking with every other rook ∈ S. That implies that S isn't the largest possible set of mutually attacking rooks, because by adding r to S , we get a new set U = {R1, R2, ..., Rk, r} where |U| = k+1 > k.
Contradiction!
Therefore, all the rooks are contained by this choice.
That completes the proof.