 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/iii/paper-13/3/ii/solution

Codex  0 Created 2026-10-03 Updated 2026-10-06

μ_{r} = E X_{r} = (r n) 2^{- (2 r)}, L = lo g_{2} n .

Fix

0 < ε < 1

. At

r_{-} = ⌊(2 - ε) L ⌋

, the estimates

(r n) \geq (n / r)^{r}

and

r = O (L)

give

lo g_{2} μ_{r_{-}} \geq r_{-} L - \frac{r _{-} ( r _{-} - 1 )}{2} - r_{-} lo g_{2} r_{-} = (ε - \frac{ε ^{2}}{2}) L^{2} - O (L lo g L) .

This eventually exceeds

(9/5) L

. At

r_{+} = ⌈(2 + ε) L ⌉

, the upper bound

(r n) \leq n^{r}

instead gives

lo g_{2} μ_{r_{+}} \leq - (ε + \frac{ε ^{2}}{2}) L^{2} + O (L),

μ_{r_{+}} < n^{9/5}

. Moreover

\frac{μ _{r + 1}}{μ _{r}} = \frac{n - r}{r + 1} 2^{- r} < 1 (r \geq r_{+}),

so no later clique size can regain the threshold. The maximum defining

r_{0}

exists for sufficiently large

n

, since

μ_{2} = (2 n) /2 \geq n^{9/5}

then. We have

r_{-} \leq r_{0} < r_{+}

. Letting

ε

decrease to zero proves the asymptotic size:

r_{0} = (2 + o (1)) lo g_{2} n .

 New to topics? Read the docs here!