Bài toán lát gạch
Cho một mảnh sân hình chữ nhật kích thước $1\times n$. Có bao nhiêu cách xếp các viên gạch $1 \times 1$ và $1 \times 2$ để lát kín mảnh sân đó?
Gọi $G(k)$ là số cách xếp gạch cho mảnh sân có kích thước $1\times k$.
Xét mảnh có kích thước $1\times(k+2)$, ta có thể lát kín mảnh này theo hai cách:
Cách 1: lắp viên $1 \times 1$ vào trước, số cách lắp phần còn lại là $G(k+1)$.
Cách 2: lắp viên $1 \times 2$ vào trước, số cách lắp phần còn lại là $G(k)$.
Từ đó ta có
$G(1)=1, G(2)=2; \\ G(k+2)=G(k+1)+G(k)$
Vậy $G(n)$ chính là số hạng thứ $n+1$ của dãy Fibonacci.
Theo công thức Binet, ta có
$G(n)=F _ { n+1 } = \frac { 1 } { \sqrt { 5 } } \left[ \left( \frac { 1 + \sqrt { 5 } } { 2 } \right) ^ { n +1} - \left( \frac { 1 - \sqrt { 5 } } { 2 } \right) ^ { n+1 } \right]$
Chẳng hạn, $n=20$ ta tính được $G(20)=10946$.
Với $n=25$ ta tính được $G(25)=121393.$
Xem thêm: DÃY FIBONACCI
Lời giải
Gọi $G(k)$ là số cách xếp gạch cho mảnh sân có kích thước $1\times k$.
Xét mảnh có kích thước $1\times(k+2)$, ta có thể lát kín mảnh này theo hai cách:
Cách 1: lắp viên $1 \times 1$ vào trước, số cách lắp phần còn lại là $G(k+1)$.
Cách 2: lắp viên $1 \times 2$ vào trước, số cách lắp phần còn lại là $G(k)$.
Từ đó ta có
$G(1)=1, G(2)=2; \\ G(k+2)=G(k+1)+G(k)$
Vậy $G(n)$ chính là số hạng thứ $n+1$ của dãy Fibonacci.
Theo công thức Binet, ta có
$G(n)=F _ { n+1 } = \frac { 1 } { \sqrt { 5 } } \left[ \left( \frac { 1 + \sqrt { 5 } } { 2 } \right) ^ { n +1} - \left( \frac { 1 - \sqrt { 5 } } { 2 } \right) ^ { n+1 } \right]$
Chẳng hạn, $n=20$ ta tính được $G(20)=10946$.
Với $n=25$ ta tính được $G(25)=121393.$
Xem thêm: DÃY FIBONACCI
Theo FB MathVn. Người đăng: Sơn Phan.