Finding a subset of nonnegative vectors with a coordinatewise large sum

Given a rational a = p / q and N nonnegative d -dimensional real vectors u 1 , … , u N , we show that it is always possible to choose ( d − 1 ) + ⌈ ( p N − d + 1 ) / q ⌉ of them such that their sum is (componentwise) at least ( p / q ) ( u 1 + ⋯ + u N ) . 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.