Problem 2

In a competition, there are

a

contestants and

b

judges, where

b\ge3

is an odd integer. Each judge rates each contestant as either “pass” or “fail”. Suppose

k

is a number such that, for any two judges, their ratings coincide for at most

k

contestants. Prove that

\frac{k}{a}\ge\frac{b-1}{2b}

Step 3 of 4: Sum over contestants

Previous step Next step

In plain words

The lower and upper counts refer to the same $N$ .

N\ge a\left(\frac{b-1}{2}\right)^2

Detailed analysis

Summing the preceding lower bound over all $a$ contestants gives $N\ge a((b-1)/2)^2$ . Combining both estimates for $N$ yields $a(b-1)^2/4\le kb(b-1)/2$ .