In my last video, I posed the following question:
If you take n points on a circle, then connect every pair of them with a line,
how many sections to these lines cut the circle into?
What was strange is that when n is less than 6, and when n is 10 for some reason,
the answer is always a power of 2, but for all other values of n,
the answer seems completely unrelated powers of 2. What love about this problem
is that it brings together many disparate concept: counting functions,
graphs, one of Euler's famous equations, and Pascal's triangle.
You might be wondering if changing the placement of points change the number of
sections
It actually can! For instance, watch how this small region in the middle
disappears if we adjust things so that three lines go through the same point.
But if we add the restriction that no three lines can go to the same point,
the number sections depends only on the number of points not their placement,
as you're about to see. I think it's fair to call this a hard problem
and in solving hard problems, it's a good idea to ask simpler questions about
the same setup.
In this case I have two questions for you: 1) How many lines are there?
and 2) At how many points to these lines intersect within the circle?
For the first question, every line corresponds uniquely with the pair of
points
and likewise every pair of points gives us a unique line.
Luckily, counting the number of pairs in a set
is common enough in math that we have specific notation for it:
"n choose 2" which we evaluate as n
times (n -1) divided by 2. To see where this formula comes from,
notice that you have n options for the first element of the pair,
which we multiply by the (n -1) remaining options for the second element.
But this would double count each pair so we divide by two.
For instance, when n equals 7, 7 choose 2 is 7 times 6 over 2,
or 21, so there are 21 pairs of points, and hence
21 lines. With, say, a hundred points
counting lines directly would be a nightmare, but we can compute it
as 100 choose 2, which is 100 times 99 divided by 2,
or 4,950. The number intersection points
is a bit more subtle. While every intersection point corresponds with a
unique
pair of lines, there are many pairs of lines that don't intersect within the circle,
so we can't just count the pairs of lines. What we can do,
though is associate each intersection point with a set of four point on the
circle
since this association goes the other way around, in that
every quadruplet of points gives a unique intersection point.
Just look at that, isn't that elegant? This means the number intersection points
is the same as the number quadruplets of our starting points.
The function "n choose 4" counts quadruplets in a set,
and we evaluate it by taking n times (n-1) times (n-2) times
(n-3)
all divided by 1 times 2 times 3 times 4. The derivation of this
formula is similar to that of n choose 2,
You multiply in the number of options you have for each successive entry,
Then divide by the extent to which you've over counted.
For instance, with n=4,
4 choose 4 is 1, and indeed there's just one intersection point.
6 choose 4 is 15, so when n=6 there are 15 intersection points.
And if n were 100, even though the prospect of counting intersection point
is horrifying
we can nevertheless deduce that there will be 3,921,225
of them. Now, how does this help us count sections in the circle,
you might ask. Well it will once we consider graphs
an Euler's formula. No, no, not function graphs, and not that e to the pi i stuff.
The word graph can also refer to a set of points,
referred to as "vertices", along with a set of lines connecting some of these points
which we call "edges". Notice if we count the number of vertices in this graph
then subtract the numbers edges, then add the number
region this graph cuts space into, along with that outer region,
we get 2.
If we do the same thing with this other graph...well...we get
2 again.
This isn't a coincidence, you could do this with any graph and as long as your
edges don't intersect each other
the answer is always 2. If edges could intersect,
then you could just change the number regions without changing the number of
vertices and edges,
so course it would be nonsense. This relation is known as
"Euler's Characteristic Formula", and it's easy to see where the name comes from
since "Euler's" is German for beautiful. If you're curious,
the reason we write "F" for the number regions is because the formula
traditionally refers to the number of vertices, edges and faces
of 3d polyhedra. In another video, I'll explain why this is true
but here let's just use it to solve our circle problem. Our set up is already a
graph
with n vertices and n choose 2 edges, one between each pair of points.
But we cannot apply Euler's characteristic formula directly, since
the edges intersect many times; n choose 4 times to be exact.
However, if we consider each intersection point
to be a vertex, meaning our original lines must be chopped up at these points,
and if we also include the segment of the circle connecting these points
as new edges, we have a graph perfectly suited for Euler's formula.
In particular the number regions in this picture
is the numbers edges in the new graph minus the number vertices
plus 2
Since our new graph retains the n original vertices,
and ads on another n choose 4 for intersection points, we replace the minus
V term
with minus n minus n choose 4. To find the number
edges, note that the intersection points can be seen as
adding two edges each, since each one takes 2 existing lines
and then cuts them into four smaller pieces.
For example, three lines intersecting at 2 points
would be cut into 3+2*2 equals 7 smaller pieces.
Four lines intersecting at three points would be cut into 4+2*3
equals 10 smaller pieces. And in our circle diagram
n choose 2 lines intersecting at n choose four points
are cut into n choose 2 plus 2 times n choose 4 smaller pieces.
plus another n for the circle segments we're now considering to be
edges.
Going back to our formula, we can replace the "E"
with n choose 2, plus 2 times n choose 4, plus n.
Combining like terms we see that our graph cuts the 2d plane
into 2 plus n choose 2 plus n choose 4 smaller pieces.
Since we're concerned with counting the regions inside the circle
we can disregard that outer region and write our answer as 1
plus n choose 2 plus n choose 4. Great!
We found the answer! But why on earth does this formula relate to powers of 2
for n less than 6, then again when n is 10?
It's not just a coincidence, it has to do with Pascal triangle.
Pascal's triangle is constructed like this: each term
is the sum of the two terms above it. If you add up each row,
you get a successive power of 2.
To convince yourself of this, notice that each term is
added into the following row twice, so the sum of each row should be twice the
sum of the row before it.
The function n choose k is closely related to this triangle,
in that the the kth entry of the nth row, where counting start at 0,
is always n choose k. For instance, to find 5 chose 3 in the triangle,
count down to the 0, 1, 2, 3, 4, 5th row,
then go in 0, 1, 2, 3. And indeed,
5 choose 3 is 10. This means that the answer to our circle problem
for n is the sum of the 0th, 2nd,
and 4th entires in the nth row of Pascal's triangle. For instance,
If n equals 5, we can see that we just have to add 1
10 and 5. Since each term is the sum of the two above it,
this is the same as adding the entire fourth row which we know is a power of 2.
Likewise for smaller values of n, the answer is going to be the sum of the
(n-1)st row.
And hence a power of 2. However,
when n = 6, and we will relate the terms to the fifth row,
notice that we're not adding the entire row since we missed that last term
so we only get 31. When n equals 10,
we're summing precisely half of the ninth row, so the answer is half of 2 to the 9th,
which is 2 to the 8th. So, to recap,
Turn our diagram into a graph suitable for Euler's characteristic formula
by adding all the intersection points as vertices and cutting up all the
edges
Next, count the number of lines and intersection points
by relating them to pairs and quadruplets of our starting points.
And, finally use Euler's formula to deduce the number of sections,
then relate this to powers of 2 using Pascal's triangle.