Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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.