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

[anemone]

In a competition there are \(\displaystyle a\) contestants and \(\displaystyle b\) judges, where \(\displaystyle b \ge 3\) is an odd integer. Each judge rates each contestant as either "pass" or "fail". Suppose \(\displaystyle k\) is a number such that for any two judges their ratings coincide for at most \(\displaystyle k\) contestants. Prove \(\displaystyle \frac{k}{a}\ge\frac{b-1}{2b}\).

 

[I like Serena]

In a competition there are \(\displaystyle a\) contestants and \(\displaystyle b\) judges, where \(\displaystyle b \ge 3\) is an odd integer. Each judge rates each contestant as either "pass" or "fail". Suppose \(\displaystyle k\) is a number such that for any two judges their ratings coincide for at most \(\displaystyle k\) contestants. Prove \(\displaystyle \frac{k}{a}\ge\frac{b-1}{2b}\).

Suppose we have

Judge	1	2	3	4
Contestant
1	fail	fail	pass	pass
2	fail	pass	fail	pass
3	fail	pass	pass	fail

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.\(\displaystyle 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 \(\displaystyle N\) of the group (judge, judge, contestant) for which the two judges are distinct that rate the contestant the same. There are \(\displaystyle {b \choose 2}=\frac{b(b-1)}{2}\) pairs of judges in total and each pair rates at most \(\displaystyle k\) contestants the same, so we have \(\displaystyle N\le \frac{kb(b-1)}{2}\).Now, consider a fixed contestant \(\displaystyle X\) and count the number of pairs of judges rating \(\displaystyle X\) the same. Suppose \(\displaystyle x\) judges pass \(\displaystyle X\), then there are \(\displaystyle \frac{x(x-1)}{2}\) pairs who pass \(\displaystyle X\) and \(\displaystyle \frac{(b-x)(b-x-1)}{2}\) who fail \(\displaystyle X\), so a total of \(\displaystyle \frac{x(x-1)}{2}+\frac{(b-x)(b-x-1)}{2}\) pairs rate \(\displaystyle X\) the same.

But

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

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

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

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

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

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

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

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

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

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

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