In contrast to the global unit, this unit is about problems starting from somewhere and perturbing it by a little bit. For example, in a greedy algorithm, if I want a set $S$ of size at least 100 with a certain property, I can imagine starting with $S$ empty and then grabbing things to add to $S$ while trying to avoid bad-ness (whatever that means for the current problem). It's then enough to prove I don't get stuck at any point. Most of the problems in this unit will have a similar algorithmic feeling.
Local is about zooming into a small portion of a problem. This includes things like smoothing and making perturbations. Very often, local solutions are based on algorithms (which are based on heuristics). When we are lazy, we use the algo-extremal duality and write shorter solutions by considering an extremal object (which usually correspond to the last step of our algorithm). You may need a “global” quantity that shows you are making progress. e.g., if you want to improve the grade that you see in your report card, you use the greedy strategy “focus on the subject that you got the least marks in”. But due to this, you are getting some marks lesser in other subjects that you earlier got. To justify that you are performing better, you show your mom that your aggregate marks are increasing.
Philosophy
The problem is usually symmetric: all the parts (a.k.a. protagonists) tend to be similar. There are two main lines of thought. The first one:
- Let me do something that makes partial progress towards the problem. (e.g., you want to choose a bunch of points, so you start by choosing any point).
- You then analyze how many choices remain after your initial choice (e.g., maybe the problem tells you that three or more points shouldn't be collinear. That may reduce your possible choices).
- You repeat until stuck (RUST).
We may call the last strategy as “expand your tiny world”. The second line of thought is:
- Wow, some cases of this problem are really easy.
- Can I “push” (or perturb) the other cases so that they become like these easy cases?
This line of thought typically needs you to think of a way to perturb the problem that preserves the properties of the problem (so, au fond, similar to circular optimization). We call this approach “just fix it”.
Notable Problems
- Putnam 2016 A5: iconic portrayal of “expand your tiny world”. Don't be too quick to click, you need some group theory to understand the problem.
- HMMT 2018 T6: required problem in the DCW version. Rather than “expand your tiny world”, this is more like “watch your tiny world expand”.
- MP4G 2010: good example of an extremal solution motivated by greedy algorithmic heuristics.
- Russia 2004: Somewhat different in flavor than rest of the problems. This is like the first line of the intro, literally - zoom into a tiny portion.
- USA TST 2017: A five pointer on DCW and a very nice portrayal of local philosophy indeed.