Toán rời rạc $1$

Bài Toán:Trong một kỳ thi có 30 thí sinh và 5 giám khảo. Mỗi giám khảo đánh giá từng thí sinh và cho kết luận thí sinh đó đỗ hay trượt. Giả sử $k$ là một số thỏa mãn điều kiện. Với hai giám khảo bất kỳ , số thi sinh mà họ cho kết luận giống nhau nhiều nhất là $k$. Chứng minh rằng : $k\geq 12$

Lời giải:Ta sẽ xét bài toán tổng quát là IMO 1998 với $a$ thí sinh và $b$ giám khảo b lẻ  $(b\geq 3)$ 

Ta cần cm :$\frac{k}{a}\geq \frac{b-1}{2b}$

Ý tưởng là đếm bằng 2 cách

Gọi N là số bộ 3 (giám khảo,giám khảo,học sinh) sao cho:

+,2 giám khảo đó là khác nhau

+,2 giám khảo đó cùng đánh giá đậu hoặc rớt cho thí sinh trong bộ 3

Có $d\frac{b(b-1)}{2}$ cách chọn bộ 2 giám khảo

Vì mỗi bộ giám khảo có  kết luận giống nhau cho nhiều nhất là k thí sinh nên $N\leq \dfrac{kb(b-1)}{2}$(1)

Bây giờ ta xét cố định 1 thí sinh X và tính số cặp giám khảo cùng đánh giá cho X

Giả sử có x giám khảo kết luận đậu$\Rightarrow$ có $\dfrac{x(x-1)}{2}$ cặp giám khảo đánh giá X đậu

Có b-x số giám khảo KL X rớt $\Rightarrow$ có $\dfrac{(b-x)(b-x-1)}{2}$ cặp giám khảo đánh giá X rớt

Do đó có $\dfrac{x(x-1)}{2}+\dfrac{(b-x)(b-x-1)}{2}$ cặp giám khảo đánh giá X

$\Rightarrow N=a\left [ \dfrac{x(x-1)}{2}+\dfrac{(x-b)(x-b+1)}{2} \right ](2)$

Từ (1) và (2) kết hợp với $\dfrac{x^{2}-x}{2}+\frac{b^{2}-2bx+x^{2}-b+x}{2}\geq \dfrac{2x^{2}-2bx+b^{2}-b}{2}$

$\geq \dfrac{2(x-\frac{b}{2})^{2}+\dfrac{b^{2}}{2}-b}{2}$

$\geq \dfrac{b^{2}}{4}-\dfrac{b}{2}$

$= \dfrac{(b-1)^{2}}{4}-\dfrac{1}{4}$ và do $b$ lẻ $\Rightarrow \dfrac{(b-1)^{2}}{4}$ nguyên

$\dfrac{k}{a}\geq \dfrac{b-1}{2b}$(đpcm)