Câu hỏi 27
Cho $n$ là một số nguyên dương. Có các đĩa tròn với bán kính $1,2, \ldots, n$. Với mỗi kích thước ta có hai đĩa: một đĩa trong suốt và một đĩa không trong suốt. Mỗi đĩa có một lỗ nhỏ ở chính tâm, nhờ đó ta có thể xếp chồng các đĩa lên một thanh thẳng đứng. Ta muốn tạo các chồng đĩa thỏa mãn các điều kiện sau:
- Với mỗi kích thước có đúng một đĩa nằm trong chồng.
- Khi nhìn thẳng từ trên xuống, ta có thể thấy mép ngoài của tất cả $n$ đĩa trong chồng. (Nghĩa là, nếu có một đĩa không trong suốt nằm trong chồng thì bên dưới nó không được có đĩa nào nhỏ hơn.)
Hãy xác định số chồng đĩa khác nhau có thể tạo được thỏa mãn các điều kiện trên. (Hai chồng được coi là khác nhau nếu chúng không dùng đúng cùng một tập hợp đĩa, hoặc nếu chúng dùng đúng cùng một tập hợp đĩa nhưng không theo cùng một thứ tự.)
- Với mỗi kích thước có đúng một đĩa nằm trong chồng.
- Khi nhìn thẳng từ trên xuống, ta có thể thấy mép ngoài của tất cả $n$ đĩa trong chồng. (Nghĩa là, nếu có một đĩa không trong suốt nằm trong chồng thì bên dưới nó không được có đĩa nào nhỏ hơn.)
Hãy xác định số chồng đĩa khác nhau có thể tạo được thỏa mãn các điều kiện trên. (Hai chồng được coi là khác nhau nếu chúng không dùng đúng cùng một tập hợp đĩa, hoặc nếu chúng dùng đúng cùng một tập hợp đĩa nhưng không theo cùng một thứ tự.)