Đề thầy cho:
Tính số xâu nhị phân có độ dài 8 và có đúng 1 cặp 00.
Bạn nào giải xong đưa lời giải lên nha.

Còn [You must be registered and logged in to see this link.]

Bài toán:
Tìm công thức tính số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp và hai số 1 liên tiếp.

Cách giải:
Trước hết ta tìm số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp:
Gọi K_n là số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp. Ta có các trường hợp xảy ra:
− Số thứ n bằng 1. Số xâu thỏa mãn là K_n-1
− Số thứ n bằng 0. Ta xét tiếp:
Số thứ n-1 bằng 1 thì số xâu thỏa mãn là K_n-2
Số thứ n-1 bằng 0 thì số xâu thỏa mãn là 2^n-2

Vậy K_n = K_n-1 + K_n-2 + 2^n-2
Với điều kiện ban đầu K₁ = 0; K₂ = 1.
Bằng cách chứng minh tương tự, ta có số xâu nhị phân có độ dài n chứa hai số 1 liên tiếp cũng là:

K_n = K_n-1 + K_n-2 + 2^n-2
Với điều kiện ban đầu K₁ = 0; K₂ = 1.
Bây giờ, ta gọi số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp và hai số 1 liên tiếp là S_n, ta có các khả năng xảy ra:
− Hai số cuối là 00. Số xâu nhị phân thỏa mãn chính bằng số xâu nhị phân có độ dài n-2 chứa hai số 1 liên tiếp và bằng K_n-2.
− Hai số cuối là 11. Số xâu nhị phân thỏa mãn chính bằng số xâu nhị phân có độ dài n-2 chứa hai số 0 liên tiếp và bằng K_n-2.
− Trường hợp còn lại. Số xâu nhị phân thỏa mãn bằng S_n-1.

Vậy số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp và hai số 1 liên tiếp cho bởi công thức:

S_n = S_n-1 + 2K_n-2 với điều kiện ban đầu là K₁ = K₂ = K₃ = 0.

Tôi có ý tưởng như thế này.

Xét xâu nhị phân có độ dài 7, sao cho có ít nhất 1 số 0 và không có 2 số 0 nào cạnh nhau, do đó số số không trong xâu lớn nhất sẽ là 4 (nó không được lớn hơn số số 1 cộng 1).
- Với xâu có 1 số 0; 6 số 1: có [You must be registered and logged in to see this image.]
- Với xâu có 2 số 0; 5 số 1: có [You must be registered and logged in to see this image.]
- Với xâu có 3 số 0; 4 số 1: có [You must be registered and logged in to see this image.]
- Với xâu có 4 số 0; 3 số 1: có [You must be registered and logged in to see this image.]

Để thỏa mãn yêu cầu của bài toán, tức là chỉ có đúng một cặp 00 trong xâu nhị phân có độ dài là 8, ta chỉ cần thêm 1 số 0 vào xâu nhị phân có độ dài là 7 như trên ta đã xét, sao cho số 0 mới thêm nằm cạnh với số 0 đã có trong xâu (đặt trước hay sau thì cũng chỉ là một cách). Với xâu có bao nhiêu số 0 thì có bấy nhiêu cách để thêm sô 0.

Vậy đáp án là:
          [You must be registered and logged in to see this image.]

Còn công thức tổng quát với xâu có độ dài là n thì có lẽ là

          [You must be registered and logged in to see this image.]

(bạn nào tính hộ mình nhé)

Tôi đang băn khoăn chỗ này là số lượng:
- Với xâu có 2 số 0; 5 số 1: có [You must be registered and logged in to see this image.]
- Với xâu có 3 số 0; 4 số 1: có [You must be registered and logged in to see this image.]
- Với xâu có 4 số 0; 3 số 1: có [You must be registered and logged in to see this image.]

Nếu nó đã thành cặp 00 rồi thì sao? Ta thêm số 0 nữa cho đủ độ dài 8, thì không thoả mãn đầu bài có đúng 1 cặp 00

@Cuong: Nếu nó đã thành cặp 00 rồi thì sao? Ta thêm số 0 nữa cho đủ độ dài 8, thì không thoả mãn đầu bài có đúng 1 cặp 00
- Anh tưởng tượng như thế này nhé. Giả sử anh có một xâu thỏa mãn yêu cầu, tức là xâu có độ dài 8 chỉ có đúng 1 cặp 00. Anh xóa béng một số 0 trong cặp đó, lúc này xâu nhị phân sẽ có độ dài là 7, và không có bất cứ cặp 00 nào. Nhớ là xâu có độ dài 7 không có bất cứ cặp 00 nào nhé. Công việc của mình là làm ngược lại. Tìm tất cả các trường hợp có độ dài là 7, không có 2 số 0 đứng cạnh nhau. Sau đó thêm 1 số 0 vào cạnh số 0 trong xâu có độ dài 7.
Ví dụ: xâu có độ dài 7: 0110101
Như vậy ta sẽ có 3 cách thêm (tương ứng với số số 0 trong xâu, thêm trước hay sau số 0 đó đều như nhau) như sau:
00110101 (hoặc 00110101)
01100101 (hoặc 01100101)
01101001 (hoặc 01101001)
- Còn trường hợp tính : Với xâu có 2 số 0; 5 số 1; Với xâu có 3 số 0; 4 số 1; Với xâu có 4 số 0; 3 số 1. Anh hãy xem lại [You must be registered and logged in to see this link.], nó không được bò dọc liên tiếp, cũng như việc 2 số 0 không đứng cạnh nhau.

uh. Cũng có lý đấy. Thử tính xem đáp án là bao nhiêu nhé:
[You must be registered and logged in to see this image.]

= 7 + 30 + 15 + 4 = 56