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.
