Finding a subset of nonnegative vectors with a coordinatewise large sum

Given a rational a=p/q and N nonnegative d-dimensional real vectors u1,…,uN, we show that it is always possible to choose (d−1)+⌈(pN−d+1)/q⌉ of them such that their sum is (componentwise) at least (p/q)(u1+⋯+uN). For fixed d and a, this bound is sharp if N is large enough. The method of the proof uses Carathéodory's theorem from linear programming.