Among six strangers there is always a triangle: 2^15 cases to check

R(3,3) = 6, the fifteen pairs give 32 768 colourings, and every one of them hides a triangle.

Statistics and data · Level: Classic result · Updated on 2026-11-10

Colour each of the lines joining six points red or blue. Somewhere in the result there is a triangle all of whose three sides are the same colour, and six is the smallest number of points for which that is guaranteed. The proof is the party argument: pick one person, who has five relations, and at least three of them are the same kind by the pigeonhole principle; if any two of those three are alike to each other you have your triangle, and if none of them are, those three are mutually unacquainted and you have the other one. The six people make 6 × 5/2 = 15 pairs (second link), so a machine can settle it by exhaustion in 2^15 = 32 768 cases (first link) — small enough that nobody has an excuse for not doing it, and the sharpness is checked by the five-cycle, a pentagon of red with a blue star inside it, which avoids both triangles on five points.

The next diagonal number, R(4,4) = 18, costs 2^153 colourings: eighteen points have 18 × 17/2 = 153 pairs between them (third link), and 2^153 is 1.1417981541648⋅10+46 (fourth), which is not a number you argue with by counting. Greenwood and Gleason got 18 in 1955 with a mixture of bounds and hand-checked cases; R(5,5), the first three colours of the same question, has been open since then, known only to lie in a narrow band that has moved a little in seventy years. Ramsey's own theorem, from 1930, was about the logical machinery underneath all of this, and was proved because it was needed for a question in the philosophy of mathematics — the certainty that any sufficiently large structure contains a large ordered piece of itself.

Answer

32768

How to read it

2^15 on the workbench: every two-colouring of the fifteen pairs of six people. The second link is the fifteen pairs themselves.

Source

Frank P. Ramsey, 'On a Problem of Formal Logic', 1930; R(3,3) = 6 is the party theorem, R(4,4) = 18 was proved by Greenwood and Gleason in 1955, and R(5,5) is still unknown

Work it in the calculator

These links open the right calculator with this problem's numbers already typed in. The line above is what the screen should show — check it yourself.

This is an independent third-party tool site. It is not affiliated with, sponsored by, or authorised by Casio, Texas Instruments or their distributors. Model names and product names are trademarks of their respective owners and appear here only to identify devices.

The keystroke sequences in these manuals were written from this site's own layout data — the same data the online calculator renders — plus publicly available product facts. Specifications and regional configurations are confirmed against the physical device and the manufacturer's most recent material.