Global
Linearity of expectation, switching the order of summation, what's often called pigeonhole principle, counting in two ways, ... turns out they're actually all more or less the same idea.
Philosophy
This unit is really about taking a holistic view of a problem, contrasting with Local. You're usually given a structure, where you need to count something, be it giving a contradiction using Pigeonhole or finding a lower bound.
This unit can be seen as an introduction to a D-leveled combo unit, and a medium B-leveled unit.
Strategy
A few strategies covered are
- switching the order of the summation
- linearity of expectation
- pigeonhole, double counting
- coloring.
Another useful strategy to consider is characterizing objects or states and considering how many times each object is counted in the final sum.
Notable Problems
- 2006 ISL C3: Demonstrates the large power EV can have, even on olympiad problems.
- IMO 2005/6: A classic global problem.
- 2010 ISL C5: An instructive problem on ways to characterize certain states in order to form a sum.