Olimpiade Sains Provinsi (OSP) 2015 - Komputer, Nomor 19

Soal ini akan diselesaikan dengan Dynamic Programming. Kita akan mencari definisi rekursif umumnya. Analisis awal : Jika kita ingin menutupi ubin dengan mengusahakan cukup kolom pertama tertutupi, maka ada 5 kemungkinan

Dari sana kita buat sebuah pemisalan,

• A(N) adalah banyaknya pengubinan untuk lantai 4xN yang utuh (tidak ada bolong, perhatikan definisi selanjutnya)
• B1(N) adalah banyaknya pengubinan untuk lantai 4xN yang bolong 2 sel paling kiri di bagian atas (perhatikan gambar di bawah)
• B2(N) adalah banyaknya pengubinan untuk lantai 4xN yang bolong 2 sel paling kiri di bagian bawah(perhatikan gambar di bawah)
  (Perhatikan bahwa B1(N) = B2(N), anggap saja nilainya = B(N))
• C(N) adalah banyaknya pengubinan untuk lantai 4xN yang bolong 2 sel paling kiri di bagian atas dan bawah (perhatikan gambar di bawah)

 

Kita akan cari definisi A(N)
Berdasarkan gambar pertama di atas, ada 5 cara untuk cukup menutupi kolom pertama.

• Jika kita isi dengan cara bentuk 1, maka kita akan mendapatkan problem A, untuk panjang lantai N-1, banyaknya cara untuk kasus ini ada A(N-1)
• Jika kita isi dengan cara bentuk 2, maka kita akan mendapatkan problem A, untuk panjang lantai N-2, banyaknya cara untuk kasus ini ada A(N-2)
• Jika kita isi dengan cara bentuk 3, maka kita akan mendapatkan problem B1, untuk panjang lantai N-1, banyaknya cara untuk kasus ini ada B(N-1)
• Jika kita isi dengan cara bentuk 4, maka kita akan mendapatkan problem B2, untuk panjang lantai N-1, banyaknya cara untuk kasus ini ada B(N-1)
• Jika kita isi dengan cara bentuk 5, maka kita akan mendapatkan problem C, untuk panjang lantai N-1, banyaknya cara untuk kasus ini ada C(N-1

Sehingga berdasarkan 5 kasus tersebut, maka A(N) = A(N-1) + A(N-2) + 2*B(N-1) + C(N-1)

 

 

Kita akan cari definisi B(N)
(Perhatikan bahwa kita menggunakan B(N) untuk mendefinisikan B1(N) dan B2(N))

• Jika kita isi dengan ubin vertikal untuk menutupi bagian yang menonjol sehingga lantai menjadi utuh, maka kita akan mendapatkan problem A, untuk panjang lantai N-1, banyaknya cara untuk kasus ini ada A(N-1)
• Jika kita isi dengan 2 ubin horizontal untuk menutupi bagian yang menonjol, maka kita akan mendapatkan problem B, untuk panjang lantai N-1, banyaknya cara untuk kasus ini ada B(N-1)

Sehingga berdasarkan 2 kasus tersebut, maka B(N) = A(N-1) + B(N-1)

 

Kita akan cari definisi C(N)

• Jika kita isi dengan ubin vertikal untuk menutupi bagian yang menonjol sehingga lantai menjadi utuh, maka kita akan mendapatkan problem A, untuk panjang lantai N-1, banyaknya cara untuk kasus ini ada A(N-1)
• Jika kita isi dengan 2 ubin horizontal untuk menutupi bagian yang menonjol, maka dua bagian yang menonjol di atas dan bawah pasti akan ditutupi dengan ubin vertikal, maka kita akan mendapatkan problem C, untuk panjang lantai N-2, banyaknya cara untuk kasus ini ada C(N-2)

Sehingga berdasarkan 2 kasus tersebut, maka C(N) = A(N-1) + C(N-2)

 

Dari 3 definisi tersebut
A(N) = A(N-1) + A(N-2) + 2*B(N-1) + C(N-1)
B(N) = A(N-1) + B(N-1)
C(N) = A(N-1) + C(N-2)

Basis untuk rekurens ini adalah
A(0)=1, B(0)=C(0)=0
A(1)=1, B(1)=C(1)=1

	0	1	2	3	4	5	6	7
A	1	1	5	11	36	95	281	781
B	0	1	2	7	18	54	149	430
C	0	1	1	6	12	42	107	323

Sehingga jawabannya adalah 781

 

Solusi lain : http://math.stackexchange.com/questions/664113/count-the-ways-to-fill-a-4-times-n-board-with-dominoes