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

AI Thread Summary
In a competition with \( a \) contestants and \( b \) judges (where \( b \) is an odd integer and \( b \ge 3 \)), the challenge is to prove that \( \frac{k}{a} \ge \frac{b-1}{2b} \), given that any two judges' ratings coincide for at most \( k \) contestants. A contradiction arises when substituting specific values, as shown in the example where \( a = 3 \), \( b = 4 \), and \( k = 1 \). The discussion highlights that the total number of pairs of judges rating contestants the same must satisfy certain inequalities, leading to a conclusion that \( N \), the count of coinciding ratings, must be at least \( \frac{a(b-1)^2}{4} \). Ultimately, combining these inequalities confirms the original statement \( \frac{k}{a} \ge \frac{b-1}{2b} \).
anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
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}$$.
 
Mathematics news on Phys.org
anemone said:
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! :eek:
 
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.:o 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}$$.
 

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Thread 'Fermat's Last Theorem'

Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
View full post »
Thread 'Imaginary Pythagorus'

Thread 'Imaginary Pythagorus'

I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
View full post »

Similar threads

MHB Prove the inequality (a^3-c^3)/3≥abc((a-b)/c+(b-c)/a)
Replies
3
Views
1K
I Prove series identity (Alternating reciprocal factorial sum)
Replies
4
Views
2K
MHB Inequality Challenge: Prove $\ge 0$ for All $a,b,c$
Replies
2
Views
1K
MHB Maximum Value of k in $(1+\frac{1}{a})(1+\frac{1}{b}) \ge k$ is 9
Replies
4
Views
2K
MHB Proving $\dfrac{(n-1)^{2n-2}}{(n-2)^{n-2}}<n^n$ for $n\ge 3$
Replies
1
Views
873
MHB Proving $abcd\ge 3$ with $a, b, c, d>0$
Replies
1
Views
989
MHB Proving $\frac{a}{b^2+4}+\frac{b}{a^2+4}\ge \frac{1}{2}$ with $a+b=ab$
Replies
3
Views
2K
I Can chatgpt accurately calculate expected lengths in Pascal's triangle?
2
Replies
66
Views
6K
MHB Prove Triangle Inequality: $\sqrt{2}\sin A-2\sin B+\sin C=0$
Replies
2
Views
2K
MHB Proving Inequality Challenge: $a,\,b,\,c$ | Real Numbers
Replies
2
Views
2K

Hot Threads

Recent Insights

Back
Top