Apparently, I have the same proof as the one on Kalva.. We count the cases when two judges agree on the result of a certain contestant. Let this number be $N$. On the one hand, we have $N\le k\cdot \binom n2=k\cdot\frac{n(n-1)}2$. On the other hand, if we show that $m\cdot \left(\frac{n-1}2\right)^2\le N$, we're done. Consider the whole thing a $0,1$-matrix having the judges as rows and the contestants as columns, and having $a_{ij}=0$ is judge $j$ fails contestant $i$ and $a_{ij}=1$ otherwise. It suffices to show now that for each of the $m$ columns there are at least $\left(\frac{n-1}2\right)^2$ pairs of equal numbers. Assume on a column there are $a$ $0$s and $b$ $1$s with $a+b=n=2k+1$. In this case the number of matching pairs on this column is $\frac{a(a-1)}2+\frac{b(b-1)}2=\frac{a^2+b^2}2-\frac n2$, which, knowing that $a+b$ is constant, is minimal when $|a-b|$ is minimal (i.e. when $a,b$ are as close to each other as possible), and this happens when $\{a,b\}=\{k,k+1\}$. If we compute the number of matching pairs on this column in this particular case, we get precisely $k^2=\left(\frac{n-1}2\right)^2$, so this is the minimal value. That is, on every column the number of matching pairs is $\geq \left(\frac{n-1}2\right)^2$. Thus, $N\geq m\cdot \left(\frac{n-1}2\right)^2$, Q.E.D.

Here is my proof which is same as above ... Consider the set $\mathcal{T} = \left \{ (j_p,j_q) ,c_k\right \}$, where two judges $j_p,j_q$ agree on the contestant $c_k$. So it follows that $|\mathcal{T}| \le k\binom{n}{2}$.

So we have $k\binom{n}{2} \ge | \mathcal{T}| = \sum_{k=1}^{m} \left ( \binom{a_k}{2} + \binom{n-a_k}{2}\right ) \ge \sum_{k=1}^{m}\frac{(n-1)^2}{4} = \frac{m(n-1)^2}{4}$ This gives $k\binom{n}{2} \ge \frac{m(n-1)^2}{4} \iff {\frac{k}{m}}\geq{\frac{n-1}{2n}} $. qed

Suppose a candidate had $x$ judges pass him and $n-x$ judges fail him. Then, there would be $\binom{x}{2} + \binom{n-x}{2}$ pairs of judges that agree. Summing across and taking the average, we see that \[k \ge \frac{m}{\binom{n}{2}} (\binom{x}{2} + \binom{n-x}{2})\] So it suffices to show that \[\frac{1}{\binom{n}{2}} (\binom{x}{2} + \binom{n-x}{2}) \ge \frac{n-1}{2n}\] This reduces down to \[(n-2x)^2 \ge 1\] which is true unless $n = 2x$, but we are given that $n$ is odd, so this cannot be the case. Hence, the inequality holds true.

The problem can be solved easily with incidence vectors: define $m$-component incidence vectors $v_{1},v_{2},\ldots,v_{n}$ where the $j$th component of $v_{i}$ is $1$ if judge $i$ awarded candidate $j$ a pass and $-1$ if not. We have $v_{i}\cdot v_{i}=m$ for all $i$. Furthermore as any pair of judges agree on at most $k$ candidates, they disagree on at least $m-k$ candidates. Two judges agree on the $l^{\text{th}}$ candidate if the $l^{\text{th}}$ components of their incidence vectors are the same (both 1 or $-1$) and disagree if they are different (one is 1 and the other is $-1$). Thus for $i\neq j$: $v_{i}\cdot v_{j}\leq k-\left(m-k\right)=2k-m$. Finally, consider $\sum_{i=1}^{n}v_{i}$: each of the $m$ components is the sum of $1$s and $-1$s and as $n$ is odd we must have that each component is odd so in particular not zero. Thus $\left(\sum_{i=1}^{n}v_{i}\right)^{2}\geq m$. Hence, \[ m\leq\left(\sum_{i=1}^{n}v_{i}\right)^{2} =\sum_{i=1}^{n}v_{i}^{2}+2\sum_{1\leq i<j\leq n}v_{i}\cdot v_{j} \] \[ \leq\sum_{i=1}^{n}m+2\sum_{1\leq i<j\leq n}\left(2k-m\right) =mn+n\left(n-1\right)\left(2k-m\right) \] \[ \Rightarrow 0\leq\left(n-1\right)\left[m+n\left(2k-m\right)\right] =\left(n-1\right)\left[2kn-m\left(n-1\right)\right] \] \[ \Rightarrow m\left(n-1\right)\leq 2kn \Rightarrow\frac{n-1}{2n}\leq\frac{k}{m}. \] Furthermore, we also get a bound for $n$ even, $n\geq4$: we have $\left(\sum_{i=1}^{n}v_{i}\right)^{2}\geq 0$ and by the same argument get the bound $\frac{k}{m}\geq\frac{n-2}{2\left(n-1\right)}$.

EDIT: Fakesolved it. Thanks AstrapiGnosis for pointing out.

rterte wrote: Assume that candidate $i$ has $x_i$ passes and $y_i$ fails. Then $x_i+y_i=n$. The number of pairs of judges agree with this evaluation is $\binom {x_1}{2} +\binom {y_i}{2}$. We have \[ \begin{aligned} 2\left(\binom {x_1}{2} +\binom {y_i}{2}\right)&=x_i(x_i-1)+y_i(y_i-1)\\ &=x_i^2+y_i^2-x_i-y_i\geq\frac{1}{2}(x_i+y_i)^2-(x_i+y_i)\\ &\Rightarrow 4\left(\binom {x_1}{2} +\binom {y_i}{2}\right)\geq (n-1)^2\quad (1) \end{aligned} \]On the other hand, due to the fact that there are $\binom{n}{2}$ pairs of judges, hence \[ k\binom{n}{2}\geq\sum_{i=1}^n\left(\binom {x_1}{2} +\binom {y_i}{2}\right) \]combine with $(1)$, we receive $4k\frac{n(n-1)}{2}\geq m(n-1)^2$. Hence $QED$ Your bound in (1) is incorrect; $n^2-n$ is not greater than $(n-1)^2$. Your bounding only uses Cauchy-Schwarz; as it turns out this problem is very tricky and a stronger bound is required. The Cauchy bound is just ever so slightly too weak.

Define $$ f(a,p_i)= \begin{cases} 1, \textnormal{if the pair $p_i$ agrees} \\ 0, \textnormal{otherwise} \end{cases} $$We have $$\sum_{i=1}^{n} \sum_{a=1}^{m} f(a,p_i) \leq k{n \choose 2}$$Now using $$\sum_{i=1}^{n} \sum_{a=1}^{m} f(a,p_i)=\sum_{a=1}^{m} \sum_{i=1}^{n} f(a,p_i)$$Suposing that $x$ judges pass and $n-x$ fail shuch that $x$ and $n-x$ are very closely, its well known ${x \choose 2} + {n-x \choose 2}$ is the fewest sum. Ergo, $$\sum_{a=1}^{m} \sum_{i=1}^{n} f(a,p_i)\geq m \left({x \choose 2} + {n-x \choose 2}\right).$$And now we have to proof that $$m \left({x \choose 2} + {n-x \choose 2}\right)\geq m{n \choose 2}\left(\dfrac{n-1}{2n}\right)$$But this computation give us $$(n-2x)^2\geq 1$$and the equality give us $n$ is an odd number. q.e.d.

Recently found next related question : If $m$ is an odd integer (instead of $n$) and each pair of judges agrees on at most $k$ candidates, then $\frac{k}{m}\geq\frac{n-2}{2n}$. $\textbf{Solution to original problem :}$ Consider $a_i$- number of judges which evaluated $i$-th candidate as pass (and $b_i$ same for fail). Then $a_i + b_i = n, \forall i$. So let $c_i$ be number of pairs of judges wich agrees on $I$-th candidate. So $c_i = \frac{a_i(a_i-1)}{2} + \frac{b_i(b_i-1)}{2}$. On other hand if $k<\frac{m(n-1)}{2n}$, then $\sum_i c_i < \frac{m(n-1)}{2n}\frac{n(n-1)}{2} = \frac{m(n-1)^2}{4}$. Easy to check that if $n$ is an odd integer, then $\min_{x\in\mathbb{N}}\left(\frac{x(x-1)}{2} + \frac{(n-x)(n-x-1)}{2}\right) = \frac{(n+1)^2}{8} + \frac{(n-1)^2}{8} - n/2$. So $m\left(\frac{(n+1)^2}{8} + \frac{(n-1)^2}{8} - n/2\right)\leq\sum_i\left(\frac{a_i(a_i-1)}{2} + \frac{b_i(b_i-1)}{2}\right) = \sum_i c_i < \frac{m(n-1)^2}{4}$, but $\frac{(n+1)^2}{8} + \frac{(n-1)^2}{8} - n/2 = \frac{(n-1)^2}{4}$ contradiction. And so $k\geq\frac{m(n-1)}{2n}$. $\Box$

$\textbf{Algebraical proof :}$ Consider algebra $\mathcal{A}$ of functions $\{1, 2,\ldots, m\}\to\mathbb{Z}$. Then decisions of $n$ judges can be seen as elements $a_j\in\mathcal{A}$, where $a_j\in \{-1, 1\}$. Consider morphism $\pi:\mathcal{A}\to\mathbb{Z}$, where $\pi(f) := \sum_i f(i)$. So one have that $\pi\left(\left(\sum_i a_i\right)^2\right) \leq mn + n(n-1)(2k-m)$. But $n$ is an odd integer, so $m\leq\pi\left(\left(\sum_i a_i\right)^2\right)$ and $m\leq mn + n(n-1)(2k-m)$. So $k\geq\frac{m(n-1)}{2n}$. $\Box$

I solved this problem as characterized in the Intermediate C&P textbook where there are $a$ contestants and $b$ judges (just to be clear about my usage of variables). $\bullet$ Let $N$ be the number of times that any two judges agree on the rating of a contestant. $\bullet$ Lets imagine that a $b\times a$ matrix represents the contestants and their respective ratings. Any entry $(i,j)$ in this matrix, (where $1\leq i\leq b$, and $1\leq j\leq a$) is 1 if the $j^{th}$ contestant has passed and is 0 if this contestant has failed according to the $i^{th}$ judge. In this scenario let, $i_1,i_2,i_3,\ldots i_a$, represent the number of 1's in columns 1 through $a$ respectively. $\bullet$ Let $\beta = \frac{b-1}{2}.$ $\bullet$ Let $f_k(x) = i_k(b-i_k).$ Lemma 1: $N = \sum_{k=1}^{a}\binom{i_k}{2} +\sum_{k=1}^{a}\binom{b-i_k}{2}$. Proof: The above formula holds, because, if there are $i_k$ 1's and $b-i_k$ in column $k$, any pairs of 0's or (non-inclusive) 1's correspond to a pair of judges that agree on the rating of a particular contestant. Summing over all $a$ columns yield the above formula. $\Box$ Lemma 2: $N\geq a\beta^2$. Proof: We start by maximizing $f_k(x)$. Since we can express $f_k(x)$ as a quadratic in terms of $i_k$ whose vertex form is $i_k(b-i_k)$, its roots are 0 and $b$, meaning that the optimal value of this function occurs when $i_k = b/2$. Making this substitution yields \begin{align*} f_k(x)&= \left \lfloor \left (\frac{b}{2}\right )^2 \right \rfloor,\\&= \left \lfloor \frac{(2\beta+1)^2}{4}\right \rfloor,\\&=\left \lfloor \frac{4\beta^2 +4\beta +1}{4}\right \rfloor,\\&= \beta^2+\beta.\end{align*} Note that we take the floor function, as $(b/2)^2$ is not integral. Consequently, we have the inequality $$\beta^2+\beta\geq i_k(b-i_k).$$ If we move $i_k(b-i_k)$ to the RHS, and add $\beta^2$ to both sides, this inequality becomes $$i_k(i_k-b)+2\beta^2+\beta\geq \beta^2, or $$ $$\binom{i_k}{2}+\binom{b-i_k}{2}\geq \beta^2,$$ which the reader can verify through some simple algebra. Thus, since $N$ is the sum of $a$ pairs of binomial coefficients of the form $\binom{i_k}{2}+\binom{b-i_k}{2}$, we can conclude in saying that $N\geq a\beta^2$. $\Box$ From the definition of $k$, we know that $N\leq k\binom{b}{2}$, as the ratings of any pair of judges can coincide at a maximum of $k$ contestants. Sunstituting $N = ac\left (\frac{b-1}{2}\right )^2$, for rational $c$ greater than or equal to 1, this inequality becomes \begin{align*} ac\left (\frac{b-1}{2}\right )^2 &\leq \frac{kb(b-1)}{2},\\\frac{ac(b-1)^2}{4}&\leq \frac{kb(b-1)}{2},\\2ac(b-1)^2&\leq 4kb(b-1),\\\frac{2ac(b-1)^2}{4b(b-1)}&\leq k,\\\frac{ac(b-1)}{2b}&\leq k,\\k&\geq c\cdot \frac{a(b-1)}{2b},\\\frac{k}{a}&\geq c\left (\frac{b-1}{2b}\right),\\\frac{k}{a}&\geq \frac{b-1}{2b},\end{align*} as desired. $\blacksquare$

Unless I'm insanely high, the straightforward solution with LoE+Global Jensen's works and makes the equality case explicit.

Nice problem. Here's my solution (Inspired from USAMO 2011 P6): We reframe the problem in set notation as follows:- Restated problem wrote: Let $X=\{a_1,a_2, \dots ,a_m\}$ be a given set. Suppose we make subsets $A_1,A_2, \dots ,A_n$ of $X$ such that they satisfy $$|A_i \cap A_j|+|A^c_i+A^c_j| \leq k \text{ } \forall 1 \leq i<j \leq n$$If $n$ is an odd integer $(n \neq 1)$, then show that the following inequality holds true- $$\frac{k}{m} \geq \frac{n-1}{2n}$$ NOTE: $A^c$ represents the complement of the set $A$. PROOF: Consider a $n \times m$ chessboard, with the $n$ rows representing $A_1,A_2, \dots ,A_n$ and the $m$ columns representing the $m$ elements of $X$. On each square of the board, we write either zero or one, according to the following criterion - $1$ is written on the intersection of the $i^{th}$ row and the $j^{th}$ column if and only if $a_j$ is present in $A_i$; otherwise $0$ is written. Let $d_i$ denote the number of times $1$ appears in the $i^{th}$ row, i.e. the number of sets in which $a_i$ is present. Then we have \begin{align*} \sum_{1 \leq i<j \leq n} |A_i \cap A_j|+|A^c_i+A^c_j| &=\sum_{i=1}^m \left(\binom{d_i}{2}+\binom{n-d_i}{2} \right) \\ &=\sum_{i=1}^m \left(\frac{d_i^2-d_i}{2}+\frac{(n-d_i)^2-(n-d_i)}{2} \right) \\ &=\sum_{i=1}^m \left(\frac{n(n-1)}{2}+(d_i^2-n \cdot d_i) \right) \\ &=\frac{m \cdot n(n-1)}{2}-\sum_{i=1}^m d_i(n-d_i) \\ \end{align*}And using the condition given in the problem, we get that $$m \cdot \binom{n}{2}-\sum_{i=1}^m d_i(n-d_i) \leq k \cdot \binom{n}{2} \Rightarrow \frac{k}{m} \geq 1-\frac{\sum_{i=1}^m d_i(n-d_i)}{\binom{n}{2}} \text{ } (*)$$Now, note that $$\sum_{i=1}^m d_i(n-d_i)=\sum_{i=1}^m \frac{((n-d_i)+d_i)^2-((n-d_i)-d_i)^2}{4}=\sum_{i=1}^m \frac{n^2-(n-2d_i)^2}{4}$$This means that this expression takes its maximum value when $(n-2d_i)^2$ is minimum. As $n$ is odd, the minimum value of $(n-d_i)^2$ can not be less than $1$. This gives that $$\sum_{i=1}^m d_i(n-d_i) \leq \frac{n^2-1}{4} \Rightarrow \sum_{i=1}^m d_i(n-d_i) \leq \frac{n-1}{2} \times \left(n-\frac{n-1}{2} \right)$$$$\Rightarrow \sum_{i=1}^m d_i(n-d_i) \leq \binom{n}{2}-\left(\frac{n-1}{2} \right)^2 \Rightarrow 1-\frac{\sum_{i=1}^m d_i(n-d_i)}{\binom{n}{2}} \geq \frac{2}{n(n-1)} \times \left(\frac{n-1}{2} \right)^2$$Combining this inequality with $(*)$, we get our final result as shown below $$\frac{k}{m} \geq 1-\frac{\sum_{i=1}^m d_i(n-d_i)}{\binom{n}{2}} \geq \frac{n-1}{2n} \text{ } \blacksquare$$

Consider the total number of agreements by pairs of judges on a candidate, over all possible pairs of judges and over all possible candidates. Fix a candidate $d$. If $x_d$ judges approve the candidate, and $n-x_d$ disapprove, we have $\tbinom{x_d}{2}+\tbinom{n-x_d}{2}$ agreements. Now fix a pair of judges. We can have at most $k$ agreements, whence we have at most $k\tbinom{n}{2}$ agreements. Therefore, \[ \sum_{d=1}^m \binom{x_d}{2}+\binom{n-x_d}{2} \le k\binom{n}{2}. \]We will now apply smoothing. Let $x<y$ be positive integers and $0<\epsilon \ll 1$. Since \[ \binom{x}{2}+\binom{y}{2} = \frac{x^2+y^2}{2}-\frac{x+y}{2},\]then \[ \binom{x+\epsilon}{2}+\binom{y-\epsilon}{2}=\frac{x^2+y^2+2\epsilon(x-y)}{2}-\frac{x+y}{2} \le \frac{x^2+y^2}{2}-\frac{x+y}{2} =\binom{x}{2}+\binom{y}{2}.\]Note that we have ignored the order two $\epsilon$ terms since we can take $\epsilon$ to be sufficiently small. Then, since $n$ is odd, by smoothing we have \[ \binom{x_d}{2} + \binom{n-x_d}{2} \ge \binom{\frac{n-1}{2}}{2}+\binom{\frac{n+1}{2}}{2}.\]Summing, \[ m\left(\binom{\frac{n-1}{2}}{2}+\binom{\frac{n+1}{2}}{2}\right) \le k\binom{n}{2}, \]so \[ \frac{k}{m} \ge \frac{\binom{\frac{n-1}{2}}{2}+\binom{\frac{n+1}{2}}{2}}{\binom{n}{2}} = \frac{(n-1)(n-3)+(n+1)(n-1)}{4n(n-1)}=\frac{n-1}{2n}.\]

What exactly is "smoothing"?

twinbrian wrote: What exactly is "smoothing"? Smoothing is a technique used to minimize or maximize a function of some variables by pushing them closer together. In particular, we prove that if we push the variables closer together, then the value of the function increases (or decreases). This proves that the maximum (or minimum) is achieved when we have made the variables as close together as possible. Note that we can only minimize if the function is convex, and maximize if the function is concave. Think about a convex graph with some points on it. To minimize the function, we can intuitively see that we want to ``push'' together all the variables together at the critical point to minimize them. We can similarly see for maximizing.

Can someone point out what's wrong with this solution. I somehow got a stronger bound and didn't use $b$ is odd? Assume FTSOC that $$k<\frac{m(n-1)}{2n}$$Then, if $A$ is the total number of agreements, we must have $$A\le k\binom{b}{2}<\frac{a(b-1)^2}{4}$$Now, the expected number of agreements between any two judges is $\tfrac{a}{2}$. Thus, the expected value of $A$ is just $$\frac{a}{2}\binom{b}{2}$$Hence, it follows that there exists a scenario where $$A\ge\frac{a}{2}\binom{b}{2}=\frac{ab(b-1)}{4}$$But this contradicts $$A<\frac{a(b-1)^2}{4}$$

Let $n = 2n' +1$.Count the number of pairs of scores that agree. There are $\frac{n(n-1)}{2} k$ such pairs maximum. On the other hand for every student, we have at least $2m \frac{n'(n'-1)}{2}$ pairs of scores that agree.

Can someone confirm that this solution is right? The probability that a pair of judges agree on one candidate is $\frac{1}{2}$. By Linearity of Expectation, the expected number of contestants that a pair of judges agree on is $\frac{a}{2}$. This means that $k \ge \frac{a}{2}$, which means that $\frac{k}{a} \ge \frac{b-1}{2b}$.

Sorry for the bump, but @above is incorrect (seems way too simple to be true anyway). If we take $(m,n)=(6,3)$, then the following construction gives $k=2 < \frac{m}{2}=3$. PPPFFF PPFPPP FFPFPP

We can just assume that $k$ is the maximum number of coinciding votes among any two judges. It remains to bound $k$. Let $b = 2c + 1$. For any one contestant, if $n$ judge rate a ``pass'' and $k - n$ rate a ``fail'', then there are in total \[ \binom{n}{2} + \binom{b-n}{2} \ge \binom{c}{2} + \binom{c+1}{2} \]coinciding votes. Thus, over all $a$ contestants, there are at least $a\left(\binom{c}{2} + \binom{c+1}{2}\right)$ coinciding votes. Over $\binom{2c+1}{2}$ pairs of judges, by pigeonhole, it follows that \[ k \ge \frac{a}{\binom{2c+1}{2}}\left(\binom{c}{2} + \binom{c+1}{2}\right) \] Thus, the result follows since \[ \frac{1}{\binom{2c+1}{2}} \left(\binom{c}{2} + \binom{c+1}{2}\right) = \frac{2c}{2(2c+1)} \]

Solved on OTIS Excerpts where m and n are a and b. This is a standard double counting problem. Counting by judges, we see that $N\le \dbinom{b}{2}k$, and letting b=2k+1 we count by contestant, from which it is clear by smoothing (essentially the minimum for sum of a_i choose 2 is when all a_i are close as possible together, which is a well known smoothing identity, can someone confirm that I can state this in contest though, although the two items are easy algebra and we sketch out induction for in general) that at MINIMUM each makes $\dbinom{k}{2}+\dbinom{k+1}{2}=k^2$ judges agree, hence $N\ge a(\frac{b-1}{2})^2.$ Transitive property and simplifying fully yields the desired result. $\blacksquare$

This is a nice problem! To get an inequality, we consider the Maximum and Minimum of the # of pairs of judges that agree on certain participants, summed over once for each participant they cover. Maximum: k*(n choose 2), this is where each pair of judges gets the maximum number of participants they are allowed to agree on. Minimum: If a(i) is the number of pairs of judges which agree on the i-th participant, then this is (a(i) choose 2) + (n-a(i) choose 2) summed over all i. To minimize, we make a(i) and n-a(i) as close as possible, resulting in a(i) = (n-1)/2. Then this sum becomes m(n-1)^2/4. Write Maximum ≥ minimum, you get the desired inequality after some trivial manipulations.

Let $m=a, n=b$ Let ${j_n, j_m, c_q}$ be stuff Make $q$ constant Let a 1 be pass and a 2 be fail The number of commons is (# of 1s choose 2)+(# of 2s choose 2) Let $z$ be # of 1s and $y$ be # of 2s # commons is $\frac{z^2+y^2-z-y}{2}$ to minimize this, note that it equals $\frac{(z-0.5)^2+(y-0.5)^2-0.5}{2}$ and $z+y=b$, so the minimum value is when $z$ and $y$ are closer together so let $z=\frac{b-1}{2}$ and $y=\frac{b+1}{2}$. Then this becomes $\frac{b^2}{4}-\frac{b}{2}+0.25$, but then divide by ${b \choose 2}$ for each pair to get $\frac{b-1}{2b}$ so $k \ge a*\frac{b-1}{2b}$ and $\frac{k}{a} \ge \frac{b-1}{2b}$

⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ blueberryfaygo_1434 and yevinkang2.71 on top!!! For each candidate we know the number of pairs of judges with opinion $(\text{pass},\text{ fail})$ is $(0, n), (1, n-1), \ldots, (n, 0)$. Then the number of pairs of judges that share the same opinion for each candidate can be $\binom02 + \binom n2, \binom{1}{2} + \binom{n-1}{2}, \ldots, \binom{n}{2}+\binom02$. Claim: The smallest value in $\binom02 + \binom n2, \binom12 + \binom{n-1}{2}, \ldots, \binom{n}{2}+\binom02$ is $\binom{\frac{n-1}{2}}{2} + \binom{\frac{n+1}{2}}{2}$. (Remember that $n$ is odd.) Proof: Note that all of the sums can be written in the form $\binom{\frac{n-c}{2}}{2} + \binom{\frac{n+c}{2}}{2}$ with $c$ odd. Expanding, we get $\frac{n^2+c^2-2n}{4}$. Therefore, the minimum value is when $c=1$, so we're done. The minimum pairs of judges in agreement for each candidate is $\binom{\frac{n-1}{2}}{2} + \binom{\frac{n+1}{2}}{2}$, so the minimum average number of agreements across all pairs of judges is $$\frac{m \cdot (\binom{\frac{n-1}{2}}{2} + \binom{\frac{n+1}{2}}{2})}{\binom n2}$$. Then we know $$k \ge \frac{m \cdot (\binom{\frac{n-1}{2}}{2} + \binom{\frac{n+1}{2}}{2})}{\binom n2},$$and $$\frac{k}{m} \ge \frac{m \cdot (\binom{\frac{n-1}{2}}{2} + \binom{\frac{n+1}{2}}{2})}{m \cdot \binom n2} = \frac{n-1}{2n}.$$

For each judge $j_u$ $(1 \leq u \leq n)$, let $J_u = \{(c_1,r_1), (c_2,r_2), \cdots, (c_m, r_m)\}$ denote the judge's set of evaluations for each of the $m$ candidates, where $r_i \in \{\mathrm{Pass, Fail}\}$. We show the desired result by double counting on the total number of ordered pairs $(c_i,r_i)$ the judges pairwise share with one another. First, the given condition is equivalent to $$|J_u \cap J_v| \leq k \, \forall u,v.$$Since there are $\binom n2$ pairs of judges, the upper bound for the total number of ordered pairs is $$k \binom n2.$$We now consider the ordered pair of a contestant and their respective evaluation under the contestants' perspective, presenting the following lemma. Lemma: For a contestant receiving $\dfrac{n+x}{2}$ passes and $\dfrac{n-x}{2}$ fails (where $n,x$ are odd), the quantity $$\binom{\frac{n+x}{2}}{2} + \binom{\frac{n-x}{2}}{2}$$or the total number of pairs of the same evaluation given for the candidate is minimized when $x=1$. Proof. Expanding and simplifying the expression above yields $$\dfrac{n^2 - 2n + x^2}{4}$$and $n$ is fixed so obviously $x=1$ is the least odd value, miniziming the sum. $\blacksquare$ It follows that the minimum number of pairs of the same evaluation for all contestants combined is $$a \left(\binom{\frac{n+1}{2}}{2} + \binom{\frac{n-1}{2}}{2}\right)$$which is the lower bound. Therefore, we have $$a \left(\binom{\frac{n+1}{2}}{2} + \binom{\frac{n-1}{2}}{2}\right) \leq k \binom n2$$which expanding and rearranging gives the desired inequality. $\blacksquare$

For a single contestant, the smallest possible number of pairs of judges whose ratings coincide is $\binom{\frac{b-1}{2}}{2}+\binom{\frac{b+1}{2}}{2}=(\frac{b-1}{2})^2$. Therefore, we have to distribute $a(\frac{b-1}{2})^2$ pairs of coinciding ratings over $\binom{b}{2}$ pairs of judges. Since $\frac{a(\frac{b-1}{2})^2}{\binom{b}{2}}=\frac{a(b-1)}{2b}$, $k\ge \frac{a(b-1)}{2b}$ by Pigeonhole Principle, as desired.

We will double count the number of pairs $T$ of $(J_c, J_d, a)$ where judge $c$ and judge $d$ pass the same judgement on contestant $a$. From the perspective of the judges, $$T \leq k\binom{n}{2}$$From the perspective of the contestants, suppose that contestant $i$ passes $x_i$ times, then $$T=\sum_{i=1}^{m} \binom{x_i}{2}+\binom{n-x_i}{2}$$By Karamata's inequality we have that $\{x_i, n-x_i\}$ majorizes $\left \{\frac{n+1}{2}, \frac{n-1}{2}\right \}$ or $ \left \{\frac{n-1}{2}, \frac{n+1}{2}\right \}$ depending on whether $x_i<\frac{n}{2}$. Thus $$k\binom{n}{2} \geq T \geq m\left (\binom{\frac{n+1}{2}}{2} + \binom{\frac{n-1}{2}}{2} \right )$$ After expanding and manipulating we get the desired inequality $\frac{k}{m} \geq \frac{n-1}{2n}$.

I thought it was more natural to view in terms of the minimum distance (disagreements) $\ell = m-k$.

Anyway, this is just the Plotkin bound on binary codes with a minimum distance between each pair of codewords.

Version I solved wrote: 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 that \[ \frac ka \ge \frac{b-1}{2b}. \] We count the number $C$ of coinciding rating pairs; that is, triples $(B_1, B_2, A)$ where $B_1$ and $B_2$ are judges who have given the same rating to contestant $A$. From the problem statement, we have $$C \le k \cdot \binom{b}{2}.$$But at the same time, $$C \ge a(\binom{d}{2} + \binom{d+1}{2}) = ad^2$$where $b = 2d+1$, so $$\frac{a(b-1)^2}{4} \le k \cdot \binom{b}{2},$$and simplifying yields the result.

OTIS Version wrote: 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 that \[ \frac ka \ge \frac{b-1}{2b}. \] The key is to consider the number of instances two judges agree. Note that this is at most $\binom{b}{2}k$ by summing over choices of two judges and seeing how much they agree. By summing over contestants, and counting how many pairs of judges agree on them we get that this number is at least $a \left[ \binom{\tfrac{b-1}{2}}{2} + \binom{\tfrac{b+1}{2}}{2} \right] = \tfrac{a(b-1)^2}{4}$. Therefore $\tfrac{a(b-1)^2}{4} \le \tfrac{b(b-1)k}{2} \implies \tfrac{b-1}{2b} \le \tfrac{k}{a} .$

Let $n = 2l - 1$. Consider the number of triplets $\text{(judge, agreed candidate, judge)}$. There are $\binom{n}{2}$ ways to pick the judges, and at most $k$ ways to pick the agreed candidate, so: $$\text{the number of triplets} \leq k\cdot\binom{n}{2}$$ Each candidate faces $n$ decisions, say $x$ of these are passes, and $y$ of these are fails. So, there will be $\frac{x(x - 1)}{2} + \frac{y(y - 1)}{2} = \frac{x^2 + y^2 - n}{2}$ triplets for this candidate, which is minimised when $x, y$ are closest together (when $x = l$, $y = l - 1$), giving at least $(l - 1)^2$ triplets for each candidate. So, $$m(l - 1)^2 \leq \frac{kn(n - 1)}{2} \implies 2m(l - 1)^2 \leq k(2l - 1)(2l - 2) \implies \frac{k}{m} \geq \frac{l - 1}{2l - 1} = \frac{n - 1}{2n}$$

Consider a bipartite graph with sets $A$ of contestants and $B$ of judges, and draw an edge between $a_i \in A$ and $b_j \in B$ if $b_j$ passes $a_i$. Considering agreements between each pair of judges, clearly \[\text{Agreements} \leq \binom b2 \cdot k,\] but we can also notice \[\text{Agreements} = \sum_{a_i \in A} \left(\binom{\deg a_i}{2} + \binom{b-\deg a_i}{2}\right)\]\[\ge \sum_{a_i \in A} \left(\binom{(b-1)/2}{2}+\binom{(b+1)/2}{2}\right) = a \cdot \frac{(b-1)^2}{4}.\] Rearranging gives the desired inequality. $\blacksquare$

We are going to count the pairs $(C,J_1,J_2)$ where $J_1$ and $J_2$ are judges and they have the same opinion for Contestant $C$. Let $X$ be total number of such pairs. $\bullet$ Fix $(J_1,J_2)$ and obviously there are atmost $k$ options for $C$ so we get \[X \leq k \binom b2\]$\bullet$ Fix $C=C_i$ and let $p_i$ and $f_i$ denote its passes and fails respectively. Then we get that \[X=\sum_{i=1}^a \binom {p_i}2+\binom {f_i}2 \overset{\text{J-S}}{\geq} a \cdot \frac{b^2-2b}4\]But see that since $b$ is odd we can safely say \[X \leq a \left(\frac{b-1}2 \right)^2\]because this is true for all $a$ contestants. Combining the two inequalities we get \[k \binom b2 \geq a \left(\frac{b-1}2 \right)^2 \iff \frac ka \geq \frac{b-1}{2b}\]And done.