Đếm số xâu nhị phân "đẹp"

**Highschoolmath** · 06-10-2014, 11:49 PM

Problem Cho trước hai số nguyên dương $n$ và $k$ ($n>k$). Một xâu nhị phân độ dài $n$ gọi là "đẹp" nếu có ít nhất $k$ số $1$ xuất hiện liên tiếp trong xâu nhị phân. Đếm tất cả các xâu "đẹp" độ dài $n$.

**huynhcongbang** · 07-10-2014, 09:24 AM

Ta sẽ đếm số các xâu mà không có $k$ số 1 nào xuất hiện liên tiếp, đặt là $S(n)$ - các xâu này gọi là "không đẹp". Khi đó, số xâu cần tìm là $2^n-S(n)$.

Mình thử trong trường hợp $k=2$ trước.

Gọi $a(n)$, $b(n)$ là số các số không đẹp và tận cùng lần lượt bởi 1 và 0. Khi đó $S(n)=a(n)+b(n)$.

Ta có các công thức truy hồi: $a(n+1)=b(n), b(n+1)=a(n)+b(n)$.

Suy ra $b(n+1)=a(n)+b(n)=b(n-1)+b(n)$ hay công thức truy hồi của $S(n)$ là $S(n)=S(n-1)+S(n-2)$.

Trong trường hợp $k=3$ thì làm như sau:

Gọi $a(n), b(n)$ là số các số không đẹp và tận cùng lần lượt bởi 1 số 1, 2 số 1, $c(n)$ là số các số không đẹp và tận cùng bởi 0. Khi đó $S(n)=a(n)+b(n)+c(n)$.

Ta có các công thức truy hồi: $a(n+1)=c(n), b(n+1)=a(n), c(n+1)=a(n)+b(n)+c(n)$.

Suy ra $c(n+1)=c(n-1)+c(n-2)+c(n)$ hay công thức truy hồi của $S(n)$ là $S(n)=S(n-1)+S(n-2)+S(n-3)$.

Bằng cách làm tương tự, suy ra công thức truy hồi của $S(n)$ với $k$ tổng quát là $S(n)=\sum_{i=1}^k S(n-i)$.

Cách này thuộc dạng nghĩ sao làm vậy, chắc là có cách tinh tế hơn, nói 1 câu là ra luôn.

P/s: hãy giải bài toán tương tự sau (mình mới làm đêm qua):

Có bao nhiêu xâu nhị phân độ dài $n$ và nếu xét độ dài của dãy các số 1 nằm liên tiếp trong đó thì các độ dài đó phải là bội của $k$?

Công thức truy hồi đơn giản hơn bài kia nhiều.

**Highschoolmath** · 07-10-2014, 01:55 PM

Tớ cũng giải ra truy hồi như vậy nhưng lý luận lằng nhằng hơn cậu Lữ ạ. Bài kia của cậu tối tớ sẽ nghĩ, dạo này đang học tiếng Anh nên bận quá.

Góp vui thêm với Lữ bài nữa nhé, cũng khá hay:
Problem Một bác nông dân có $2n$ con gà, bác quyết định nhốt số gà này vào $n$ chiếc lồng sao cho:
i/ Mỗi lồng có đúng $2$ con gà.
ii/ Sau mỗi ngày, bác lại đổi chỗ các con gà theo quy tắc gà không được ở cùng lồng với những con gà mà nó đã từng ở cùng các ngày trước đó. Ví dụ ở ngày thứ nhất, gà $x$ ở với gà $a_1$, thì ngày thứ hai gà $x$ sẽ ở với gà $a_2$ khác $a_1$, ngày thứ ba thì sẽ là gà $a_3$ khác cả $a_1$ và $a_2$.
Tính số ngày tối đa mà bác nông dân có thể đổi chỗ các con gà.

RAIZA · 17-10-2014, 04:56 PM

Trích:

Nguyên văn bởi Highschoolmath

Tớ cũng giải ra truy hồi như vậy nhưng lý luận lằng nhằng hơn cậu Lữ ạ. Bài kia của cậu tối tớ sẽ nghĩ, dạo này đang học tiếng Anh nên bận quá.

Góp vui thêm với Lữ bài nữa nhé, cũng khá hay:
Problem Một bác nông dân có $2n$ con gà, bác quyết định nhốt số gà này vào $n$ chiếc lồng sao cho:
i/ Mỗi lồng có đúng $2$ con gà.
ii/ Sau mỗi ngày, bác lại đổi chỗ các con gà theo quy tắc gà không được ở cùng lồng với những con gà mà nó đã từng ở cùng các ngày trước đó. Ví dụ ở ngày thứ nhất, gà $x$ ở với gà $a_1$, thì ngày thứ hai gà $x$ sẽ ở với gà $a_2$ khác $a_1$, ngày thứ ba thì sẽ là gà $a_3$ khác cả $a_1$ và $a_2$.
Tính số ngày tối đa mà bác nông dân có thể đổi chỗ các con gà.

Mình nghĩ bài toán này liên quan đến bổ đề "Đấu vòng tròn":
Cho $n$ đội bóng. Một giải đấu vòng tròn là một giải đấu mà hai dội bất kì gặp nhau đúng một lần. Một vòng của giải đấu là một một tập các trận đấu mà có mặt đủ $n$ đội bóng sao cho mỗi đội có mặt đúng một lần (nếu $n$ lẻ thì mỗi vòng sẽ có một đội được miễn thi đấu). Khi ấy giải đấu vòng tròn gồm $n-1$ vòng nếu $n$ chẵn và $n$ vòng nếu $n$ lẻ.

06-10-2014, 11:49 PM	#1
Highschoolmath Moderator Tham gia ngày: Apr 2008 Đến từ: Hàm Dương-Đại Tần Bài gởi: 698 Thanks: 247 Thanked 350 Times in 224 Posts	Đếm số xâu nhị phân "đẹp" Problem Cho trước hai số nguyên dương $n$ và $k$ ($n>k$). Một xâu nhị phân độ dài $n$ gọi là "đẹp" nếu có ít nhất $k$ số $1$ xuất hiện liên tiếp trong xâu nhị phân. Đếm tất cả các xâu "đẹp" độ dài $n$. __________________ As long as I live, I shall think only of the Victory......................

07-10-2014, 09:24 AM	#2
huynhcongbang Administrator Tham gia ngày: Feb 2009 Đến từ: Ho Chi Minh City Bài gởi: 2,413 Thanks: 2,165 Thanked 4,188 Times in 1,381 Posts	Ta sẽ đếm số các xâu mà không có $k$ số 1 nào xuất hiện liên tiếp, đặt là $S(n)$ - các xâu này gọi là "không đẹp". Khi đó, số xâu cần tìm là $2^n-S(n)$. Mình thử trong trường hợp $k=2$ trước. Gọi $a(n)$, $b(n)$ là số các số không đẹp và tận cùng lần lượt bởi 1 và 0. Khi đó $S(n)=a(n)+b(n)$. Ta có các công thức truy hồi: $a(n+1)=b(n), b(n+1)=a(n)+b(n)$. Suy ra $b(n+1)=a(n)+b(n)=b(n-1)+b(n)$ hay công thức truy hồi của $S(n)$ là $S(n)=S(n-1)+S(n-2)$. Trong trường hợp $k=3$ thì làm như sau: Gọi $a(n), b(n)$ là số các số không đẹp và tận cùng lần lượt bởi 1 số 1, 2 số 1, $c(n)$ là số các số không đẹp và tận cùng bởi 0. Khi đó $S(n)=a(n)+b(n)+c(n)$. Ta có các công thức truy hồi: $a(n+1)=c(n), b(n+1)=a(n), c(n+1)=a(n)+b(n)+c(n)$. Suy ra $c(n+1)=c(n-1)+c(n-2)+c(n)$ hay công thức truy hồi của $S(n)$ là $S(n)=S(n-1)+S(n-2)+S(n-3)$. Bằng cách làm tương tự, suy ra công thức truy hồi của $S(n)$ với $k$ tổng quát là $S(n)=\sum_{i=1}^k S(n-i)$. Cách này thuộc dạng nghĩ sao làm vậy, chắc là có cách tinh tế hơn, nói 1 câu là ra luôn. P/s: hãy giải bài toán tương tự sau (mình mới làm đêm qua): Có bao nhiêu xâu nhị phân độ dài $n$ và nếu xét độ dài của dãy các số 1 nằm liên tiếp trong đó thì các độ dài đó phải là bội của $k$? Công thức truy hồi đơn giản hơn bài kia nhiều. __________________ Sự im lặng của bầy mèo

07-10-2014, 01:55 PM	#3
Highschoolmath Moderator Tham gia ngày: Apr 2008 Đến từ: Hàm Dương-Đại Tần Bài gởi: 698 Thanks: 247 Thanked 350 Times in 224 Posts	Tớ cũng giải ra truy hồi như vậy nhưng lý luận lằng nhằng hơn cậu Lữ ạ. Bài kia của cậu tối tớ sẽ nghĩ, dạo này đang học tiếng Anh nên bận quá. Góp vui thêm với Lữ bài nữa nhé, cũng khá hay: Problem Một bác nông dân có $2n$ con gà, bác quyết định nhốt số gà này vào $n$ chiếc lồng sao cho: i/ Mỗi lồng có đúng $2$ con gà. ii/ Sau mỗi ngày, bác lại đổi chỗ các con gà theo quy tắc gà không được ở cùng lồng với những con gà mà nó đã từng ở cùng các ngày trước đó. Ví dụ ở ngày thứ nhất, gà $x$ ở với gà $a_1$, thì ngày thứ hai gà $x$ sẽ ở với gà $a_2$ khác $a_1$, ngày thứ ba thì sẽ là gà $a_3$ khác cả $a_1$ và $a_2$. Tính số ngày tối đa mà bác nông dân có thể đổi chỗ các con gà. __________________ As long as I live, I shall think only of the Victory......................