Diễn Đàn MathScope - Xem bài viết đơn - Việt Nam TST 2010(Đề thi-Đáp án-Danh sách đội tuyển)

**Traum** · 18-04-2010, 04:38 PM

Bài tổ hợp 5 thì chính là một trường hợp đặc biệt của định lí Hall trong Graph Theory.

Ta gọi một nước $X $ và một nhóm $Y $ có liên hệ với nhau nếu trong nhóm $Y $ có người của nước $X $. Khi đó ta có nước $X $ bất kì có liên hệ với đúng $k $ nhóm và một nhóm $Y $ bất kì có liên hệ với đúng $k $ nước khác nhau.
Khi đó một hợp $m $ nước bất kì thì sẽ có liên hệ với một hợp ít nhất $m.k/k = m $ nhóm khác nhau. Do đó theo định lý Hall thì sẽ có cách ghép $n $ nước với $n $ nhóm mà không có hai nước nào cùng liên hệ với một nhóm. ( chính là cách chọn ra $n $ người từ $n $ nước khác nhau và từ $n $ nhóm khác nhau).

Nếu không dùng định lý Hall thì có thể chứng minh bằng quy nạp theo kiểu định lý đó.

18-04-2010, 04:38 PM	#26
Traum Moderator Tham gia ngày: Nov 2007 Đến từ: cyber world Bài gởi: 413 Thanks: 14 Thanked 466 Times in 171 Posts	Bài tổ hợp 5 thì chính là một trường hợp đặc biệt của định lí Hall trong Graph Theory. Ta gọi một nước $X $ và một nhóm $Y $ có liên hệ với nhau nếu trong nhóm $Y $ có người của nước $X $. Khi đó ta có nước $X $ bất kì có liên hệ với đúng $k $ nhóm và một nhóm $Y $ bất kì có liên hệ với đúng $k $ nước khác nhau. Khi đó một hợp $m $ nước bất kì thì sẽ có liên hệ với một hợp ít nhất $m.k/k = m $ nhóm khác nhau. Do đó theo định lý Hall thì sẽ có cách ghép $n $ nước với $n $ nhóm mà không có hai nước nào cùng liên hệ với một nhóm. ( chính là cách chọn ra $n $ người từ $n $ nước khác nhau và từ $n $ nhóm khác nhau). Nếu không dùng định lý Hall thì có thể chứng minh bằng quy nạp theo kiểu định lý đó. __________________ Traum is giấc mơ.