MathLabs

Problem 2

In a competition, there are a a contestants and b b judges, where b≥3 b\ge3 is an odd integer. Each judge rates each contestant as either “pass” or “fail”. Suppose k k is a number such that, for any two judges, their ratings coincide for at most k k contestants. Prove that ka≥b−12b\frac{k}{a}\ge\frac{b-1}{2b}.
Step 2 of 4: Count agreements for one contestant
Previous stepNext step
In plain words

The two rating groups are as balanced as possible at the minimum.

(ci2)+(b−ci2)≥(b−12)2\binom{c_i}{2}+\binom{b-c_i}{2}\ge\left(\frac{b-1}{2}\right)^2
Detailed analysis

For contestant i i , let ci c_i judges say “pass”. The number of agreeing judge pairs is (ci2)+(b−ci2)\binom{c_i}{2}+\binom{b-c_i}{2}. Since b b is odd, the minimum over the integer ci c_i occurs at ci=(b±1)/2 c_i=(b\pm1)/2 and equals ((b−1)/2)2((b-1)/2)^2.