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

[quocbaolqd11]

Cho $m, n$ nguyên dương , $S = \{ 1, 2, ... , 2014 \}$ . Tìm số tập con của $S$ có $m$ số chẵn, $n$ số lẻ và không chứa $2$ số liên tiếp.

đề thi chọn đội tuyển khtn vừa rồi. Mình thấy có lời giải của 1 bạn trên diễn đàn nhưng chưa chính xác lắm vì lời giải ấy không đề cập gì đến $m, n$. Mong các thành viên của diễn đàn và các bạn khtn thi đợt vừa rồi giúp đỡ.

 

[hxthanh]

Cho $m, n$ nguyên dương , $S = \{ 1, 2, ... , 2014 \}$ . Tìm số tập con của $S$ có $m$ số chẵn, $n$ số lẻ và không chứa $2$ số liên tiếp.

đề thi chọn đội tuyển khtn vừa rồi. Mình thấy có lời giải của 1 bạn trên diễn đàn nhưng chưa chính xác lắm vì lời giải ấy không đề cập gì đến $m, n$. Mong các thành viên của diễn đàn và các bạn khtn thi đợt vừa rồi giúp đỡ.

Xét bài toán tổng quát:

Tập $A=\{1,2,3,4,...,2N-1,2N\}$

Cần tìm số tập con có $n+m$ phần tử với $n$ phần tử chẵn, $m$ phần tử lẻ, và không có $2$ phần tử nào liên tiếp!

Gọi số đó là $S_N(n,m)$

Ta chia tập $A$ thành $N$ cặp liên tiếp:

$A=\{1,2\}\cup\{3,4\}\cup\ldots\cup\{2N-1,2N\}$

 

Giả sử ta chọn ra $n$ số chẵn trong $n$ cặp, khi đó các số lẻ trong các cặp đó sẽ không được chọn. Như vậy ta có $C_{N-n}^m$ cách chọn $m$ số lẻ. Lập luận tương tự ta cũng có số cách chọn ra $n$ số chẵn là $C_{N-m}^n$

 

Vậy $S_N(n,m)=C_{N-n}^m.C_{N-m}^n$.

 

Ví dụ $S_5(1,3)=C_4^3.C_2^1=8$

Cụ thể $A=\{1,2,3,4,5,6,7,8,9,10\}$

$\{1,3,5,8\};\quad\{1,3,5,10\};\quad\{1,3,6,9\};\quad\{1,3,7,10\};\quad\{1,4,7,9\};\quad\{1,5,7,10\};\quad\{2,5,7,9\};\quad\{3,5,7,10\}$

[quocbaolqd11]

Xét bài toán tổng quát:

Tập $A=\{1,2,3,4,...,2N-1,2N\}$

Cần tìm số tập con có $n+m$ phần tử với $n$ phần tử chẵn, $m$ phần tử lẻ, và không có $2$ phần tử nào liên tiếp!

Gọi số đó là $S_N(n,m)$

Ta chia tập $A$ thành $N$ cặp liên tiếp:

$A=\{1,2\}\cup\{3,4\}\cup\ldots\cup\{2N-1,2N\}$

 

Giả sử ta chọn ra $n$ số chẵn trong $n$ cặp, khi đó các số lẻ trong các cặp đó sẽ không được chọn. Như vậy ta có $C_{N-n}^m$ cách chọn $m$ số lẻ. Lập luận tương tự ta cũng có số cách chọn ra $n$ số chẵn là $C_{N-m}^n$

 

Vậy $S_N(n,m)=C_{N-n}^m.C_{N-m}^n$.

 

Ví dụ $S_5(1,3)=C_4^3.C_2^1=8$

Cụ thể $A=\{1,2,3,4,5,6,7,8,9,10\}$

$\{1,3,5,8\};\quad\{1,3,5,10\};\quad\{1,3,6,9\};\quad\{1,3,7,10\};\quad\{1,4,7,9\};\quad\{1,5,7,10\};\quad\{2,5,7,9\};\quad\{3,5,7,10\}$

em nghĩ lời giải có chút vấn đề ở chỗ tô đỏ, nó không chỉ không được chọn số còn lại trong cặp đã phân hoạch mà còn không được chọn cả số ở trong tập liền kề nữa. Ví dụ như $\{2k-1,2k\}$ và $\{2k+1,2k+2\}$ nếu như ta chọn $2k$ thì không chỉ có $2k-1$ không được chọn mà kéo theo cả $2k+1$ không được chọn nên chưa chắc chỉ có $N-m$ số lẻ là được phép lựa vào tập hợp. Em nghĩ phải tách chỗ này ra thành các tập mà các số được lẻ (chẵn) chọn là các bộ số có dạng $(a,b)$ mà $a-b=2$ và các bộ mà $a-b \ge 4$.

[hxthanh]

Em thắc mắc như vậy là rất xác đáng!

Tuy nhiên kết quả của bài toán vẫn chính xác! (Thế mới hay )

Ta lập công thức truy hồi cho $S_N(n,m)$ như sau:

Trong cặp thứ nhất nếu không chọn chẵn cũng không chọn lẻ thì ta có $S_{N-1}(n,m)$ cách chọn

Nếu chọn lẻ thì có $S_{N-1}(n,m-1)$ cách chọn

Nếu chọn chẵn thì cặp thứ 2: Có 2 khả năng:

KN1: Không chọn gì: Có $S_{N-2}(n-1,m)$ cách

KN2: Chọn chẵn tiếp thì cặp thứ 3 lại có 2 khả năng ...

 

Như vậy $S_N(n,m)=S_{N-1}(n,m-1)+\sum_{k=0}^n S_{N-1-k}(n-k,m)\qquad (1)$

 

Ta có thể kiểm tra thấy rằng $S_N(n,m)=C_{N-m}^n. C_{N-n}^m$ thỏa mãn $(1)$

Tuy nhiên, chứng minh nó bằng quy nạp thì cần lập luận thật đặc biệt và phải thật chặt chẽ, vì cần phải quy nạp theo cả 3 chiều! (Tạm thời tôi chưa nghĩ ra )