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


C1. Cho số nguyên n>1. Hãy tìm số các hoán vị (a_1,a_2,\cdots,a_n) của \{1,2,\cdots,n\} sao cho tồn tại duy nhất i để a_i>a_{i+1}.

C2. Cho n>1 là một số nguyên dương. Tìm số các tập con của \{1,2,\cdots,n\} sao cho trong mỗi tập con có ít nhất hai phần tử là hai số nguyên liên tiếp.

C3. Cho n>1 thí sinh ngồi quanh một bàn tròn. Hỏi có bao nhiêu cách phát đề sao cho hai thí sinh ngồi cạnh nhau luôn có đề khác nhau, biết rằng trong ngân hàng đề có đúng m>1 đề và mỗi đề có nhiều bản.

C4. Cho một mặt cầu. Một đường tròn lớn của mặt cầu là đường tròn nằm trong một mặt phẳng đi qua tâm của cầu và nằm trên mặt cầu. 5 đường tròn lớn khác nhau chia mặt cầu thành n phần. Tìm giá trị lớn nhất và bé nhất của n.

C5. Một tập hữu hạn các số nguyên dương được gọi là tốt nếu mỗi phần tử của nó ít nhất bằng số phần tử của nó. (Tập rỗng cũng được xem là tốt) Gọi a_n là số tập con tốt của [n] mà không chứa hai số liên tiếp, và b_n là số các tập con của [n] mà hai phần tử bất kì khác nhau ít nhất 3. Chứng minh rằng a_n=b_n với mỗi n\geq 0.

C6. Sử dụng các chữ số 0,1,2,3,4 ta có thể lập bao nhiêu dãy 10 chữ số sao cho hay chữ số cạnh nhau vênh nhau 1?

C7. Gọi A_n là kí hiệu tập các đoạn mã độ dài n hình thành bởi sử dụng các chữ a,b,c sao cho không có các chữ a hay b đứng cạnh nhau. B_n là tập các đoạn mã độ dài n hình thành từ các chữ a,b,c sao cho không có 3 chữ phân biệt đứng cạnh nhau. Chứng minh rằng |B_{n+1}|=3|A_n|\forall n\geq 1.

C8. Cho AE là hai đỉnh đối nhau của bát giác đều ABCDEFGH. Một con ếch bắt đầu nhảy từ A. Từ mỗi đỉnh khác E của đa giác, ếch có thể nhảy đến một trong hai đỉnh kề với đỉnh đó. Khi ếch đến đỉnh E nó sẽ dừng lại không nhảy nữa. Gọi u_n là số các đường khác nhau gồm n lần nhảy từ A đến E của ếch. Chứng minh rằng u_{2n-1}=0u_{2n}=\dfrac{x^{n-1}-y^{n-1}}{\sqrt{2}}, ở đây x=2+\sqrt{2},y=2-\sqrt{2}.

C9. Cho các số nguyên r,n thoả mãn 0\leq n\leq r. Kí hiệu s(r,n) là số cách xếp r người xung quanh n cái bàn tròn giống nhau sao cho mỗi bàn có ít nhất một người. Chứng minh rằng s(r,n)=s(r-1,n-1)+(r-1)s(r-1,n).

C10. Cho số nguyên dương n. Có tất cả bao nhiêu tập con S của [2n] có tính chất: trong S không có các số a,b|a-b|\in\{1;n\}? (Tập rỗng được xem là tập con có tính chất trên.)

3 thoughts on “Đếm bằng truy hồi (1)”

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