Solve this contestant and judge problem?

Question

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 that (k/a) >= ((b-1)/2b) .

Answer 1

For a given single contestant, let p and (b-p) be the number of pass and fail votes respectively. The number of disagreements among all possible distinct pairs of judges is:

p(b-p)

The maximum (for b an odd integer) is easily seen to occur at (b+1)/2 or (b-1)/2 with the value in both cases being:

Max Disagreements = (b-1)(b+1)/4

That means the minimum number of agreements among all pairs (b(b-1)/2) of judges for this contestant is:

b(b-1)/2-(b-1)(b+1)/4 = (1/4)(b-1)^2

Now consider each distinct combination of two judges and one contestant (there are ab(b-1)/2 such combinations in all) and define S as the total number of agreements produced by this entire set. The above inequality directly tells us that (since there are a contestants in all):

S >= a(1/4)(b-1)^2

By hypothesis each pair of judges agree on at most k contestants, so:

S <= (b(b-1)/2)k

Putting the above two inequalities for S together gives:

a(1/4)(b-1)^2 <= S <= (b(b-1)/2)k
-->
(1/2)(b-1) <= bk/a
-->
(b-1)/2b <= k/a

which was to be demonstrated.

Answer 2

lim b→∞ ((b-1)/2b) = 1. So long as k/a>1, this is true. But if you have 190 contestants and 19 judges, I can't support this assertion; it would mean that two judges' ratings coincide for nearly every contestant.