Chủ đề này có 3 trả lời

[batigoal]

Mười hai hiệp sĩ ngồi quanh một bàn tròn. Mỗi hiệp sĩ ghét hai hiệp sĩ ngồi bên cạnh anh ta, nhưng không ghét ai trong số các hiệp sĩ khác. Một nhóm gồm năm hiệp sĩ được cử đi bảo vệ công chúa. Hai hiệp sĩ ghét nhau thì không được vào cùng 1 nhóm . Hỏi có thể lập được bao nhiêu nhóm hiệp sỹ đi bảo vệ công chúa.

[Karl Heinrich Marx]

Mười hai hiệp sĩ ngồi quanh một bàn tròn. Mỗi hiệp sĩ ghét hai hiệp sĩ ngồi bên cạnh anh ta, nhưng không ghét ai trong số các hiệp sĩ khác. Một nhóm gồm năm hiệp sĩ được cử đi bảo vệ công chúa. Hai hiệp sĩ ghét nhau thì không được vào cùng 1 nhóm . Hỏi có thể lập được bao nhiêu nhóm hiệp sỹ đi bảo vệ công chúa.

Hai hiệp sĩ được chọn gọi là kề nhau nếu họ chỉ ngồi cách nhau có 1 người. Ta dễ dàng suy ra là phải có ít nhất 3 cặp kề nhau trong 5 hiệp sĩ lựa chọn.
TH1: có 5 người kề nhau, có 12 cách chọn
TH2: có 4 người kề nhau cũng có 12 cách chọn, người còn lại chỉ có duy nhất 1 cách sắp chỗ. Suy ra th này có 12 cách
TH3: có 3 người kề nhau, số cách sắp xếp cho 2 người còn lại cũng chỉ có đúng 1 cách nên th này có 12 cách.
Tổng cộng là 36 cách.

[Friedrich Engels]

Tổng quát lên một chút.
Số hiệp sỹ lúc này sẽ là n, số hiệp sỹ được lựa chọn là k.
đặt n hiệp sĩ theo chiều kim đồng hồ là ${A_1} \to {A_n}$.
Nếu ${A_1}$ được chọn, khi đó, gọi ${x_t}$ là khoảng cách từ ${A_t}$ ( được chọn) đến người tiếp theo được chọn, tức là
\[\sum\limits_k {{x_i}} = n - k;{x_i} > 0\]
Như ta đã biết, phương trình này có $C_{n - k - 1}^{k - 1}$
Nếu ${A_1}$ không được chọn, tính từ ${A_1}$, ${A_p}$ là số được chọn đầu tiên thì ta có
\[\sum\limits_k {{x_i}} = n - k;{x_i} > 0\]
Nhưng lần này, \[{x_k} > p - 2\], tức là số nghiệm sẽ là $C_{n - k - p + 1}^{k - 1}$
vậy số nghiệm sẽ là

\[M = C_{n - k - 1}^{k - 1} + \sum\limits_{p = 2 \to n + 2 - 2k} {C_{n - k - p + 1}^{k - 1}} = C_{n - k - 1}^{k - 1} + C_{n - k}^k\]
P/S: bài này làm thì k mệt mà gõ mathtype thì mệt bơ phờ luôn , nên ai thấy hay thì like nhé

Bài viết đã được chỉnh sửa nội dung bởi Friedrich Engels: 03-07-2012 - 18:59

[anh qua]

Tổng quát lên một chút.
Số hiệp sỹ lúc này sẽ là n, số hiệp sỹ được lựa chọn là k.
đặt n hiệp sĩ theo chiều kim đồng hồ là ${A_1} \to {A_n}$.
Nếu ${A_1}$ được chọn, khi đó, gọi ${x_t}$ là khoảng cách từ ${A_t}$ ( được chọn) đến người tiếp theo được chọn, tức là
\[\sum\limits_k {{x_i}}  = n - k;{x_i} > 0\]
Như ta đã biết, phương trình này có $C_{n - k - 1}^{k - 1}$
Nếu  ${A_1}$  không được chọn, tính từ ${A_1}$, ${A_p}$ là số được chọn đầu tiên thì ta có
\[\sum\limits_k {{x_i}}  = n - k;{x_i} > 0\]
Nhưng lần này, \[{x_k} > p - 2\], tức là số nghiệm sẽ là $C_{n - k - p + 1}^{k - 1}$
vậy số nghiệm sẽ là

\[M = C_{n - k - 1}^{k - 1} + \sum\limits_{p = 2 \to n + 2 - 2k} {C_{n - k - p + 1}^{k - 1}}  = C_{n - k - 1}^{k - 1} + C_{n - k}^k\]
P/S: bài này làm thì k mệt mà gõ mathtype thì mệt bơ phờ luôn , nên ai thấy hay thì like nhé

Nếu em nhớ không nhầm thì bài này có trong Chuyên đề tổ hợp của nhóm anh Friedrich Engels phải không anh Engles - anh TP.