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

[Dung Du Duong]

Tìm số tập con của A={1;2;...;n} thỏa mãn trong mỗi tập con chứa ít nhất 2 số nguyên liên tiếp.

[khanghaxuan]

Tìm số tập con của A={1;2;...;n} thỏa mãn trong mỗi tập con chứa ít nhất 2 số nguyên liên tiếp.

Gọi số tập con của $A$ mà không có hai số nào liên tiếp nhau là $A_{0}$ .

 

Số tập con của A khác rỗng là :      $2^{n}-1$   

 

Gọi số tập con của A thỏa đề bài là $A$ 

 

Ta có :    $A=2^{n}-1-A_{0}$

Đến đây ta tìm cách tính $A_{0}$

 

Để tính $A_{0}$ thì ta quy về bài toán hình học như sau :   

 

(*)Cho một đa giác lồi $n$ cạnh . Tìm số các đa giác ( với cạnh nhỏ hơn ) không có bất kì cạnh nào là cạnh của đa giác đã cho.

 

Bài này trình bày khá dài nên mình chỉ nói cách giải thôi .   

( Dùng dãy truy hồi )  

Gọi $S_{n}$ là số các đa giác thỏa yêu cầu đề bài (*) 

 

Tới đây thì bạn lập ra một dãy truy hồi là xong bài ( Nói trước là dãy này khá dài ) 

[Kofee]

Mình nghĩ thế này...

Đặt S là tập con của A mà trong đó có ít nhất 2 ptử a,b sao cho |a-b|=1

Xét tập gồm các ptử (1;2);3;4;....;n-1;n gồm 1 ptử là cặp (1;2) và n-2 ptử là các số 3,4,5,...,n-1,n. Vậy với n-2 ptử 3,4,5,...,n-1,n ta có $2^{n-2}$ tập con.

Với mỗi tập con đó ta bỏ cặp (1;2) vào thì ta có tập con dạng S cho nên số tập con có cặp (1;2) là $2^{n-2}$

Tương tự, với tập (2;3);4;5;....;n-1;n (không chứa csố 1) ta có số tập con có cặp (2;3) (không chứa csố 1) là $2^{n-3}$

.....................

Số tập con có chứa (n-2;n-1) (không chứa 1,2,3,....,n-3) là 2.

Số tập con có chứa (n-1;n) (không chứa 1,2,3,....,n-2) là 1.

Vậy số tập con chứa ít nhất 2 số nguyên liên tiếp là:

$1+2+2^{2}+2^{3}+.....+2^{n-3}+2^{n-2}=2^{n-1}-1$

[quyennct1250daknong]

Lời giải đos chưa đúng kofee ah