 Solution

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

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

Put

v = t (1 - t)

and

M = max_{i} β_{i}

. If

v = 0

the assertion is immediate. Otherwise, suppose

M < \frac{v l o g n}{2 n} .

Since

v \leq 1/4

, this makes

M \leq lo g n / (8 n)

, so

M

is sufficiently small to apply the maximum-influence logarithmic lower bound once

n

is large. That bound gives

n M \geq \sum_{i} β_{i} \geq \frac{2}{3} v lo g (1/ M) \geq \frac{2}{3} v (lo g n - lo g lo g n + lo g 8) .

For all sufficiently large

n

, the last quantity exceeds

v lo g n /2

, contradicting

n M < v lo g n /2

. The choice of sufficiently large

n

is independent of

t

. Therefore

i max β_{i} \geq \frac{1}{2} t (1 - t) \frac{lo g n}{n} .

 New to topics? Read the docs here!