Bài toán xếp khách của Lucas
I. Những bài toán đơn giản:
Bài toán 1:
Có bao nhiêu cách lấy k phần tử trong n phần tử xếp trên đường thẳng sao cho không có 2 phần tử kề nhau cùng được lấy ra?
Giải
Lấy k phần tử ra, sẽ còn lại n - k phần tử.
Tính cả 2 đầu, sẽ có tổng cộng n - k + 1 khoảng trống (giữa các phần tử).
Mỗi cách lấy ra k khoảng từ các khoảng này, sẽ tương ứng chọn k phần tử thoả mãn yêu cầu đã nêu.

Số cách cần tìm sẽ là: C^k_n-k+1

Bài toán 2:
Có bao nhiêu cách lấy k phần tử trong n phần tử xếp thành vòng tròn sao cho không có 2 phần tử kề nhau cùng được lấy ra?
Giải
Trong n phần tử trên, chỉ định một phần tử a, để cố định nó xem xét cho dễ. Khi đó bài toán này sẽ được chia làm 2 lớp để giải:
Lớp thứ nhất: Tập hợp các cách chọn, mà có chọn phần tử a.
Khi a được chọn, 2 phần tử kề a (trái, phải) sẽ không được chọn. Số phần tử còn lại sẽ là n - 3. Ta phải lấy k - 1 phần tử trong số các phần tử còn lại đó. Các phần tử này được coi như trên một đường thẳng (quy về bài toán 1), nên số cách thuộc lớp này là: C^k-1_{(n-3)-(k-1)+1} = C^k-1_n-k-1

Lớp thứ hai: Tập hợp các cách chọn, mà không chọn phần tử a.
Khi đó bỏ a đi, sẽ trở thành dạng bài toán lấy k phần tử từ n-1 phần tử xếp trên đường thẳng (bài toán 1). Nên số cách thuộc lớp này là: C^k_n-k

Hai lớp trên đều giải quyết từ đầu đến cuối, nên áp dụng nguyên lý cộng, số cách cần tìm là:
C^k-1_n-k-1 + C^k_n-k
[You must be registered and logged in to see this image.]

I. Bài toán xếp khách của Lucas
Một bàn tròn có 2n ghế. Cần sắp xếp n cặp vợ chồng vào bàn tròn sao cho các ông ngồi xen kẽ với các bà và không có cặp vợ chồng nào ngồi cạnh nhau. Hỏi có bao nhiêu cách xếp?
Giải
Lời giải ở trong sách của mình học giống hệt sách Toán rời rạc của tác giả Nguyễn Đức Nghĩa, Nguyễn Tô Thành, giống đến mức không sai một dấu phảy, chấm. → Nên lời giải này quá kinh điển, nên gõ lại cũng phải không để sai một dấu phảy, chấm cũng là một vấn đề.

Gọi số phải tìm là Mn. Xếp cho các bà trước(cứ xếp một ghế thì một ghế để trống dành cho các ông), số cách xếp cho các bà là 2n! cách. Gọi số cách xếp cho các ông ứng với một cách xếp các bà là Un ta được số cách xếp là:
Vấn đề còn lại là tính số Un.
Đánh số các bà (đã xếp) từ 1đến n,đánh số các ông tương ứng với các bà (ông i là chồng bà i), sau đó đánh số các ghế trống theo nguyên tắc: ghế số i nằm giữa bà i và bà i+1 (các phép cộng được hiểu lấy modul n nghĩa là n +1 = 1). Mỗi cách xếp các ông được biểu diễn bằng một phép thế ϕ trên tập {1, 2,.., n } với qui ước ϕ(i) = j có nghĩa là ghế i được xếp cho ông j. Theo giả thiết ϕ phải thoả mãn:
Như vậy, Un là số tất cả các phép thế ϕ thoả mãn điều kiện (**).
Trong toán học gọi Un là số phân bố .

Xét tập hợp tất cả các phép thế ϕ của { 1, 2,.., n }. Trên tập này ta gọi Pi là tính chất ϕ(i) = i, Qi là tính chất ϕ(i) = i+1. Đặt P_n+i= Qi, theo nguyên lý bù trừ tương ứng với 2n tính chất Pi ta có:

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

Trong đó Nk là tổng số tất cả các phép thế thoả mãn k tính chất lấy từ 2n tính chất đang xét. Cần chú ý rằng, không thể xảy ra đồng thời thoả mãn Pi và Qi hoặc đồng thời thoả mãn P_i+1và Qi. Do đó trong các phép lấy ra k tính chất từ 2n tính chất đang xét cần thêm vào điều kiện: Pi và Qi hoặc P_i+1 và Qi không được đồng thời có mặt.

Gọi số các cách này là g(2n, k) (nói riêng g(2n,k) = 0 khi k > n). Với mỗi cách lấy ra k tính chất như vậy (k ≤ n) ta có (n - k)! phép thế thoả mãn chúng. Từ đó ta nhận được:

Nk = g(2n, k) (n-k)!
và:
Un = n! - g(2n, 1).(n - 1)! + g(2n, 2).(n - 2)! -...+(-1)ⁿg(2n, n) (***)

Bây giờ chúng ta phải tính các hệ số g(2n,k), k = 1, 2,.., n. Xếp 2n tính chất đang xét trên vòng tròn theo thứ tự P₁, Q₁, P₂, Q₂,.., Pn, Qn, ta thấy rằng g(2n,k) chính là số cách lấy k phần tử trong 2n phần tử xếp thành vòng tròn sao cho không có hai phần tử nào kề nhau cùng được lấy ra. Để tính g(2n,k) ta áp dụng công thức (*) của bài toán 2:
[You must be registered and logged in to see this image.]

Số phân bố Un lắp công thức trên vào (***) ta nhận được:
[You must be registered and logged in to see this image.]

Vậy đáp số cần tìm sẽ là Công thức Lucas: Mn= 2n! x Un.
[You must be registered and logged in to see this image.]

Áp dụng cho bài tập 8 trang 81, bài tập củ chuối nhất trong các loại bài tâp:
Có 4 cặp vợ chồng khách đến dự tiệc tại một gia đình vợ chồng chủ nhà sắp chỗ ngồi quanh bàn tròn. Hãy tính số cách sắp xếp sao cho
các ông ngồi xen kẽ với các bà và không có cặp vợ chồng nào ngồi cạnh nhau. Vợ chồng chủ nhà luôn ngồi cạnh nhau và chồng luôn ngồi bên phải.
Giải
Bỏ vợ chồng chủ nhà ra, chưa ngồi vào thì ta có 4 cặp vợ chồng ngồi quanh bàn tròn với bài toán Lucas áp dụng cho n = 4 thay vào công thức Lucas:
[You must be registered and logged in to see this image.]

Tính trong ngoặc cẩn thận:

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

M4 = 190*8* 6!
Kinh không? Đấy là chưa kể xếp vào với chủ nhà đấy nhé!
Ta thấy 8 người trên khi xếp vào vòng tròn sẽ có 8 cái khe. Vợ chồng chủ nhà ngồi cạnh nhau có thể nhét vào 1 trong 8 cái khe đó. Vậy theo nguyên lý nhân sẽ có tới M4 * 8 cách xếp cả thảy.
Đáp số quả là một số kinh khủng luôn:
Số cách xếp = 190*8*6!*8
Nhân ra xem mặt mũi nó thế nào sẽ được: 12160 * 6! = 12160 * 720 = 8.755.200 cách xếp.
Ngồi nhà có thời gian bấm tính từng tí một, kiểm tra đã thấy nhức đầu, nếu đề thi mà ra bài toán dạng này có lẽ thí sinh sẽ có người phát điên.

- vì ông ngồi bên phải bà chủ nhà nên chỉ nhét được vào bốn khe thôi nhé, chứ không phải 8 đâu.

- Ngoài ra còn trường hợp những người khách đến, có một cặp ngồi cạnh nhau, và cặp đấy ông cũng ngồi bên phải bà. Sau đó nhét ông bà chủ nhà vào giữa cặp đó. Khi đó ta thêm được số cách là 3*4*M3 nữa nhé.

Đề số 6, câu 2, trang 168:
Có 4 cặp vợ chồng khách đến dự tiệc tại một gia đình vợ chồng chủ nhà sắp chỗ ngồi quanh bàn tròn. Hãy tính số cách sắp xếp sao cho mỗi ông ngồi xen kẽ với hai bà. Vợ chủ nhà luôn ngồi bên phải chồng mình. Hãy tính số cách thoả mãn điều kiện:
a. Chỉ có một cặp vợ chồng khách ngồi cạnh nhau
b. Có ít nhất một cặp vợ chồng ngồi cạnh nhau

Có 4 cặp vợ chồng khách đến dự tiệc tại một gia đình vợ chồng chủ nhà sắp chỗ ngồi quanh bàn tròn. Hãy tính số cách sắp xếp sao cho các ông ngồi xen kẽ với các bà và không có cặp vợ chồng nào ngồi cạnh nhau. Vợ chồng chủ nhà luôn ngồi cạnh nhau và chồng luôn ngồi bên phải.
Bàn luận cách giải:
Theo đầu bài, các ông ngồi xen kẽ với các bà, không có cặp vợ chồng nào ngồi cạnh nhau.
Vợ chồng chủ nhà ngồi cạnh nhau và chồng luôn ngồi bên phải.
Vậy ta cố định vợ chồng chủ ngồi 2 ghế trong 10 ghế của bàn tròn: số cách lấy trường hợp này là 10.
Với mỗi cách lấy vợ chồng chủ nhà, ta sắp 4 cặp vợ chồng khách vào 8 vị trí còn lại thoả mãn tiêu chí đầu bài. mỗi cách lấy này là Mn (n = 4). Tổng số cách là 8 * Mn.
Tính Mn:
* Theo giả thiết thì ta chỉ có dạng xếp như sau: vợ chủ - chồng chủ - vợ khách - chồng khách ... (vì các ông xen các bà mà) . Cho nên trong 8 vị trí còn lại sắp cho khách, ta sắp các người vợ khách trước, thì được n! cách sắp người vợ khách (chứ không phải 2n! đâu nhé). Ứng với mỗi cách sắp người vợ khách ta có Un cách sắp người chồng khách. Mn = n! * Un.
Tính Un: Thực ra là bài toán bỏ thư ứng với n. Vì chỉ cần sắp người chồng khách i không ngồi cạnh người vợ khách i là được.
Vậy [You must be registered and logged in to see this image.]
Như vậy tổng số cách của bài toán là 8 * Mn = 8 * n! * Un với n = 4.
Các đ/c nhận xét xem thế nào.

@ Đạt
- Giải bài toán này theo cách bỏ thư là không được, bởi vì không những ông i không được ngồi vào chỗ i, mà ông i còn không được ngồi vào ghế i-1 nữa. Tức là không được ngồi bên phải hoặc bên trái vợ mình. Trong bài của Đạt thì mới chỉ tính đến một trường hợp, do đó chưa có thể giải quyết được bài toán.

- Bài toán xếp khách của Lucas thuộc vào bài toán khó, nên mình cũng lười giải. Theo mình bài toán ở trên ta chia làm mấy trường hợp như sau.

+ Trường hợp 1: Có 10 vị trí cho vợ chồng chủ nhà. Còn 8 chỗ để xếp 4 cặp vợ chồng khách sao cho không có vợ chồng nào ngồi cạnh nhau. (Số cách thì ta lấy kết quả trong sách thay vào). Số cách là 10*M₄/2 = 10*2*n!*U₄/2 = (10*2*24*2)/2 = 480

+ Trường hợp 2: Ta có C(3,4) cách để lấy 1 cặp vợ chồng khách xếp cạnh nhau. Xếp vợ chồng chủ nhà vào giữa cặp vợ chồng này. Ta có 10 vị trí sắp cho 4 người này. Xếp 3 cặp vợ chồng khách còn lại vào 6 vị trí sao cho không có vợ chồng nào ngồi cạnh nhau. Số cách là 10*C(3,4)*M₃/2 = (10*4*2*3!*1)/2 = 240.

+ Mặt khác các trường hợp trên không thể trùng nhau nên ta thay số và tính toán các trường hợp ở trên ra kết quả là 720.




- Ngoài ra ta có thể phân tích bài toán như sau. Xếp 4 cặp vợ chồng khách không phải theo vòng tròn mà theo đường thẳng. Vợ chồng chủ nhà sẽ nối vào hai đầu để thành xếp vòng tròn. Như thế này thì ta lại phân tích bài toán Lucas từ đầu, nhưng hệ số g(n,k) lại khác với trong sách. Bù lại chúng ta không phải xét các trường hợp. Nói chung bài toán này là rất phức tạp. :)

Bài toán 8T81: 4 cặp vợ chồng khách và vợ chồng chủ nhà sao cho vợ chồng chủ nhà luôn ngồi cạnh nhau và ông chồng ngồi bên phải có thể giải như sau:

- sắp vợ chồng ông chủ nhà trước. có 10 ghế, vậy có 10 cách sắp 2 ông bà ngồi cạnh nhau, ông ngồi bên phải bà.
- với mỗi cách sắp vợ chồng ông chủ nhà, ta tách vòng tròn thành đường thẳng trong đó 2 đầu đường thẳng là vợ chồng chủ nhà, cụ thể là: chồng chủ nhà, vợ khách, chồng khách, ........, chồng khách, vợ chủ nhà.
          + xếp vợ khách trước: có 4! cách xếp
          + với mỗi cách xếp vợ khách, ta xếp 4 ông chồng vào 4 vị trí xen kẽ các bà sao cho ông i không ngồi cạnh bà i (chỉ có 4 vị trí chứ k phải 5 khoảng đâu nhé):
xét trường hợp tổng quát: xếp n ông chồng vào n ghế trên 1 đường thẳng sao cho ông i không ngồi cạnh bà i (Un)
Xét tập hợp các phép thế f của {1, 2, 3..,n}(là phép thế ϕ trong sách) Pi là t/c: f(i)=i, Qi là t/c: f(i)=i+1
Un= |N = n! - N1 + N2 -...
với Nk là tổng số các phép thế thỏa mãn k t/c lấy từ 2n-1 t/c đang xét: P1, Q1, P2, Q2,...Pn. Số cách lấy k t/c với đ.k Pi và Qi hoặc P(i+1) và Qi không đồng thời có mặt là: g(2n-1, k)
Xếp 2n-1 t/c trên đường thẳng theo thứ tự P1, Q1, P2, Q2, ... Pn ta thấy g(2n-1, k): số cách lấy ra k phần tử trong 2n-1 phần tử sắp trên đường thẳng sao cho không có 2 phần tử kề nhau được lấy ra
g(2n-1, k) = C(k, 2n-1-k+1) = C(k, 2n-k)
→ Nk= C(k, 2n-k)*(n-k)!
thay vào U4 = 4!- C(1,7)3! + C(2,6)2! - C(3,5)1!+ C(4,4)=3
vậy đ/s: 10*4!*3 = 720

Hoan hô cách giải của em Hiền.

Hôm nay tự nhiên mình có hứng nghiên cứu bài toán sắp khách của Lucas. Ai có hứng thì mời vào thảo luận mấy bài toán sắp khách của Lucas trong sách giáo khoa.
Xin mời các ý kiến.

Ban QT: Hết ý kiến.

- Không biết anh Phương đã giải bài toán Lucas chưa mà ủng hộ lời giải của em hiền. Lý luận sai hẳn bản chất.
- Không biết anh Admin đã hiểu hết bài toán Lucas chưa mà đã nói là "Hết ý kiến" may cho anh là những bài toán này sẽ rất khó thi nhưng không có nghĩa là không có. Nhưng nếu có thì cũng chỉ môt điểm. Do vậy lấy 5-6 điểm không cần quan tâm.
- Ý của em đưa ra những bài toán khó là để những ai muốn kiếm điểm cao thì quan tâm những bài toán khó và họ chưa giải quyết được. Đưa thắc mắc lên sẽ được giải quyết.
- Ý nữa là Để nâng cao chất lượng diễn đàn lên.
- Ý nữa là dạo này hơi buồn tẻ đưa ra chủ đề khó một một tý để thảo luận cho vui. Còn vấn đề cơ bản miễn bàn.

Chú Tống xem lại bài toán xếp khách xong rồi hãy phán nhé. Chú hay phán bừa theo cảm tính lắm. Em Hiền viết rõ ràng rồi, có lẽ anh không cần phải giải thích lại cho chú đâu nhỉ.

Trong bài toán xếp khách Lucas, anh và em Hiền mỗi người đều có một cách giải, nhưng kết quả thì giống nhau. Không biết liệu có sai giống nhau không??? Chú Tống làm được thì post cách giải lên cho anh em xem nhé. Nếu ai cũng không muốn post bài, mà chỉ muốn đọc bài của người khác thì có lẽ diễn đàn không thể tồn tại được.

Em không nói là kết quả sai. Mà em nói là lý luận sai bản chất. Kết quả em cũng ra là 720 cách.
Em Post lời giải của em lên. Bác phán giúp.

Gọi số cách xếp 5 cặp vợ chồng thỏa mãn đầu bài là M5.
Vì cặp vợ chồng chủ nhà luôn ngồi cạnh nhau và chồng luôn ngồi bên phải. Suy ra số cách xếp cho vợ chồng chủ nhà ngồi trong 10 ghế là: 10 cách.
Với mỗi cách xếp vợ chồng chủ nhà: Ta xếp 5 cặp vợ chồng thành hàng ngang trong đó hai đầu là vợ chồng chủ nhà như: Vợ chủ nhà, chồng khách, vợ khách,.....,vợ khách, chồng chủ nhà.
Số cách xếp các bà vợ khách là: 4! cách (vì ông luôn ngồi xen kẽ hai bà).
Suy ra M5 = 10*4! * U4 , trong đó U4 là số cách xếp 4 ông chồng khách.
*) Tính U4 = ?
Đánh số các bà vợ khách (đã xếp) từ 1 đến 4 và đánh số các ông chồng khách tương ứng (ông i khách là chồng bà i khách). Sau đó đánh số ghế : Ghế i ở giữa bà khách i và bà khách i+1. Mỗi cách xếp các ông chồng khách được biểu diễn bằng phép thế từ tập {1,2,3,4} với qui ước có nghĩa là ghế i được xếp cho ông khách j. Theo đầu bài, phải thỏa mãn điều kiện và (*). Như vậy số tất cả các phép thế thỏa mãn điều kiện (*) chính là U4.
Xét tập tất cả các phép thế từ tập {1,2,3,4}. Gọi Pi là tính chất và Qi là tính chất . Áp dụng nguyên lý bù trừ ta có:
U4 = = 4! – N1 + N2 – N3 + N4
trong đó Nk ( là số các cách lấy ra k tính chất từ tập 7 tính chất đang xét.
Ta nhận thấy Pi và Qi không thể đồng thời xảy ra, và Pi+1 và Qi cũng không thể đồng thời xảy ra. Do vậy số cách lấy ra k tính chất từ 7 tính chất đang xét phải thêm vào điều kiện Pi và Qi, Pi+1 và Qi không đồng thời xảy ra cùng nhau (**). Số cách lấy ra k tính chất từ 7 tính chất đang xét là g(7,k) (g(7,k)=0 nếu k>4), sẽ có (4-k)! cách thỏa mãn. Suy ra Nk = g(7,k)*(4-k)!. Thay vào ta có:
U4 = 4! – g(7,1)*3! + g(7,2)*2! – g(7,3)*1! + g(7,4)*0!
*) Ta tính g(7,k) = ?
Xét 8 tính chất đang xét xếp thành hàng ngang P1Q1P2Q2...P4Q4 . Số cách lấy ra k tính chất chính thỏa mãn điều kiện (**) là (Vì khi lấy k tính chất ra sẽ còn (7-k) tính chất còn lại, (7-k) tính chất này tạo ra (7-k)+1 ô trống (tính cả ô trống ở hai đầu)). Suy ra g(7,k) = , thay vào ta được U4 như sau:
U4 = 4! - C(1,7)*3! + C(2,6)*2! - C(3,5)*1! + C(4,4)*0!
= 24 – 42 + 30 – 10 + 1 = 3
Thay U4 = 3 vào ta được M5 = 10*4! * U4 = 240 * 3 = 720 cách.

Em Copy từ bản Word giải của em ra nên có thể thiếu một số biến, nhưng không quan trọng lắm.

@ T.M.C: anh nói bài giải của em lý luận sai hẳn bản chất, vậy "sai hẳn bản chất" ở đây là ở chỗ nào và nên sửa thế nào? em "ngu lâu dốt dai" rất mong anh chỉ giáo!
còn về bài trình bày của anh, em có nhận xét nhỏ như thế này: vì anh nói là anh cop vào thiếu một số công thức, nếu công thức Pi và Qi của anh giống như thầy giảng thì em nghĩ ở đây chỉ có 7 thôi chứ không phải 8. lí do: các ghế được xếp trên đường thẳng nên không tồn tại tính chất Q4 = 5, không có ghế số 5. Trong bổ đề 1 tồn tại t/c này vì họ xếp theo vòng tròn và qui định n+1 =1

Hehe, mình cũng nghĩ như em Hiền, Qi và Pi tổng cộng chỉ có 7 tính chất thôi.

Uh đúng rồi. Em Hiền nói có lý, anh thắc mắc bài của em là chỗ 7 tính chất đấy. Có lẽ anh nhầm rồi. Xin lỗi em Hiền nha.

@T.M.C: ok, em chấp nhận lời xin lỗi của anh. he. lần sau anh thắc mắc thì nên hỏi thẳng, cũng có thể bài viết của em và mọi người chưa chính xác, đừng vội phủ đầu người khác như vậy.