The Happy Ending Problem

Take five points on a page, no three of them in a straight line. Try as hard as you like to scatter them so that no four form the corners of a convex quadrilateral — a four-sided shape with no dent in it. You will fail. Every single time, some four of the five points line up into a convex shape.

This little fact was discovered in the 1930s by a group of young mathematicians in Budapest, among them Esther Klein, who first noticed the pattern, and George Szekeres, who worked with Paul Erdős to prove it in general. The story has a twist: Klein and Szekeres fell in love while chasing the proof and eventually married — which is why Erdős nicknamed it the Happy Ending problem.

But the cute love story hides a genuinely hard mathematical question. Five points always force a convex quadrilateral. How many points does it take to force a convex pentagon? A convex hexagon? A convex shape with $n$ corners? That question, asked almost a century ago, is still not fully answered.

Click anywhere on the canvas to drop points, one at a time. As soon as you have placed five points (no three in a line), press Find the convex quadrilateral and watch the computer highlight four of them that always form a convex shape.

<p class="hint">{{hint_para}}</p>
<svg id="canvas" class="canvas" viewBox="0 0 360 260" role="img" aria-label="{{canvas_label}}"></svg>
<div class="status" id="status">{{place_hint}}</div>
<div class="btns">
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.canvas { width: 100%; max-width: 360px; height: 260px; background: #f4f6f8; border: 1px solid #cdd9e3;
          border-radius: 8px; display: block; cursor: crosshair; touch-action: manipulation; }
.pt { fill: #1d3557; stroke: #fff; stroke-width: 1.5; }
.pt.used { fill: #e63946; }
.quad { fill: rgba(230,57,70,.15); stroke: #e63946; stroke-width: 2; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Drag points around and try again — place them in a cluster, in a near-line, in a star pattern. It doesn't matter how you arrange five points: four of them will always outline a convex quadrilateral. The demo checks every group of four points and stops at the first convex one it finds.

The five-point case is solved: any 5 points in general position contain 4 that form a convex quadrilateral, and 4 points are not always enough (place one point inside a triangle formed by the other three and no convex quadrilateral appears). This was settled by Klein, Erdős and Szekeres in the 1930s.

Erdős and Szekeres went further and defined $ES(n)$ as the smallest number of points (in general position) that is guaranteed to contain a convex polygon with $n$ vertices. They proved $ES(n)$ is always finite — no matter how large $n$ is, enough points will always force a convex $n$-gon, they just conjectured exactly how many:

$$ES(n) = 2^{n-2} + 1$$

• For $n = 4$: $2^{2}+1 = 5$ points — proved (the case above).
• For $n = 5$: $2^{3}+1 = 9$ points — proved (Erdős and Szekeres themselves, later confirmed exhaustively by computer search).
• For $n = 6$: $2^{4}+1 = 17$ points — proved in 2006, via an exhaustive computer-assisted case analysis.
• For $n \geq 7$: open. Nobody has proved or disproved the formula for any larger $n$. The best known bounds sandwich $ES(n)$ between roughly $2^{n + o(n)}$ below and $2^{n-2}+1$ above — a 2016 breakthrough by Andrew Suk showed the conjecture is "asymptotically almost true," but the exact value for $n \geq 7$ remains unknown.

Erdős, true to his habit of attaching cash prizes to open problems, offered $500 for a resolution of the general conjecture — one of many "Erdős prizes" still unclaimed decades after his death. This sits squarely inside Ramsey theory: the idea that any sufficiently large, sufficiently unstructured set of objects must contain some highly structured pattern, whether the objects are points, graphs, or numbers.

A puzzle about five dots might look like pure recreation, but the same reasoning shows up across mathematics and computing:

• Computational geometry: algorithms that build a convex hull, triangulate point sets, or detect convex substructures all lean on the same "some subset must be convex" reasoning.
• Ramsey theory: the Happy Ending problem is one of the founding examples of Ramsey-type results — guarantees that structure is unavoidable once a set is large enough, later generalized far beyond geometry.
• Extremal combinatorics: pinning down exact thresholds like $ES(n)$ is a template for a whole family of "how many objects force this pattern" questions.
• Robust statistics and pattern recognition: reasoning about which subsets of scattered data points are guaranteed to have a "nice" (convex) shape shows up when outlier-resistant shapes are extracted from noisy geometric data.

Understand why five points can't dodge a convex quadrilateral, and you've touched the same combinatorial machinery that powers geometric algorithms and decades of Ramsey-theoretic research.

Five points always hide a convex quadrilateral — that much has been certain since the 1930s, and the mathematicians who proved it fell in love doing so. But scale the question up, ask about convex hexagons, heptagons, or any $n$-gon, and the exact threshold $2^{n-2}+1$ is only confirmed up to $n = 6$.

For every larger $n$, the precise answer remains open, guarded by an unclaimed $500 prize. It's a rare kind of problem: simple enough to try with a handful of dots on a napkin, and stubborn enough that, decades later, nobody knows exactly where the next convex shape is guaranteed to appear.