I. Hệ đại diện phân biệt
Bài toán của chúng ta là:
Cho n chàng trai, nếu một nhóm k chàng trai bất kì quen với ít nhất k cô gái (1 ≤ k ≤ n).
Chứng tỏ rằng đây là điều kiện cần và đủ để tổ chức một đám cưới tập thể sao cho mỗi chàng trai cưới một cô gái mình quen
Có thể mô hình lại bài toán bằng tập hợp. Gọi Si, i = 1, 2, .., n là tập các cô gái mà chàng trai thứ i quen. Khi đó với mọi i₁, i₂, ..., i_k ∈ {1, 2, ..., n} thỏa mãn |S_i1 ∪ S_i2 ∪ ... ∪ S_ik | ≥ k (Điều kiện Hall)
khi và chỉ khi tồn tại (a₁, ..., a_n) ∈ S₁ × S₂ × ... × S_n sao cho a_i = a_j với i = j
Đây là cũng là nội dung của định lý Hall còn gọi là định lý Đám cưới (Hall’s Marriage Theorem)
Một bộ (a₁, ..., a_n) như vậy gọi là một hệ đại diện phân biệt cho hệ tập hợp (S₁,S₂, ...,Sn) (viết tắt là TRAN), phần tử a_i ∈ Si gọi là đại diện cho Si, lưu ý rằng a_i = a_j với i = j. Như vậy nếu như hệ tập (S₁, ...,Sn) thỏa mãn điều kiện Hall thì tồn tại một TRAN cho hệ đó và điều ngược lại nếu một hệ có TRAN thì nó thỏa mãn điều kiện Hall. Một TRAN nếu có nói chung là không duy nhất, bài toán cần quan tâm là có bao nhiêu TRAN của một hệ tập hợp cho trước.

II. Định lý Hall
Giả sử các tập con S₁, S₂,..., S_m thoả mãn điều kiện:
N (S_i1 U S_i2 U....U S_ik) ≥ k (1)
với mọi 1 ≤ k ≤ m, 1 ≤ i₁ < i₂ <....< i_k ≤ m và mỗi tập con này có ít nhất t phần tử khi đó:

- Nếu t ≤ m thì họ đang xét có ít nhất số TRAN là t!

- Nếu t > m thì họ đang xét có ít nhất số TRAN là [You must be registered and logged in to see this image.]

- Khi (1) có 1 họ con trở thành đẳng thức, thì họ con đó gọi là họ con tới hạn.

III. Bài trong đề thi
(Trang 94, bài 32) Một nhóm thợ gồm:
- Hùng có thể đảm nhận (Gò, hàn, rèn)
- Dũng có thể đảm nhận (Mạ, rũa, hàn, rèn)
- Chính có thể đảm nhận (Gò, mạ, rèn)
- Trung có thể đảm nhận (Rũa, đánh bóng, sơn, rèn)
- Lan có thể đảm nhận (Rũa, đánh bóng, sơn, mạ)
- Vân có thể đảm nhận (Đánh bóng, sơn, gò)

Một công việc cần thực hiện là (Rèn, gò, rũa, mạ, đánh bóng, sơn)
Hỏi:
- Có ít nhất bao nhiêu cách phân công công việc mà mỗi thợ thực hiện một công đoạn?
- Chỉ ra 2 cách phân công, nếu có.

Chỉ ra một số TRAN

[You must be registered and logged in to see this image.]

Thưa anh Admin, theo em, khi làm bài thi thì cứ mỗi TRAN ta sẽ lập một bảng...

Nhưng theo anh Thứ tự điền tên người và tên công việc như trong bảng có cần có yêu cầu gì không, em không đi học nên không rõ thầy nói sao, Nhưng em nghe nói là phải có thứ tự gì đó.. Mong anh giải thích giúp...

Ban QT: Hãy trình bày sao cho bài làm dễ xem nhất, còn việc lập 1 bảng hay nhiều bảng tùy cách trình bày của mỗi người, có người chỉ trình bày bằng 1 bảng, mỗi TRAN vẽ bằng một kiểu nét vẽ, ví dụ TRAN1 là nét liền, TRAN2 là nét gạch gạch, TRAN3 là nét chấm gạch...

Theo định lý HALL thì t ≤ m thì có t!TRAN, vậy với bài toán trên có t! = 2! = 2 TRAN, trong hình vẽ ta chỉ vẽ được duy nhất là 2 cách phân công công việc phải không?

Ban QT: Bạn cần phân biệt khái niệm "có ít nhất" với khái niệm "có" để làm bài và viết cho đúng với yêu cầu đề bài.

Thưa anh Admin, vì em không đi học nên không chắc chắn lắm, nhưng em nghe nói, bài toán liên quan đến định lý Hall trước hết phải tìm m,k,t.. tức là phải kiểm tra điều kiện áp dụng định lý Hall. Em không đi học nên thực sự không rõ, trước khi kẻ bảng ta cần làm những gì, trình bày ra sao.. mong anh hỗ trợ nhanh vì đã sát ngày thi quá rồi...

Ban QT: Việc thuộc định lý thì bạn phải thuộc thôi. Công thức tối thiểu nếu viết ra chỉ có 3 dòng có 2 giá trị t! và t!/((t-m)! chẳng lẽ lại khó thế. m, t, k đã được chỉ ra có sẵn trong đề bài. Bạn hãy chép định lý ra giấy, xem ví dụ mẫu, viết m, t, k mỗi ký tự 1 dòng. Sau đó dò trong ví dụ mẫu xem nó là gì. Như ví dụ vừa xét thì m → người, t → việc. Cần nhớ ví dụ mẫu để bài khác tương tự. Kẻ như bài mẫu. Lập luận như sách. Còn không thể nhớ nổi thì... làm thơ hoặc một câu dễ nhớ, việc sáng tạo là do bạn. Ví dụ:
Ta mà nhỏ hơn em thì ta than (Tương ứng với t < m thì t! là có ít nhất giá trị TRAN)
Ta mà lớn hơn hoặc bằng em thì ta than trên việc ta sẽ trừ bỏ em để than (Tương ứng t ≥ m thì t!/((t-m)!)

nhutaptech đã viết:Theo định lý HALL thì t ≤ m thì có t!TRAN, vậy với bài toán trên có t! = 2! = 2 TRAN, trong hình vẽ ta chỉ vẽ được duy nhất là 2 cách phân công công việc phải không?

Ban QT: Bạn cần phân biệt khái niệm "có ít nhất" với khái niệm "có" để làm bài và viết cho đúng với yêu cầu đề bài.

m=6 , nhung t lam sao bang 2 duoc .
t la so cong viec, thì no la 3 hay 4 mới đúng nhỉ

- Hùng có thể đảm nhận (Gò, hàn, rèn)
- Dũng có thể đảm nhận (Mạ, rũa, hàn, rèn)
- Chính có thể đảm nhận (Gò, mạ, rèn)
- Trung có thể đảm nhận (Rũa, đánh bóng, sơn, rèn)
- Lan có thể đảm nhận (Rũa, đánh bóng, sơn, mạ)
- Vân có thể đảm nhận (Đánh bóng, sơn, gò)