Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • The happy ending problem

      Marianne Freiberger
      7 November, 2016
      5 comments

      The happy ending problem is one of those mathematical questions that are quite easy to explain but have as yet defied all attempts to answer them. Some of the best mathematicians in the world have put their minds to it, to no avail. It concerns points drawn on a piece of paper and the figures you can create by connecting them up.

      Let's start with three points, drawn on a piece of paper, that don't all lie on a line. You can always connect them up to form a triangle which has the three points as its corners:

      Triangles

      Three points in the plane form a triangle (as long as they don't lie on the same line).

      What happens when you have four points (with no three of them lying on the same line)? Connecting them you can create a four-sided figure (called a quadrilateral) which has the four points as its corners:

      Quadrilaterals

      Some quadrilaterals.

      But depending on how the points are distributed, the quadrilateral might look a bit odd (like the centre one in the image above) containing dents and spikes and not at all resembling the neat and regular rectangle that first springs to mind when we think of four-sided figures. So let's impose a further restriction. Let's see if we can draw a convex quadrilateral with our four points, that is, one in which all internal angles are at most 180 degrees. This ensures the shape contains no corners that are "pushed inwards", creating a dent. The quadrilateral below is not convex, but the left and right ones in the figure above are.

      Non-convex quadrilateral

      A non-convex quadrilateral.

      Some simple examples show that given four points, you can't always draw a convex quadrilateral:

      Non-convex quadrilaterals

      Given four points, it's not always possible to connect them up to form a convex quadrilateral.

      Things change, though, when you add one more point. When you have five points drawn on a piece of paper (without three of them lying on the same line), you can always connect four of them to form a convex quadrilateral. The extra point gives you just enough flexibility to do it. Here are some examples (you might actually be able to draw several different convex quadrilateral with the same five points):

      Quadrilaterals

      Given five points (with no three lying on the same line), you can always find a convex quadrilateral which has four of them as its corners.

      This result was named the happy ending theorem by the mathematician Paul Erdős, because two of his friends who worked on it, George Szekeres and Esther Klein, ended up getting married. You can see a sketch proof of this result below.

      Adding sides

      The obvious next question is how many points you need to ensure that you can connect five of them to form a convex pentagon (five-sided figure). The answer is 9 (without three of them lying on the same line). Here are two examples:

      Pentagons

      Given nine points (with no three lying on the same line), you can always find a convex pentagon which has five of them as its corners.

      To be sure you can draw a convex hexagon (six sides) you need 17 points. Here's an example:

      Hexagon

      Given 17 points (with no three lying on the same line), you can always find a convex hexagon which has six of them as its corners.

      How many points do you need to be sure you can draw a convex heptagon (7 sides), which has these points as its corners? The answer is that nobody knows. The same goes for 8, 9, 10 or any number n of sides. Erdős and Szekeres believed that given a natural number n≥3, the number of points you need to ensure you can connect n of them to form a convex n-sided polygon is 1+2n−2. The result is true for n=3 (triangles), as in that case 1+2n−2=1+23−2=1+2=3. It also works for n=4, n=5 and n=6, as 1+24−2=1+22=1+4=5, 1+25−2=1+23=1+8=9, and 1+26−2=1+24=1+16=17. But whether the result is true for n>6 is not known. Erdős and Szekeres were able to prove that the number of points you need to guarantee a convex n-sided polygon is always at least 1+2n−2 and they also proved that it is finite: in other words, by drawing enough points you can be sure that there'll be a convex n-sided polygon within them. What hasn't been proved is how much is enough.

      The happy ending problem illustrates an interesting phenomenon: if a system is large enough (e.g. sufficiently many points) then you can hope to find some order within it (e.g. convex figures), even if the system as a whole is disordered. It's a phenomenon studied by an area of maths called Ramsey theory. You can find out more in the Plus article Friends and strangers.

      Sketch proof of the happy ending theorem for n=4

      Suppose you have five points in the plane. Let's first suppose that three of these points can be connected up to form a triangle that contains the two remaining points, call them A and B, in its interior. The line that connects these two interior points cuts the triangle into two parts. One piece only contains one of the triangle's corners, and the other contains two: call these two corners C and D.
      Proof

      The triangle cut in two pieces.

      It's now not too difficult to convince yourself, using some elementary geometry, that the quadrilateral ABCD (see the figure below) has no interior angles greater than 180 degrees. This means that it is convex.
      Proof

      At least one point lies outside of the triangle.

      What if there isn't a triangle that contains two of the five points in its interior? Then at least one of them lies outside any triangle you form with three of the points (see the figure below). You can form a quadrilateral from the three points of the triangle and the outside point, and again it's not too hard to show that all the interior angles of that quadrilateral are less than 180 degrees, which means that it is convex.
      Proof


      About the author

      Marianne Freiberger is Editor of Plus.

      • Log in or register to post comments

      Comments

      Giorgio Antonelli

      7 November 2016

      Permalink

      Let's see if we can draw a convex quadrilateral with our four points, that is, one in which all internal angles are at most 180 degrees.

      I think 180 was meant to be 360.

      • Log in or register to post comments

      Rachel

      14 November 2016

      In reply to Error in article by Giorgio Antonelli

      Permalink

      The internal angles of any convex polygon are at most 180, otherwise it would be concave.

      • Log in or register to post comments

      puzzlemaker3

      18 January 2017

      In reply to Convex by Rachel

      Permalink

      No, each internal angle of any convex polygon is not at most 180 degrees. That would mean they could be 180 degrees. Every n-sided convex polygon has n internal angles, and each of them is less than 180 degrees. "At most" means "less than or equal to," and that is false here.

      • Log in or register to post comments

      danlboon

      19 June 2019

      In reply to Error in the article by puzzlemaker3

      Permalink

      I believe that a polygon with a 180 degree angle would still be considered convex. In general, a convex region is defined as a region where the line segment connecting any two points in he region falls entirely within the region. In any case, the Happy End problem was originally considering a set of points in the plane in "general position", which meant that no three points were co-linear. In such a case, there could be no 180 degree angles.

      • Log in or register to post comments

      Jay Hurley

      31 October 2022

      In reply to Convex Polygon by danlboon

      Permalink

      I think I solved this problem for 7-gon, and on the path to a provable formula for n-gon.

      • Log in or register to post comments

      Read more about...

      geometry
      Euclidean geometry
      happy ending problem
      polygon
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms