The video explains Moser’s circle problem: placing n points on a circle and drawing all chords between them partitions the interior into a certain number of regions. For the first few n (2 → 2 regions, 3 → 4, 4 → 8, 5 → 16) the counts look like powers of two, but at n = 6 the pattern breaks, giving 31 regions (one less than 2⁵).
The exact number of regions is derived by treating the diagram as a planar graph whose vertices are the original n points plus all interior intersection points of chords. The number of intersection points equals C(n,4) (choose 4 points, whose two diagonal chords cross). The number of chord segments (edges) equals C(n,2) (original chords) plus twice the number of intersections (each intersection splits two chords into four pieces) plus the n arcs of the circle itself. Applying Euler’s formula v − e + f = 2 (and discarding the unbounded face) yields
\[
\text{regions}=1+\binom{n}{2}+\binom{n}{4}.
\]
Connecting this expression to Pascal’s triangle shows that for n ≤ 5 the sum 1 + C(n,2) + C(n,4) equals the sum of an entire previous row, hence a power of two. Starting at n = 6 the sum omits the last element of that row, falling short by exactly 1; at n = 10 it again hits a power of two because the selected terms sum to half of a symmetric row.
Thus Moser’s circle problem illustrates how a tempting pattern can fail without proof, while also revealing a deeper combinatorial reason behind the initial powers‑of‑two behavior.
1. Moser's circle problem asks for the number of regions formed when all chords connecting n points on a circle are drawn.
2. With 2 points the circle is divided into 2 regions.
3. With 3 points it is divided into 4 regions.
4. With 4 points it is divided into 8 regions.
5. With 5 points it is divided into 16 regions.
6. With 6 points it is divided into 31 regions (one less than 2⁵).
7. The total number of chords equals \(\binom{n}{2}\).
8. The number of interior intersection points (assuming no three chords meet) equals \(\binom{n}{4}\).
9. For any planar graph, Euler’s formula states \(V - E + F = 2\), where V is vertices, E edges, and F faces (including the outer infinite region).
10. Treating the original n points and the interior intersection points as vertices gives \(V = n + \binom{n}{4}\).
11. After splitting each chord at its intersection points, the number of edges becomes \(E = \binom{n}{2} + 2\binom{n}{4} + n\) (the extra n accounts for the circular arcs).
12. Applying Euler’s formula and excluding the outer region yields the number of regions \(F = 1 + \binom{n}{2} + \binom{n}{4}\).
13. This formula produces the sequence 1, 2, 4, 8, 16, 31, 57, 99, … for n = 0, 1, 2, 3, 4, 5, 6, 7, …
14. The expression \(1 + \binom{n}{2} + \binom{n}{4}\) corresponds to summing the 0th, 2nd, and 4th entries of row n in Pascal’s triangle.
15. For n ≤ 5, this sum equals the sum of the entire previous row of Pascal’s triangle, which is a power of 2.
16. At n = 6 the sum equals the sum of the first five entries of row 5, missing the final 1, giving \(2^5 - 1 = 31\).
17. At n = 10 the sum equals half of row 9, which is \(2^8 = 256\), another power of 2.
18. Thus the regions follow powers of two for small n and then deviate, with the deviation explained by the partial sums of Pascal’s triangle.