Maths Olympiad Prep

Library / /40 of 65

Combinatorics Difficulty 6.1 National Olympiad Prove it Romania

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 mm rooks of type T1 and nn of type T2, with m+n=xm + n = x. 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 mm rooks, there are mm lines on which there can be no other rooks. In total, we could have at most 2n2+m=n+m\frac{2n}{2} + m = n + m lines. Hence 16m+n=x16 \ge m + n = x. 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.

Figure 1

Solution 2

We prove by induction after n2n \ge 2 that on an n×nn \times n board one can place at most 2n2n rooks with the above restrictions.
For n=2n = 2 the statement is obvious.
For the inductive step, assume the statement above to hold for an arbitrary n2n \ge 2 and let us prove it for n+1n + 1.
Assume that on an (n+1)×(n+1)(n+1) \times (n+1) one could place at least 2n+32n+3 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 n×nn \times n board with 2n+12n + 1 rooks that still satisfies the condition that each rook attacks exactly two other rooks. This contradicts our inductive hypothesis for nn.
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.)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.