# Probability Challenge

#### anemone

##### MHB POTW Director
Staff member
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}$$.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### MHB POTW Director
Staff member
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}$$.