Có 3366 nhà phê bình điện ảnh bỏ phiếu cho giải Oscar. Mỗi một nhà phê bình bỏ phiếu cho đúng 1 nam diễn viên và đúng 1 nữ diễn viên. Sau khi các nhà phê bình bỏ phiếu xong, người ta thấy rằng với mỗi n thuộc {1, 2, ..., 100} đều có một nam diễn viên hoặc 1 nữ diễn viên được đúng n phiếu. Chứng minh rằng tồn tại 2 nhà phê bình bỏ phiếu như nhau (tức là bỏ phiếu cho cùng 1 nam diễn viên và 1 nữ diễn viên).
Trước tiên ta khai thác một số điều từ giả thiết. Tổng số phiếu sẽ là $\frac{100.101}{2}=5050$, mà chỉ có $3366$ nhà phê bình nên phải có ít nhất $5050-3366=1684$ người bỏ 2 phiếu. Rõ ràng từ câu hỏi của bài toán thì ta phải xem xét đến $1684$ ông này, để chứng minh có $2$ ông bỏ phiếu giống nhau thì chỉ có thể rơi vào $1684$ vị này là khả thi thôi. Tức là nếu xét các cặp được cùng một nhà phê bình bỏ phiếu thì trong $100$ diễn viên đề cập trong đề phải có ít nhất $1684$ cặp nam nữ. Đến đây ý tưởng sẽ phải chứng minh không thể có đến $1684$ cặp được. Bây giờ ta sẽ cố gắng tạo ra nhiều cặp nam nữ nhất trong số $100$ người này
Không mất tính tổng quát giả sử có $k$ người nam và $100-k$ người nữ trong đó $k \le 50$. Như vậy nhiều nhất ta tạo ra được $(100-k)k$ cặp. Tuy nhiên như thế thì $k$ nam sẽ có $100-k$ phiếu và $100-k$ nữ sẽ có $k$ phiếu. Như vậy số phiếu của những người này đều không nhỏ hơn $k$, điều này không hợp lí. Buộc ta phải bỏ bớt các cặp trong này để đưa một số giá trị về $1,2,3,..,k-1$, chú ý là $100-k \ge k$ nên để loại bỏ ít cặp nhất ta sẽ chọn ra $k-1$ cô gái trong $100-k$ người có $k$ phiếu và bỏ bớt phiếu những người này tạo thành dãy $1,2,..,k-1$. Như vậy ta đã bỏ đi $k.(k-1)-(1+2+..+k-1)=\frac{k(k-1)}{2}$. Vậy chỉ có thể tạo ra nhiều nhất là $(100-k)k-\frac{k(k-1)}{2}=k(100-k-\frac{k-1}{2})$. Áp dụng Cauchy thì ta có:
$$ \frac{3}{2}k(100-k-\frac{k-1}{2}) \le \frac{1}{4}(100+1/2)^2<\frac{100.101}{4} \Rightarrow k(100-k-\frac{k-1}{2}) < \frac{100.101}{6}=\frac{5050}{3}<1684$$
Vậy là kết quả được chứng minh.
Dù là giải đi đến kết quả thậm chí có thể thấy là ta hoàn toàn có thể tổng quát $100$ thành $n$ và thay đổi số nhà phê bình bé hơn $\frac{n(n+1)}{3}$. Tuy nhiên chúng ta cần nhìn nhận vấn đề cẩn thận hơn một chút, việc chứng minh này chưa có nhiều ý nghĩa lắm. Mình sẽ nêu ra một số vấn đề để các bạn tìm hiểu để hiểu rõ bài toán hơn:
1. Đầu tiên hãy xem khi tiếp cận bài toán các bạn suy nghĩ ntn? Dĩ nhiên các bạn sẽ phải hình dung đến một cấu hình tốt nhất nào đấy để cố gắng tìm điểm mâu thuẫn ở đó.
2.. Nếu ta tăng số nhà phê bình thêm 1 hoặc 2 đơn vị. Khi đó đpcm không đúng nữa, vậy cấu hình giám khảo chấm như thế nào để nó không đúng (đây có thể gọi là cấu hình "tốt nhất", dĩ nhiên hướng xây dựng cấu hình này sẽ dựa vào dấu bất đẳng thức ở trên). Từ đó các bạn có thể thấy được cách đưa bài toán vào trạng thái tối ưu.
3. Có một vấn đề là ta mới chỉ ra mâu thuẫn ở việc đánh giá của 1684 giám khảo chấm cả 2 phiếu trên 100 người thôi. Giả sử ta đáp ứng được số cặp trong 100 người thỏa mãn bđt trên, liệu những người chỉ bỏ 1 phiếu còn lại có thể hoàn thành được đk của bài toán là cứ $1 \le i \le 100$ thì có một người có $i$ phiếu? Thay $100$ bằng $n$ thì sẽ rơi vào những vấn đề gì? Đổi lại tìm số giám khảo nhiều nhất để đảm bảo có 2 người bỏ phiếu giống nhau thì xử lí thế nào với $n$?
4. Nếu vấn đề đòi hỏi đến 2 cặp giám khảo bỏ phiếu giống nhau thì thế nào? hoặc một giám khảo có thể bỏ phiếu cho 2 người nam và 1 người nữ thì ntn?
Khi tìm hiểu bài toán đủ nhiều các bạn có thể tự đặt ra thêm những câu hỏi và tự giải quyết chúng. Đôi khi có thể đặt ra rồi không giải quyết được nhưng chắc chắn là không vô ích!
Hi vọng các bạn tham gia thảo luận nhiều hơn là đưa ra một lời giải.
P/s em chủ topic: À muốn hỏi e một vấn đề nhỏ, thầy Thông trong chữ kí của em có phải là thầy Nguyễn Văn Thông ở LQĐ Đà Nẵng k nhỉ?
Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 03-06-2015 - 06:20