Trích:
Nguyên văn bởi huynhcongbang  Bài 11. Trong một lớp học mỗi bạn nam quen với ít nhất một bạn nữ. Chứng minh rằng có thể chọn một nhóm gồm nhiều hơn nửa số thành viên của lớp mà mỗi bạn nam quen với một số lẻ bạn nữ trong nhóm. Đây là một bài trong tuyển tập các bài toán Tổ hợp của VMF cách đây 8 năm. Hiện tại mình biết 2 lời giải của bài này (một dùng quy nạp, một dùng nguyên lý bù trừ nhưng khá phức tạp), nhưng mình nghe nói bản chất bài này là đồ thị 2 phe. Mọi người thử sức nhé! Mình sẽ giới thiệu 2 lời giải kia sau.  |
Có một cách khá gọn là chứng minh bằng cách đếm hai cách
. Dựa vào nhận xét là nếu có $N $ bạn nữ thì với mỗi nam, số cặp (nam, tập nữ) sao cho nam quen với số chẵn người trong tập nữ đó là $2^{N-1} $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]