IMO 1998 SL 26

Origin: IND

Problem

In a contest, there are m candidates and n judges, where n \geq3 is an odd integer. Each candidate is evaluated by each judge as either pass or fail. Suppose that each pair of judges agrees on at most k candidates. Prove that k m \geqn−1 2n .

Solution

Put n = 2r + 1. Since each of the
n  pairs of judges agrees on at most two candidates, the total number of agreements is at most k
n  . On the other hand, if the ith candidate is passed by xi judges and failed by n−xi judges, then the number of agreements on this candidate equals xi  + n −xi  = x2 i + (n −xi)2 −n \geqr2 + (n −r)2 −n = (n −1)2 . Therefore the total number of agreements is at least m(n−1)2 , which im- plies that k n  \geqm(n −1)2 , hence k m \geqn −1 2n . Remark. The obtained inequality is sharp. Indeed, if m =
2r+1 r  and each candidate is passed by a different subset of r judges, we get equality. A similar example shows that the result is not valid for even n. In that case the weaker estimate k m \geq n−2 2n−2 holds.