Recreational Mathematics Problem

The post that was quoted here has been removed

A little clarification is needed, for me anyway. What do you mean by diagonal? The polygon is specified as being convex but not regular, let's take a pentagon as the first non-trivial example, if the vertices are labelled p1,p2,p3,p4,p5 and lines as <1,2> = p1 - p2, then the set of possible lines are {<1,3>, <1,4>, <2, 4>, <2,5>, <3,5>, <3,1>, <4, 1>, <4,2>, <5, 2>, <5, 3>} is this set what you mean by diagonals? In other words is the problem to find the maximum number of regions enclosed by the set of lines {<p, q> | 0 < p,q < N} where the exterior lines form a convex polygon?

We need to know two sums. S(n) = 1 + 2 + 3 + ... + n = n(n + 1)/2 which is easy to see. The other one is S(n) = 1 + 4 + 9 + ... + n². To do this sum first notice that S(n) < n³ since each term <= n² and there are n terms. So we look for a sum of the form An³ + Bn² + Cn + D. S(0) = 0 so that D = 0 and S(1) = A + B + C + D = A + B + C = 1. To get A and B we work out S(n + 1) in two ways:
S(n + 1) = S(n) + (n + 1)² = An³ + (B + 1)n² + (C + 2)n + 1
S(n + 1) = A(n + 1)³ + B(n + 1)² + C(n + 1) = An³ + (3A + B)n² + (3A + 2B + C) + A + B + C
Comparing coefficients we have A = 1/3, B = 1/2, C = 1/6 so that
S(n) = n(n+1)(2n + 3)/6

Given a polygon there are N exterior vertices, call then p1, ..., pn. Draw all possible lines between vertices, there are n vertices, n-1 target vertices per vertex and each line has two vertices to go between. This gives n(n - 1)/2 lines (including the exterior ones).
In drawing these lines we will have generated some extra vertices.

Pick two vertices pi, pj, the remaining vertices form two sets. There are (|i - j| - 1) vertices in one group and (n - |i - j| - 1) vertices in the other group. So the total number of lines drawable between vertices in one of each of these groups is the product of these. So the total number of new vertices is:

Vnew = ¼sum(i) sum(j != i) (n - |i - j| - 1)(|i - j| - 1)

The factor of 4 is because I've double counted twice over (once pairing vertices and once when considering the crossed line), inserting a cunningly chosen factor of 1 we get to:

Vnew = ¼ sum(r = 1 ... N - 1)sum(i = 1 ... N)sum( j !=i ) ð(|i - j| - r) (r - 1)(n - r - 1)
Vnew = ¼ sum(i) sum(r = 1 ... n - 1) (r - 1)(n - r - 1)

The summand no longer depends on i so that just gives a factor of n

Vnew = N/4 sum(r = 0 ... n - 2) r (n - 2 - r)
Vnew = N/4 [(n - 2) sum (r = 0 ... n - 2) r - sum(r = 1 ... n - 2) r²]
putting n - 2 into our earlier results for this and a little rearranging gives:

Vnew = n(n - 1)(n - 2)(n - 3)/24

which has the nice property that it correctly gives the internal vertices as zero for the cases n = 1, 2, and 3. Lets check N = 4, V = 4·3·2·1/24 = 1 as we'd expect. For a pentagon the result is V(5) = 5·4·3·2/24 = 5 which drawing the case confirms.

Each new vertex generates two new lines. Recall Euler's formula on the plane, then F - E + V = 1, F = faces, E = edges and V = all vertices, Vnew are the new vertices and Vinitial the number of vertices in the original polygon.

We have V = Vinitial + Vnew = N + Vnew and E = N(N - 1)/2 + 2*Vnew. So the number of faces is given by:

F = E - V + 1 = 1 + N(N - 1)/2 + Vnew - Vinitial.

Putting it all together and rearranging gives our final result:

F = (N - 1)(N - 2)/2 + N(N - 1)(N - 2)(N - 3)/24

As a quick check for N = 5 we then have F = 4*3/2 + 5*4*3*2/24 = 6 + 5 = 11.

A couple of points I forgot to make. I assumed that all the internal vertices are of order 4, this maximises the number of faces, in the case of polygons with an even number of vertices the regular ones have all their diameters meeting at the same point which changes the number of vertices and the number of faces. Assuming none of the vertices are degenerate makes the calculation easier as well as maximising the number of faces. This is only a problem (I think 😕) for the diagonals for even numbered polygons so the corrections are easy to work out.

I realised the hint you'd dropped when I got my expression for the number of "new" vertices. Apart from the overall factor of 24, which could be found by mapping to N = 4, the formula automatically zeros the first three cases, so the form (n - 1)(n - 2)(n - 3) is guessable. Comparison with the square and pentagon cases would give the correct n/24 prefactor. The difficulty is that to do the proof by iteration you still have to do the calculation I did above for the extra vertex. The only simplification is that you lose a trivial sum.

The post that was quoted here has been removed

You have a better method for calculating the number of generated vertices. I used brute force. I needed the two results for 1 + 2 + ··· + n and 1 + 2 + ··· n² to get the number of internal vertices. Your diagonal removing argument is a restatement of Euler's formula.

The right hand side of Euler's formula is the Euler character of the surface. If a two dimensional surface has g handles and p punctures then it's Euler character is 2 - 2g - p. A plane is topologically a sphere (g = 0) with a puncture (p = 1), to give F - E + V = 1. In this view a face with a puncture in it is not a face. This just saves me removing the extra face by hand. On a torus g = 1 and one gets F - E + V = 0.