Terdapat Sebuah Lantai yang Berukuran 2×N. Pada Lantai Tersebut, Ingin Dipasang N Buah Keramik
Terdapat sebuah lantai yang berukuran 2×N. Pada lantai tersebut, ingin dipasang N buah keramik, yang masing-masing berukuran 1×2 (perhatikan ilustrasi pada gambar 2.6).
Setiap keramik dapat dipasang secara mendatar (horizontal ataupun secara tegak (vertikal). Sebagai contoh, jika N=4 maka akan ada 5 buah cara berbeda memasang 4 keramik yaitu:
• Semua keramik dipasang secara horizontal.
• Semua keramik dipasang secara vertikal.
• Paling kiri ada 2 keramik vertikal, sisanya horizontal.
• Paling kiri ada 2 keramik horisontal, sisanya vertikal.
• Paling kiri dan paling kanan vertikal, sisanya horizontal.
Tentukan ada berapa cara memasang keramik untuk N=8?
Jawaban:
Untuk N = 8, kita perlu mencari berapa banyak cara memasang keramik pada lantai berukuran 2x8.
Jika kita mencoba menghitung secara manual, mungkin akan memakan waktu dan sulit dilakukan dengan cepat. Namun, kita dapat menggunakan pendekatan rekursif untuk menyelesaikan masalah ini dengan lebih efisien.
Misalnya, kita menandai dengan H jika keramik dipasang secara horizontal dan V jika keramik dipasang secara vertikal. Kemudian, untuk setiap lantai berukuran 2xN, kita dapat memikirkan dua kemungkinan: keramik pertama dipasang secara horizontal atau keramik pertama dipasang secara vertikal.
Jika keramik pertama dipasang secara horizontal (H), maka lantai yang tersisa adalah 2x(N-1). Kita bisa memasang sisa keramik dengan mempertimbangkan cara memasang lantai berukuran 2x(N-1).
Jika keramik pertama dipasang secara vertikal (V), maka keramik kedua juga harus dipasang secara vertikal (V) agar bisa menutupi lantai berukuran 2x2. Kemudian, lantai yang tersisa adalah 2x(N-2). Kita bisa memasang sisa keramik dengan mempertimbangkan cara memasang lantai berukuran 2x(N-2).
Dengan menggunakan pendekatan rekursif ini, kita dapat menghitung berapa banyak cara memasang keramik untuk N=8 dengan mempertimbangkan kedua kasus di atas.
Jumlah cara memasang keramik untuk N = 8 = jumlah cara memasang keramik pada lantai berukuran 2x7 + jumlah cara memasang keramik pada lantai berukuran 2x6.
Mari kita hitung secara bertahap:
Untuk N = 2, jumlah cara = 2 (HH, VV)
Untuk N = 3, jumlah cara = 3 (HHH, VVV, HVH)
Untuk N = 4, jumlah cara = 5 (HHHH, VVVV, HVHH, HVVH, VHHV)
Untuk N = 5, jumlah cara = 8 (HHHHH, VVVVV, HVHHH, HVVHH, VHHVV, HHVVH, VVHHV, HHHVH)
Untuk N = 6, jumlah cara = 13 (HHHHHH, VVVVVV, HVHHHH, HVVHHH, VHHVVV, HHVVHH, VVHHVV, HHHVVH, VVVHHV, HVHVHH, HHHVHV, VHHVHV, VVHVHH)
Untuk N = 7, jumlah cara = 21 (HHHHHHH, VVVVVVV, HVHHHHH, HVVHHHH, VHHVVVV, HHVVHHH, VVHHVVV, HHHVVHH, VVVHHVV, HVHVHHH, HHHVHVV, VHHVHVV, VVHVHHV, HVHHVHV, HHHHVHV, VHHHVHH, HVVVHVH, VVVVHHV, HVVHVHH, VHVHHHV, HHHVVHV)
Untuk N = 8, jumlah cara = 34
Jadi, ada 34 cara memasang keramik untuk N=8 pada lantai berukuran 2xN.