Probability Challenge: Prove $\frac{k}{a}\ge\frac{b-1}{2b}$

[anemone]

In a competition there are $$a$$ contestants and $$b$$ judges, where $$b \ge 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 $$\frac{k}{a}\ge\frac{b-1}{2b}$$.

 

[I like Serena]

In a competition there are $$a$$ contestants and $$b$$ judges, where $$b \ge 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 $$\frac{k}{a}\ge\frac{b-1}{2b}$$.

Suppose we have

[TABLE="class: grid, align: left"]
[TR]
[TD="align: right"]Judge[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]4[/TD]
[/TR]
[TR]
[TD="align: center"]Contestant[/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[TD="align: center"][/TD]
[/TR]
[TR]
[TD="align: center"]1[/TD]
[TD="align: center"]fail[/TD]
[TD="align: center"]fail[/TD]
[TD="align: center"]pass[/TD]
[TD="align: center"]pass[/TD]
[/TR]
[TR]
[TD="align: center"]2[/TD]
[TD="align: center"]fail[/TD]
[TD="align: center"]pass[/TD]
[TD="align: center"]fail[/TD]
[TD="align: center"]pass[/TD]
[/TR]
[TR]
[TD="align: center"]3[/TD]
[TD="align: center"]fail[/TD]
[TD="align: center"]pass[/TD]
[TD="align: center"]pass[/TD]
[TD="align: center"]fail[/TD]
[/TR]
[/TABLE]

So $a=3$ and $b=4$.
The maximum coinciding rankings for any two judges is $k=1$.

Substituting we get:
\begin{array}{lcl}
\frac{k}{a}&\ge&\frac{b-1}{2b} \\
\frac{1}{3}&\ge&\frac{4-1}{2\cdot 4} \\
\frac{1}{3}&\ge&\frac{3}{8} \\
0.333... &\ge& 0.375
\end{array}
But... this is a contradiction!

 

[anemone]

Hi I like Serena, thanks for participating and I want to tell you that the number of judges, i.e.$$b$$ should be an odd integer. Sorry...I will show the solution I found online and I hope you and others will enjoy reading it just as much as I do.First, let us count the number $$N$$ of the group (judge, judge, contestant) for which the two judges are distinct that rate the contestant the same. There are $${b \choose 2}=\frac{b(b-1)}{2}$$ pairs of judges in total and each pair rates at most $$k$$ contestants the same, so we have $$N\le \frac{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 $$\frac{x(x-1)}{2}$$ pairs who pass $$X$$ and $$\frac{(b-x)(b-x-1)}{2}$$ who fail $$X$$, so a total of $$\frac{x(x-1)}{2}+\frac{(b-x)(b-x-1)}{2}$$ pairs rate $$X$$ the same.

But

$$\frac{x(x-1)}{2}+\frac{(b-x)(b-x-1)}{2}=\frac{2x^2-2bx+b^2-b}{2}$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;= \frac {2(x^2-bx)+b^2-b}{2}$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;= \frac {2((x-\frac{b}{2})^2-\frac{b^2}{4})+b^2-b}{2}$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;= \frac{2(x-\frac{b}{2})^2+\frac{b^2}{2}-b}{2}$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=(x-\frac{b}{2})^2+\frac{b^2}{4}-\frac{b}{2}$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ge \frac{b^2}{4}-\frac{b}{2}$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ge \frac{1}{4}\left(b^2-2b\right)$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ge \frac{1}{4}\left((b-1)^2-1\right)$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ge \frac{1}{4}(b-1)^2-\frac{1}{4}$$

Since $$\frac{(b-1)^2}{4}$$ is an integer ($$b\ge 3$$ and b is odd integer), so the number of pairs rating $$X$$ the same is at least $$\frac{(b-1)^2}{4}$$. Hence, $$N\ge \frac{a(b-1)^2}{4}$$.

Putting the two inequalities of N together gives $$\frac{k}{a} \ge \frac{(b-1)}{2b}$$.