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.
Problem
Source: China Chengdu Nov 15, 2018
Tags: inequalities, algebra, geometry, trigonometry
15.11.2018 09:11
This is a very very beautiful problem.
15.11.2018 14:55
And extremely hard. The maximum is attained when five vertice of pentagon have $(235,468,468,235,612)$ $P_i$s, respectively.
15.11.2018 16:48
sqing wrote: The point $P_1, P_2,\cdots ,P_{2018} $ is placed inside or on the boundary of a given 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.
Attachments:


15.11.2018 17:07
It's well known that for any set of $m$ points $A_1,\dots, A_m$ and a point $P$ it holds: $$\sum\limits_{i=1}^m |PA_i|^2= \sum\limits_{i=1}^m |GA_i|^2 + m|GP|^2.$$where $G$ is the center of gravity of $A_1,\dots,A_m$. Put $n$ instead $2018$. Let $P_1,P_2,\dots,P_n$ be a position with maximal sum. It exists because any continuous function on a compact sets attains its extremal values. Fix $P_2,P_3,\dots,P_n$ and let $G'$ be the center of their gravity. Now, vary $P_1$. By above claim $\sum\limits_{i=2}^{m}|P_1P_i|^2$ attains its maximum when $P_1$ is at maximal distance from $G'$. Thus, $P_1$ must coincide with some vertex of the given pentagon. Similarly, it can be applied to any other $P_i$ implying all $P_i,i=1,\dots,n$ are at the vertices of the pentagon. It remains to carry out some simple calculations to establish the number of points at each vertex.
15.11.2018 17:11
dgrozev wrote: It's well known that for any set of $m$ points $A_1,\dots, A_m$ and a point $P$ it holds: $$\sum\limits_{i=1}^m |PA_i|^2= \sum\limits_{i=1}^m |GA_i|^2 + m|GP|^2.$$where $G$ is the center of gravity of $A_1,\dots,A_m$. Put $n$ instead $2018$. Let $P_1,P_2,\dots,P_n$ be a position with maximal sum. It exists because any continuous function on a compact sets attains its extremal values. Fix $P_2,P_3,\dots,P_n$ and let $G'$ be the center of their gravity. Now, vary $P_1$. By above claim $\sum\limits_{i=2}^{m}|P_1P_i|^2$ attains its maximum when $P_1$ is at maximal distance from $G'$. Thus, $P_1$ must coincide with some vertex of the given pentagon. Similarly, it can be applied to any other $P_i$ implying all $P_i,i=1,\dots,n$ are at the vertices of the pentagon. It remains to carry out some simple calculations to establish the number of points at each vertex. Thank you very much.
15.11.2018 17:23
@sqing: Would you translate (at least the idea) of that (I suppose the official) solution, since many people here (including me) don't understand Chinese.
15.11.2018 20:56
The idea is basically the same as yours up to calculation, and calculation still requires some work, and in my opinion is the hardest part of the problem. (I tried to solve the problem using the equality cases of the inequalities by doing adjustments like $(a,c)\to (a+1,c-1)$ etc. Then I ran out of time Don't think would've solved it anyway ) ___Wrong solution was written here before___
16.11.2018 04:06
dgrozev wrote: @sqing: Would you translate (at least the idea) of that (I suppose the official) solution, since many people here (including me) don't understand Chinese. This is not an official solution.
16.11.2018 04:09
stroller wrote: The idea is basically the same as yours up to calculation, and calculation still requires some work, and in my opinion is the hardest part of the problem. (I tried to solve the problem using the equality cases of the inequalities by doing adjustments like $(a,c)\to (a+1,c-1)$ etc. Then I ran out of time Don't think would've solved it anyway ) The problem is proposed by Luo Wei, and indeed beautiful and hard. Solution When $S$ attains maximum, let $P$ be the center of all the points, $Q_i$ the center of gravity of the 2017 points other than $P_i$. Then the function $S$ in $P_i$ differ from $2017|P_i-Q_i|^2$ by some value independent of $P_i$. Thus when $S$ attains maximum, $P_i$ is the point furthest away from $Q_i$. Therefore $P_i$ is equal to one of the vertices of the pentagon. Thus when $S$ is maximum, all points are at the vertices of the pentagon. Let $P$ be the center of gravity of these 2018 points. Suppose $P_i$ is on $A$, $AB$ is a side of the regular pentagon. Then the distance from $B$ to $Q_i$ is not less than that from $A$ to $Q_i$, hence the orthogonal projection of $Q_i$ on $AB$ on the same side $M$ as $B$, where $M$ is the midpoint of $AB$. Also, the projection $P'$ of $P=(A+2017Q_i)/2018$ on $AB$ is on the same side of $B$ as $(A+2017M)/2018$. If $A,B$ both contain points in $\{P_i:1\le i \le 2018\}$, then $P'M \le |AB|/4036$. Suppose the vertices of the pentagon are $A,B,C,D,E$ counterclockwise, with $a,b,c,d,e$ points, respectively. $k=\frac{\sqrt{5}+3}{2}$ is also equal to $|CD|^2/|AB|^2$. Let $u=1/2018$. By the above discussion $$a>0, b>0 \implies |a-b+k(c-e)| \le u.$$ Also for any $x,y $ not all equal to $0$, we have $$|(x+ky)(x+y/k)| = |x^2+3xy-y^2|\ge 1.$$ Thus $(a-b) = \frac{-1}{k}(c-e)\ge \frac{1}{u} = 2018.$ Thus $|a-b|+|c-e| \ge 2018$, contradiction. Therefore $$a>0, b>0 \implies a=b, c=e$$ If $a,b,c,d,e$ contains $3$ consecutive nonzero numbers, say $a,b,c>0$. By the above result we have $a=b,c=e,b=c, a=d$, so $a=b=c=d=e$, contradiction to $5\nmid 2018$. If no two consecutive vertices have zero points, then evidently all points $P_i$ are at one of two non-consecutive vertices, whence $S\le 1009^2k$. Finally, if $a=b$, then $c=e=0, S=k\cdot 2a(2018-2a)+a^2$. When $a=585$, this reaches maximum (which is larger than $1009^2k$). Therefore, $S$ achieves maximum when the five vertices have $585,585,0,848,0$ points. Any mistake here is due to the scribe (me). The problem is proposed by Luo Wei ?
16.11.2018 04:24
@sqing I don't know. I thought it was proposed by 罗炜 because his name is written in the screenshot you sent, right below the problem. Whoops. Did he only provide the solution then? Sorry!! I only wanted to translate it as it was written...
16.11.2018 04:29
stroller wrote: @sqing I don't know. I thought it was proposed by 罗炜 because his name is written in the screenshot you sent, right below the problem. Whoops. Did he only provide the solution then? Sorry!! I only wanted to translate it as it was written... That solution is Luo Wei’s. Thanks.
16.11.2018 05:26
dgrozev wrote:
The rest is extremely hard. Your solution can only get 1 point from 7 points. And another solution is wrong, too. And author of that solution is notified. The maximum is attained when five vertice of pentagon have $(235,468,468,235,612)$ $P_i$s, respectively.
16.11.2018 16:08
Here's a solution by Wu Zhuo I am translating. \textbf{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)\}$. \textit{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! \qed