Maths Olympiad Prep

Library / /127 of 220

Combinatorics Difficulty 6.1 National Olympiad Prove it Ukraine

In how many ways can a chessboard n×nn \times n, n3n \ge 3, from which two diagonally opposite corner cells 1×11 \times 1 were cut out, accommodate nn rooks, neither of which attacks one other? A rook is a chess piece that attacks all the cells adjacent horizontally or vertically to the cell it is located in.

Solution

Without limitation of generality, suppose that the left lower cell AA and the right upper cell ZZ were cut out. First, let us see in how many ways rooks can be placed on a n×nn \times n chessboard. There are n!n! ways, since for a rook, there are nn options in the first column, n1n-1 option in the second column, and so on. Consider the arrangements of rooks, in which one of them is located in cell AA. There are (n1)!(n-1)! such arrangements, and analogously, (n1)!(n-1)! ways, for when a rook occupies cell ZZ. In the expression n!2(n1)!n!-2(n-1)! positions where rooks occupy cells AA and ZZ are rejected twice. There are (n2)!(n-2)! such arrangements. Thus, the correct expression would be:
n!2(n1)!+(n2)!=(n2)!(n(n1)2(n1)+1)=(n2)!(n23n+3). n!-2(n-1)!+(n-2)!=(n-2)!(n(n-1)-2(n-1)+1)=(n-2)!(n^2-3n+3).

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.