Please turn on javascript in your browser to play chess.
Science Forum

Science Forum

  1. 02 Nov '14 23:02
    Given that a few people seem interested in solving more problems in
    elementary mathematics, here's another one (which I recall with nostalgia):

    Let a convex polygon with N sides (N>3) have all its diagonals constructed,
    dividing it into interior regions. What's the maximum number M of interior regions?

    Advice: Recreational mathematics should be fun, so I don't want anyone to
    waste many hours of time on this problem. If you think about the problem
    in the right way, you could solve it within a few minutes. But there seem to
    be various tempting ways to go astray. You could start by playing around
    with specific cases when N is small (if N=4, M=4) to get an intuitive sense of
    how quickly M increases when N does. You could conjecture a solution and
    attempt to prove it through mathematical induction. You could ignore this.

    As usual, I would ask that people rely only upon their own brains and not
    attempt to look up the solution elsewhere. I used to explain the solution
    in a lecture (which is unavailable as a video, alas, on YouTube), and I expect
    that the problem and its solution have been published in various places.
    Good luck to everyone who cares enough to make an honest effort.
  2. Standard member DeepThought
    Losing the Thread
    02 Nov '14 23:22
    Originally posted by Duchess64
    Given that a few people seem interested in solving more problems in
    elementary mathematics, here's another one (which I recall with nostalgia):

    Let a convex polygon with N sides (N>3) have all its diagonals constructed,
    dividing it into interior regions. What's the maximum number M of interior regions?

    Advice: Recreational mathematics should be fun ...[text shortened]... n published in various places.
    Good luck to everyone who cares enough to make an honest effort.
    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?
  3. 02 Nov '14 23:56
    Originally posted by DeepThought
    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>, ...[text shortened]... losed by the set of lines {<p, q> | 0 < p,q < N} where the exterior lines form a convex polygon?
    A diagonal may be defined as a line segment constructed (apart from the
    polygon's original edges) between any two vertices of the polygon.
    In the interest of further clarity, all diagonals constructed will lie completely
    within the polygon's interior. (Don't worry about anything exterior.)
    You may make the simplifying assumption that the polygon's regular if that helps.

    For example, if N=5, M=11. A pentagon has at most 11 interior regions.
  4. Standard member DeepThought
    Losing the Thread
    03 Nov '14 02:52
    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.
  5. Standard member DeepThought
    Losing the Thread
    03 Nov '14 03:21
    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.
  6. 03 Nov '14 04:10
    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"
    --DeepThought

    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"
    --DeepThought

    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"
    --Wikipedia

    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!
  7. Standard member DeepThought
    Losing the Thread
    03 Nov '14 04:43
    Originally posted by Duchess64
    "F = (N-1)(N-2)/2 + N(N-1)(N-2)(N-3)/24"
    --DeepThought

    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. ...[text shortened]... by other related problems?

    Congratulations to DeepThought for arriving at the correct answer!
    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.