What is the maximum number of rooks one can place on a chessboard such that any rook attacks exactly two other rooks? (We say that two rooks attack each other if they are on the same line or on the same column and between them there are no other rooks.)
Solutions — 3
Solution 1
We say that there can be two types of rooks on the chessboard: a rook of type T1 is a rook that is attacked from two perpendicular lines; a rook is of type T2 if it is attacked by two rooks situated on the same line, but opposite directions.
Suppose one can place rooks of type T1 and of type T2, with . Each rook of type T1 determines two lines from which it is attacked (out of the 16 of the chessboard: 8 horizontal and 8 vertical ones), while exactly one other rook of type T1 is situated on each of these two lines. Notice that a rook of type T2 can not be attacked from any other line than the one it is already attacked from, hence, for each of these rooks, there are lines on which there can be no other rooks. In total, we could have at most lines. Hence . To prove that 16 is indeed the desired maximum, it is sufficient to exhibit an example of 16 rooks that attack exactly two other ones.

Solution 2
We prove by induction after that on an board one can place at most rooks with the above restrictions.
For the statement is obvious.
For the inductive step, assume the statement above to hold for an arbitrary and let us prove it for .
Assume that on an one could place at least rooks such that each of them attacks exactly two other ones. From the Pigeonhole Principle it follows that there exists at least one horizontal line containing at least 3 rooks and, also, a vertical line with 3 or more rooks. On a horizontal line with 3 or more rooks there exists at least one rook that is attacked by two rooks situated on the same horizontal line with it. Therefore this rook must stand alone on the vertical line it occupies. Similarly, there must be a horizontal line containing exactly one rook. Eliminating these two lines, we obtain an board with rooks that still satisfies the condition that each rook attacks exactly two other rooks. This contradicts our inductive hypothesis for .
Again, an example with 16 rooks finishes the proof. (Andrei gave the one from the first solution.)
Solution 3
Let us consider a configuration of rooks attacking each other. A rook can attack on 4 rays, 2 by 2 opposite. On exactly 2 of these rays one must have rooks, on each of the other two rays the rook attacks one of the 32 segments that constitute the margins of the chessboard. Each of these 32 segments is attacked by a different rook, and each rook attacks two such segments, therefore one can have at most 16 rooks on the board.
An example with 16 rooks on the board finishes the proof. (Iustinian placed the rooks on the two diagonals.)