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

[lucas123]

Có 4 giáo viên và 20 học sinh xếp hàng ngang để chụp ảnh lưu niệm. Có bao nhiêu cách xếp để giữa 2 giáo viên bất kì đều có ít nhất 2 học sinh

[Nobodyv3]

Có 4 giáo viên và 20 học sinh xếp hàng ngang để chụp ảnh lưu niệm. Có bao nhiêu cách xếp để giữa 2 giáo viên bất kì đều có ít nhất 2 học sinh

Giả sử các hs là giống nhau, được xếp thành hàng ngang. Ta tính số cách đặt 4 vạch chia vào các khoảng trống giữa các hs. Từ trái sang phải,gọi $x_{1}$ là số hs đứng trước vạch chia thứ nhất, $x_{2}$ là số hs đứng giữa vạch chia thứ nhất và thứ hai, $x_{3}$ là số hs đứng giữa vạch chia thứ hai và thứ ba, $x_{4}$ là số hs đứng giữa vạch chia thứ ba và thứ tư và $x_{5}$ là số hs đứng sau vạch chia thứ tư, được minh họa như sau :
$$ \underbrace{\ldots}_{x_{1}}\boldsymbol {\mid}\underbrace{\ldots}_{x_{2}}\boldsymbol {\mid}\underbrace{\ldots}_{x_{3}}\boldsymbol {\mid}\underbrace{\ldots}_{x_{4}}\boldsymbol {\mid}\underbrace{\ldots}_{x_{5}}$$
Và được biểu diễn bằng phương trình :
$$\left\{\begin{matrix}
x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=20\\
x_{1},x_{5}\geqslant 0,x_{2,3,4}\geqslant 2
\end{matrix}\right.
\Leftrightarrow \left\{\begin{matrix}
x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=14\\
x_{1,2,3,4,5}\geqslant 0
\end{matrix}\right.$$
có nghiệm là $ \binom{14+5-1}{5-1}=\binom{18}{4}$
Cuối cùng, vì hs, giáo viên là khác nhau nên ta có số cách xếp thỏa yêu cầu là $ 4!20!\binom{18}{4}\text{ cách} $.

[perfectstrong]

Một câu hỏi mở rộng thú vị là:

Nếu bây giờ các giáo viên và học sinh xếp thành vòng tròn để nhảy lửa trại nhưng vẫn thỏa yêu cầu ban đầu (giữa hai giáo viên có ít nhất 2 học sinh), thì có bao nhiêu cách sắp xếp?

[Dang Hong Ngoc]

Một câu hỏi mở rộng thú vị là:

Nếu bây giờ các giáo viên và học sinh xếp thành vòng tròn để nhảy lửa trại nhưng vẫn thỏa yêu cầu ban đầu (giữa hai giáo viên có ít nhất 2 học sinh), thì có bao nhiêu cách sắp xếp?

Ý tưởng của em là giả sử mỗi người đứng cạnh nhau thì nắm tay nhau, ta cho $4$ giáo viên mỗi người nắm tay $2$ học sinh

Chọn $1$ giáo viên và $2$ học sinh để tạo thành một nhóm xem như một phần tử, có $4$ phần tử như thế, xếp $4$ phần tử này và $12$ học sinh còn lại thành vòng tròn có $15!$ cách.

số cách là: $\left(2!C^{1}_{4}C^{2}_{20}\right)\left(2!C^{1}_{3}C^{2}_{18}\right)\left(2!C^{1}_{2}C^{2}_{16}\right)\left(2!C^{1}_{1}C^{2}_{14}\right)15!$

em nghĩ hình như đã đếm trùng một số cách nhưng em không biết trùng ở đâu ạ :'<

[perfectstrong]

Ý tưởng của em là giả sử mỗi người đứng cạnh nhau thì nắm tay nhau, ta cho $4$ giáo viên mỗi người nắm tay $2$ học sinh

Chọn $1$ giáo viên và $2$ học sinh để tạo thành một nhóm xem như một phần tử, có $4$ phần tử như thế, xếp $4$ phần tử này và $12$ học sinh còn lại thành vòng tròn có $15!$ cách.

số cách là: $\left(2!C^{1}_{4}C^{2}_{20}\right)\left(2!C^{1}_{3}C^{2}_{18}\right)\left(2!C^{1}_{2}C^{2}_{16}\right)\left(2!C^{1}_{1}C^{2}_{14}\right)15!$

em nghĩ hình như đã đếm trùng một số cách nhưng em không biết trùng ở đâu ạ :'<

Cái trùng đầu tiên là "sự quay vòng": ví dụ ABC, BCA, CAB đều cùng biểu diễn một vòng tròn nhưng là 3 cách khác nhau nếu của hàng ngang.

Cái trùng thứ hai là "sự đối xứng": ví dụ ABC và ACB là hai vòng tròn ngược nhau nhưng đối xứng trục của nhau.

[Nobodyv3]

Một câu hỏi mở rộng thú vị là:
Nếu bây giờ các giáo viên và học sinh xếp thành vòng tròn để nhảy lửa trại nhưng vẫn thỏa yêu cầu ban đầu (giữa hai giáo viên có ít nhất 2 học sinh), thì có bao nhiêu cách sắp xếp?

Trước hết, hoán vị vòng quanh 20 hs: có $19!$ cách.
Bố trí 4 vạch chia,WLOG theo chiều kim đồng hồ, ta có hình minh họa sau:
$$\ldots\boldsymbol {\mid}\underbrace{\ldots}_{x_{1}}\boldsymbol {\mid}\underbrace{\ldots}_{x_{2}}\boldsymbol {\mid}\underbrace{\ldots}_{x_{3}}\boldsymbol {\mid}\underbrace{\ldots}_{x_{4}}$$
Phương trình :
$$ \left\{\begin{matrix}
x_{1}+x_{2}+x_{3}+x_{4}=20\\
x_{i}\geqslant 2, i=\overline{1,4}
\end{matrix}\right.
\Leftrightarrow \left\{\begin{matrix}
x_{1}+x_{2}+x_{3}+x_{4}=12\\
x_{i}\geqslant 0
\end{matrix}\right.$$
có nghiệm là $\binom{12+4-1}{4-1}=\binom{15}{3}$.
Vậy số cách xếp thỏa yc là :
$19!4!\binom{15}{4}\text{ cách}$.
Em thấy hình như xoay $90^{o},180^{o},270^{o}$ là như nhau nên kết quả trên chia cho 4 thì phải!
Xin các anh chỉ bảo ạ.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 11-07-2021 - 17:14

[perfectstrong]

Những bài toán kiểu vòng tròn này thì đầu tiên là cố định một người nào đó làm mốc, và chỉ quan tâm phần còn lại

Ví dụ trong 4 giáo viên, cố định giáo viên $G_1$. Như thế sẽ xử lý được sự đếm trùng của "quay tròn".

[chanhquocnghiem]

Một câu hỏi mở rộng thú vị là:

Nếu bây giờ các giáo viên và học sinh xếp thành vòng tròn để nhảy lửa trại nhưng vẫn thỏa yêu cầu ban đầu (giữa hai giáo viên có ít nhất 2 học sinh), thì có bao nhiêu cách sắp xếp?

Ở bước đầu tiên là xếp 20 học sinh vào vòng tròn, ta có $19!$ cách. $19!$ cách này là theo quy ước về đếm cách xếp người theo vòng tròn, tức là chỉ quan tâm đến vị trí tương đối giữa các thành viên trong vòng tròn (không quan tâm đến cảnh quan bên ngoài). Tất cả các cách có được bằng cách xoay một góc $\alpha$ nào đó từ một cách ban đầu đều không được tính.

Vì vậy ở bước sau cùng không cần phải chia cho $4$, cho $24$ hoặc cho bất kỳ số nào khác.

Kết quả là $19!4!\binom{15}{3}$ (cách)
 

[perfectstrong]

Kết quả là $19!4!\binom{15}{3}$ (cách)

Anh đã cố định người giáo viên đầu tiên rồi đúng không? Thế thì ở cuối chỉ còn $3!$ thay vì $4!$ chứ nhỉ?
 

[chanhquocnghiem]

Anh đã cố định người giáo viên đầu tiên rồi đúng không? Thế thì ở cuối chỉ còn $3!$ thay vì $4!$ chứ nhỉ?
 

Cố định em học sinh đầu tiên xếp vào vòng tròn (gọi là em $A$ chẳng hạn), xem em này là mốc.

Mọi thành viên xếp vào sau đều xét vị trí tương đối so với em $A$.

Khi xếp giáo viên đầu tiên vào 1 trong 4 vạch thì có $4$ cách, chứ không phải $1$ cách (vì vị trí tương đối của $4$ vạch so với mốc là khác nhau). Xếp tiếp giáo viên thứ hai có $3$ cách... Như vậy xếp $4$ giáo viên vào vị trí $4$ vạch có $4!$ cách.