说在前面

这个问题我还没有解决.

题目

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

原题如下

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

猜想

我猜测结果是 $1/\pi$ .

一些结果

令 $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)$ 的程序, 来使我的猜想更加可信.

代码验证

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))