Page 13 - Matematika Diskrit Decision Making Based
P. 13
Contoh [LIU85]
Teka teki susun potongan gambar (jigsaw puzzle) terdiri dari sejumlah
potongan (bagian) gambar (lihat Gambar 1.1). Dua atau lebih potongan
dapat disatukan untuk membentuk potongan yang lebih besar. Lebih
tepatnya kita gunakan istilah blok bagi satu potongan gambar. Blok-
blok dengan batas yang cocok dapat disatukan membentuk blok yang lain
yang lebih besar. Akhirnya, jika semua potongan telah disatukan menjadi
satu buah blok, teka-teki susun gambar itu dikatakan telah dipecahkan.
Menggabungkan dua buah blok dengan batas yang cocok dihitung sebagai
satu langkah. Gunakan prinsip induksi kuat untuk membuktikan bahwa
untuk suatu teka-teki susun gambar dengan n potongan, selalu diperlukan
n-1 langkah untuk memecahkan teka-teki itu.
Gambar 1.1. Jigsaw Puzzle
Matematika Diskrit 09 Induksi Matematika
Ebook Decision Making Prinsip Induksi Kuat
