f*****e
发帖数: 2992 | 1 证明存在xi = 1 or -1 (i=1,...n),
||sum(xi*ai)||<=1/3
其中
sum(||ai||^2)=1
||ai||<=0.1
ai是二维向量. | i******t
发帖数: 370 | 2 I think the square sum=1 is not necessary, and the proposition can be
stronger:
||sum(xi*ai)||<=0.2 for 2D.
【在 f*****e 的大作中提到】
: 证明存在xi = 1 or -1 (i=1,...n),
: ||sum(xi*ai)||<=1/3
: 其中
: sum(||ai||^2)=1
: ||ai||<=0.1
: ai是二维向量.
| f*****e
发帖数: 2992 | 3 how?你说得确实是对的,你说的是不是beck的那边文章呢?那边文章证得啰里八嗦,但是
比较general,所有维都考虑到了,但是我想用method of variance得到该情形下一种比
较简单的证法.
【在 i******t 的大作中提到】
: I think the square sum=1 is not necessary, and the proposition can be
: stronger:
: ||sum(xi*ai)||<=0.2 for 2D.
| i******t
发帖数: 370 | 4 我没有看过beck的文章，不过这题可以这样证明：
用反证法。假设存在x_1,...,x_n，使得无论怎样label a_i=+/-1，||sum(x_ia_i)||>0
.2。考虑最小的点数n，令L=min||sum(x_ia_i)||>0.2。以下证明要么n可以减小，要么
L可以减小。
W.l.o.g. 令s=sum(x_ia_i)=(0,L)，否则旋转坐标轴即可。引入以下记号phase(u)=向
量u的幅角，P(a,b)={u: a<=phase(u)<=b}，y_i=x_i*a_i。考虑以下两种情况：
1）若存在y_i in P(theta-pi/2, pi/2-theta)，theta=arcsin(0.1/0.2)=pi/6，则
norm(s-2*y_i)
2）否则，考察对称的两个集合S_1=P(pi/2-theta, pi/2+theta), S_2=P(-theta-pi/2,
theta-pi/2)。对任意u in S_1, v in S_2, angle(u,v)>=pi-2*theta=2
【在 f*****e 的大作中提到】
: how?你说得确实是对的,你说的是不是beck的那边文章呢?那边文章证得啰里八嗦,但是
: 比较general,所有维都考虑到了,但是我想用method of variance得到该情形下一种比
: 较简单的证法.
| f*****e
发帖数: 2992 | 5 对你的证明做了一点修改,主要思想还是你的.
divide the plane into six angular othants in degree (0, 60),(60,120),(120,18
0),(180,240), (240,300),(300,360)
and we can always eliminate two vectors in the same angle or oposite angles
by + or - and get a vector with no larger length, for example:
if a1,a2 are in the same angle, say, (0,60), then according to laws of cosin
e: |a1-a2|=sqrt(|a1|^2+|a2|^2-2*cos(a1,a2)*|a1|*|a2|)<=max(|a1|,|a2|).
if a1,a2 are in oposite angles, say (0,60), (180,240), then |a1+a2| <= max(|
a1|
【在 i******t 的大作中提到】
: 我没有看过beck的文章，不过这题可以这样证明：
: 用反证法。假设存在x_1,...,x_n，使得无论怎样label a_i=+/-1，||sum(x_ia_i)||>0
: .2。考虑最小的点数n，令L=min||sum(x_ia_i)||>0.2。以下证明要么n可以减小，要么
: L可以减小。
: W.l.o.g. 令s=sum(x_ia_i)=(0,L)，否则旋转坐标轴即可。引入以下记号phase(u)=向
: 量u的幅角，P(a,b)={u: a<=phase(u)<=b}，y_i=x_i*a_i。考虑以下两种情况：
: 1）若存在y_i in P(theta-pi/2, pi/2-theta)，theta=arcsin(0.1/0.2)=pi/6，则
: norm(s-2*y_i): 2）否则，考察对称的两个集合S_1=P(pi/2-theta, pi/2+theta), S_2=P(-theta-pi/2,
: theta-pi/2)。对任意u in S_1, v in S_2, angle(u,v)>=pi-2*theta=2
| c**********r
发帖数: 944 | 6 不会是alon-spencer那本书习题吧
【在 f*****e 的大作中提到】
: 证明存在xi = 1 or -1 (i=1,...n),
: ||sum(xi*ai)||<=1/3
: 其中
: sum(||ai||^2)=1
: ||ai||<=0.1
: ai是二维向量.
|
|
