So, if we plug in N, we get the total number of chords in the diagram.
Moser’s Circle Problem is a famous cautionary tale in math. It starts with a circle and two points on it which are connected with a line, dividing the circle into two regions. If a third point is added and connected to the previous two with two more chords, the circle is divided into four regions. Adding a fourth point and connecting it to the previous three results in eight regions, and adding a fifth point results in sixteen. Adding a sixth point connect it to all the previous ones results in one shy of a power of two. It depends on where the points are placed and if three lines never intersect each other, the problem is a tease as it looks like powers of two. To solve the problem, it is helpful to solve easier questions related to it, such as counting the total number of chords and points within the circle. The total number of chords corresponds to the number of distinct pairs of points, which can be calculated with the “n choose 2” function. To calculate the number of distinct pairs of items from a set of size N, you use the function N choose 2, which is calculated by multiplying N and N-1, then dividing by 2. For example, 7 choose 2 would be 7 times 6 divided by 2, which is 7 times 3 or 21.
Counting the number of intersection points in a circle is a bit trickier. Every intersection point is uniquely associated with a quadruplet of points on the exterior. To calculate the number of distinct ways to choose four items given N total choices, you use the function N choose 4, which is calculated by multiplying N, N-1, N-2 and N-3, then dividing by 4 factorial.
Using a very nice little fact about Planer Graphs, the number of regions the circle has been cut into is always two, regardless of the plane or graph you started with. You count up the number of vertices, subtract the total number of edges, then consider the number of regions the graph has cut the plane into, including the infinite outer region. It’s actually very fun to try this for yourself. Draw any graph, making 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. No matter what diagram you choose, the answer always works out to be two. More commonly, you would see this written as V - E + F = 2 since originally, the equation described the vertices, edges and faces of three dimensional polyhedra.
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 goes up by one 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 - E + 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 - V + 1.
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 the vertices. So, the total number of vertices here would not be N but N + N choose four 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 two 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 four plus two times three or 10.
And for the diagram we care about where we started off with N choose two separate lines and they chopped up at N choose 4 points in the middle, you would end up with N choose 2 + two times N choose 4 edges and actually there are few more than that. Because we are 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. Hence why the answer is always a power of two minus one.
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 $\binom{N}{4}$ intersection points and you also plug in the slightly larger expression for the new number of edges, $\binom{N}{2}$ plus $2 \times \binom{N}{4}$ plus $N$. 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 $\binom{N}{4}$ but subtracting another copy of $\binom{N}{4}$. When all the dust settles, the answer to the question is $1 + \binom{N}{2} + \binom{N}{4}$.
On the one hand, you’re done. You’ve 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 are not really done because that doesn’t scratch the itch. Why is it the case that this looks like powers of two and then fall short by just one? 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 $\binom{N}{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 zero. For example, if you count up to the $0, 1, 2, 3, 4, 5$th row and you count $N$ to the $0, 1, 2, 3$rd element, you see $10$. And indeed, $\binom{5}{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 + 1$ is $2$, $1 + 2 + 1$ is $4$. $1 + 3 + 3 + 1$ is $8$. And as you continue on, you always get powers of two. Maybe at this point, you’re little gun shy about jumping to conclusions about powers of two too quickly. But in this case, it’s a genuine pattern, there is no trickery being pulled. And there are a few ways that you can think about why there should be powers of two 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 ones 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 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 + \binom{N}{2} + \binom{N}{4}$. In the context of Pascal’s triangle, you could think about that as adding up the $0$th, $2$nd, and $4$th terms inside some row of that triangle. For instance, when $N$ is equal to five, it looks like adding up $1 + 10 + 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 five elements in the previous row, which in this case is adding up the entire previous row hence why it’s a power of two. Same deal for all the numbers that are five 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. Hence why the answer is always a power of two minus one. At the point where N = 6, the sum of the first five elements of the row does not cover the whole row, which is why it falls short by one. When N = 10, the sum of the first five elements of the ninth row is exactly half of that row, and due to the triangle’s symmetry, this means that the sum is also half of a power of two. As a challenge, one may try to prove if this is the last time a power of two is seen.
To summarize, the total number of chords and intersection points is equivalent to computing N choose 2 and N choose 4, which can be found using Euler’s formula. Connecting this to Pascal’s triangle gives a connection to the powers of two and why they break when they do.
The Summer of Math Exposition is happening again this year and provides an opportunity to create an online math explainer for cash prizes thanks to Jane Street. More details can be found at some.3b1b.co.