MATEMATIKA DISKRIT : SOAL INDUKSI (5, 6 & 8)

5.  Ketika n pasangan tamu tiba di pesta, mereka disambut oleh tuan dan nyonya rumah di pintu. Setelah saling berjabat tangan, tuan rumah bertanya kepada para tamu maupun istrinya untuk mengatakan berapa kali mereka masing – masing telah berjabat tangan. Ia memperoleh 2n + 1 jawaban yang berbeda. Jika tidak seorang pun berjabat tangan dengan istri atau suaminya sendiri, berapa kalikah nyonya rumah telah berjabat tangan?Buktikan jawaban anda dengan induksi matematika.

6.  Buktikan bahwa surat pos yang menggunakan perangko 24 sen atau lebih dapat hanya mengunakan perangko  sen atau 7 sen.

8.   sebuah kios penukaran uang hanya mempunyai pe cahan uang senilai Rp 2.000 dan Rp 5.000. Untuk uang senilai berapa saja yang dapat ditukar dengan kedua pecahan tersebut?Buktikan jawaban anda dengan induksi matematika.

JAWABAN

5. 

 i.  Basis Induksi :

p(1) benar, karena untuk n = 1 pasang, nyonya rumah berjabat tangan sebanyak 2 x 1 = 2

ii.  Langkah Induksi :

Andaikan p (n) benar, yaitu asumsikan jumlah jabat tangan nyonya rumah terjadi sebanyak 2n (hipotesis induksi). Kita harus menunjukan bahwa p(n + 1) juga benar, yaitu jumlah jabat tangan yang dlakukan nyonya rumah dengan n + 1 pasang tamu adalah 2(n+1).

Hal ini dapat ditunjukkan sebagai berikut:

Untuk n + 1 pasang, maka jumlah jabat tangan nyonya rumah yang terjadi haruslah jumlah jabat tangan nyonya rumah dengan tamu n pasang ditambah pasangan tamu ke(n+1). Menurut hipotesis induksi, untuk n pasang tamu, jumlah jabat tangan nyonya rumah adalah sebanyak 2n. Dengan di tambah pasangan tamu ke – (n+1) maka jumlah jabat tangan nyonya rumah bertambah 2 kali jabat tangan sehingga menjadi :

2n + 2 = 2 (n + 1)

6. kombinasi biaya pos dengan perangko 5 sen dan 7 sen saja untuk biaya sebesar n ≥ 24 dapat ditulis sebagai kombinasi 5n + 7m
Misalkan p(n) adalah proposisi bahwa untuk biaya pos sebesar n ≥ 24 hanya dapat menggunakan perangko 5 sen dan 7 sen.

i. Basis induksi :

p(24) benar, karena untuk biaya pos sebesar 24 dapat digunakan 2 buah perangko seharga 5 sen dan 2 perango seharga 7 sen.

ii. Langkah Induksi :

Misalkan p(n) benar yaitu biaya pos sebesar n ≥ 24  sen selalu dapat menggunakan perangko 5 sen dan 7 sen (hipotesis induksi). Kita harus menunjukan bahwa p(n+1) bener adalah biaya pos sebesar n + 1 juga dapat menggunakan perangko 5 sen dan 7 sen, yaitu :

Jika untuk membayar biaya pos sebesar n sen digunakan perangko 5 sen dan 7 sen, maka paling sedikit digunakan 2 buah perangko 5 sen dan 2 buah perangko 7 sen dengan 23 buah perangko 5 sen sehingga menggunakan 5 buah perangko 5 sen dapat dibayarlah biaya pos sebesar n + 1

 8.  Misalkan p(n) adalah proposisi yang menunjukan jumlah uang n 1000n rupiah yang akan ditukar dengan uang Rp 2.000, sedangkan dengan pecahan Rp 5.000. Kita akan buktikan p(n) degan induksi matematika.

i. Basis Induksi :

p(4) benar, karena uang Rp 4.000 dapat ditukarkan dengan 2 buah pecahan Rp 2.000.

ii.  Langkat Induksi :

Misalkan p(n) benar, yaitu asumsikan bahwa kios penukaran dapat menukarkan uang senilai 1000n rupiah dengan pecahan Rp 2.000 dan Rp 5.000 (hipotesis Induksi). Kita harus membuktikan bahwa p(n+1) rupiah denga menggunakan pecahan Rp 2.000 dan Rp 5.000. Ada dua kemungkinan yang kita tinjau :

• Jika untuk uang senilai 1000n rupiah, kios penukaran menggunakan minimal 2 buah pecahan Rp 2.000 (sebab n ≥ 4), maka dengan mengganti 2 buah pecahan Rp 2.000 tersebut dengan pecahan Rp 5.000, maka selalu diperoleh uang senilai  1000(n + 1) rupiah.

•  Jika untuk uang senilai 1000n rupiah, kios penukaran minimal 1 buah uang pecahan Rp 5.000 (sebab n ≥ 4), maka dengan mengganti 1 uang peahan Rp 5.000 dengan 3 buah uang pecahan Rp 2.000 selalu dapat di peroleh uang senilai 1000 (n + 1) rupiah.