I’ve spent the last few days in Cambridge, helping to run the first camp to select the UK team for the International Mathematical Olympiad. We’ve had two 4.5 hour exams, replicating what six of the students will face in the final competition, which this year is held in Cape Town, and also lots of problem-solving sessions, introducing the students to different areas of mathematics relevant to the olympiad. For various reasons, I ended up choosing to discuss combinatorial problems involving points and lines with both sets of students. This is an area which is very popular with problem setters (witness for example Question Two at last year’s IMO in Colombia) but which, because of a lack of any real ‘theory’, is often not treated at these camps.
Anyway, 90 minutes is not a lot of time to solve a large number of problems, so I was interested in the notion of using the time to try to teach the students how to have the right sort of ideas to deal with these. Obviously if there were an easy way to teach people to have good ideas, mathematically or otherwise, life would be a whole lot more straightforward. So, given we can’t do that, the next best thing is to have lots of ideas of any kind, and to get practice at choosing which ones seem best reliably and quickly.
We have two problems to consider that are very similar. I’ll state the first one:
Q1: a strip of width w is the set of all points which lie on or between two parallel lines that are a distance w apart. Let S be a set of n>2 points such that any three can be covered by a strip of width 1. Prove that S can be covered by a strip of width 2.
This sort of thing comes up all the time in olympiad combinatorics and beyond. We have some condition that is local, in the sense that it only affects triples of points, but we want to show that the same condition works for all the points together.
The first step is to be clear about what we are looking for. We are looking for a strip, but we have also been given lots of strips, namely the strips covering each triple of points. So the natural thing to do is to construct the strip we are looking for from the strips we have.
The next observation offered was that we might want to combine two strips of width 1 to get a strip of width 2. This is certainly an idea, but a quick check makes you realise it isn’t a very promising idea. Why? Well unless two strips are parallel, it takes an infinite-width strip to cover their union. Ok, so although that wasn’t useful in itself, it now encourages us to focus on constructing the strip we are looking for from a single one of the strips we are given.
It’s not yet clear exactly how we are going to construct the desired strip from the strip we are given. We should be alive to the possibility that 2 might be a weak bound, and actually 
Maybe this doesn’t help so much. So perhaps we should think not about how to construct the big strip from the little strip, but instead, how to choose the little strip from the large set we have at our disposal. It is at this stage that I feel it is really important to use all the power at our disposal. In many combinatorics problems we have dealing with a discrete set like [n], where the roles of the labels are interchangeable, and so it can sometimes to be difficult to pick out a particular element. For example, it doesn’t matter for induction whether we take [n-1] then add {n} or start with [2,n] and add {1}. When the construction is geometric, we should use the geometry to make life easier in the construction. For example, if we want to induct, we could add the left-most point in some co-ordinate axes, or some point on the convex hull.
In our particular example, we are still trying to decide which strip to work with. If we consider the triple of points which is in some sense hardest to cover with a strip, this might be a sensible thing to work with. Now we need to decide what it means to be hard to cover a triangle with a strip. We might observe that if the triangle has an altitude of height h, we can certainly cover the triangle with a strip of width h. Further playing around convinces us that the minimum width of a strip required to cover a triangle is given by the shortest altitude. So our intuition that it’s hard to cover a triangle if it is large has been made a bit more concrete. We might also observe that we don’t have much flexibility for a strip if one of the lengths of the triangle is very long. For fixed strip width, as the length of the triangle gets large, the range of angles the strip could sit at (if it is possible at all) gets small.
This motivates considering the least convenient triangle as the one with maximal width and maximal height of altitude. We might try both orders, but certainly considering the triangle ABC such that d(A,B) is maximal among the set of points, and d(AB, C) is maximal once A,B are determined, is useful. The fact that we can cover ABC with one of the strips tells us from the above that 
The key ingredient here was using what we already had, realising it probably wasn’t going to be helpful to attempt to use *all* of what we already had, then coming up with a sensible way to choose which pre-existing strip to develop.
With this in mind, the next question seems a lot easier:
Q2: Given n points in the plane such that any three lie within some circle of radius 1, prove that *all* the points lie within some circle of radius 1.
Circulating round the room, there were lots of pairs of compasses out and various diagrams of interlocking circles snaking around pieces of A4. But after discussing Q1, suddenly all seems a lot more clear. Similarly to the previous case, we have a lot of circles, and we are looking for a circle. Conveniently, the circle we are looking for is even the same size as the circles we have.
So we need to choose which circle we already have is likely to be most useful. Suppose we have three points very close together. Then we know very little about the circle containing those points – it could be almost anything. By contrast, if we have three points which form a triangle with circumradius equal to 1, then there is in fact no choice about what the covering circle could be. So this is most likely to be useful. So we conjecture that we should consider the triangle with largest circumradius. In fact, this is a problem: if the triangle is obtuse, then the circumradius might actually be greater than 1, but the points still satisfy the condition. In that case, it makes sense to consider the circle with diameter given by the longest side of the triangle.
With that clarification, we now have a collection of circles with radii all 
Related articles
Eventually Almost Everywhere 