ĐỊNH LÍ HALL MỞ RỘNG VÀ ỨNG DỤNG TRONG VNTST 2002

ĐỊNH LÍ HALL:Cho m cô gái,mỗi cô gái quen một số chàng trai,khi đó mỗi cô gái có thể cưới 1 chàng trai mà mình quen(mỗi chàng quân tử chỉ lấy 1 cô) <=> $k$ cô gái quen ít nhất $k$ chàng với $k=1->m$
Chứng minh:Sử dụng quy nạp

ĐỊNH LÍ HALL MỞ RỘNG:Cho $m$ cô gái,$t=<m$,khi đó tồn tại một cách ghép t cặp gái trai mà cô gái quen chàng trai <=>$k$ cô gái quen đúng $k+t-m$ chàng trai
Chứng minh:Tương tự sử dụng quy nạp
NX:Định lí Hall chính là định lí Hall mở rộng trong TH $t=m$

ÁP DỤNG:VNTST 2002:
Cho 42 bạn,cứ 31 bạn bất kì thì có 1 đôi nam nữ quen nhau.CMR:tồn tại 12 đôi nam nữ đôi một phân biệt,quen nhau.
Lời giải:
Gọi $m$ là số bạn nam,khi đó số nữ là $42-m$
Giả sử $m\ge 21$
Khi đó ta cần cm $k$ bạn nam quen ít nhất $k+12-m$ bạn nữ,điều này dễ dàng cm được từ các dữ kiện bài toán!