Here are some problems which build towards extremal constructions using some kind of “dynamic” argument.

Problem. (Mediterrenean 2015) In a mathematical contest, some of the competitors are friends and friendship is mutual. Prove that there is a subset $M$ of the competitors such that each element of $M$ has at most three friends in $M$ and such that each competitor who is not in $M,$ has at least four friends in $M$.

Solution. It’s reasonable to attempt a greedy algorithm, but it’s quickly evident that it doesn’t work: adding a new person with less than four friends in $M$ could cause some existing member of $M$ to have more than 4 friends in $M$.

We will attempt to find some “extremal” assumptions that automatically guarantee the properties of $M$. We go back to the greedy algorithm earlier. In an ideal world, we would be able to remove the existing member with more than 4 friends. However, the worry here is that the algorithm now is not guaranteed to terminate, since we could add a person and remove a person and continue in some kind of cycle. This is not a problem because there is another monovariance at work. But consider this perspective: at each step we add at most 3 friendships each step or take away at least 4 friendships. If we have an ideal picture of exchanging the number of elements of $M$ for the number of friendships, we can see that in some sense we “losing” something gradually and eventually have to stop. This can be made concrete by considering a quantity like $|E| - (7/2)|V|$, where $V,E$ refer to the vertices and edges within $M$. Since this quantity always decreases, the algorithm terminates.

Problem. (ISL 2007 C2) A rectangle $D$ is partitioned in several ($\ge2$) rectangles with sides parallel to those of $D$. Given that any line parallel to one of the sides of $D$, and having common points with the interior of $D$, also has common interior points with the interior of at least one rectangle of the partition; prove that there is at least one rectangle of the partition having no common points with $D$’s boundary.

Solution. The official solution in the IMO shortlist booklet is basically case bash, which is rather unfortunate. Here’s a different idea: imagine tracing along the boundaries of the diagram (consisting of all sides of sub-rectangles). One way to isolate a rectangle is to just keep turning anticlockwise at the earliest opportunity. This doesn’t really help because we need an “interior” rectangle… so instead we will turn whichever way that doesn’t lead out into the boundary (which makes perfect use of the condition that no line cuts straight through all the rectangles). Eventually, because the number of vertices are finite, we will bound some non-empty region with the traced path, and clearly that contains a rectangle.

Problem. (ISL 2017 C1) A rectangle $\mathcal{R}$ with odd integer side lengths is divided into small rectangles with integer side lengths. Prove that there is at least one among the small rectangles whose distances from the four sides of $\mathcal{R}$ are either all odd or all even.

Solution. One comes up with this when slightly overinspired by the previous problem. First, impose a lattice grid onto the diagram: the condition that the distance of a rectangle to each side of $\mathcal{R}$ all have the same parity is simply that the rectangles have its sides oriented all clockwise or all anticlockwise. We can now imagine how an algorithm could help us out: we can start from the outer boundary (guaranteed to be oriented one way), and just “turn into” the interior, following the path until it comes back to the boundary or loops in on itself. Either way, we have obtained a smaller loop. If it happens that we cannot “turn into” the interior, simply reverse the direction of all arrows and repeat. Eventually we get to a loop that is a single rectangle, which is what we wanted.

Remark. It is curious that the official solution is a double counting one, since usually problems can only be solved by either global methods (like double counting) or local methods (like algorithmic). It is interesting to determine the differences (and the nuances).

Remark. There was a similar Russian problem that went like this:

You have a convex polygonal room painted blue on the inside. Suppose that for this polygon, no three of its diagonals intersect. Build a wall for each diagonal, and paint one side of each wall (the whole diagonal). Show that there is a room with only blue walls.

Remark. One of the things that make this argument work is that there is always guaranteed at least one way out of any point. The analogous statement for planar graphs is then: either some point has all in or all out edges, or there is some region that is oriented in a single direction.

Remark. There is a very vague interpretation in terms of winding numbers and vector fields: if the path integral along the exterior is 0 then we expect there to be a zero somewhere in the interior. So this “zero point” is in one indivisible region, which has the same property.

Problem. Given a graph such that every vertex has degree not less than 3, prove that there exists a (simple) cycle of even length.

Solution. Consider the longest path in the graph. Label the vertices $0,1,2,...k$. By extremal assumptions, all neighbors of 0 are already in the path, so two of them have the same parity.

Remark. This generalizes to showing that if every vertex has degree at least $k+1$, there exists a simple cycle of length divisible by $k$.

Exploration. Consider a spanning tree. We can fix a root and label each vertex with the distance to the root. The analogue of finding the longest path is the same as finding the “maximal” spanning tree (i.e. sum of distance to root is maximized). This forces every vertex to be connected to one of its ancestors. What kind of conclusions can be drawn?