Câu hỏi 46
Quốc hội của một nước gồm một số người, một số người trong đó là bạn bè của nhau. Máy tính in ra tất cả các danh sách thành viên quốc hội sao cho không có hai người nào trong cùng một danh sách là bạn của nhau. Số các danh sách này (kể cả danh sách rỗng) bằng $M$. Các thành viên quốc hội muốn lập hai ủy ban — ủy ban cấp cao $A$ và ủy ban cấp thấp $B$, sao cho:
1) các ủy ban có thể rỗng, có thể giao nhau, thậm chí trùng nhau;
2) trong mỗi ủy ban được phép có các cặp bạn bè, nhưng không có người nào của ủy ban $A$ có bạn trong ủy ban $B$ (giả sử không ai là bạn của chính mình);
3) trong các buổi họp chung của hai ủy ban $A$ và $B$, tất cả mọi người có thể được chia thành hai nhóm sao cho trong mỗi nhóm không có hai người nào là bạn.
Chứng minh rằng số cách chọn các ủy ban bằng $M^2$.
1) các ủy ban có thể rỗng, có thể giao nhau, thậm chí trùng nhau;
2) trong mỗi ủy ban được phép có các cặp bạn bè, nhưng không có người nào của ủy ban $A$ có bạn trong ủy ban $B$ (giả sử không ai là bạn của chính mình);
3) trong các buổi họp chung của hai ủy ban $A$ và $B$, tất cả mọi người có thể được chia thành hai nhóm sao cho trong mỗi nhóm không có hai người nào là bạn.
Chứng minh rằng số cách chọn các ủy ban bằng $M^2$.