Maths Olympiad Prep

Library / /297 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

On a chessboard, a queen attacks every square it can reach by moving from its current square along a row, column, or diagonal without passing through a different square that is occupied by a chess piece. Find the number of ways in which three indistinguishable queens can be placed on an 8×88 \times 8 chess board so that each queen attacks both others.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The configuration of three cells must come in a 45-45-90 triangle. There are two cases, both shown above: the triangle has legs parallel to the axes, or it has its hypotenuse parallel to an axis. The first case can be solved by noticing that each selection of four cells in the shape of a square corresponds to four such possibilities. There are 727^{2} possible squares of size 2×2,622 \times 2,6^{2} possible squares of size 3×33 \times 3, and so on. The total for this first case is thus 4(72+62++12)=5604\left(7^{2}+6^{2}+\cdots+1^{2}\right)=560. The second case can also be done by casework: each triangle in this case can be completed into an n+1n+1 by 2n+12 n+1 rectangle, of which there are 76+64+527 \cdot 6+6 \cdot 4+5 \cdot 2 (for n=1,2,3n=1,2,3 respectively). Multiply this by 4 to get all orientations of the triangle. The final answer is 560+4(76+64+52)=864560+4(7 \cdot 6+6 \cdot 4+5 \cdot 2)=864.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.