This pattern breaks, but for a good reason | Moser's circle problem

This is a very famous cautionary tale in math, known as Moser's circle problem. Some of you may have seen this before, but what I want to do here is really explain what's going on. The way this starts is we take a circle and put two points on that circle and connect them with a line, that is a chord of the circle, and note that it divides the circle into two different regions. If I add a third point and then connect that to the previous two points with two more chords, then these lines all divide the circle into four separate regions. Then if you add a fourth point and connect that to the previous three, and you play the same game, you count up how many regions has this cut the circle into, you end up with eight. Add a fifth point to the circle, connect it to the previous four, count up the total number of regions, and if you're careful with your counting, you'll get a total of sixteen. Naturally, you can guess what might come next, but would you bet your life on it? Add a sixth point, connect it to all the previous ones, and if you carefully count up all the different regions, you end up not with the power of two you might have expected, but just one shy of it. Some of you might be raising your hand saying, doesn't it depend on where we put the points? For example, watch how this middle region disappears if I place everything nice and symmetrically around the circle. So yes, it does depend, but we're going to consider the cases where you never have any three lines intersecting with each other. This would be the generic case if you just choose n random points, almost certainly you'll never have three lines coincide, but setting aside the technical nuances, the problem is such a tease, it looks so convincingly like powers of two until it just barely breaks. And I have such a strange soft spot for this particular question. When I was younger I wrote a poem about it and also a song. And on the one hand it's kind of silly, because this is just one example of what the mathematician Richard Guy called the strong law of small numbers, summed up in the phrase, there aren't enough small numbers to meet the many demands made of them. But I think what I really like about this problem is that if you sit down to try to work out what is the real pattern, what's actually going on here, one, it's just a really good exercise in problem solving, so it makes for a nice lesson right here, but also it's not just a coincidence that it starts off being powers of two. There's a very good reason this happens. And it's also not a coincidence that you seemingly randomly hit another power of two a little bit later on the tenth iteration.

So we've got this pattern, and what you want to find is what function describes it. If you put n points on the boundary of a circle, and you connect them with all the possible chords, and you count how many regions the circle has been cut into, if the answer isn't a power of two, what is it? What function of n should we plug in? As always with math, problem solving rule number one if you're stuck is to try solving easier questions somehow related to the problem at hand. It helps you get a foothold, and sometimes those answers are helpful in the final question. In this case, two warm-up questions that come to mind are, how many total chords are there in this diagram, and at how many points within the circle do those chords intersect each other? The first question is relatively friendly. Every one of those chords corresponds uniquely with a pair of points on the circle. So effectively what you want to do is count how many distinct pairs of points are there. There's a function that does this, it's called n choose two. By definition, this counts the number of distinct pairs that you can choose from a set of n items, where order doesn't matter. To calculate it, the way you often think about it is that you have n choices for what your first item should be, and then you have n minus one options for what that second item should be, but simply multiplying those would over count, since for a given pair you would have two distinct ways to arrive at that pair. And remember, we don't care about order. To account for this, you divide by two. So for example, seven choose two would look like seven times six divided by two, which is seven times three, or twenty-one, and if you count up the number of distinct pairs of seven items, there are indeed twenty-one of them. Counting the number of intersection points in the diagram is a little bit trickier.

One idea might be that it should be the number of pairs of chords, since every intersection point comes from two different chords. However, that would not quite be right, because the association is not unique. You can find a pair of chords that don't intersect within the circle. As I said, it's a little bit tricky. I'd encourage you to try to pause and think about it for yourself, and if you do that, you give yourself a moment, maybe if you're a little bit lucky, here's one thing you might notice. Every intersection point is uniquely associated with a quadruplet of points on the exterior. For a given quadruplet, you look at the two kind of diagonal chords between them, and those will intersect within the circle, and it goes the other way around. Every intersection point corresponds with some quadruplet of points. So, what you want now is to count how many distinct ways can you choose four items given n total choices. This is very similar to the previous question. The function that answers it is called n choose four, which by definition counts the number of quadruplets from a set of size n, and the way to calculate it is similar to what we saw before. You would think of having n choices for your first item, leaving you with n minus one choices for the next two choices for the third item, and n minus three choices for the last item. That, however, would grossly overcount the total number, since all the different ways you can permute these four items would be counted separately. To account for that, you divide out by the extent to which you've overcounted, the number of permutations of four items, which looks like four factorial. For example, if you calculate four choose four, everything cancels and you just get one, and indeed there is a single intersection point in this diagram. If you calculate six choose four, it works out to be 15, and if you look at this diagram and you count them all up, you would notice there are indeed 15 different intersection points. And even if you would never want to count it up by hand, if we had a diagram that has 100 distinct points on the exterior, and we drew all of the connecting lines, you can conclude that there have to be 100 choose four, or just about four million intersection points somewhere in the middle. You've probably guessed this, but these are more than just warm-up questions.

They give us the necessary information to answer the question we care about. How many regions has the circle been cut into? The trick is to use a very nice little fact about planar graphs. Here I'm using the word graph in the sense of a diagram that has nodes and lines connecting them, and what it means to be planar is that you can draw this diagram without any of the lines intersecting with each other. In graph theory lingo, you typically call those nodes vertices and the lines connecting them edges, and the wonderful fact that we can leverage is that if you count up the number of vertices, and then you subtract the total number of edges, and then you consider the number of regions that this graph has cut the plane into, including that infinite outer region, then always, no matter what planar graph you started with, you get two. It's actually very fun. Try this for yourself. Draw any graph, make sure the lines don't intersect, and then count the number of vertices, subtract the number of edges, and count the number of regions that it's cut the plane into, and no matter what diagram you chose, the answer always works out to be two. More commonly you would see this written as v minus e plus f is equal to two, since originally the equation described the vertices edges and faces of three-dimensional polyhedra, and if you want to know why this magical fact is true, you can think about building up your graph from a trivial case, where you have a single node and no edges. So v would be equal to one, f would also be equal to one because of that infinite outer region, and e is zero, so the equation is obviously true. Then if you build up your graph one edge at a time, one thing that could happen is that for each new edge you introduce a new vertex. So e goes up by one, but v also leaving the equation balanced. But if a new edge doesn't correspond to a new vertex, meaning it's connecting to a pre-existing vertex, that means that it's enclosed a new region of space, so e goes up by one, but f also goes up by one, which again leaves the equation balanced. So as you build up some potentially complicated graph, v minus e plus f always stays fixed at two. This equation has a name, it's called Euler's characteristic formula, and I remember when I made a video about this a while ago, I had some dumb joke in there about Euler's being German for beautiful, and there were a decent number of comments that were like, you know, Euler is actually a person, I speak German, and it doesn't mean beautiful. Anyway, for our purposes, it gives us a tool for counting the number of regions that a planar graph has cut space into. Rearranging a little, you would take the number of edges minus the number of vertices plus two. This is exactly the tool that we want to understand our circle question, although in that case we don't care about the infinite outer region, so instead I'll write this as e minus v plus one. And at first you might complain, but we can't use Euler's formula in this case, because it only applies to planar graphs, and in our case the lines absolutely intersect with each other. We even counted how many times they intersect with each other. But the key is to treat this as a new graph, where those intersection points are themselves vertices, so the total number of vertices here would not be n, but n plus the n choose 4 total intersection points. That in turn chops up all of our chords into a larger number of edges, it's much more than just n choose 2, and initially it might seem really annoying and tricky to think about exactly how much it's chopped them up, but one way you can think about it is that every intersection point takes what started as two separate lines and then turns it into four lines. So in effect, each intersection point adds two more edges. For example, look at this simple diagram where we have three lines and two intersection points. The total number of edges after the chopping would look like three plus two times two, or seven. If you had four lines that intersected at three separate points, then the total number of little lines after chopping would be 4 plus 2 times 3, or 10. And for the diagram we care about where we started off with n choose two separate lines and they're getting chopped up at n choose four points in the middle, you would end up with n choose two plus two times n choose four edges. And actually there are a few more than that, because we're including the circle, we also need to count the n different arcs that sit on the outside of this diagram. So with all of that you have the information you need to answer the original question. Pulling up our variant of Euler's formula that counts the number of regions we'll plug in the expression for the number of vertices which is n plus the n choose four intersection points, and you also plug in the slightly larger expression for the new number of edges n choose two plus two times n choose four plus n, and the expression has a lot of nice cancellation, for example you are adding an n but also subtracting an n and you're adding two copies of n choose four but subtracting another copy and when all the dust settles the answer to the question is one plus n choose two plus n choose four. On the one hand, you're done, you answered the question. I give you one of these circle diagrams with n points on the boundary, and using this formula you can figure out how many regions the circle has been cut into. But of course we're not really done, because that doesn't scratch the itch.

Why is it the case that this looks like powers of 2 and then falls short by just 1? It's not just a coincidence, and the key to answering it is to consider Pascal's triangle. You know this triangle, it's the one where each term looks like a sum of the two different terms above it, and there are basically two facts we need to bring in about this triangle. The first is that every term inside this triangle looks like n choose k for some value of n and k. That is, the answer to the question of how many ways can you select a subset of size k from a set of size n is visible within this triangle. The way to think about it is by indexing the rows and columns starting from 0. For example, if you count up to the 0, 1, 2, 3, 4, 5th row, you count in to the 0, 1, 2, 3rd element, you see 10. And indeed, 5 choose 3 is equal to 10. If you've never seen this before and you want to know why it's true, there's a really lovely argument, I'll leave it up as an exercise. But moving on to the second thing that we need to know, notice what happens when you add up the rows of this triangle. You get 1, and then 1 plus 1 is 2, 1 plus 2 plus 1 is 4, 1 plus 3 plus 1 is 8, and as you continue on, you always get powers of 2. Maybe at this point you're a little gun-shy about jumping to conclusions about powers of 2 too quickly, but in this case it's a genuine pattern, there's no trickery being pulled. And there are a few ways that you can think about why there should be powers of 2 here. But one that I like is to think about how as you go from that first row to the next one, it's like the number 1 is sort of donating two copies of itself into the next row. Likewise, as you go from the second row to the third, each of those 1s is donating two copies of itself to the next row, and in general, as you go from one row to the next, each number donates two copies of itself to the one below. So as you add up the totals for each of these rows, it stands to reason that those totals double on each iteration. Circling back to our original question, think about what this means. The answer to our question looked like 1 plus n choose 2 plus n choose 4. In the context of Pascal's triangle, you could think about that as adding up the 0th, 2nd, and 4th terms inside some row of that triangle. For instance, when n is equal to 5, it looks like adding up 1 plus 10 plus 5. Now, because each of those numbers is the sum of the two above it, this is the same thing as adding up the first 5 elements in the previous row, which in this case is adding up the entire previous row, hence why it's a power of 2. Same deal for all the numbers that are 5 or less. When you situate this formula inside Pascal's triangle, and you relate it to the previous row, what you're doing is adding up the entirety of that previous row. The point at which this breaks is for n equals 6, because in that case, when you relate this to the previous row, adding up the first 5 elements of that row, it doesn't cover the whole thing. It falls short specifically by just 1, which is why we miss the power of 2, and why it falls short specifically by just 1. Also, notice what happens when we plug in n equals 10. Looking down at the 10th row, and relating those terms to the previous one, adding the first 5 elements of the 9th row is exactly half of that row, and because the triangle is symmetric, this means that when you add them up, you get exactly half of a power of 2, which itself of course is another power of 2. And as a challenge problem for you, I don't actually know if this is the last time you'll ever see a power of 2. Maybe one of you out there who's cleverer with diaphantine equations than I am can come up with some clever proof. Stepping back, to summarize, we started by counting the total number of

This is exactly the tool that we want to understand our circle question, although in that case we don't care about the infinite outer region, so instead I'll write this as e minus v plus one. And at first you might complain, but we can't use Euler's formula in this case, because it only applies to planar graphs, and in our case the lines absolutely intersect with each other. We even counted how many times they intersect with each other. But the key is to treat this as a new graph, where those intersection points are themselves vertices, so the total number of vertices here would not be n, but n plus the n choose 4 total intersection points. That in turn chops up all of our chords into a larger number of edges, it's much more than just n choose 2, and initially it might seem really annoying and tricky to think about exactly how much it's chopped them up, but one way you can think about it is that every intersection point takes what started as two separate lines and then turns it into four lines. So in effect, each intersection point adds two more edges. For example, look at this simple diagram where we have three lines and two intersection points. The total number of edges after the chopping would look like three plus two times two, or seven. If you had four lines that intersected at three separate points, then the total number of little lines after chopping would be 4 plus 2 times 3, or 10. And for the diagram we care about where we started off with n choose two separate lines and they're getting chopped up at n choose four points in the middle, you would end up with n choose two plus two times n choose four edges. And actually there are a few more than that, because we're including the circle, we also need to count the n different arcs that sit on the outside of this diagram. So with all of that you have the information you need to answer the original question. Pulling up our variant of Euler's formula that counts the number of regions we'll plug in the expression for the number of vertices which is n plus the n choose four intersection points, and you also plug in the slightly larger expression for the new number of edges n choose two plus two times n choose four plus n, and the expression has a lot of nice cancellation, for example you are adding an n but also subtracting an n and you're adding two copies of n choose four but subtracting another copy and when all the dust settles the answer to the question is one plus n choose two plus n choose four. On the one hand, you're done, you answered the question. I give you one of these circle diagrams with n points on the boundary, and using this formula you can figure out how many regions the circle has been cut into. But of course we're not really done, because that doesn't scratch the itch. Why is it the case that this looks like powers of 2 and then falls short by just 1? It's not just a coincidence, and the key to answering it is to consider Pascal's triangle. You know this triangle, it's the one where each term looks like a sum of the two different terms above it, and there are basically two facts we need to bring in about this triangle. The first is that every term inside this triangle looks like n choose k for some value of n and k. That is, the answer to the question of how many ways can you select a subset of size k from a set of size n is visible within this triangle. The way to think about it is by indexing the rows and columns starting from 0. For example, if you count up to the 0, 1, 2, 3, 4, 5th row, you count in to the 0, 1, 2, 3rd element, you see 10. And indeed, 5 choose 3 is equal to 10. If you've never seen this before and you want to know why it's true, there's a really lovely argument, I'll leave it up as an exercise. But moving on to the second thing that we need to know, notice what happens when you add up the rows of this triangle. You get 1, and then 1 plus 1 is 2, 1 plus 2 plus 1 is 4, 1 plus 3 plus 1 is 8, and as you continue on, you always get powers of 2. Maybe at this point you're a little gun-shy about jumping to conclusions about powers of 2 too quickly, but in this case it's a genuine pattern, there's no trickery being pulled. And there are a few ways that you can think about why there should be powers of 2 here. But one that I like is to think about how as you go from that first row to the next one, it's like the number 1 is sort of donating two copies of itself into the next row. Likewise, as you go from the second row to the third, each of those 1s is donating two copies of itself to the next row, and in general, as you go from one row to the next, each number donates two copies of itself to the one below. So as you add up the totals for each of these rows, it stands to reason that those totals double on each iteration. Circling back to our original question, think about what this means. The answer to our question looked like 1 plus n choose 2 plus n choose 4. In the context of Pascal's triangle, you could think about that as adding up the 0th, 2nd, and 4th terms inside some row of that triangle. For instance, when n is equal to 5, it looks like adding up 1 plus 10 plus 5. Now, because each of those numbers is the sum of the two above it, this is the same thing as adding up the first 5 elements in the previous row, which in this case is adding up the entire previous row, hence why it's a power of 2. Same deal for all the numbers that are 5 or less. When you situate this formula inside Pascal's triangle, and you relate it to the previous row, what you're doing is adding up the entirety of that previous row. The point at which this breaks is for n equals 6, because in that case, when you relate this to the previous row, adding up the first 5 elements of that row, it doesn't cover the whole thing. It falls short specifically by just 1, which is why we miss the power of 2, and why it falls short specifically by just 1. Also, notice what happens when we plug in n equals 10. Looking down at the 10th row, and relating those terms to the previous one, adding the first 5 elements of the 9th row is exactly half of that row, and because the triangle is symmetric, this means that when you add them up, you get exactly half of a power of 2, which itself of course is another power of 2. And as a challenge problem for you, I don't actually know if this is the last time you'll ever see a power of 2. Maybe one of you out there who's cleverer with diaphantine equations than I am can come up with some clever proof. Stepping back, to summarize, we started by counting the total number of chords and the total number of intersection points, which, by thinking about the right associations, is the same as computing n choose 2 and n choose 4. Bringing in Euler's formula, this let us get an exact closed form expression for the number of regions inside the circle. Then connecting that with Pascal's triangle gives us a very visceral connection with the powers of 2 and why they break when they do. So yes, Moser's circle problem is a cautionary tale about being wary of patterns without proof, but at a deeper level, it also tells us that what's sometimes chalked up to be coincidence still leaves room for satisfying understandings.