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

Click For 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}$$.
 
Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?

Similar threads

  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 1 ·
Replies
1
Views
962
  • · Replies 1 ·
Replies
1
Views
1K
Replies
3
Views
2K
  • · Replies 66 ·
3
Replies
66
Views
7K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K