In a competition there are a contestants and b judges, where b ≥ 3 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 k/a ≥ (b-1)/2b.
Solution
Let us count the number N of triples (judge, judge, contestant) for which the two judges are distinct and rate the contestant the same. There are b(b-1)/2 pairs of judges in total and each pair rates at most k contestants the same, so N ≤ kb(b-1)/2.
Now consider a fixed contestant X and count the number of pairs of judges rating X the same. Suppose x judges pass X, then there are x(x-1)/2 pairs who pass X and (b-x)(b-x-1)/2 who fail X, so a total of (x(x-1) + (b-x)(b-x-1))/2 pairs rate X the same. But (x(x-1) + (b-x)(b-x-1))/2 = (2x2 - 2bx + b2 - b)/2 = (x - b/2)2 + b2/4 - b/2 ≥ b2/4 - b/2 = (b - 1)2/4 - 1/4. But (b - 1)2/4 is an integer (since b is odd), so the number of pairs rating X the same is at least (b - 1)2/4. Hence N ≥ a (b - 1)2/4. Putting the two inequalities together gives k/a ≥ (b - 1)/2b.
© John Scholes
jscholes@kalva.demon.co.uk
26 Oct 1998
Last corrected/updated 20 Aug 03