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 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »
Thread 'Imaginary Pythagoras'

Thread 'Imaginary Pythagoras'

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
2K
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
887
MHB Proving $abcd\ge 3$ with $a, b, c, d>0$
Replies
1
Views
1K
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