 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2010/ii/paper-1/17f/a/solution

Codex  0 Created 2026-09-24 Updated 2026-10-14

R (s)

is the least

n

such that every red-blue edge coloring of

K_{n}

contains a monochromatic

K_{s}

. More generally let

R (s, t)

require a red

K_{s}

or blue

K_{t}

. The base cases are

R (1, t) = R (s, 1) = 1

. Given

R (s - 1, t) + R (s, t - 1)

vertices, select one vertex. Either it has at least

R (s - 1, t)

red neighbors or at least

R (s, t - 1)

blue neighbors. Applying the corresponding smaller problem and, when needed, adjoining that selected vertex gives

R (s, t) \leq R (s - 1, t) + R (s, t - 1) .

Induction and Pascal's identity now prove existence and

R (s) = R (s, s) \leq (s - 1 2 s - 2) \leq 2^{2 s - 2} < 4^{s} .

 New to topics? Read the docs here!