模长<1的d维向量之和为0存在一个排列,其部分和的模长均$<C_d$

hbghlyj

(Little Mathematics Library) L. I. Golovina and I. M. Yaglom - Induction in Geometry (几何中的归纳法) page 123
$\bbox[5px, border: 2px solid red]{C_1=1}$
结论1: $a_i\in\Bbb R\;(i=1,\cdots,n)$之和为0, $|a_i|<1$, 则存在它们的排列$b_i$, 其部分和$s_i=\sum_{k=1}^ib_k$满足$|s_i|<1$
用这帖方法,
设$\{a_1,\cdots,a_n\}=A_+∪A_-$, 其中$A_+$的元素≥0, $A_-$的元素≤0.
令$b_1=a_1$
第$k$步, 若$s_{k-1}\ge0$, 在$A_-∖\{b_1,\cdots,b_{k-1}\}$任取元素$b_k$, 则$-1\le b_k\le s_k=s_{k-1}+b_k\le s_{k-1}\le1$;
若$s_{k-1}<0$, 在$A_+∖\{b_1,\cdots,b_{k-1}\}$任取元素$b_k$, 则$-1\le s_{k-1}\le s_k=s_{k-1}+b_k\le b_k\le1$.
下面证明, 这种取法, 不会把$A_-$(或$A_+$)取空, 导致没有$b_k$取.
假设第$k$步, $s_{k-1}\ge0$, 且$A_-∖\{b_1,\cdots,b_{k-1}\}=\emptyset$, 则剩下的$n-(k-1)$个$a_i$皆$>0$, 所以$0=a_1+\cdots+a_n=s_{k-1}+\sum_{剩下的}a_i>0$, 矛盾.
证毕.
结论2: 如果把“任取元素”改为“取编号最小的元素”, 则$A_+$内的元素的顺序不变, $A_-$内的元素的顺序也不变, 只是把两个“子序列”交错地放到一起, 就像“对切法洗牌”.所以这样得到的排列$b_i$可以分为正数集$B_+$和负数集$B_-$, 其中$B_+=A_+,B_-=A_-$且元素顺序相同.
$\bbox[5px, border: 2px solid red]{C_2=\sqrt5}$
$\mathbf a_i\in\Bbb R^2\;(i=1,\cdots,n)$之和为0, $|\mathbf a_i|<1$,则存在它们的排列$\mathbf b_i$, 其部分和$\mathbf s_i$满足$|\mathbf s_i|<\sqrt5$
在$\mathbf a_1,\cdots,\mathbf a_n$的所有子集中, 设$\mathbf a'_1,\cdots,\mathbf a'_s$使$|\mathbf a'_1+\cdots+\mathbf a'_s|$最大.
把剩下的$\mathbf a_i$记为$\mathbf a''_1,\cdots,\mathbf a''_{n-s}$.
取$\mathbf a'_1+\cdots+\mathbf a'_s$为$x$轴正方向, 设$\mathbf a_i=(x_i,y_i)$.
则$x'_1,\cdots,x'_s\ge0\ge x''_1,\cdots,x''_{n-s}$ 且 $\sum_{i=1}^sy'_i=\sum_{i=1}^{n-s}y''_i=0$. [见Fig. 83]
$y'_i\le|\mathbf a'_i|\le1$. 根据结论1,存在$y'_i$的一个排列$y^*_i$使得部分和$\sum_{k=1}^iy^*_i<1\;\forall i=1,\cdots,s$.
$y''_i\le|\mathbf a''_i|\le1$. 根据结论1,存在$y''_i$的一个排列$y^{**}_i$使得部分和$\sum_{k=1}^iy^{**}_i<1\;\forall i=1,\cdots,n-s$.
把$y^*_1,\cdots,y^*_s$与$y^{**}_1,\cdots,y^{**}_{n-s}$串联记为$y^\star_i$.
(上面在排列$y$的时候,把配对的$x$作相同的编号)
$x^\star_i\le1$. 根据结论1、2,存在$x^\star_i$的一个排列$x^{\star\star}_i$使得部分和$\sum_{k=1}^ix^{\star\star}_i<1\;\forall i=1,\cdots,n$且保持正数项$x^*_i$和负数项$x^{**}_i$的内部顺序不变,那么保持$y^*_i$和$y^{**}_i$的内部顺序不变,那么部分和$\sum_{k=1}^iy^{\star\star}_i<2\;\forall i=1,\cdots,n$.
最后得到$\sum_{k=1}^i|(x^{\star\star}_i,y^{\star\star}_i)|<\sqrt{1^2+2^2}=\sqrt5\;\forall i=1,\cdots,n$.
用类似的方法得到$C_3=\sqrt{1^2+(2\sqrt5)^2}=\sqrt{21}$
由递推式$C_{n+1}=\sqrt{1^2+(2C_n)^2}$得到:
$\bbox[5px, border: 2px solid red]{C_n=\sqrt{4^n-1\over3}}$

hbghlyj

上面是我的理解. 不是按照原文逐句翻译的.
这道题的证明有很多页

Page 122	Page 123上
Page 123中	Page 123下 124上 $C_1=1$证明完毕
Page 124下	Page 125
Page 126上 $C_2=\sqrt5$证明完毕	Page 126下 对于证明$C_3=\sqrt{21}$给了一个提示

kuing

请删除 1# 的无关图片。