Xét hình chữ nhật $1 \times n$ gồm $n$ ô vuông $1 \times 1$. Mỗi ô điền số $0$ hoặc $1$. Một cách điền "đẹp" nếu như ba ô liên tiếp nhau bất kỳ đều không chứa ba số giống nhau. Với mỗi $n \geq 3$, gọi $a_n$ là số cách điền "đẹp". Tính $a_n$.
Tính $a_n$ là số cách điền thỏa ba ô liên tiếp nhau bất kỳ đều không chứa ba số giống nhau
#1
Đã gửi 23-03-2023 - 10:43
#2
Đã gửi 24-03-2023 - 01:53
Ta gọi một cách điền "rất đẹp" nếu như đó là cách điền đẹp và có hai ô cuối cùng có số giống nhau.
Thế thì gọi $b_n$ là số cách điền "rất đẹp".
+) Tính $a_{n+1}$: Với mỗi cách điền $n$ ô trước là "đẹp" nhưng không phải "rất đẹp" ta có $2$ cách điền ô thứ $n+1$. Đồng thời với mỗi cách điền $n$ ô trước "không đẹp" ta có duy nhát $1$ cách điền ô thứ $n=1$. Do đó $a_{n+1} = 2a_n - b_n$.
+) Tính $b_{n+1}$: Giả sử ô thứ $n$ và $n+1$ đều là $0$. Thế thì ô thứ $n-1$ là $1$, và số cách điền lúc này chính là số cách điền $n-2$ ô đầu tiên có hai vị trí cuối không cùng bằng $1$, và bằng $a_{n-2} - \frac{b_{n-2}}{2}$.
Suy ra $b_{n+1} = 2a_{n-2} - b_{n-2}$.
Kết hợp lại ta có công thức truy hồi: $\begin{cases} a_{n+1} = 2a_n - b_n \\ b_{n+1} = 2a_{n-2} - b_{n-2}\end{cases}$
$\Rightarrow b_n = 2a_n - a_{n+1},\forall n\geq 1\Rightarrow 2a_{n+1} - a_{n+2} = 2a_{n-2} - 2a_{n-2} + a_{n-1},\forall n\geq 3$
$\Rightarrow a_{n+2} = 2a_{n+1} - a_{n-1},\forall n\geq 3$.
Tính được: $a_1 = 2, a_2 = 4, a_3 = 6, a_4 = 10$. Do đó ta có $a_{n+3} = 2a_{n+2} - a_n,\forall n\in\mathbb N^*$.
Từ đây dễ dàng tìm được CTTQ của $(a_n)$.
- Nesbit, supermember, perfectstrong và 2 người khác yêu thích
#3
Đã gửi 24-03-2023 - 14:14
Một bài toán có kết quả tương tự cũng liên quan tới xâu nhị phân có độ dài $n$
Các bạn thử thiết lập một song ánh với bài toán gốc xem!
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 24-03-2023 - 22:10
- Nesbit, perfectstrong và Hoang72 thích
#4
Đã gửi 25-03-2023 - 15:19
Ta gọi một cách điền "rất đẹp" nếu như đó là cách điền đẹp và có hai ô cuối cùng có số giống nhau.
Thế thì gọi $b_n$ là số cách điền "rất đẹp".
+) Tính $a_{n+1}$: Với mỗi cách điền $n$ ô trước là "đẹp" nhưng không phải "rất đẹp" ta có $2$ cách điền ô thứ $n+1$. Đồng thời với mỗi cách điền $n$ ô trước "không đẹp" ta có duy nhát $1$ cách điền ô thứ $n=1$. Do đó $a_{n+1} = 2a_n - b_n$.
+) Tính $b_{n+1}$: Giả sử ô thứ $n$ và $n+1$ đều là $0$. Thế thì ô thứ $n-1$ là $1$, và số cách điền lúc này chính là số cách điền $n-2$ ô đầu tiên có hai vị trí cuối không cùng bằng $1$, và bằng $a_{n-2} - \frac{b_{n-2}}{2}$.
Suy ra $b_{n+1} = 2a_{n-2} - b_{n-2}$.
Kết hợp lại ta có công thức truy hồi: $\begin{cases} a_{n+1} = 2a_n - b_n \\ b_{n+1} = 2a_{n-2} - b_{n-2}\end{cases}$
$\Rightarrow b_n = 2a_n - a_{n+1},\forall n\geq 1\Rightarrow 2a_{n+1} - a_{n+2} = 2a_{n-2} - 2a_{n-2} + a_{n-1},\forall n\geq 3$
$\Rightarrow a_{n+2} = 2a_{n+1} - a_{n-1},\forall n\geq 3$.
Tính được: $a_1 = 2, a_2 = 4, a_3 = 6, a_4 = 10$. Do đó ta có $a_{n+3} = 2a_{n+2} - a_n,\forall n\in\mathbb N^*$.
Từ đây dễ dàng tìm được CTTQ của $(a_n)$.
Hoàng có thể chia sẻ cách em học các phân môn không nhỉ cũng như từng tài liệu/ nguồn bài mà em tham khảo
- Nesbit yêu thích
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh