Đến nội dung

Hình ảnh

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

- - - - -

  • Please log in to reply
Chủ đề này có 3 trả lời

#1
Math04

Math04

    Trung sĩ

  • Thành viên
  • 120 Bài viết

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$.



#2
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

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)$.



#3
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3916 Bài viết
Vâng, vậy là @Hoang72 đã chứng minh được $a_n=2F_{n+1}$ với $(F_{n})$ là dãy số Fibonacci.
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$
Bài toán
Đếm số các xâu nhị phân độ dài $n$ mà không có bit nào đứng riêng lẻ (nghĩa là có ít nhất 2 bit cùng loại đứng cạnh nhau)

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


#4
Math04

Math04

    Trung sĩ

  • Thành viên
  • 120 Bài viết

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






1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh