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 1 of 4: Count agreements by pairs of judges

Previous step Next step

In plain words

Count the same objects from the judges’ side.

N\le k\binom b2

Detailed analysis

Let $N$ be the number of triples consisting of a contestant and an unordered pair of distinct judges who give the same rating. Every pair of judges agrees on at most $k$ contestants, so $N\le k\binom b2=\frac{kb(b-1)}2$ .