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

[Trần Đức Anh @@]

Bài toán: Một câu lạc bộ bơi lội có n thành viên tổ chức 4 cuộc bơi lội và $F_1$, $F_2$, $F_3$, $F_4$ là các đội tham gia vào các cuộc bơi lội ấy. Hỏi có bao nhiêu cách chia các đội sao cho $F_{1}\cap F_{2}\neq\varnothing$, $F_{2}\cap F_{3}\neq\varnothing$, $F_{3}\cap F_{4}\neq\varnothing$.

Bài viết đã được chỉnh sửa nội dung bởi Trần Đức Anh @@: 04-11-2012 - 17:08

[The Gunner]

Haiz mấy bài đếm này làm toát mồ hôi mà chả bik đúng ko nữa. Mình post sơ ý tưởng trước xem thử:
gọi $P_n,Q_n,R_n,S_n$ là số các bộ $F_1,F_3,F_3,F_4$ thỏa mãn trong $|F_1 \cap F_2|,|F_2 \cap F_3|,|F_3 \cap F_4|$ lần lượt có 0,1,2,3 số bằng 0.
Bài toán sẽ đưa về đếm $P_n$
mà ta nhận thấy
Xét $P_{n+1}$. nếu bỏ đi 1 phần tử thì nó có thể thuộc một trong 4 tập $|F_i|$ hoặc giao của 2 , của 3 hoặc của 4 tập đó nên ta có $\binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4}$ cách chèn vào trong $P_n$. Mà phần tử này có thể thuộc phần giao của của các tập $F_i$ nên ta có thể suy ra được $P_{n+1}=15P_n+Q_n+R_n+S_n $ (1)
bây giờ ta lại xây dựng cho $Q_n$. Tương tự như trên ta sẽ suy ra $Q_{n+1}=11Q_{n}+2R_{n}+3S_{n}$ (2)
ở đây $11=\binom{4}{1}+\binom{4}{2}-1+\binom{4}{3}-2 $
ở chỗ tô màu đỏ là do xét 1 số bằng 0 chẳng hạn $|F_1 \cap F_2|$ thì trường này ko đc tính vì ko có phần tử chung. tương tự như ở chỗ màu xanh
con với $2R_{n}$ là do xét trường hợp n phần tử mà trong 3 số đang xét có 2 số bằng 0 thì ta chỉ có 2 cách để bổ sung phần tử $n+1$ để 3 số đang xét còn 1 số bằng 0, tương tự với xét $3S_n$
Tiep tục như thế ta xây dựng được $R_{n+1}=8R_n+3S_n$(3)
Ta tinh $S_n$. vì trường hợp này 3 số đang xét ở trên đều bằng 0 tức là mỗi phần tử của tập n phần tử đều ko thuộc giao của 3 tập trên. tức là mỗi phần tử sẽ có $15-3=12$ cách chọn nên có $S_n=12^n$ (4)
Tư (1),(2),(3) và (4) ta có thể suy ngược lại công thức của $P_n$.

P/s:Trên đây chỉ là ý tưởng,mình chưa tính ra rõ ràng có thể có sai sót mình sẽ edit sau.
@ai có thể giúp mình tính nốt phần còn lại được ko

Bài viết đã được chỉnh sửa nội dung bởi Trần Đức Anh @@: 05-11-2012 - 05:50

[perfectstrong]

Lời giải 2:
Gọi mỗi thành viên là $x_1;x_2;...;x_n$. Xét một cách chia $\alpha$ thỏa yêu cầu.
Ta xét ánh xạ $f$ như sau: Đặt tương ứng $x_i$ với tập $A_i$ theo quy tắc: nếu $x_i \in F_j$ thì bổ sung phần tử $j$ vào $A_i$.
Dễ dàng thấy rằng $f$ là song ánh. Như vậy, số cách chia $\alpha$ thỏa yêu cầu là số $n$-bộ $(A_1;A_2;...;A_n)$ sao cho $A_i \subset \lbrace 1;2;3;4 \rbrace$ và $A_i$ không chứa các cặp phần tử $(1;2);(2;3);(3;4)$.
Các tập con của $\lbrace 1;2;3;4 \rbrace$ không chứa các cặp phần tử $(1;2);(2;3);(3;4)$ là \[
\left\{ 1 \right\};\left\{ 2 \right\};\left\{ 3 \right\};\left\{ 4 \right\};\left\{ {1;3} \right\};\left\{ {1;4} \right\};\left\{ {2;4} \right\}
\]
Có $7$ tập như vậy, và $A_i$ được chọn một và chỉ một trong các tập đó.
Suy ra, số cách phân đội thỏa đề là $7^n$.

[HeilHitler]

Bài toán: Một câu lạc bộ bơi lội có n thành viên tổ chức 4 cuộc bơi lội và $F_1$, $F_2$, $F_3$, $F_4$ là các đội tham gia vào các cuộc bơi lội ấy. Hỏi có bao nhiêu cách chia các đội sao cho $F_{1}\cap F_{2}\neq\varnothing$, $F_{2}\cap F_{3}\neq\varnothing$, $F_{3}\cap F_{4}\neq\varnothing$.

Hoặc là:
Đặt $M=F_1 \cap F_3; N= F_3 \cap F_2; P=F_2 \cap F_4; H_1=F_1\M; H_2=M; H_3=F_3\(M \cup N); H_4=N; H_5=F_2\(N \cup P); H_6=P; H_7=F_4\P$.
Khi đó thấy ngay:
$|H_1|+|H_2|+|H_3|+|H_4|+|H_5|+|H_6|+|H_7|=n$
Bài toán quy về việc đếm số cách chia $n$ cái kẹo cho 7 em bé.
+Nếu các chiếc kẹo là phân biệt thì có $7^n$ cách.
+Nếu số kẹo là không phân biệt thì có $C^{6}_{n+6}$ cách.

Bài viết đã được chỉnh sửa nội dung bởi HeilHitler: 06-11-2012 - 23:44

[The Gunner]

nice solution
Nhìn bài này mới nhớ có một bài khá đẹp và khá giống bài này:
Cho tập $M=(1,2,...,n)$ tính số các phân hoạch M thành 3 tập con $A,B,C$ thỏa mãn các đk
$|A \cap B|>0,|B \cap C|>0,|C \cap A|>0,|A \cup B \cup C|=M,|A \cap B \cap C|=0$
---------------------------------------------------------------------------------------------------
Giải bài này luôn anh!

Bài viết đã được chỉnh sửa nội dung bởi Trần Đức Anh @@: 09-11-2012 - 20:06

[The Gunner]

Bài này nó khác bài trên ở chỗ cái giao 3 tập là rỗng nên sử dụng ý tưởng truy hồi như cách truy hồi trên cũng ko khác là mấy.
Đặt các dãy tương tự như trên với $P_n,Q_n,R_n,S_n$ là số bộ $ A,B,C$ thỏa mãn trong 3 số $|A \cap B|,|B \cap C|,|C \cap A|$ lần lượt có 0,1,2,3 số bằng 0. Thì theo cách lí luận như cách mình bài trên thì xây dựng đc hệ sau
$P_{n+1}=6P_n+Q_n$
$Q_{n+1}=5Q_n+2R_n$
$R_{n+1}=4R_n+3S_n$
tính đc $S_n=3^n$
suy ngược lại $P_n=3.4^n+6^n-3^n-3.5^n$
Nếu ko tính tứ tự thì là $\frac{P_n}{6}$