Đến nội dung

Hình ảnh

Có bao nhiêu cách lát một hình chữ nhật kích thước $2\times n$

- - - - -

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

#1
tiendatlhp

tiendatlhp

    Binh nhất

  • Thành viên
  • 35 Bài viết
Có bao nhiêu cách lát một hình chữ nhật kích thước $2\times n$ bởi các viên gạch hình chữ I (hình chữ nhất kích thước $1\times2$) và hình chữ L (hình vuông $2\times2$ bỏ đi 1 ô) ?

@supermember:

Mấy bài kiểu này có cách làm chung là tìm hệ thức truy hồi :).

Bài viết đã được chỉnh sửa nội dung bởi supermember: 24-02-2013 - 10:36


#2
reddevil1998

reddevil1998

    Hạ sĩ

  • Thành viên
  • 85 Bài viết
ý tưởng là hệ thức truy hồi :
Đánh số các ô từ trái qua phải là:$(1,2,3,...,n)$ (hàng 1) và $(n+1,n+2,...,2n)$ (hàng 2).Lát chúng bằng các viên $1\times 2$ sao cho chúng phủ kín hcn ,với $n$ lẻ thì ta bổ sung thêm viên $2\times 2$ để chúng phủ hết 2 ô $n,n+1$
Gọi $S_{n}$ là số cách lát thoả đề
Giả sử ta đã lát được hcn $2\times (n+1)$ ,xét viên gạch phủ lên ô vuông $n$
TH1:Viên gạch phủ lên $2$ ô$(n,2n)$ ,suy ra phần còn lại là một hcn $2\times n$ ,số cách lát :$S_{n}$
TH2:Viên gạch phủ lên $2$ ô $(n,n+1)$,suy ra phải có một viên phủ 2 ô $(2n-1,2n)$ ,phần còn lại là 1 hcn $2\times n-1$ ,suy ra số cách lát :$S_{n-1}$
TH3: viên gạch phủ lên 2 ô $(n,n+1)$ ($n$ lẻ) ,vậy phần còn lại chỉ được lát bởi các viên gạch nằm ngang (nếu có viên nào nằm dọc thì nó sẽ chia hcn thành 2 phần ,mỗi phần có 1 số lẻ ô chưa được lát ,số cách lát trong TH này : 1 cách.
Vậy công thức truy hồi cho bài này là:
$S_{2k}=S_{2k-1}+S_{2k-2}-1$(nếu n chẵn thì phải bớt đi 1 cách của $S_{2k-1}$)
Hoặc $S_{2k+1}=S_{2k}+S_{2k-1}$
Xử lí dãy số này ,ta tìm được số cách lát:
$S_{n}=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n})+\frac{1-(-1)^{n}}{2}$

#3
quocbaolqd11

quocbaolqd11

    Hạ sĩ

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

lời giải trên sai nhé, xét mấy TH đầu của bảng $2 \times n$ là thấy ngay. Và thêm nữa là bạn chưa xét trường hợp viên gạch chữ L phủ vào 3 ô $n,n+1,2n+2$ hay $n+1,2n+2,2n+1$.






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

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