设点 $P_{1}, P_{2}, \cdots, P_{2018}$ 放在给定正五边形的内部或边界上．求所有的放置方式使得 $\displaystyle S=\sum\limits_{1 \leqslant i<j \leqslant 2018}\left|P_{i} P_{j}\right|^{2}$ 取到最大值．
【难度】
【出处】
2018第34届CMO试题
【标注】
【答案】
略
【解析】
引理一：$x^{2}-5 y^{2}=-4$ 的正整数解，都由斐波那切数列 $F_{1}=F_{2}=1, F_{n+1}=F_{n}+F_{n-1}$ 中某相邻两项表示为 $x=2 F_{n}+F_{n+1}, y=F_{n+1}$，其中 $n$ 为奇数．
证明：$x^{2}-5 y^{2}=-4$，则 $(9 x-20 y)^{2}-5(9 y-4 x)^{2}=x^{2}-5 y^{2}=-4$，记 $x_{1}=9 x-20 y, y_{1}=9 y-4 x$．
$x_{1}>0 \Longleftrightarrow 9 x>20 y \Longleftrightarrow 81 x^{2}>400 y^{2} \Longleftrightarrow 405 y^{2}-324>400 y^{2} \Longleftrightarrow y>8$
$y_{1}>0 \Longleftrightarrow 9 y>4 x \Longleftrightarrow 81 y^{2}>16 x^{2} \Longleftrightarrow 81 y^{2}>80 y^{2}-64$，总成立；
$x_{1}<x \Longleftrightarrow 8 x<20 y \Longleftrightarrow 4 x^{2}<25 y^{2} \Longleftrightarrow 20 y^{2}-16<25 y^{2}$，总成立；
$y_{1}<y \Longleftrightarrow 8 y-4 x<0 \Longleftrightarrow 4 y^{2}<x^{2} \Longleftrightarrow y>2$；
因此方程满足 $y>8$ 的正整数解，总能得到更小的正整数解．对于 $y\leqslant 8$，验证有解 $(1,1),(4,2),(11,5)$，这些都满足 $x=2 F_{n}+F_{n+1}, y=F_{n+1}, n=1,3,5$．上述递推过程可以描述为 $(x+\sqrt{5} y)(9-4 \sqrt{5})=(9 x-20 y)+\sqrt{5}(9 y-4 x)$
其逆操作为 $x=9(9 x-20 y)+20(9 y-4 x), \quad y=9(9 y-4 x)+4(9 x-20 y)$
上述操作下
$ 9\left(2 F_{n}+F_{n+1}\right)+20 F_{n+1} =18 F_{n}+29 F_{n+1}=11 F_{n+1}+18 F_{n+2}=7 F_{n+2}+11 F_{n+3} \\ =4 F_{n+3}+7 F_{n+4}=3 F_{n+4}+4 F_{n+5}=F_{n+5}+3 F_{n+6} =2 F_{n+6}+F_{n+7}$
因此从 $(1,1),(4,2),(11,5)$ 开始递推恰好得到题中用斐波那契数列描述的解．
引理二：$x^{2}-5 y^{2}=-4, y \leqslant 1009$ 的正整数解为 $(1,1),(4,2),(11,5),(29,13), (76,34), (199,89),(521,233), (1364,610)$
引理三：若 $n$ 个点集中在正 $5$ 边形的 $5$ 个顶点上，则当它们的重心到正 $5$ 边形中心距离最小时，存在 $5$ 个顶点的一个轮换顺序，$5$ 个顶点上的顶点个数依次是 $a, a, b, c, b$，其中 $a,b,c$ 是正整数，$2a+2b+c=n$．
证明：$5$ 个顶点按点数奇偶性涂色．$5$ 个点任意涂两色，总有保持颜色的反射对称性，将此反射下对应的两顶点上点数求平均（对称点奇偶性相同保证平均为整数），得到 $n$ 个点的一种放置；新的放置的重心是旧放置重心及其反射放置重心的中点，因此距离正 $5$ 边形中心不会更远．
引理四：设向量 $X_{1}, X_{2}, \cdots, X_{n}$ 的算术平均（重心）为 $\displaystyle X^{*}=\dfrac{1}{n} \sum\limits_{i=1}^{n} X_{i}$，则对任何向量 $Y$，有 $\displaystyle \sum\limits_{i=1}^{n}\left|Y-X_{i}\right|^{2}=\sum_{i=1}^{n}\left|X_{i}-X^{*}\right|^{2}+n\left|Y-X^{*}\right|^{2}$．
证明：及向量 $A,B$ 的內积为 $(A,B)$，根据內积的对称性，双线性性质，及 $|A|^{2}=(A, A)$，有
$\displaystyle \sum\limits_{i=1}^{n}\left|Y-X_{i}\right|^{2} =\sum_{i=1}^{n}\left(Y-X_{i}, Y-X_{i}\right)=\sum_{i=1}^{n}(Y, Y)-2\left(Y, X_{i}\right)+\left(X_{i}, X_{i}\right) \\ =n(Y, Y)-2 n\left(Y, X^{*}\right)+\sum_{i=1}^{n}\left(X_{i}, X_{i}\right)=n\left|Y-X^{*}\right|^{2}+\sum_{i=1}^{n}\left(-\left(X^{*}, X^{*}\right)+\left(X_{i}, X_{i}\right)\right) \\ =n\left|Y-X^{*}\right|^{2}+\sum_{i=1}^{n}\left(\left(X^{*}, X^{*}\right)-2\left(X^{*}, X_{i}\right)+\left(X_{i}, X_{i}\right)\right)=n\left|Y-X^{*}\right|^{2}+\sum_{i=1}^{n}\left|X_{i}-X^{*}\right|^{2} $
根据引理四，对任何 $P_i$，$\displaystyle S=2017\left|P_{i}-P_{i}^{*}\right|^{2}+\sum\limits_{j \neq i}\left|P_{j}-P_{i}^{*}\right|^{2}+\sum_{j<j^{\prime}, j \neq i, j^{\prime} \neq i}\left|P_{j}-P_{j^{\prime}}\right|^{2}$，其中 $\displaystyle P_{i}^{*}=\dfrac{1}{2017} \sum\limits_{j \neq i} P_{j}$ 为除去 $P_i$ 的其余点的重心．因此当 $S$ 达到最大值时，$P_i$ 在到 $P_{i}^{*}$ 最远的一个点上，必然是正五边形的一个顶点．因此每个 $P_{i}, i=1, \cdots, 2018$ 都在正五边形的某个顶点上，不妨设正五边形内接于单位圆．
利用引理四类似的计算，记 $n=2018$，当 $P_i$ 都是正五边形顶点时 $\displaystyle 2 S=\sum\limits_{i, j=1}^{n}\left|P_{i}-P_{j}\right|^{2}=2 n \sum_{i=1}^{n}\left|P_{i}\right|^{2}-2 \sum_{i, j=1}^{n}\left(P_{i}, P_{j}\right)=2 n^{2}-2 n^{2}\left(P^{*}, P^{*}\right)$，其中 $\displaystyle P^{*}=\dfrac{1}{n} \sum\limits_{i=1}^{n} P_{i}$ 为重心，因此 $S$ 达到极大值当且仅当 $\left|P_{i}^{*}\right|$ 达到极小值．
根据引理三，当 $S$ 达到最大值时，$5$ 个顶点上点数具有一个反射对称性，可设顶点数依次是 $a, a, b, c, b$，其中 $2 a+2 b+c=n$．不妨设复平面上的 $1$ 是五边形一个顶点，上面有 $c$ 个 $P_i$ 中的点，则
$ n P^{*} =2 a \cos \dfrac{4 \pi}{5}+2 b \cos \dfrac{2 \pi}{5}+c=-\dfrac{\sqrt{5}+1}{2} a+\dfrac{\sqrt{5}-1}{2} b+c =\dfrac{1}{2}(4036-2 a-2 b-\sqrt{5}(a-b)) $
记 $x=4036-5 a-5 b, y=a-b$，则上述距离 $2$ 倍为 $x-\sqrt{5} y=\dfrac{x^{2}-5 y^{2}}{x+\sqrt{5} y}$，其中 $x^{2}-5 y^{2} \equiv 1 (\bmod 5), x^{2}-5 y^{2} \equiv 0 (\bmod 4)$
因此 $x^{2}-5 y^{2}=-4$ 或者 $\left|x^{2}-5 y^{2}\right| \geqslant 16$．
若 $x>0$，则 $a+b \leqslant 807$，于是 $|y| \leqslant a+b \leqslant 807$；
若 $x \leqslant 0$，则 $x \geqslant 4036-5 * 1009=-1009$，于是若 $|x-\sqrt{5} y|<1$（很容易达到），则 $|y|<500$．
当 $x^{2}-5 y^{2}=-4$ 时，根据引理二，枚举这样的解，试验 $y=233, x=521$ 解得 $a=468, b=235$；
当 $y=610, x=1364$ 时，$a,b$ 无解，因此这时 $|x-\sqrt{5} y|$ 最小值在 $a=468, b=235$ 时取到，其值为 $\dfrac{4}{521+233 \sqrt{5}} \leqslant \dfrac{2}{521}$
当 $\left|x^{2}-5 y^{2}\right| \geqslant 16$ 时，$|x-\sqrt{5} y|=\left|\dfrac{x^{2}-5 y^{2}}{x+\sqrt{5} y}\right| \geqslant \dfrac{16}{1+2 \sqrt{5}|y|} \geqslant \dfrac{16}{5 * 807+1}>\dfrac{2}{521}$
综上所述，题目中的最小值在正五边形 $5$ 个顶点上点数（在某个轮换顺序下）依次为 $(468,235,612,235,468)$ 时达到．
证明：$x^{2}-5 y^{2}=-4$，则 $(9 x-20 y)^{2}-5(9 y-4 x)^{2}=x^{2}-5 y^{2}=-4$，记 $x_{1}=9 x-20 y, y_{1}=9 y-4 x$．
$x_{1}>0 \Longleftrightarrow 9 x>20 y \Longleftrightarrow 81 x^{2}>400 y^{2} \Longleftrightarrow 405 y^{2}-324>400 y^{2} \Longleftrightarrow y>8$
$y_{1}>0 \Longleftrightarrow 9 y>4 x \Longleftrightarrow 81 y^{2}>16 x^{2} \Longleftrightarrow 81 y^{2}>80 y^{2}-64$，总成立；
$x_{1}<x \Longleftrightarrow 8 x<20 y \Longleftrightarrow 4 x^{2}<25 y^{2} \Longleftrightarrow 20 y^{2}-16<25 y^{2}$，总成立；
$y_{1}<y \Longleftrightarrow 8 y-4 x<0 \Longleftrightarrow 4 y^{2}<x^{2} \Longleftrightarrow y>2$；
因此方程满足 $y>8$ 的正整数解，总能得到更小的正整数解．对于 $y\leqslant 8$，验证有解 $(1,1),(4,2),(11,5)$，这些都满足 $x=2 F_{n}+F_{n+1}, y=F_{n+1}, n=1,3,5$．上述递推过程可以描述为 $(x+\sqrt{5} y)(9-4 \sqrt{5})=(9 x-20 y)+\sqrt{5}(9 y-4 x)$
其逆操作为 $x=9(9 x-20 y)+20(9 y-4 x), \quad y=9(9 y-4 x)+4(9 x-20 y)$
上述操作下
$ 9\left(2 F_{n}+F_{n+1}\right)+20 F_{n+1} =18 F_{n}+29 F_{n+1}=11 F_{n+1}+18 F_{n+2}=7 F_{n+2}+11 F_{n+3} \\ =4 F_{n+3}+7 F_{n+4}=3 F_{n+4}+4 F_{n+5}=F_{n+5}+3 F_{n+6} =2 F_{n+6}+F_{n+7}$
因此从 $(1,1),(4,2),(11,5)$ 开始递推恰好得到题中用斐波那契数列描述的解．
引理二：$x^{2}-5 y^{2}=-4, y \leqslant 1009$ 的正整数解为 $(1,1),(4,2),(11,5),(29,13), (76,34), (199,89),(521,233), (1364,610)$
引理三：若 $n$ 个点集中在正 $5$ 边形的 $5$ 个顶点上，则当它们的重心到正 $5$ 边形中心距离最小时，存在 $5$ 个顶点的一个轮换顺序，$5$ 个顶点上的顶点个数依次是 $a, a, b, c, b$，其中 $a,b,c$ 是正整数，$2a+2b+c=n$．
证明：$5$ 个顶点按点数奇偶性涂色．$5$ 个点任意涂两色，总有保持颜色的反射对称性，将此反射下对应的两顶点上点数求平均（对称点奇偶性相同保证平均为整数），得到 $n$ 个点的一种放置；新的放置的重心是旧放置重心及其反射放置重心的中点，因此距离正 $5$ 边形中心不会更远．
引理四：设向量 $X_{1}, X_{2}, \cdots, X_{n}$ 的算术平均（重心）为 $\displaystyle X^{*}=\dfrac{1}{n} \sum\limits_{i=1}^{n} X_{i}$，则对任何向量 $Y$，有 $\displaystyle \sum\limits_{i=1}^{n}\left|Y-X_{i}\right|^{2}=\sum_{i=1}^{n}\left|X_{i}-X^{*}\right|^{2}+n\left|Y-X^{*}\right|^{2}$．
证明：及向量 $A,B$ 的內积为 $(A,B)$，根据內积的对称性，双线性性质，及 $|A|^{2}=(A, A)$，有
$\displaystyle \sum\limits_{i=1}^{n}\left|Y-X_{i}\right|^{2} =\sum_{i=1}^{n}\left(Y-X_{i}, Y-X_{i}\right)=\sum_{i=1}^{n}(Y, Y)-2\left(Y, X_{i}\right)+\left(X_{i}, X_{i}\right) \\ =n(Y, Y)-2 n\left(Y, X^{*}\right)+\sum_{i=1}^{n}\left(X_{i}, X_{i}\right)=n\left|Y-X^{*}\right|^{2}+\sum_{i=1}^{n}\left(-\left(X^{*}, X^{*}\right)+\left(X_{i}, X_{i}\right)\right) \\ =n\left|Y-X^{*}\right|^{2}+\sum_{i=1}^{n}\left(\left(X^{*}, X^{*}\right)-2\left(X^{*}, X_{i}\right)+\left(X_{i}, X_{i}\right)\right)=n\left|Y-X^{*}\right|^{2}+\sum_{i=1}^{n}\left|X_{i}-X^{*}\right|^{2} $
根据引理四，对任何 $P_i$，$\displaystyle S=2017\left|P_{i}-P_{i}^{*}\right|^{2}+\sum\limits_{j \neq i}\left|P_{j}-P_{i}^{*}\right|^{2}+\sum_{j<j^{\prime}, j \neq i, j^{\prime} \neq i}\left|P_{j}-P_{j^{\prime}}\right|^{2}$，其中 $\displaystyle P_{i}^{*}=\dfrac{1}{2017} \sum\limits_{j \neq i} P_{j}$ 为除去 $P_i$ 的其余点的重心．因此当 $S$ 达到最大值时，$P_i$ 在到 $P_{i}^{*}$ 最远的一个点上，必然是正五边形的一个顶点．因此每个 $P_{i}, i=1, \cdots, 2018$ 都在正五边形的某个顶点上，不妨设正五边形内接于单位圆．
利用引理四类似的计算，记 $n=2018$，当 $P_i$ 都是正五边形顶点时 $\displaystyle 2 S=\sum\limits_{i, j=1}^{n}\left|P_{i}-P_{j}\right|^{2}=2 n \sum_{i=1}^{n}\left|P_{i}\right|^{2}-2 \sum_{i, j=1}^{n}\left(P_{i}, P_{j}\right)=2 n^{2}-2 n^{2}\left(P^{*}, P^{*}\right)$，其中 $\displaystyle P^{*}=\dfrac{1}{n} \sum\limits_{i=1}^{n} P_{i}$ 为重心，因此 $S$ 达到极大值当且仅当 $\left|P_{i}^{*}\right|$ 达到极小值．
根据引理三，当 $S$ 达到最大值时，$5$ 个顶点上点数具有一个反射对称性，可设顶点数依次是 $a, a, b, c, b$，其中 $2 a+2 b+c=n$．不妨设复平面上的 $1$ 是五边形一个顶点，上面有 $c$ 个 $P_i$ 中的点，则
$ n P^{*} =2 a \cos \dfrac{4 \pi}{5}+2 b \cos \dfrac{2 \pi}{5}+c=-\dfrac{\sqrt{5}+1}{2} a+\dfrac{\sqrt{5}-1}{2} b+c =\dfrac{1}{2}(4036-2 a-2 b-\sqrt{5}(a-b)) $
记 $x=4036-5 a-5 b, y=a-b$，则上述距离 $2$ 倍为 $x-\sqrt{5} y=\dfrac{x^{2}-5 y^{2}}{x+\sqrt{5} y}$，其中 $x^{2}-5 y^{2} \equiv 1 (\bmod 5), x^{2}-5 y^{2} \equiv 0 (\bmod 4)$
因此 $x^{2}-5 y^{2}=-4$ 或者 $\left|x^{2}-5 y^{2}\right| \geqslant 16$．
若 $x>0$，则 $a+b \leqslant 807$，于是 $|y| \leqslant a+b \leqslant 807$；
若 $x \leqslant 0$，则 $x \geqslant 4036-5 * 1009=-1009$，于是若 $|x-\sqrt{5} y|<1$（很容易达到），则 $|y|<500$．
当 $x^{2}-5 y^{2}=-4$ 时，根据引理二，枚举这样的解，试验 $y=233, x=521$ 解得 $a=468, b=235$；
当 $y=610, x=1364$ 时，$a,b$ 无解，因此这时 $|x-\sqrt{5} y|$ 最小值在 $a=468, b=235$ 时取到，其值为 $\dfrac{4}{521+233 \sqrt{5}} \leqslant \dfrac{2}{521}$
当 $\left|x^{2}-5 y^{2}\right| \geqslant 16$ 时，$|x-\sqrt{5} y|=\left|\dfrac{x^{2}-5 y^{2}}{x+\sqrt{5} y}\right| \geqslant \dfrac{16}{1+2 \sqrt{5}|y|} \geqslant \dfrac{16}{5 * 807+1}>\dfrac{2}{521}$
综上所述，题目中的最小值在正五边形 $5$ 个顶点上点数（在某个轮换顺序下）依次为 $(468,235,612,235,468)$ 时达到．
答案
解析
备注
