Đếm bằng truy hồi (2)


C11. Cho số nguyên dương n. Từ tập các hoán vị f của [n] thỏa mãn f(i)\geq i-1\,\,\forall i=2,3,\ldots,n ta chọn ngẫu nhiên một hoán vị, kí hiệu g. Gọi p_n là xác suất để hoán vị đó thỏa mãn g(i)\leq i+1\,\,\forall i=1,2,\ldots,n. Tìm tất cả các số nguyên dương n để p_n>\frac{1}{3}.

C12.  Cho số nguyên dương n. Gọi a_n là số các xâu nhị phân độ dài n không chứa khối 010, b_n là số các xâu nhị phân độ dài n không chứa các khối dạng 00111100. Chứng minh rằng với mỗi số nguyên dương n, ta có b_{n+1}=2a_n.

C13. Có bao nhiêu số tự nhiên n1000 chữ số thỏa mãn đồng thời hai điều kiện

1/. Tất cả các chữ số của n là lẻ;

2/. Giá trị tuyệt đối của hiệu hai chữ số liên tiếp bất kì của n bằng 2.

C14. Cho số nguyên dương n. Gọi O_n là số các xâu nhị phân (x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n) thỏa mãn \sum x_iy_i là số lẻ, và E_n là số các xâu nhị phân (x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n) thỏa mãn \sum x_iy_i là số chẵn. Chứng minh rằng \frac{O_n}{E_n}=\frac{2^n-1}{2^n+1}.

C15. Tìm số các số nguyên dương n thỏa mãn 4\leq n\leq 1023 và trong biểu diễn nhị phân của nó không có ba chữ số liên tiếp bằng nhau.

C16. Bảng chữ cái của một loại ngôn ngữ nào đó chỉ có hai chữ cái AB. Các từ trong ngôn ngữ này phải thỏa mãn đồng thời các điều kiện sau

1/. Không có từ với độ dài bằng 1;

2/. Chỉ có hai từ với độ dài bằng 2ABBB;

3/. Một dãy các chữ cái có độ dài n>2 là một từ khi và chỉ khi nó được tạo từ một từ khác có độ dài nhỏ hơn n theo cách sau: Các chữ A trong từ đó được giữ nguyên, mỗi chữ B của nó sẽ được thay bởi một từ khác (hai chữ B khác vị trí có thể được thay bởi hai từ khác nhau hoặc không).

Chứng minh rằng với mỗi số nguyên dương n, số các từ có độ dài bằng n trong ngôn ngữ đó là \frac{2^n+2\cdot (-1)^n}{3}.

C17. Cho số nguyên dương n. Tìm số các ánh xạ f:[n]\to [5] thỏa mãn

|f(i+1)-f(i)|\geq 3\,\,\forall i=1,2,\ldots,n-1.

C18. Với mỗi số nguyên n>1, kí hiệu S_n là số các hoán vị (a_1,a_2,\ldots,a_n) của n số nguyên dương đầu tiên, mà mỗi hoán vị (a_1,a_2,\ldots,a_n) đều có tính chất 1\leq |a_k-k|\leq 2\,\,\forall k=1,2,\ldots,n.

Chứng minh rằng 1,75\cdot S_{n-1}<S_n<2\cdot S_{n-1}\,\,\forall n>6.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s