Global and Local

To global or to local, 'tis the question. Global and Local is a difficult unit that combines Local and Global, units with two radically different ideas. It is fairly difficult, probably in the middle-to-hard part of Z. It is a very large unit with a good number of problems, so expect to spend some time on it. It is also very fundamental; try to do as much of the problem set as you can, rather than targeting the required number of clubs.

Should I do this unit?

Of course, it's an amazing unit. You will have a much easier time if you have done either of Local or Global before, preferably both. Additionally, it teaches about two extremely important themes in combinatorics problems, and the fact that they show up side by side allows you to hone your intuition for which problems are susceptible to which ideas really well in the problem set. I hope that you enjoy this unit and learn from it as much as I did :).

Reading

7.1-7.3 from The OTIS Excerpts; this discusses global concepts and has examples+walkthroughs.

Philosophy

Global: This is all about examining the whole problem structure (which usually has an amount of symmetry in it) and doing something like double counting, summing a quantity across the whole (say, grid) or calculating expected values for the number of certain objects, or just using good old pigeonhole. More details at [Global] (wiki:global) and in the unit.

Local: This is the opposite, where you look at small parts of the problem and make a small change. This usually lends itself into inductive or algorithmic arguments. The RUST (Repeat Until STuck) principle (Greedy) is more useful than it might seem. You can also make small optimizations to the problem that make life easier but wouldn't change whether the problem would hold or not (such as deleting unnecessary edges in a graph, or combining two $$\frac{1}{2n}$$ coins into a $$\frac{1}{n}$$ coin). Smoothing in inequalities contexts fits well into this philosophy.

Fair warning: The walkthroughs are for the most part considerably easier than the problems.

Notable Problems

This unit has way more great problems than I have included here.

1. 2020 Cyberspace P7: This problem has both a global and a local solution. Which one shalt thou find first?

2. 2005 IMO 6: This problem emphasizes the (Guess what?) strategy, and solving this means you have understood how to apply it well.

3. 2013 ISL C4: A very unexpected problem, with which neither philosophy works particularly well at first glance. One triumphs though.

4. 2014 IMO 6: This problem emphasizes the (Guess what?) strategy, and solving this means you have understood how to apply it well. Required on ZCX.

5. 2008 USAMO 3: This solution admits solutions using either approach, both of which are tricky to find. Doing this problem is highly recommended.

6. 2006 ISL C3: A real shocker of a problem. Prepare to be wowed away when you stumble into the solution.