What maximum number of regions (bits of pizza) do you get if you mark n points on the circumference of a circle (edge of a pizza) and draw all the lines connecting them?
At first it looks as if you get 2n–1 regions. You get 1 region for 1 point, 2 regions for 2 points, 4 regions for 3 points, 8 regions for 4 points, 16 regions for 5 points.
Then you see that the pattern is more complicated: 31 regions for 6 points, 57 for 7 points, 99 for 8 points…
Claim: for n points on the circumference, we get nC4+nC2+1 areas. This is also equal to the sum of the first 5 elements of the (n−1) row of Pascal’s triangle. (nC4 means: number of ways of choosing 4 items out of n; nC2 = number of ways of choosing 2 items out of n).
First proof: If necessary, tilt the circle microscopically so that every meeting-point of lines (or of a line and the circumference) is at a different height.
Then every region in the circle has exactly one meeting-point as its lowest vertex, and every meeting-point which is inside the circle (rather than on the circumference) is the lowest vertex of exactly one region.
There are nC4 (n-choose-4: number of ways of choosing 4 items out of n) meeting-points inside the circle, because every four points on the circumference define such a meeting point. Each is a lowest vertex of one region (marked in red on the example below).
There are nC2 lines joining points on the circumference. The lower point-on-the-circumference of each of those lines defines an additional region of which it is the lowest vertex (marked in green).
And then there is one more region right at the bottom of the circle (marked in blue).
Therefore total regions = nC4+nC2+1
Since nC2=(n−1)C1+(n−1)C2 and nC4=(n−1)C3+(n−1)C4 and (n−1)C0=1, also:
total regions = sum from r=0 to r=4 of (n−1)Cr = sum of first 5 elements of (n−1) row of Pascal’s triangle. ◾
The second and third proofs use the table of differences of the number of regions.
If an = the number of regions with n points, this table tells us that:
Δ4an = 1
where Δan is defined as an+1−an
We could get this just by an argument of orders of magnitude. If there are n points, there are ½n(n−1) lines, i.e. of of the order of n2 lines. Therefore there are of the order of n4 meeting-points of lines. Since every region has a lowest point which is either a meeting-point of lines, or a meeting-point of lines and the circumference of the circle, and there are of the order of n2 meeting-points of lines and the circumference of the circle – the number of regions is O(n4).
So Δ4an = a constant, and the first few an tell us the constant is 1.
Second proof: Taking differences Δ is the discrete equivalent of what differentiation is for continuous functions.
Do the equivalent of integration. You can check that:
Δ-11 = n = nC1, Δ-1n = nC2, Δ-1nC2 = nC3, and Δ-1nC3 = nC4
So Δ4an=1 ⇒ an = nC4 + A nC3 + B nC2 + C nC1 + D
for some “constants of integration” A, B, C, D
Checking the first few values from the table, D=1, C=0, B=1, A=0, so
an = nC4 + nC2 + 1
Third proof: A little checking shows that although Δ is not a number, we can calculate on the right hand side as if it were. So:
=sum from r=0 to r=n of n-1 Cr.Δra1
=sum from r=0 to r=4 of n-1 Cr.Δra1
(since Δ5a1, Δ6a1, Δ7a1, etc. all equal zero)
=sum from r=0 to r=4 of n-1 Cr = sum of first 5 elements of (n−1) row of Pascal’s triangle.
The pizza problem is similar but easier. What is the maximum number of regions (pieces of pizza) you can get by cutting a plane (or a pizza) with n lines?
If necessary, tilt the plane microscopically so that every meeting-point of lines is at a different height.
Draw a horizontal line across the plane below all the meeting-points of lines.
Above the horizontal line, the regions which have a lowest point all have a unique lower vertex, and each vertex is the lowest point of a region.
So number of regions above the line = number of vertices = number of meeting-points of lines = nC2
Below the horizontal line, there are n+1 regions which have no lowest point.
Total number of regions = nC2 + n + 1 = sum of first three numbers in n’th row of Pascal’s triangle.