Maths Olympiad Prep

Library / /118 of 136

Combinatorics Difficulty 8.4 Shortlist Prove it Hong Kong

2n+12n + 1 distinct points are chosen on a circle and each two of them are connected with a vector going in one of the two possible directions. Let RR be the number of triangles with the vertices at the given points such that the sum of the vectors going along the sides of the triangle is equal to zero, (i.e. starting from any vertex, the vectors will go back to itself). Find the smallest and the biggest possible values of RR.

Solution

The smallest and the largest possible values of RR are 00 and n(n+1)(2n+1)6\frac{n(n+1)(2n+1)}{6} respectively.
Let the points be A1,A2,,A2n+1A_1, A_2, \dots, A_{2n+1}. If we draw the vector AiAj\overrightarrow{A_iA_j} whenever i<ji < j, then for any AiAjAk\triangle A_iA_jA_k with i<j<ki < j < k, we have
AiAj+AiAk+AjAk=2AiAk0. \overrightarrow{A_iA_j} + \overrightarrow{A_iA_k} + \overrightarrow{A_jA_k} = 2\overrightarrow{A_iA_k} \neq \mathbf{0}.

Therefore, it is possible that R=0R = 0.
For the maximum value, we call AiAjAk\triangle A_i A_j A_k special if it does not have sum 00. Note that the vectors of a special triangle must be AiAj\overrightarrow{A_i A_j}, AiAk\overrightarrow{A_i A_k} and AjAk\overrightarrow{A_j A_k} up to symmetry. We say that AiA_i is the initial vertex and AkA_k is the terminal vertex of this triangle.
For each vertex AiA_i, suppose there are bib_i vectors pointing away from AiA_i and cic_i vectors pointing towards AiA_i. Note that bi+ci=2nb_i + c_i = 2n. Then there are (bj2)\binom{b_j}{2} pairs of vectors AiAj\overrightarrow{A_i A_j} and AiAk\overrightarrow{A_i A_k}, and (cj2)\binom{c_j}{2} pairs of vectors AjAi\overrightarrow{A_j A_i} and AkAi\overrightarrow{A_k A_i}. Therefore, there are (bj2)\binom{b_j}{2} special triangles with AiA_i as initial vertex (note that the vector between AjA_j and AkA_k is irrelevant), and (cj2)\binom{c_j}{2} special triangles with AiA_i as terminal vertex. As each special triangle is counted twice, it follows that the number of special triangles is
12j=12n+1[(bj2)+(cj2)]12j=12n+1[(n2)+(n2)]=n(n1)(2n+1)2 \frac{1}{2} \sum_{j=1}^{2n+1} \left[ \binom{b_j}{2} + \binom{c_j}{2} \right] \ge \frac{1}{2} \sum_{j=1}^{2n+1} \left[ \binom{n}{2} + \binom{n}{2} \right] = \frac{n(n-1)(2n+1)}{2}
by Jensen's inequality. Since there are (2n+13)\binom{2n+1}{3} triangles in total, this implies
R(2n+13)n(n1)(2n+1)2=n(n+1)(2n+1)6. R \le \binom{2n+1}{3} - \frac{n(n-1)(2n+1)}{2} = \frac{n(n+1)(2n+1)}{6}.
This maximum value R=n(n+1)(2n+1)6R = \frac{n(n+1)(2n+1)}{6} can be attained. For example, suppose we draw the vector AjAj+m\overrightarrow{A_j A_{j+m}} for 1j2n+11 \le j \le 2n+1 and m=1,2,,nm = 1, 2, \dots, n, where the indices are taken modulo 2n+12n+1. Then bj=cj=nb_j = c_j = n for any jj, and so equality holds.

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.