说在前面

这个问题我还没有解决.

题目

已知平面向量 $v_1,v_2,v_3,\cdots,v_n$ 满足 $\sum_{i=1}^n|\vec{v_i}|=1$ . 若必存在若干个向量, 它们的和的模不小于 $k$ , 求 $k$ 的最大值.

原题如下

给出的解法虽然很精彩, 但是并不是最大值 (最少是没证明 $1/4$ 是最大值) . 于是就产生了这个求最大值的想法.

猜想

我猜测结果是 $1/3$ .

一些结果

令 $P\subseteq {1,2,3,\cdots,n}$ , 且满足 $\left|\sum_{i\in P}v_i\right|$ 为所有向量相加的组合中能取到的最大值, 我们来考虑如何选取得到这个向量的集合. 设一个向量 $\vec{w}\not=\vec 0$ , 如何取向量并相加才能使得这个相加后的向量在 $\vec{w}$ 上的投影的模最大? 很显然, 取一条过原点的直线, 然后分别将直线的两边的所有向量相加 (在直线上的向量相加与否并不影响这个模的取值), 得到的两个向量必有一个在 $\vec{w}$ 上的投影的模是最大的, 但是这样取到的最大的模必然小于等于 $\left|\sum_{i\in P}v_i\right|$ (当 $\vec w$ 与 $\sum_{i\in P}v_i$ 的方向相同或相反时取等号). 于是, 向量 $\left|\sum_{i\in P}v_i\right|$ 必然是某条过原点的直线的一边的所有向量的和的模.

因此, 我们就可以利用这个结果来设计一个较低复杂度 $O(n)$ 的程序, 来使我的猜想更加可信.

代码验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import numpy as np
rand = lambda num, t: np.random.rand(num, t) - 0.5
sin = np.sin
cos = np.cos
arcsin = np.arcsin
arccos = np.arccos
sqrt = np.sqrt
pi = np.pi

def angle(x0, y0):
x = x0 / sqrt(x0**2 + y0**2)
y = y0 / sqrt(x0**2 + y0**2)
efactor = 0.01
if y > 0:
theta = arcsin(y)
if cos(theta) - x < efactor:
return theta
else:
return pi - theta
else:
theta = arcsin(y) + 2*pi
if cos(theta) - x < efactor:
return theta
else:
return 3*pi - theta

def angle(x0, y0):
x = x0 / sqrt(x0**2 + y0**2)
y = y0 / sqrt(x0**2 + y0**2)
efactor = 0.01
if y > 0:
theta = arcsin(y)
if cos(theta) - x < efactor:
return theta
else:
return pi - theta
else:
theta = arcsin(y) + 2*pi
if cos(theta) - x < efactor:
return theta
else:
return 3*pi - theta
def rand_vec(num):
res = []
for x, y in rand(num, 2):
res.append(Vector(x, y))
return res

def init_vec(num):
vec_arr = rand_vec(num)
res = []
length = 0
for vec in vec_arr:
length += vec.length()
for vec in vec_arr:
res.append(Vector(vec.x / length, vec.y / length))
return res

def init_sum_vec_list(MAXNUM = 100):
vec_list = init_vec(MAXNUM)
vec_list.sort(key=(lambda vec: vec.angle))
sum_vec = vec_list[-1]
sum_vec_list = []
bedex = 0
edex = 0

for bdex in range(MAXNUM):
sum_vec -= vec_list[bdex - 1]
bedex = edex
for edex in range(bedex, bedex + MAXNUM):
sum_vec += vec_list[edex % MAXNUM]
if edex + 1 < MAXNUM:
if vec_list[(edex + 1) % MAXNUM].angle - vec_list[bdex % MAXNUM].angle > pi:
sum_vec_list.append(sum_vec)
break
else:
if vec_list[(edex + 1) % MAXNUM].angle - vec_list[bdex % MAXNUM].angle > -pi:
sum_vec_list.append(sum_vec)
break
return sum_vec_list

res_len = []
for i in range(100):
res_len.append(max(init_sum_vec_list()).length())
print(min(res_len))

代码没有注释是因为优秀的代码不需要注释我太懒了. 最后结果算出来基本上都大于 0.5, 想来可能是简单的等概率随机分布并不适合生成随机向量, 以后有时间再优化一下吧.