Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've got $\sum_{i} F_+(i) \ge k \sum_{i} G(i)$ and it says that implies there's an $i$ such that $F(i) \ge k G(i)$, $F_+$ is the positive part of $F$ and $\sum_{i} F(i) = 0$. How does it follow?

From Thomas Andrews I realized $$\sum_{i} F_+(i) = \sum_{i,F(i)\ge 0} F(i) \ge k \sum_{i} G(i).$$ This seems like it could be useful.

share|improve this question
Do you mean $F_{+}(i)=F(i)$ if $F(i)>0$ and $0$ otherwise? –  Thomas Andrews Dec 6 '12 at 17:30

1 Answer 1

up vote 0 down vote accepted

I do know how to solve it with the pigeonhole principle.

Just use contraddiction: say that for each $i$ $F(i) < kG(i)$, take the sum: $\sum F(i) < \sum {kG(i)}$. Now $\sum_{F(i)\geq 0}{F(i)} \leq \sum F(i) < \sum {kG(i)}$, but this is a contraddiction of your initial hypothesis, so should exist at least an index $i$ such that $F(i) \geq kG(i)$.

share|improve this answer
That's great! Thank you very much! –  user51427 Dec 6 '12 at 17:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.