Math Labs

Bài 6

Trong một kỳ thi toán học có 66 bài toán được đưa ra cho các thí sinh, cứ hai bài bất kỳ trong số đó đều có hơn 25\frac25 số thí sinh giải được. Hơn nữa, không có thí sinh nào giải được cả 66 bài. Chứng minh rằng có ít nhất 22 thí sinh mà mỗi người giải được đúng 55 bài.
Bước 1 trên 6: Chuẩn hóa về một người giải 55 bài và (n−1)(n-1) người giải 44 bài
Bước trướcBước tiếp
Hiểu nôm na

Nếu có phản ví dụ với nhiều nhất một người giải 55 bài, việc tặng thêm bài giải được cho những người khác tới khi người đứng đầu có 55 bài và mọi người còn lại có 44 bài chỉ làm tăng số đếm mỗi cặp, nên phản ví dụ vẫn hợp lệ và trở nên hoàn toàn cứng.

n=1+∑i=15ai+∑1≤i<j≤5bijn=1+\sum_{i=1}^5 a_i+\sum_{1\le i<j\le 5}b_{ij}
Phân tích chi tiết

Giả sử phản chứng có nhiều nhất một thí sinh giải được 55 bài. Việc thêm bài giải được cho thí sinh chỉ làm tăng số đếm mỗi cặp mà không vi phạm giả thiết nào, nên không mất tính tổng quát có thể giả sử một thí sinh giải được các bài 1,2,3,4,51,2,3,4,5 (bỏ bài 66) và mọi thí sinh khác giải được 44 bài. Trong n−1n-1 thí sinh còn lại, gọi aia_i (1≤i≤51\le i\le5) là số người bỏ bài 66 và bài ii, và bijb_{ij} (1≤i<j≤51\le i<j\le5) là số người giải được bài 66 và bỏ hai bài i,ji,j; khi đó n=1+∑i=15ai+∑1≤i<j≤5bijn=1+\sum_{i=1}^5 a_i+\sum_{1\le i<j\le5}b_{ij}.