查看数据源：5cac2742210b2866bb0a6976
在平面直角坐标系中，设点集 $\left\{ {{P}_{1}}\text{,}{{P}_{2}},\cdots \text{,}{{P}_{4n+1}} \right\}\text{=}\left\{ \left. \left( x\text{,}y \right) \right|x\text{,}y\in \mathbb{Z}\text{,}\left| x \right|\leqslant n\text{,}\left| y \right|\leqslant n\text{,}xy\text{=}0 \right\}$，其中 $n\in {{\mathbb{N}}_{+}}$ 。求 ${{\left( {{P}_{1}}{{P}_{2}} \right)}^{2}}+{{\left( {{P}_{2}}{{P}_{3}} \right)}^{2}}+\cdots +{{\left( {{P}_{4n}}{{P}_{4n+1}} \right)}^{2}}+{{\left( {{P}_{4n+1}}{{P}_{1}} \right)}^{2}}$ 的最小值。
【难度】
【出处】
2009第8届CGMO试题
【标注】
  • 知识点
    >
    二试组合部分
【答案】
$16n+8$
【解析】
首先证明一个引理。 引理 设实数 ${{s}_{1}}\geqslant {{s}_{2}}\geqslant \cdots \geqslant{{s}_{m}}$，且 $f\left( {{s}_{1}}\text{,}{{s}_{2}}\text{,}\cdots \text{,}{{s}_{m}}\right)\text{=}\underset{\left( {{t}_{1}}\text{,}{{t}_{2}}\text{,}\cdots\text{,}{{t}_{m}} \right)}{\mathop{\min }} \left\{ {{\left|{{t}_{1}}-{{t}_{2}} \right|}^{2}}+{{\left| {{t}_{2}}-{{t}_{3}}\right|}^{2}}+\cdots +{{\left| {{t}_{m-1}}-{{t}_{m}} \right|}^{2}}+{{\left|{{t}_{m}}-{{t}_{1}} \right|}^{2}} \right\}$，其中 $\left({{t}_{1}}\text{,}{{t}_{2}}\text{,}\cdots \text{,}{{t}_{m}} \right)$ 取遍 $\left({{s}_{1}}\text{,}{{s}_{2}}\text{,}\cdots \text{,}{{s}_{m}} \right)$ 的所有排列。则 $f\left({{s}_{1}}\text{,}{{s}_{2}}\text{,}\cdots \text{,}{{s}_{m}} \right)\geqslant f\left({{s}_{2}}\text{,}{{s}_{3}}\text{,}\cdots \text{,}{{s}_{m}} \right)+2\left({{s}_{1}}-{{s}_{2}} \right)\left( {{s}_{1}}-{{s}_{3}} \right)$ 引理的证明：不妨设 ${{t}_{1}}\text{=}{{s}_{1}}$ 。则 ${{\left|{{t}_{1}}-{{t}_{2}} \right|}^{2}}+{{\left| {{t}_{2}}-{{t}_{3}}\right|}^{2}}+\cdots +{{\left| {{t}_{m-1}}-{{t}_{m}} \right|}^{2}}+{{\left|{{t}_{m}}-{{t}_{1}} \right|}^{2}}\text{=}{{\left| {{t}_{2}}-{{t}_{3}}\right|}^{2}}+\cdots +{{\left| {{t}_{m-1}}-{{t}_{m}} \right|}^{2}}+{{\left|{{t}_{m}}-{{t}_{2}} \right|}^{2}}+\left( {{\left| {{t}_{1}}-{{t}_{2}}\right|}^{2}}+{{\left| {{t}_{m}}-{{t}_{1}} \right|}^{2}}-{{\left|{{t}_{m}}-{{t}_{2}} \right|}^{2}} \right)\text{=}{{\left| {{t}_{2}}-{{t}_{3}}\right|}^{2}}+\cdots +{{\left| {{t}_{m-1}}-{{t}_{m}} \right|}^{2}}+{{\left|{{t}_{m}}-{{t}_{2}} \right|}^{2}}+2\left( {{t}_{1}}-{{t}_{2}} \right)\left( {{t}_{1}}-{{t}_{m}}\right)\geqslant f\left( {{s}_{2}}\text{,}{{s}_{3}}\text{,}\cdots \text{,}{{s}_{m}}\right)+2\left( {{s}_{1}}-{{s}_{2}} \right)\left( {{s}_{1}}-{{s}_{3}} \right)$ 回到原题。设 ${{P}_{i}}\text{=}\left({{x}_{i}}\text{,}{{y}_{i}} \right)\left( i\text{=}1\text{,}2\text{,}\cdots\text{,}4n+2 \right)$，其中 ${{P}_{4n+2}}\text{=}{{P}_{1}}$ 。则 $\displaystyle \sum\limits_{i\text{=}1}^{4n+1}{{{P}_{i}}P_{i+1}^{2}\text{=}\sum\limits_{i\text{=}1}^{4n+1}{\left[{{\left( {{x}_{i}}-{{x}_{i+1}} \right)}^{2}}+{{\left( {{y}_{i}}-{{y}_{i+1}}\right)}^{2}} \right]}}$ $\displaystyle \sum\limits_{i\text{=}1}^{4n+1}{{{P}_{i}}P_{i+1}^{2}}\geqslant 2f\left(n,\cdots ,1,\underbrace{0,\cdots 0}_{2n+1},-1,\cdots ,-n \right)\geqslant 2f\left(n-1,\cdots ,1,\underbrace{0,\cdots 0}_{2n+1},-1,\cdots ,1-n \right)+16\geqslant\cdots \geqslant 2f\left( 1,\underbrace{0,\cdots 0}_{2n+1},-1 \right)+16\left( n-1\right)=16n-8$
当 ${{P}_{\text{1}}},{{P}_{\text{2}}},\cdots,{{P}_{4n+1}}$ 分别为 $\left( \text{2,0} \right),\left( \text{4,0} \right),\cdots,\left( n,0 \right),\cdots ,\left( 3,0 \right),\left( 1,0 \right),\left( 0,2\right),\left( 0,4 \right),\cdots ,\left( 0,n \right),\cdots ,\left( 0,3\right),\left( 0,1 \right),\left( -2,0 \right),\left( -4,0 \right),\cdots,\left( -n,0 \right),\cdots ,\left( -3,0 \right),\left( -1,0 \right),\left(0,-2 \right),\left( 0,-4 \right),\cdots ,\left( 0,-n \right),\cdots ,\left(0,-3 \right),\left( 0,-1 \right),\left( 0,0 \right)$ 时，$\displaystyle \sum\limits_{i\text{=}1}^{4n+1}{{{P}_{i}}P_{i+1}^{2}}\text{=16n+8}$
答案 解析 备注
0.114587s