Chủ đề này có 3 trả lời

[trungnob]

In how many ways can nine identical dominos (2 x 1 rectangles) be used to exactly cover a 3 x 6 rectangle with no overlap? Assume two coverings are different if the nine dominos are not in exactly the same positions.

I solved this problem and the answer is 41 , however I couldn't generalize this question ? .
Could anyone help me out to ?

[tuanmap]

Bằng cách nào bạn có thể tìm ra 41 là đáp số thế ? Để tổng quát bài toán này, bạn có thể đưa ra bài toán như sau:

Cho N domino giống nhau, hỏi có bao nhiêu cách xếp N domino phủ kín hình chữ nhật A x B ( A x B = 2N) ?

Hoặc mình đưa bài toán trên về 1 bài toán quen thuộc khác.
Giả sử ta đánh số các ô trong hình chữ nhật A x B từ trái qua phải, từ trên xuống dưới. Một domino có thể nằm trên 2 ô cạnh nhau. Ví dụ: trong bài toán ở trên, ô số 1 và 7 có thể phủ bởi 1 domino. Hay ô số 8 có 4 cách phủ (bởi donimo 7-8, 2-8, 8-9, 8-14).
Từ ý tưởng trên, ta thiết lập 1 đồ thị gồm A x B đỉnh, đỉnh a, b nối với nhau nếu 1 domino có thể phủ ô a và ô b.

1 cách phủ hình chữ nhật A x B là 1 chu trình Halmiton. Bài toán được đưa về bài toán đếm số chu trình Halmiton.

Mình đang tìm kiếm trên mạng xem có cách gì giải bài này không Hi vọng có.

[tuanmap]

hichichichic, sau 1 hồi shi nghĩ, mình thấy cách đếm dựa trên số chu trình Hamilton không ổn.
Vấn đề là 1 cách phủ có phải là 1 chu trình Hamilton hay không? Và ngược lại.

[namdung]

Bài này phải lập công thức truy hồi. Gọi a_n là số cách phủ hình chữ nhật 3x2n bằng các domino 1x2 thì có lẽ là


Làm thế nào để chứng minh được công thức truy hồi trên?

Hãy thử chứng minh cái này trước


bằng cách phân hoạch các cách xếp thành các loại:

loại k: Hình chữ nhật 3x2k là hình chữ nhật đầu tiên từ bên trái sang được phủ hoàn chỉnh bởi 3k domino.

rồi tính số cách xếp của từng loại.

Có thể là tôi cũng có nhầm lẫn gì đó, nhưng ý tưởng là như vậy.