22/11/2013


Bài 56. (Tháp Hà Nội) Bài toán này được đưa ra bởi nhà Toán học Pháp Edouard Lucas vào năm 1883. Có ba cái cọc và 8 cái đĩa được đặt trên một cái cọc, đĩa bé nằm trên đĩa to như hình dưới đây:

thaphanoi

Ta có mong muốn là chuyển tất cả các đĩa này sang một cái cọc khác trong hai cọc còn lại. Sao cho mỗi lần chỉ chuyển một đĩa và không bao giờ đĩa lớn nằm trên đĩa nhỏ. Thử vài lần ta thấy có thể làm được điều này, chỉ có điều là hơi lâu mà thôi.

Có người kể rằng Lucas còn làm bài toán với tháp Brahma với 64 cái đĩa với cùng luật chơi như trên nhưng mỗi ngày chỉ chuyển một cái đĩa. Và ông có nói rằng khi hoàn thành công việc thì Trái đất sẽ nổ tung.

Câu hỏi. Nếu ta có n\in\mathbb{N}^* cái đĩa thì cần ít nhất bao nhiêu bước để chuyển chúng sang một cái cọc khác?

Bài 57. (Jacob Steiner,1826) Trong mặt phẳng cho n đường thẳng sao cho không có hai đường nào song song và không có ba đường nào đồng quy. Hỏi các đường thẳng này chia mặt phẳng thành bao nhiêu phần?

Bài 58. 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}.

Bài 59. 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.

Bài 60.  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.

Bài 61. 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 hai chữ số cạnh nhau vênh nhau 1?

Bài 62. 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.

Bài 63. 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}.

Bài 64. 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).

Bài 65. 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}.

Bài 66.  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.

Bài 67. 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.

 Bài 68. 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}.

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