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 barely 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 hands 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 and 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 2". By definition, this counts the
number of distinct pairs 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 overcount. 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 21. And if
you count up the number of distinct pairs of 7 items, there are indeed 21 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 cords 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 4" 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 item,
leaving you with N minus 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 4 choose 4, everything cancels and you just get one and
indeed, there is a single intersection point in this diagram. If you calculate 6 choose 4,
it works out to be 15 and if 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 4 or just about four million intersection points somewhere in the middle.
You 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 Planer 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 plane or 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 common you would see this written as V - E + F = 2 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 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 them
vertices. So the total number of vertices here would not be N but N plus 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 there
chopped up at N choose 4 points in the middle, you would end up with N choose 2 plus 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. 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 4 intersection points and you
also plug in the slightly larger expression for the new number of edges, N choose 2 plus
2 times N choose 4 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 4 but
subtracting another copy of N choose 4 and when all the dust settles, the answer to the question
is 1 plus N choose 2 plus N choose 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 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 zero.
For example, if you count up to the zero, one, two, three, four,
fifth row and you count N to the zero, one, two, third element, you see ten. And indeed,
5 choose 3 is equal to ten. 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 one and then one plus one is two, one plus two plus one is four. One
plus three plus three plus one is eight. 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 one 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 plus N choose 2 plus N choose 4. In the context of Pascal's triangle, you could think
about that as adding up the zeroth, second, and fourth terms inside some row of that triangle.
For instance, when N is equal to five, 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 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. 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 five elements of that row, it doesn't cover the whole thing. It falls short specifically
by just one which is why we miss the power of two and why it falls short specifically by just one.
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 five elements of the ninth
row is exactly half of that row and because the triangle is symmetric, this means that when you
add them up, you exactly half of a power of two which itself of course is another power of two.
And as a challenge problem for you, I don't actually know if this is the last
time that you'll ever see a power of two. Maybe one of you out there who's
clever with diophantine 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 two 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 sometimes chalked
up to be coincidence still leaves room for satisfying understandings.
By the way, The Summer of Math Exposition is indeed happening again this year. If you have
any interest in making an online math explainer of some form, whether that's a video or an article or
anything else you dream up, the last two years have proven that this is a great way to get more
eyes on your work and also there are opportunities for cash prizes, thanks to the generosity of this
year's sponsor, Jane Street. You can find all the information you need at some.3b1b.co
and I'll also leave other relevant links in the description. So, do check them out. It
was a ton of fun the last two years and I'm very excited to see what people come up with this year.