The absurd circle division pattern (updated) | Moser's circle problem

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments
Captions
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.
Info
Channel: 3Blue1Brown
Views: 775,838
Rating: undefined out of 5
Keywords: Mathematics, three blue one brown, 3 blue 1 brown, 3b1b, 3brown1blue, 3 brown 1 blue, three brown one blue
Id: YtkIWDE36qU
Channel Id: undefined
Length: 16min 51sec (1011 seconds)
Published: Sat Jul 01 2023
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.