Câu hỏi 169
Cho $n$ là một số nguyên dương. Trong một ngôi làng có $n$ chàng trai và $n$ cô gái. Cho buổi khiêu vũ thường niên, cần lập $n$ cặp nhảy, mỗi cặp gồm một chàng trai và một cô gái. Mỗi cô gái đưa ra một danh sách gồm tên chàng trai mà cô muốn nhảy cùng nhất, cộng với không hoặc nhiều tên các chàng trai khác mà cô cũng bằng lòng nhảy cùng. Biết rằng có thể lập $n$ cặp nhảy sao cho mỗi cô gái nhảy với một chàng trai có trong danh sách của cô.
Chứng minh rằng có thể lập $n$ cặp nhảy sao cho mỗi cô gái nhảy với một chàng trai có trong danh sách của cô và có ít nhất một cô gái nhảy với chàng trai mà cô muốn nhảy cùng nhất.
Chứng minh rằng có thể lập $n$ cặp nhảy sao cho mỗi cô gái nhảy với một chàng trai có trong danh sách của cô và có ít nhất một cô gái nhảy với chàng trai mà cô muốn nhảy cùng nhất.