Moser’s Circle Problem

Now imagine a sequence, starting at 2, 4, 8, 16… well, what comes next? Most people’s guess would be 32, while looking at the sequence as 2n, 32 would be correct, but taking a deep dive into the fascinating world of mathematics reveals that the answer can also be 31. This problem is known as Moser’s Circle Problem. Imagine you have a circle, and you take 2 points on the circumference of that circle, and draw a line between them, mathematically known as a chord. This divides that circle into 2 distinct regions. If you add one more point on the circle and connect it to both those points, you get 4 separate regions. Add a fourth point and the circle will have 8 points, 5th point, 16 regions. Looks all like the power of 2 doesn't it? It sure is, until the 6th point, where it has 31, instead of the expected 32. To find the mathematical function to find the number of regions compared to the number of points on the circle, we have to first find the number of chords, and the number of points of intersection. Finding the number of chords is easy, counting the number of distinct pairs of points. For example, suppose there are 4 points, there are 6 chords, because chord 1 is from line AB, chord 2 from line AC, chord 3 from line AD, chord 4 from line BC, chord 5 from line BD and chord 6 from line CD. Each point has lines going to all other points. The function of this is called ‘n choose 2’. The mathematical formula for this is n(n-1)/2. Counting the number of intersection points however, is a bit harder. If you notice, every intersection point is related to a quadruplet of points. So now we need to calculate the number of distinct quadruplets. This is answered by the function ‘n choose 4’. The formula for that is, n(n-1)(n-2)(n-3)/1*2*3*4. Next we must use Euler’s  Characteristic Formula, as in V - E + F = 2. To explain this, I will use an example from math class, when you are solving for vertices, or edges or faces in class, somehow ‘2’ is always involved. To explain that, imagine a singular point that is 1 vertex and 1 face (the background), so 1 - 0 + 1 = 2, which is correct. If you add a vertex, you also add an edge. If you add a vertex and connect it with an edge to another 2 vertices, you get a face. So it is always equal to 2. Using simple algebra we can change it to F = E - V + 1. (1 instead of 2 as to not count the outer region). Now the issue is the Euler’s Formula is applied for non-intersecting graphs only, but ours does intersect. The trick is to think of the separate intersection points as vertices themselves instead of intersections, as in to create multiple smaller equations. So for that reason, vertices will be n + n choose 2. Ok so to chop up the lines into their individual intersections, think of each intersection as what started as 2 separate lines, and then turns it into 4 lines. So basically E = Original Lines + (Intersection Points 2). So back to Euler’s Formula, F =(n(n-1)/2 + (2n(n-1)(n-2)(n-3)/234) + n) - (n+n(n-1)(n-2)(n-3)/2*3*4) + 1. After cancellations, the final formula for this issue is F = 1 + (n(n-1)2)+(n(n-1)(n-2)(n-2)/2*3*4). Well that’s it, that is the reason why this sequence 1, 2, 4, 8, 16… is 31, not 32.