0
$\begingroup$

A few days ago, China held the Mathematics Olympiad. In this competition, all the students did not do the last question. But what I'm more interested in right now is, what's the background to this question? I searched for a lot of relevant articles and didn't find that if we replaced 2018 with a normal positive integer N, what would the result be? I wonder if anyone has studied this problem?

The point $P_1, P_2,\cdots ,P_{2018} $ is placed inside or on the boundary of a given regular pentagon. Find all placement methods are made so that $$S=\sum_{1\leq i<j\leq 2018}|P_iP_j| ^2$$takes the maximum value

Following is solution:

Lemma:

Given any $n$ points $A_1,...,A_n$, let $F(X)$ denote $\sum_{i=1}^n |A_iX_i|^2$. If $BC$ is a segment, then for any point other than $B,C$ on $\overline{BC}$, we have $F(D)< \max\{F(B),F(C)\}$.

Proof of the Lemma Set $B(-1,0),C(1,0)<D(x,0),A_i(x_i,y_i)$, then $F(x) = \sum_{i=1}^n [(x-x_i)^2+y_i^2]$ is a quadratic with positive leading coefficient in $x$, from the convexity of the quadratic the lemma follows.

Back to the main problem.m Suppose $R_1,...,R_{2018}$ allows $S$ to attain maximum. First we prove the claim that $R_i (1\le i \le 2018)$ are all at the vertices of the pentagon. If not, say $R_1$ is not one of the vertices, we can always find $\overline{MN}$ with $MN$ not outside of the pentagon, and $R_1\in \overline{MN}.$ By the Lemma, there exists $ K \in \{M,N\}$ with $F(R_1)<F(K)$. Then $K,R_2,...,R_{2018}$ generates a larger $S$, contradiction. This proves our claim.

Let $R_i$ be represented by complex number $u_i $ on the unit circle in the complex plane, and the vertices of the pentagon being the $5$th roots of unity. We have $$S=\sum_{1\le i < j \le 2018} |u_i-u_j|^2.$$ Note the identity $$\sum_{1\le i < j \le 2018} |u_i-u_j|^2 + |\sum_{i=1}^{2018} u_i|^2 = 2018\sum_{i=1}^{2018} |u_i|^2=2018^2.$$

Thus it suffices to minimize $T:=|\sum_{i=1}^{2018} u_i|$. Note that all of $u_i$ are the vertices of the regular pentagon. Let $z = e^{i\frac{2\pi}{5}} = a+bi,$ $z^2 = c+di, z^3 = c-di, z^4 = a-bi$. Suppose $1,z,z^2,z^3,z^4$ have multiplicities $p,q,r,s,t$ among the $R_i$. Furthermore, we contend that we may suppose WLOG that $2|q-t, r-s$. It suffices to prove that there must be a side having two numbers of the same parity, and the diagonal parallel to this side have numbers of the same parity as well. When at least 4 numbers have the same parity then we are done. Otherwise there are $3$ numbers with the same parity, and $2$ numbers of another parity, so we may divide into cases (3 numbers with same parity (are / are not) consecutive), as desired.

Now we have $|T|^2 = (p+qa+rc+sc+ta)^2 + (qb+dr-ds-bt)^2 \ge (p+qa+sc+rc+ta)^2. \qquad (*)$ Set $q+t = 2u, \ s+r = 2v$, note that $a= \frac{\sqrt{5}-1}{4}, c= \frac{-\sqrt{5}-1}{4}$, the above expression is equal to $$\frac{1}{4}(2p-u-v+\sqrt{5}(u-v))^2.$$ Now we find the minimum of the above expression. Set $m=2p-u-v, n=v-u \in \mathbb{Z}$ and $2|m-n$, it suffices to minimize $|m-\sqrt{5}n|$. First note that

$$|m-\sqrt{5}n| = \frac{|m^2-5n^2|}{|m+\sqrt{5}n|}.$$

Since $m,n$ have the same parity, $|m^2-5n^2|\ge 4$. Note that $2m = 4p-2u-2v = 5p-2018$, hence $m\equiv 1 \pmod 5$. Hence $m^2-5n^2 \equiv 0 \pmod 4, 1 \pmod 5$. Thus $m^2 - 5n^2 =-4$ or $|m^2-5n^2|\ge 16$. If $|m^2 - 5n^2| \ge 16$ then $2u+2v \le 2018 \implies |n| \le u+v \le 1009 \implies |m-\sqrt{5}n| \ge \frac{16}{4000}.$ When $m^2-5n^2 = -4$, by the theory of Pell's Equation the only solutions $(|m|,|n|)$ with $|n| \le 2018$ are $$(1,1),(4,2),(29,13),(76,34),(521,233),(1364,610).$$ Among these we have to maximize the denominator, so we have to choose the largest of them that works. If we pick the largest of the listed pairs, since $m\equiv 1 \pmod 5$, it follows that $m = -1364$, in which case $p< 0$, contradiction. Thus $(1364, 610)$ is impossible. Now consider $(m,n) = (521,233)$. The above expression is $\frac{4}{521+\sqrt{5} \times 233} < \frac{4}{521 \times 2} < \frac{16}{4000}$, therefore the above expression attains minimum. For all equality cases of inequalities to hold, we must have $m=521, n = 233$, hence $p = 612, u = 470, v = 936$. The imagenary part of $(*)$ must be $0$, thus $q=t, r=s$. Therefore when the five vertices have been chosen $(612, 235, 468,468,235)$ times, the problem conditions are satisfied!

Question 1:

The point $P_1, P_2,\cdots ,P_{n} $ is placed inside or on the boundary of a given regular pentagon. Find all placement methods are made so that $$S=\sum_{1\leq i<j\leq n}|P_iP_j| ^2$$takes the maximum value?

Question 2: what's the background to this question?

$\endgroup$
  • $\begingroup$ Small values of integer combinations of roots of unity of degree 5 are expected to be related with Pell's equation which provides small values of $a-b\sqrt{5}$. So I do not think there should be some special background. The general question should be solvable along these lines with more cases to consider. $\endgroup$ – Fedor Petrov Nov 22 '18 at 6:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.