Originally posted by DeepThought
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 ...[text shortened]... 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.
"F = (N-1)(N-2)/2 + N(N-1)(N-2)(N-3)/24"
Apart from slightly confusing the issue by using the variable 'F' when I had
stipulated 'M' as the maximum number of the polygon's interior regions,
the answer is correct. The proof seems unnecessarily complicated to me,
and I don't have enough time now to check it, so I shall assume it's OK.
(I have grown indolent about almost everything mathematical.)
Yet I have this question.
"Recall Euler's formula on the plane, then F - E + V = 1"
I assume that you mean Euler's formula about planar graphs.
"Euler's formula states that if a finite, connected, planar graph is drawn
in the plane without any edge intersections ... then v - e + f = 2"
Why is there a difference between what you and Wikipedia state as Euler's
formula for planar graphs? Is Wikipedia defining something else as a 'face'?
Here's how I solved this problem:
First observe that, in order to have a maximum number of interior regions,
no more than two diagonals may intersect at any one interior point.
Now consider the polygon with all its diagonals constructed. Let's begin
by removing one diagonal and ask how many interior regions that removes.
*It's 1 + its number of intersection points with other diagonals.*
So when all the diagonals are removed, the number of interior regions
*removed* equals the total number of diagonals + the total number of
diagonal intersection points within the polygon. We must keep in mind that
leaves one interior region--the original one--of the polygon, so we must add
1 to the number of diagonals + the number of diagonal intersection points.
M = 1 + A (number of diagonals) + B (number of diagonal intersection points)
Given that each diagonal is defined by two non-adjacent vertices, A = N(N-3)/2.
Given that each diagonal intersection point is corresponds to four vertices,
B = C(N 4) meaning N(N-1)(N-2)(N-3)/4! (a basic combinatoric concept)
1+A=(N-1)(N-2) so we get
M = (N-1)(N-2) + N(N-1)(N-2)(N-3)/24 or (using combinatorial notation)
M = C((N-1) 2) + C(N 4) (RHP text makes it hard to use normal notation)
Now about the heuristics of problem-solving:
If someone could not see what I did (above), one could make the plausible
conjecture that M is a polynomial of the fourth degree, which could be
corroborated by the N's apparent rate of increase in cases where N is small.
I wonder why you began by declaring 'We need to know two sums' since
that does not seem (to me) directly related to the nature of this problem.
Did you conclude that after being influenced by other related problems?
Congratulations to DeepThought for arriving at the correct answer!