MathDB
Least number of indices with sum ≥ 0

Source: Baltic Way 2003

November 6, 2010
combinatorics proposedcombinatorics

Problem Statement

Let n≥2n\ge 2 and d≥1d\ge 1 be integers with d∣nd\mid n, and let x1,x2,…xnx_1,x_2,\ldots x_n be real numbers such that x1+x2+⋯+xn=0x_1+x_2+\cdots + x_n=0. Show that there are at least (n−1d−1)\binom{n-1}{d-1} choices of dd indices 1≤i1<i2<⋯<id≤n1\le i_1<i_2<\cdots <i_d\le n such that xi1+xi2+⋯+xid≥0x_{i_{1}}+x_{i_{2}}+\cdots +x_{i_{d}}\ge 0.
Back to ProblemsView on AoPS