Đề bài: Hình dưới đây mô tả một cách sắp xếp bảy quân Domino giống nhau kích thước 1 cm x 2 cm phủ kín một hình chữ nhật kích thước 2 cm x 7 cm. Hỏi có tất cả bao nhiêu cách sắp xếp khác nhau cho bảy quân Domino kích thước 1 cm x 2 cm phủ kín hình chữ nhật kích thước 2 cm x 7 cm?
Bình luận và lời giải:
Một số bạn đọc cho đáp án là 21, nhưng riêng em Hoàng Nguyễn Minh Phương (học sinh lớp 10 trường THPT Chuyên Hà Nội Amsterdam) có đáp án là 11.
Có hai phương pháp giải. Một cách là phân loại thủ công và một cách là đếm số khả năng khi xếp lần lượt 1 quân, 2 quân, 3 quân Domino vào tương ứng các hình chữ nhật 2 x 1, 2 x 2, 2 x 3... để thiết lập hệ thức truy hồi cho trường hợp tổng quát xếp n quân Domino 1 x 2 vào hình chữ nhật 2 x n. Đáng chú ý ở đây là một số bạn đọc cho đáp án là 21 nhưng riêng em Hoàng Nguyễn Minh Phương (học sinh lớp 10 trường PTTH Chuyên Hà Nội Amsterdam) có đáp án là 11.
Lời giải 1 (của học sinh Hoàng Nguyễn Minh Phương)
Số quân domino xếp theo chiều đứng phải là số lẻ 1, 3, 5, 7. Xét 4 khả năng sau.
Trường hợp 1: Có 1 quân domino xếp đứng và 3 cặp hai quân domino xếp nằm.
Có 4 cách xếp lặp lại 2 lần như hình dưới do có thể xoay lại giống nhau:
Trường hợp 2: Có 3 quân domino xếp đứng và 2 cặp hai quân domino xếp nằm.
Có 10 cách xếp lặp lại 2 lần như hình dưới do có thể xoay lại giống nhau:
Trường hợp 3: Có 5 quân domino xếp đứng và 1 cặp hai quân domino xếp nằm.
Có 6 cách xếp lặp lại 2 lần như hình dưới do có thể xoay lại giống nhau:
Trường hợp 4: Có 7 quân domino xếp đứng và không có quân domino xếp nằm.
Có 1 cách xếp:
Kết luận: Tổng hợp 4 trường hợp phân loại ta có số cách xếp Domino là:
(4 + 10 + 6) : 2 + 1 = 11 (cách)
Chú ý : Nếu trong ba trường hợp 1, 2, 3 không tính số cách xoay coi là giống nhau thì số cách xếp Domino là 4 + 10 + 6 + 1 = 21 (cách).
Lời giải 2
Có 1 cách xếp 1 quân Domino 1 x 2 vào hình chữ nhật 2 x 1
Có 2 cách xếp 2 quân Domino 1 x 2 vào hình chữ nhật 2 x 2
Có 3 cách xếp 3 quân Domino 1 x 2 vào hình chữ nhật 2 x 3
Bằng quy nạp ta thiết lập được hệ thức truy hồi cho bài toán tổng quát.
Gọi an là số cách xếp n quân Domino 1 x 2 vào hình chữ nhật 2 x n
Khi đó ta có hệ thức truy hồi:
Cho n = 7 ta có đáp số bài toán là 21 cách xếp.
Lời cuối
Hai đáp số khác nhau vì trong đề bài không nêu rõ ràng định nghĩa thế nào là 2 cách xếp được coi là giống nhau. Bài toán này lấy ý tưởng từ một kỳ thi Olympic Toán. Đây là một bài học cho những người ra đề thi, đặc biệt là với các bài toán tổ hợp thì cần định nghĩa rõ ràng trong đề thi.