Câu hỏi 3
Có $n$ chàng trai $B_1, B_2, \dots, B_n$ và $n$ cô gái $G_1, G_2, \dots, G_n$. Mỗi chàng trai xếp các cô gái theo thứ tự ưu tiên và mỗi cô gái xếp các chàng trai theo thứ tự ưu tiên. Chứng minh rằng chúng ta có thể sắp xếp các bé trai và bé gái thành các cặp $n$ sao cho không thể tìm được bé trai và bé gái thích nhau hơn bạn đời của mình. Ví dụ: nếu $(B_1, G_3)$ và $(B_4, G_7)$ là hai trong số các cặp thì không phải trường hợp $B_4$ thích $G_3$ hơn $G_7$ và $G_3$ thích $B_4$ hơn $B_1$.