Maths Olympiad Prep

Library / /8 of 18

Combinatorics Difficulty 7.9 National olympiad, round 2 Prove it Balkan Mathematical Olympiad

Consider a lattice of side length 11 equilateral triangles forming a regular hexagon of side length nn. Show that the number of ways of simultaneously selecting six vertices of the lattice to form the vertices of a regular hexagon is a perfect square.

Solution

By a lattice hexagon we will mean a regular hexagon whose sides run along edges of the lattice. Given any regular hexagon HH, we construct a lattice hexagon whose edges pass through the vertices of HH, as shown in the figure, which we will call the enveloping lattice hexagon of HH. Given a lattice hexagon GG of side length mm, the number of regular hexagons whose enveloping lattice hexagon is GG is exactly mm.
Figure 1
Yet also there are precisely 3(nm)(nm+1)+13(n-m)(n-m+1)+1 lattice hexagons of side length mm in our lattice: they are those with centres lying at most nmn-m steps from the centre of the lattice. In particular, the total number of regular hexagons equals
N=m=1n(3(nm)(nm+1)+1)m=(3n2+3n)m=1nm3(2m+1)m=1nm2+3m=1nm3. N = \sum_{m=1}^{n} (3(n-m)(n-m+1)+1)m = (3n^2+3n) \sum_{m=1}^{n} m - 3(2m+1) \sum_{m=1}^{n} m^2 + 3 \sum_{m=1}^{n} m^3.
Since m=1nm=n(n+1)2\sum_{m=1}^{n} m = \frac{n(n+1)}{2}, m=1nm2=n(n+1)(2n+1)6\sum_{m=1}^{n} m^2 = \frac{n(n+1)(2n+1)}{6} and m=1nm3=(n(n+1)2)2\sum_{m=1}^{n} m^3 = \left(\frac{n(n+1)}{2}\right)^2 it is easily checked that N=(n(n+1)2)2N = \left(\frac{n(n+1)}{2}\right)^2.

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 and solution reproduced as published; topic and difficulty added by this site.