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

  • Context: MHB 
  • Thread starter Thread starter anemone
  • Start date Start date
  • Tags Tags
    Challenge Probability
Click For Summary
SUMMARY

The discussion centers on proving the inequality $$\frac{k}{a} \ge \frac{b-1}{2b}$$ in a competition scenario with $$a$$ contestants and $$b$$ judges, where $$b$$ is an odd integer greater than or equal to 3. The analysis reveals that for any two judges, their ratings coincide for at most $$k$$ contestants. A contradiction arises when substituting specific values, leading to the conclusion that the number of pairs of judges rating a contestant the same is at least $$\frac{(b-1)^2}{4}$$, thus confirming the original inequality.

PREREQUISITES
  • Understanding of combinatorial counting principles
  • Familiarity with inequalities and their proofs
  • Knowledge of basic probability concepts
  • Ability to manipulate algebraic expressions
NEXT STEPS
  • Study combinatorial proofs in depth
  • Explore advanced topics in probability theory
  • Learn about the implications of odd integers in combinatorial settings
  • Investigate applications of inequalities in competitive scenarios
USEFUL FOR

Mathematicians, statisticians, educators, and students interested in combinatorial mathematics and probability theory.

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}$$.
 
Physics 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}$$.
 

Similar threads

  • · Replies 66 ·
3
Replies
66
Views
7K
  • · Replies 29 ·
Replies
29
Views
4K
  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 36 ·
2
Replies
36
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 4 ·
Replies
4
Views
3K
Replies
1
Views
2K