Maths Olympiad Prep

Library / /35 of 49

, 2022

Combinatorics Difficulty 6.6 National Olympiad Prove it Bulgaria

Equilateral triangle of area n2n^2 is partitioned into n2n^2 small triangles with unit area with lines parallel to its sides. The vertices of all small triangles are called knots. Find the sum of the areas of all equilateral triangles with vertices knots as a polynomial of nn and write this polynomial as a product of irreducible polynomials.

Solution

Answer: n(n+1)(n+2)(n+3)(n2+3n+6)240\frac{n(n+1)(n+2)(n+3)(n^2+3n+6)}{240}.

Any equilateral triangle TT under consideration can be embedded into an unique equilateral triangle MM, such that the vertices of TT lie on the sides of MM and those sides are parallel to the sides of the bigger triangle. If MM has kk times bigger side than the side of a unit triangle (k=1,2,,nk = 1, 2, \dots, n) then there are 1+2++(n+1k)=(n+2k2)1 + 2 + \dots + (n+1-k) = \binom{n+2-k}{2} choices of MM. We find the sum of the areas of all TT by enumerating the knots of one of the sides of MM with 0,1,,k0, 1, \dots, k and realizing that there is exactly one equilateral triangle with vertex at ii-th knot for each i=1,2,,ki = 1, 2, \dots, k and the area of this triangle is k23i(ki)k^2 - 3i(k-i). Thus the sum of the areas of all such TT equals
i=1k(k23i(ki))=k33(k+13)=k3+k2. \sum_{i=1}^{k} (k^2 - 3i(k - i)) = k^3 - 3\binom{k+1}{3} = \frac{k^3 + k}{2}.
We used the well known equality i=1ki(ki)=(k+13)\sum_{i=1}^{k} i(k - i) = \binom{k+1}{3}. Therefore the desired sum equals:
k=1nk3+k2(n+2k2)=12k=1nk3(n+2k2)+12k=1nk(n+2k2). \sum_{k=1}^{n} \frac{k^3 + k}{2} \binom{n+2-k}{2} = \frac{1}{2} \sum_{k=1}^{n} k^3 \binom{n+2-k}{2} + \frac{1}{2} \sum_{k=1}^{n} k \binom{n+2-k}{2}.
To find the second sum count the number of words with 4 letters "a" and n1n-1 letters "b" such that the second letter "a" appears on (k+1)(k+1)-th place. There are kk choices for the first "a" and n+3(k+1)=n+2kn+3-(k+1) = n+2-k choices for the last two letters "a". Therefore k=1nk(n+2k2)=(n+34)\sum_{k=1}^{n} k \binom{n+2-k}{2} = \binom{n+3}{4}.

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.