Olimpiade Sains Kota (OSK) 2013 - Komputer, Nomor 3

Question

Berapa banyak cara memasang domino 1x2 agar menutupi seluruh papan berukuran 3x4? Domino tidak dapat dipotong, maupun bertumpukan dengan domino lain. Selain itu seluruh bagian domino harus berada di dalam papan. Setiap domino dapat diputar/dirotasi.
A. 3
B. 11
C. 9
D. 10
E. 18

Mamat Rahmat · Accepted Answer

Soal ini juga dapat diselesaikan dengan membagi kasus dengan tepat (divide and conquer)

Bagi daerah menjadi dua bagian sebagai berikut :

Jika tidak ada domino yang melewati garis pembatas
Maka terdapat dua bagian sama besar.
Untuk setiap bagian, terdapat 3 kemungkinan, sehingga total ada 3x3=9
Jika terdapat domino yang melewati garis pembatas
Pasti terdapat 2 domino yang melewati garis pembatas. Karena jika ganjil (1 atau 3), maka setiap bagian akan terdapat ganjil sel yang kosong dan kita tidak dapat menutupi seluruh papan.
Terdapat 2 kemungkinan untuk kasus ini.

Dengan membagi kasus secara sistematis, akan diperoleh banyaknya kemungkinan adalah 9+2 = 11 cara
Jawaban : B

Restu Dhiyabilal · Answer

Carilah pola dari 3*n Pola ini dapat terlihat pada f(3), f(n) = f(n-1) + 2*f(n-2) f(0) = 1 f(1) = 1 f(2) = f(1) + 2*f(0) = 3 f(3) = f(2) + 2*f(1) = 5 f(4) = f(3) + 2*f(2) = 5 + 2*3 = 5+6 = 11

Kadek Surya Mahardika · Answer

misalkan papan dengan ukuran 3*N:

f(n) = f(n-1) + 2*f(n-2)

f(0) = 1

f(1) = 1

f(2) = 1 + 2*f(0) = 3

f(3) = 3 + 2*f(1) = 5

f(4) = 5 + 2*f(2) = 5 + 2*3 = 5+6 = 11

jadi banyaknya cara memasang: 11 cara

CMIIW

Olimpiade Sains Kota (OSK) 2013 - Komputer, Nomor 3

3 jawaban