Maths Olympiad Prep

Library / /387 of 462

Combinatorics Difficulty 6.8 National Olympiad Prove it Ireland

Let n3n \ge 3 be an odd positive integer. We are given an n×nn \times n board which is divided into white unit squares by lines drawn parallel to the sides of the board. Let NN denote the number of ways of placing 2 identical red checkers and 2 identical blue checkers on the board such that
(a) in any such placement, no two checkers occupy the same square; and
(b) none of the placements can be obtained from any other by a rotation of the board.
Prove that
N=(n212)4(n212)3 N = \left(\frac{n^2-1}{2}\right)^4 - \left(\frac{n^2-1}{2}\right)^3

Solution

Let Nb=n2N_b = n^2 and k=(Nb1)/2k = (N_b - 1)/2. There are (Nb2)\binom{N_b}{2} ways of placing 2 identical red checkers, and for any such placement there are (Nb22)\binom{N_b-2}{2} ways of next placing the 2 identical blue checkers. Therefore the total number of ways of placing 2 identical red checkers and 2 identical blue checkers on the board is
Nt=(Nb2)(Nb22)=Nb(Nb1)(Nb2)(Nb3)4=Nb(Nb2)k(k1). N_t = \binom{N_b}{2} \binom{N_b-2}{2} = \frac{N_b(N_b-1)(N_b-2)(N_b-3)}{4} \\ = N_b \cdot (N_b-2) \cdot k \cdot (k-1).
Some of these checker placements have 180180^\circ symmetry. The number of such placements, denoted NsN_s, is equal to the number of ways of placing a red checker and a blue checker on the "semi-board" formed by taking any subset of k=(Nb1)/2k = (N_b - 1)/2 squares such that the centre square is omitted, and no square in the subset is the image of another square under central symmetry in the central square (to complete the symmetrical placement, the missing red checker is placed on the image square of the placed red checker, and similarly for the missing blue checker). It follows that the number of 180symmetrical180^\circ-symmetrical checker placements is
Ns=k(k1). N_s = k(k-1).
There are NtNsN_t - N_s placements which do not possess 180180^\circ symmetry; such placements are counted four times, while the NsN_s 180symmetrical180^\circ-symmetrical placements are counted twice. Thus
N=NtNs4+Ns2=Nt+Ns4=k(k1)Nb(Nb2)+14=k(k1)k2=k4k3, \begin{aligned} N &= \frac{N_t - N_s}{4} + \frac{N_s}{2} = \frac{N_t + N_s}{4} \\ &= k(k-1)\frac{N_b(N_b-2)+1}{4} = k(k-1) \cdot k^2 = k^4 - k^3, \end{aligned}
and the result is proved.

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.