Diskusi Kelompok (I) MA2151 Matematika diskrit Semester 1, 2008-2009 Waktu: 100 menit Selasa, 23 September 2008 Pengajar: Hilda Assiyatun, Djoko Suprijanto
1. Ubahlah pernyataan ke dalam berikut ke dalam bentuk ”Jika p maka q.” (a) Mahasiswa perlu membawakan tas dosen untuk mendapat nilai A. (b) Angin dari utara menandakan musim kemarau. (c) Syarat cukup agar garansi komputer berlaku adalah komputer tersebut dibeli kurang dari setahun yang lalu. (d) Kamu dapat mengakses website hanya jika kamu berlangganan internet. 2. Misalkan I ( x) dan C ( x, y) mendefinisikan pernyataan-pernyataan berikut. I ( x) : ”x mempunyai akses internet”, C ( x, y) : ”x dan y ’chatting’ di internet,” dengan semesta untuk x dan y adalah himpunan semua mahasiswa di kelas matematika diskrit. Tuliskan kembali pernyataan-pernyataan berikut dengan menggunakan kuantor dan simbol di atas. (a) Tidak semua mahasiswa di kelas mempunyai akses internet. (b) Ada mahasiswa di kelas yang mempunyai akses internet tetapi tidak pernah ”chatting”. (c) Setiap mahasiswa di kelas yang mempunyai akses internet sudah pernah ”chatting” dengan sedikitnya seorang teman sekelasnya. (d) Terdapat dua mahasiswa yang belum pernah ”chatting” dengan orang yang sama di kelas. 3. Misalkan x ∈ R. Buktikan bahwa terdapat tepat sebuah bilangan n dan sedemikian sehingga x = n + , dengan n bilangan bulat dan 0 ≤ < 1. 4. Sebatang coklat berbentuk persegi panjang terdiri atas n persegi (bujursangkar), dengan n ≥ 1. Coklat dapat dipotong sepanjang garis vertikal atau horizontal untuk mendapatkan potongan coklat berbentuk persegi panjang yang lebih kecil. Tentukan berapa kali pemotongan harus dilakukan agar kita memperoleh n potong coklat berbentuk persegi kecil.
Solusi Diskusi Kelompok (I) MA2151 Matematika diskrit Semester 1, 2008-2009 Selasa, 23 September 2008
1. (a) Jika mahasiswa mendapat A maka dia (pernah) membawakan tas dosen. (b) Jika angin (bertiup) dari utara maka (sekarang) musim kemarau. (c) Jika komputer dibeli kurang dari satu tahun lalu maka garansinya berlaku. (d) Jika kamu dapat mengakses internet maka kamu berlangganan internet. 2. (a) Terdapat x sehingga ¬ I ( x). Atau ∃ x 3 ¬ I ( x). (b) Terdapat x sehingga I ( x) dan ¬C ( x, y) untuk setiap y, ( y 6= x). Atau ∃ x 3 I ( x) ∧ ¬C ( x, y), ∀ y, ( y 6= x). Atau ∃ x 3 ∀ y, ( y 6= x), I ( x) ∧ ¬C ( x, y). (c) Jika I ( x) maka terdapat y sehingga C ( x, y). Atau I ( x) =⇒ ∃ y 3 C ( x, y). Atau untuk semua x terdapat y, ( y 6= x, ) sehingga I ( x) ∧ C ( x, y). Atau ∀ x, ∃ y, ( y 6= x) 3 I ( x) ∧ C ( x, y). (d) Terdapat x dan y sehingga untuk setiap z, ( z 6= x, z 6= y), ¬(C ( x, z) ∨ C ( y, z)). Atau ∃ x, ∃ y 3 ¬(C ( x, z) ∨ C ( y, z)), ∀ z, ( z 6= x, z 6= y). Atau ∃ x, ∃ y 3 ¬C ( x, z) ∧ ¬C ( y, z)), ∀ z, ( z 6= x, z 6= y). 3. Misalkan x ∈ R. Pilih n = b xc, dan pilih = x − n = x − b xc. Jelas bahwa n dan bernilai tunggal, dimana n bilangan bulat dan 0 ≤ < 1. Diperoleh bahwa = x − n = x − b xc ⇐⇒ x = n + . 4. Akan dibuktikan dengan menggunakan induksi kuat. Misalkan proposisi ini P(n), n ∈ N adalah: banyaknya pemotongan yang dibutuhkan adalah n − 1. Langkah basis: Jika n = 1, jelas bahwa dibutuhkan 0 pemotongan untuk mendapatkan 1 persegi. Jadi P(1) benar. Langkah induktif: Misalkan P( j) benar untuk setiap 1 ≤ j ≤ k. Akan ditunjukkan P(k + 1) benar. Pandang coklat C yang terdiri dari k + 1 persegi. Asumsikan C memuat sedikitnya 2 kolom, karena k + 1 ≥ 2. Potong sepanjang salah satu kolom, sehingga diperoleh dua potong coklat, sebut C1 dan C2 , masingmasing terdiri dari k1 dan k2 persegi, dimana k1 + k2 = k + 1, dan k1 , k2 < k + 1. Berdasarkan hipotesis induksi, Ci , i = 1, 2, dapat dipecah menjadi ki persegi melalui ki − 1 pemotongan. Akibatnya C dapat dipecah menjadi k + 1 persegi melalui 1 + (k1 − 1) + (k2 − 1) = k1 + k2 − 1 = k pemotongan. Jadi terbukti P(k + 1) benar. Dengan demikian terbukti P(n) benar untuk setiap n ∈ N.
2
Solusi Diskusi Kelompok II MA2151 Matematika diskrit Semester 1, 2008-2009 Waktu: 100 menit Selasa, 28 Oktober 2008 Pengajar: Hilda Assiyatun, Djoko Suprijanto
1. Ada 51 rumah di sebuah jalan. Setiap rumah diberi nomor berupa bilangan yang dipilih mulai dari 1000 sampai dengan 1099. Tunjukkan bahwa ada dua buah rumah yang nomornya adalah dua bilangan yang berurutan. Jawab: Perhatikan 50 kotak berikut beserta labelnya yang diberikan pada lajur bawah. (1000,1001)
(1002,1003)
(1004,1005)
···
(1098,1099)
Masukkan ke-51 nomor rumah ke dalam kotak yang labelnya memuat nomor tersebut. Perhatikan bahwa setiap kotak hanya bisa diisi oleh paling banyak dua nomor. Karena kotak lebih sedikit dari nomor rumah, berdasarkan PHP, terdapat kotak yang berisi dua nomor rumah, yaitu yang merupakan dua bilangan berurutan. 2. Tentukan banyaknya bilangan bulat positif yang kurang dari 1000000 (1 juta) yang hasil penjumlahan digit-digitnya kurang dari 16. Jawab: Kita ubah dulu persyaratan bulat positif menjadi bulat nonnegatif. Bilangan yang diinginkan mempunyai paling banyak enam digit. Perhatikan bahwa bilangan yang kurang dari enam digit dapat dituliskan dalam enam digit, dimana digitdigit awalnya adalah 0. Misalkan bilangan tersebut adalah x1 x2 x3 x4 x5 x6 , dengan xi bilangan bulat nonnegatif, untuk i = 1, 2, . . . , 6. Maka banyaknya bilangan bulat nonnegatif yang dicari adalah sama dengan banyaknya solusi bulat nonnegatif dari x1 + x2 + x3 + x4 + x5 + x6 < 16, dengan xi ≤ 9.
(1)
Untuk selanjutnya, setiap varibel yang kita gunakan selalu diasumsikan bilangan bulat nonnegatif. Perhatikan dua pertaksamaan di bawah ini, x1 + x2 + x3 + x4 + x5 + x6 < 16, xi ≥ 0.
(2)
x1 + x2 + x3 + x4 + x5 + x6 < 16, terdapat xi > 9.
(3)
Banyaknya solusi (1) adalah banyaknya solusi (2) dikurangi banyaknya solusi (3). Pertaksamaan (2) dapat diselesaikan dengan menambahkan variabel baru y yang bernilai bulat positif. x1 + x2 + x3 + x4 + x5 + x6 + y = 16. (4) Definisikan z = y − 1. Maka z adalah bilangan bulat nonnegatif.
Akibatnya, banyaknya solusi bulat nonnegatif dari (2) adalah sama dengan banyaknya solusi bulat nonnegatif dari
⇐⇒ x1 + x2 + x3 + x4 + x5 + x6 + ( z + 1) = 16 ⇐⇒ x1 + x2 + x3 + x4 + x5 + x6 + z = 15.
(5)
Banyaknya solusi bulat nonnegatif dari (2) adalah C (15 + (7 − 1), 15) = C (21, 15) = C (21, 6) = 54264. Untuk pertaksamaan (3), perhatikan bahwa hanya ada tepat satu xi yang boleh bernilai lebih dari 9. Untuk sementara kita misalkan x1 ≥ 10. Maka banyaknya solusi dari (3) sama dengan 6 kali banyaknya solusi dari persamaan di bawah ini (karena x1 dapat digantikan oleh xi yang lain, i = 2, . . . , 6.) x1 + x2 + x3 + x4 + x5 + x6 + y = 16, x1 ≥ 10, y ≥ 1.
(6)
Dengan cara serupa seperti pada penyelesaian (1), kita peroleh bahwa banyaknya solusi untuk (6) adalah C (5 + (7 − 1), 5) = C (11, 5) = 462. Jadi banyaknya solusi untuk (3) adalah 6 × 462 = 2772. Dengan demikian banyaknya solusi untuk (1) adalah C (21, 6) − 6C (11, 5) = 54264 − 2772 = 51492. Terkait dengan bilangan yang sedang kita cacah, satu solusi dari (1) harus dibuang, yaitu saat xi = 0, untuk semua i, karena solusi ini berpadanan dengan bilangan 0. Jadi banyaknya bilangan bulat positif yang kurang dari 1000000 (1 juta) yang hasil penjumlahan digit-digitnya kurang dari 16 adalah C (21, 6) − 6C (11, 5) − 1 = 54264 − 2772 − 1 = 51491. Catatan: Cara lain untuk menghitung banyaknya solusi bulat nonnegatif dari (2) adalah dengan menambahkan variabel baru y yang bernilai bulat nonnegatif, yang akan menghasilkan C (22, 6) solusi. Kemudian kurangi dengan banyaknya solusi bulat nonnegatif dimana y = 0, yaitu C (21, 5). Jadi banyaknya solusi untuk (2) adalah juga C (22, 6) − C (21, 5). 3. Buktikan identitas berikut dengan menggunakan argumentasi kombinatorik:
2n n
2 2 2 n n n +···+ . + = 1 n 0
Jawab: Ruas kiri adalah banyaknya cara memilih n orang dari n pria dan n wanita. Pemilihan ini dapat dilakukan dengan memilih r pria dari n, dilanjutkan dengan memilih n − r wanita dari n, dimana r = 0, 1, . . . , n. Dengan demikian, 2n n n n n n n n n = + + +···+ n 0 n 1 n−1 2 n−2 n 0 n n n n n n n n = + + +···+ 0 0 1 1 2 2 n n 2 2 2 n n n = + +···+ . 0 1 n Kesamaan kedua kita peroleh dari fakta bahwa 2
n n = . k n−k
4. Sebuah uang logam dilempar sebanyak lima kali. Berapakah peluang sedikitnya dua gambar muncul jika diketahui pada lemparan pertama yang muncul adalah angka? Jawab: Misalkan saat uang logam ditos lima kali E adalah kejadian sedikitnya dua gambar muncul dan F adalah kejadian lemparan pertama adalah angka. Maka kejadian sedikitnya dua gambar muncul, diketahui angka muncul pada lemparan pertama dapat dinyatakan sebagai kejadian ( E| F ). Jika S adalah ruang sampel maka |S| = 25 = 32, sedangkan
| E| = 25 − C (5, 0) − C (5, 1) = 32 − 1 − 5 = 26, | F | = 24 = 16, | E ∩ F | = 24 − C (4, 0) − C (4, 1) = 16 − 1 − 4 = 11. 13 26 16 = 21 , dan P( E ∩ F ) = = , P( F ) = 32 32 16 P( E ∩ F ) 11/32 11 Akibatnya P( E| F ) = = = . P( F ) 1/2 16 Jadi P( E) =
3
11 32 .
Solusi Diskusi Kelompok III MA2151 Matematika diskrit Semester 1, 2008-2009 Waktu: 100 menit Selasa, 18 November 2008 Pengajar: Hilda Assiyatun, Djoko Suprijanto
1. Misalkan an , n ≥ 0, menyatakan banyaknya barisan biner dengan panjang n yang memiliki dua suku 0 berturutan. Buktikan bahwa barisan { an }n≥0 memenuhi relasi rekuren an = an−1 + an−2 + 2n−2 , untuk n ≥ 2, dengan a0 = a1 = 0. (Petunjuk: perhatikan dua suku terakhir.) Jawab: Misalkan barisan biner dengan panjang n, n ≥ 0, yang memiliki dua suku 0 berturutan kita sebut sebagai barisan biner-00. Barisan biner-00, dengan panjang n, n ≥ 2, dapat dibedakan menjadi 4 jenis, berdasarkan dua suku terakhirnya, yaitu berakhiran 01, 11, 10, atau 00. Perhatikan bahwa: • dua jenis yang pertama, berakhiran 01 dan 11, dapat dibangun dari barisan biner-00 dengan panjang n − 1, dengan cara menambahkan suku terakhir 1, • jenis yang berakhiran 10 dapat diperoleh dari barisan biner-00 dengan panjang n − 2, dengan cara menambahkan dua suku terakhir 10, • jenis yang berakhiran 00 didapat dari semua barisan biner dengan panjang n − 2 dengan cara menambahkan dua suku terakhir 00. Dari uraian diatas jelas bahwa, an = an−1 + an−2 + 2n−2 , untuk n ≥ 2, dimana a0 = a1 = 0. 2. Tentukan solusi dari relasi rekuren an = 2an−1 + 3an−2 + 3n , untuk n ≥ 2, dengan a0 = 0, a1 = 2. Jawab: Persamaan karakteristik untuk bentuk homogen relasi diatas adalah r2 − 2r − 3 = 0 ⇔ (r − 3)(r + 1) = 0. Jadi solusi umum bentuk homogen adalah (h)
an = A3n + B(−1)n .
(1)
Karena 3 adalah akar dari persamaan karakteristik dengan multiplisitas 1, maka ( p) kita misalkan solusi khusus mempunyai bentuk an = αn3n . Substitusikan bentuk ini ke dalam relasi rekuren, didapat, αn3n = 2α (n − 1)3n−1 + 3α (n − 2)3n−2 + 3n 2 3 ⇔ αn3n = α (n − 1)3n + α (n − 2)3n + 3n . 3 9
Dengan menyamakan suku-suku sejenis kita peroleh 1 2 n α + α n3n , dan αn3 = 3 3 2 2 0 = − α − α + 1 3n . 3 3 Dari persamaan terakhir didapat α = 43 . Jadi ( p)
an =
3 n n3 . 4
(2)
Dari (1) dan (2) diperoleh solusi umum relasi rekuren adalah 3 ( p) (h) an = an + an = A3n + B(−1)n + n3n . 4 Dari syarat awal kita dapatkan a0 = A + B = 0 9 a1 = 3A − B + = 2. 4 1 Dengan menyelesaikan sistem persamaan diatas kita peroleh A = − 16 dan B = 1 . 16
Jadi an = −
1 n 1 3 3 + (−1)n + n3n . 16 16 4
3. (a) Berikan sebuah interpretasi kombinatorik untuk koefisien xn dari fungsi pembangkit ( x + x2 + x3 + . . .)k . Jawab: Koefisien xn adalah banyaknya cara mendistribusikan n objek ke dalam k kotak, dimana masing-masing kotak menerima sedikitnya 1 objek. Atau, koefisien xn adalah banyaknya solusi bilangan bulat persamaan x1 + x2 + · · · + xk = n, dengan xi ≥ 1. (b) Dengan menggunakan interpretasi pada bagian (a), tentukan koefisien tersebut. Jawab: Banyaknya solusi sama dengan banyaknya cara menempatkan k − 1 pembatas diantara n − 1 celah yang memisahkan n buah bintang.
∗
∗ ⇑
∗ ⇑
∗ ··· ⇑
∗
∗ ⇑
∗ ⇑
Jadi koefisien xn adalah C (n − 1, k − 1). Atau dengan mendefinisikan yi = xi − 1, x1 + x2 + · · · + xk = n
⇔ ( y1 + 1) + ( y2 + 1) + · · · + ( yk + 1) = n ⇔ y1 + y2 + · · · + yk = n − k, yi ≥ 0. Banyaknya solusi bilangan bulat untuk persamaan terakhir (koefisien xn ) adalah C (n − k + (k − 1), k − 1) = C (n − 1, k − 1). 2
4. Diberikan relasi rekuren an = an−1 + 1, n ≥ 1, a0 = 0. Buktikan bahwa fungsi pembangkit untuk barisan { an }n≥0 adalah G ( x) =
x . (1 − x)2
Jawab: Misalkan fungsi pembangkit untuk { an }n≥0 adalah G ( x) = ∑n≥0 an xn . Dengan menggunakan relasi rekuren dan 1−1 x = ∑n≥0 xn , didapat an = an−1 + 1, n ≥ 1
⇔
∑ an xn = ∑ an−1 xn + ∑ xn
n≥1
n≥1
⇔ G ( x) − a0 = x ⇔ G ( x) = x ∑
∑ an−1 x
n≥1 ar xr +
r≥0
x
n≥1 n−1
∑x
r≥0
x 1−x x ⇔ G ( x)(1 − x) = 1−x x ⇔ G ( x) = . (1 − x)2
⇔ G ( x) = xG ( x) +
3
+x
∑ xn−1
n≥1 r
Solusi Diskusi Kelompok (IV) MA2151 Matematika diskrit Semester 1, 2008-2009 Waktu: 100 menit Selasa, 9 Desember 2008 Pengajar: Hilda Assiyatun, Djoko Suprijanto
1. Hitunglah banyaknya cara mendistribusikan 8 buah bola berbeda ke dalam 3 buah kotak berbeda sedemikian sehingga setiap kotak terisi sedikitnya oleh 1 buah bola. Jawab: Setiap cara mendistribusikan bola ke dalam kotak seperti dalam soal berkorespondensi 1-1 dengan sebuah pemetaan pada (surjektif) dari himpunan A ke himpunan B, dimana | A| = 8 dan | B| = 3. Dengan demikian banyaknya cara mendistribusikan 8 buah bola berbeda ke dalam 3 buah kotak berbeda sedemikian sehingga setiap kotak terisi sedikitnya oleh 1 buah bola adalah sama dengan banyaknya pemetaan surjektif dari A ke B. Misalkan B = {1, 2, 3}, dan misalkan pula N (i ) adalah banyaknya pemetaan tak surjektif dari A ke B dimana i ∈ B tidak mempunyai pasangan di A. Definisikan pula N (i, j), i 6= j, serta N (i, j, k), i 6= j 6= k, dengan cara serupa. Maka berdasarkan PIE, banyaknya pemetaan tak surjektif dari A ke B adalah N (1) + N (2) + N (3) − N (1, 2) − N (1, 3) − N (2, 3) + N (1, 2, 3) = 28 + 28 + 28 − 18 − 18 − 18 + 0 = 3(28 − 1). Banyaknya pemetaan surjektif dari A ke B sama dengan banyaknya pemetaan dari A ke B dikurangi banyaknya pemetaan tak surjektif dari A ke B. Jadi banyaknya surjektif dari A ke B adalah 38 − 3(28 − 1) = 5796. Dengan demikian banyaknya cara mendistribusikan 8 buah bola berbeda ke dalam 3 buah kotak berbeda sedemikian sehingga setiap kotak terisi sedikitnya oleh 1 buah bola adalah 5796. 2. Misalkan A = (−3, 3] ⊆ R. Definisikan relasi ∼ pada A sebagai berikut: a ∼ b ⇐⇒ d ae = dbe. (a) Buktikan bahwa ∼ merupakan relasi ekivalen. Jawab: Jelas bahwa d ae = d ae, untuk setiap a ∈ A. Jadi a ∼ a, untuk setiap a ∈ A. Jadi ∼ refleksif. a ∼ b ⇐⇒ d ae = dbe ⇐⇒ dbe = d ae ⇐⇒ b ∼ a. Jadi ∼ simetris. Misalkan a ∼ b dan b ∼ c. Maka d ae = dbe dan dbe = dce. Akibatnya d ae = dce, atau a ∼ c. Jadi ∼ transitif. Karena ∼ bersifat refleksif, simetris, dan transitif, maka ∼ adalah relasi ekivalen. (b) Tentukan kelas ekivalen dari relasi ∼ . Jawab: Definisikan [i ] = { a ∈ A| a ∼ i }, untuk i = −2, −1, 0, 1, 2, 3. Maka [i ] = { a ∈ A| i − 1 < a ≤ i }. Perhatikan bahwa
(−3, 3] = (−3, −2] ∪ (−2, −1] ∪ (−1, 0] ∪ (0, 1] ∪ (1, 2] ∪ (2, 3] = [−2] ∪ [−1] ∪ [0] ∪ [1] ∪ [2] ∪ [3]. Jadi kelas ekivalen dari ∼ adalah [−2], [−1], [0], [1], [2], dan [3].
3. Daftarkan semua pasangan terurut dari poset yang diberikan oleh Diagram Hasse di bawah ini
Jawab: Misalkan R adalah poset yang diberikan oleh diagram Hasse di atas. Maka R = {( a, a), (b, b), (c, c), (d, d), (e, e), ( a, b), (b, c), (b, d), (d, e), ( a, c), ( a, d), ( a, e), (b, e)}. 4. Misalkan R adalah relasi pada R yang didefinisikan sebagai
( x, y) ∈ R ⇐⇒ xy ≥ 0. Periksa apakah R bersifat refleksif, simetris, anti-simetris, dan transitif. Jawab: Karena x2 = xx ≥ 0, untuk setiap x ∈ R, maka ( x, y) ∈ R. Jadi R refleksif. Karena xy ≥ 0 ⇐⇒ yx ≥ 0, untuk setiap x, y ∈ R, maka ( x, y) ∈ R =⇒ ( y, x) ∈ R. Jadi R simetris. Perhatikan bahwa 2 × 5 = 5 × 2 ≥ 0. Jadi (2, 5), (5, 2) ∈ R, tetapi 2 6= 5. Jadi R tidak antisimetris. Perhatikan bahwa xy ≥ 0 jika dan hanya jika x dan y bertanda sama, atau salah satu dari x dan y sama dengan nol. Karena −5 × 0 = 0, maka (−5, 0) ∈ R. Dengan alasan serupa (0, 3) ∈ R. Tetapi, (−5, 3) ∈ / R. Jadi R tidak transitif.
2
Tes I MA2151 Matematika diskrit Semester 1, 2008-2009 Kamis, 25 September 2008 Waktu: 90 menit Pengajar: Hilda Assiyatun, Djoko Suprijanto
1. Kesimpulan apa yang dapat diambil dari pernyataan-pernyataan berikut ini? Berikan penjelasan untuk jawaban anda. (a) Jika saya main bola, maka saya akan deman keesokan harinya. Saya mandi dengan air hangat jika saya demam. Hari ini saya tidak mandi air hangat. (b) Setiap mahasiswa mempunyai akses internet. Hani tidak mempunyai akses internet. Magi mempunyai akses internet. 2. Buktikanlah pernyataan berikut ini. n ganjil ⇐⇒ 5n + 6 ganjil . 3. Untuk n bilangan bulat tak-negatif yang mana saja berlaku pertaksamaan 2n + 3 ≤ 2n ? Buktikan! 4. Berikan definisi rekursif untuk barisan { an }, n = 1, 2, 3, . . . , berikut ini. (a) an = 5n. (b) an = n(n + 1).
Solusi Tes I MA2151 Matematika diskrit Semester 1, 2008-2009 Kamis, 25 September 2008 Waktu: 90 menit Pengajar: Hilda Assiyatun, Djoko Suprijanto
1. (a) Diketahui a Saya main bola =⇒ saya demam keesokan harinya b Saya demam =⇒ saya mandi air hangat Hari ini saya tidak mandi air hangat. Berdasarkan kontrapositif implikasi [b], maka saya tidak demam. Akibatnya, berdasarkan kontrapositif implikasi [a], saya tidak main bola. Jadi kesimpulannya: kemarin saya tidak main bola. (b) Pernyataan ”Setiap mahasiswa mempunyai akses internet” setara dengan implikasi x mahasiswa =⇒ x mempunyai akses internet. Hani tidak punya akses internet. Berdasarkan kontrapositif implikasi di atas, maka Hani bukan mahasiswa. Tidak ada yang bisa disimpulkan tentang Magi, dia bisa jadi mahasiswa, bisa juga bukan. 2. Akan ditunjukkan bahwa n ganjil ⇐⇒ 5n + 6 ganjil .
=⇒ Misalkan n ganjil. Maka 5n ganjil (hasilkali dua bilangan ganjil adalah ganjil). Akibatnya 5n + 6 ganjil (hasiltambah bilangan genap dan bilangan ganjil adalah ganjil).
2
⇐= Akan dibuktikan dengan metode kontradiksi. Andaikan n genap. Maka 5n genap (hasilkali bilangan ganjil dan bilangan genap adalah genap). Akibatnya 5n + 6 genap (hasiltambah dua bilangan genap adalah genap). Kontradiksi dengan diketahui 5n + 6 ganjil. 3. Akan dibuktikan dengan induksi lemah bahwa 2n + 3 ≤ 2n , n ∈ Z, n ≥ 4. Misalkan proposisi ini P(n), n ∈ Z, n ≥ 4 adalah: 2n + 3 ≤ 2n . Langkah basis: Jika n = 4, diperoleh 2(4) + 3 < 24 ⇐⇒ 11 < 16 Jadi P(4) benar. Langkah induktif: Misalkan P(k) benar untuk k ≥ 4. Akan ditunjukkan P(k + 1) benar. 2(k + 1) + 3 = (2k + 3) + 2 ≤ 2k + 2 ≤ 2k + 2k = 2k+1 . Perhatikan bahwa ketaksamaan pertama didapat dengan menggunakan hipotesis induksi, sedangkan ketaksamaan kedua didapat dari hubungan 2 ≤ 2k , k ≥ 4. Jadi terbukti P(k + 1) benar. Dengan demikian terbukti P(n) benar untuk setiap n ∈ Z, n ≥ 4. 4. (a) an = 5n, n = 1, 2, . . . . Beberapa suku pertama dari barisan ini adalah 5, 10, 15, . . . ... Definisikan bentuk rekursif sebagai berikut: a1 = 5, an+1 = an + 5, n = 1, 2, 3, . . . (b) an = n(n + 1), n = 1, 2, . . . . Beberapa suku pertama dari barisan ini adalah 2, 6, 12, 20, . . . ... Perhatikan bahwa selisih antara dua sukunya membentuk barisan 4, 6, 8, . . . . Definisikan bentuk rekursif sebagai berikut: a1 = 2, an+1 = an + 2(n + 1), n = 1, 2, 3, . . .
3
Solusi Tes II MA2151 Matematika diskrit Semester 1, 2008-2009 Kamis, 30 Oktober 2008 Waktu: 100 menit Pengajar: Hilda Assiyatun, Djoko Suprijanto
1. (a) Tunjukkan bahwa jika enam bilangan dipilih dari 10 bilangan asli pertama, maka pasti terdapat dua bilangan yang hasil penjumlahannya 11. (b) Apakah kesimpulan di atas tetap benar jika dipilih lima bilangan? Jelaskan! Jawab: (a) Perhatikan 5 kotak berikut beserta labelnya yang diberikan pada lajur bawah. (1,10)
(2,9)
(3,8)
(4,7)
(5,6)
Masukkan keenam bilangan yang dipilih ke dalam kotak yang labelnya memuat bilangan tersebut. Perhatikan bahwa setiap kotak hanya bisa diisi oleh paling banyak dua bilangan. Karena kotak lebih sedikit dari bilangan yang dipilih, berdasarkan PHP, terdapat kotak yang berisi dua bilangan, yaitu yang hasil tambahnya sama dengan 11. (b) Jika hanya dipilih 5 bilangan, kesimpulan ini tidak selalu benar. Contohnya jika yang dipilih adalah 1, 2, 4, 5, dan 8. 2. Pada sebaris kursi yang terdiri dari 10 kursi duduk empat orang. Setiap orang dari mereka tidak mau duduk bersebelahan dengan yang lainnya. Berapa banyaknya cara memilih kursi untuk keempat orang ini. (Petunjuk: perhatikan kursi yang tidak ditempati.) Jawab: Perhatikan 10 − 4 = 6 kursi yang kosong. Maka 4 kursi yang terisi bisa memilih tempat dari 7 celah diantara kursi-kursi kusong, termasuk di kedua ujung (lihat gambar).
t ⇑
t ⇑
t ⇑
t ⇑
t ⇑
t ⇑
⇑
Jadi banyaknya cara memilih keempat kursi adalah C (7, 4) = C (7, 3) = 35. 3. Tentukan banyaknya solusi bulat tak-negatif dari persamaan x1 + x2 + x3 + x4 + x5 = 10, dengan x1 ≤ 2. Jawab: Kita bagi menjadi 3 kasus. Jika x1 = 0, maka persamaan di (1) menjadi x2 + x3 + x4 + x5 = 10, dengan banyaknya solusi bulat nonnegatif C (10 + (4 − 1), 3) = C (13, 3) = 286.
(1)
Jika x1 = 1, maka persamaan di (1) menjadi x2 + x3 + x4 + x5 = 9, dengan banyaknya solusi bulat nonnegatif C (9 + (4 − 1), 3) = C (12, 3) = 220. Jika x1 = 2, maka persamaan di (1) menjadi x2 + x3 + x4 + x5 = 8, dengan banyaknya solusi bulat nonnegatif C (8 + (4 − 1), 3) = C (11, 3) = 165. Dengan demikian banyaknya solusi bulat nonnegatif dari (1) adalah C (13, 3) + C (12, 3) + C (11, 3) = 671. Cara lain adalah dengan menghitung terlebih dulu banyaknya solusi bulat nonnegatif dari persamaan di (1), yaitu C (10 + (5 − 1), 4) = C (14, 4) = 1001. Kemudian kurangi dengan banyaknya solusi bulat nonnegatif dari x1 + x2 + x3 + x4 + x5 = 10, dengan x1 ≥ 3.
(2)
Untuk menghitung solusi dari (2), definisikan y = x1 − 3. Maka x1 + x2 + x3 + x4 + x5
( y + 3) + x2 + x3 + x4 + x5
= 10, dengan x1 ≥ 3 m = 10, dengan y bulat nonnegatif.
Persamaan terakhir ini mempunyai solusi sebanyak C (7 + (5 − 1), 4) = C (11, 4) = 330 Jadi banyaknya solusi bulat nonnegatif dari (1) adalah C (14, 4) − C (11, 4) = 671. 4. Misalkan S = {1, 2, . . . , 20} dan T ⊆ S dengan | T | = 4. Berapakah peluang bahwa T terdiri dari dua bilangan genap dan dua bilangan ganjil. Jawab: Misalkan S adalah ruang sampel dari pengambilan subhimpunan T beranggota 4 dari S. Maka |S| = C (20, 4). Misalkan E adalah kejadian T yang terambil memuat dua bilangan genap dan dua bilangan ganjil. Maka | E| = C (10, 2)C (10, 2). Maka p( E) =
(C (10, 2))2 452 135 | E| = = = . |S| C (20, 4) 4845 323 − − − ≪≫ − − −
2
Solusi Tes III MA2151 Matematika diskrit Semester 1, 2008-2009 Kamis, 20 November 2008 Waktu: 100 menit Pengajar: Hilda Assiyatun, Djoko Suprijanto
1. Berikan sebuah relasi rekuren untuk banyaknya cara untuk menutup suatu papan persegipanjang berukuran 2 × n dengan menggunakan papan-papan kecil yang berukuran 1 × 2 dan 2 × 2, dengan n ≥ 0. Berikan argumentasi untuk jawaban anda. Jawab: Cara menutup papan berukuran 2 × n, n ≥ 2, dapat dibedakan menjadi tiga jenis berdasarkan potongan terakhir yang digunakan dan posisinya, yaitu • 1 buah papan ukuran 1 × 2 dipasang horisontal, menutupi luas 2 × 1, atau • 2 papan ukuran 1 × 2 dipasang vertikal, menutupi luas 2 × 2, atau • 1 papan ukuran 2 × 2 , menutupi luas 2 × 2. Dengan begitu, banyaknya jenis pertama adalah an−1 , sedangkan yang jenis kedua dan ketiga, masing-masing, adalah an−2 . Diperoleh relasi rekuren an = an−1 + 2an−2 , n ≥ 2, dengan a0 = a1 = 1. 2. Diberikan relasi rekuren an = 8an−2 − 16an−4 + F (n). (a) Berikan solusi umum untuk bentuk homogen relasi di atas. Jawab: Persamaan karakteristik untuk bentuk homogen adalah r4 − 8r2 + 16 = 0 ⇔ (r2 − 4)2 = 0 ⇔ (r − 2)2 (r + 2)2 = 0. Karena terdapat dua akar berbeda, masing-masing dengan multiplisitas 2, maka solusi umum bentuk homogen adalah (h)
an = ( A0 + A1 n)2n + ( B0 + B1 n)(−2)n . (b) Berikan bentuk umum untuk solusi khusus relasi di atas jika F (n) = n2n . Jawab: Karena 2 adalah akar persamaan karakteristik dengan multiplisitas 2, maka bentuk umum solusi khusus adalah ( p)
an = n2 (C0 + C1 n)2n .
3. (a) Tentukan fungsi pembangkit untuk barisan { ak }k≥0 , dimana ak adalah banyaknya solusi bilangan bulat dari x1 + x2 + x3 = k, dengan x1 ≥ 3, 2 ≤ x2 ≤ 4, 0 ≤ x3 ≤ 5. Jawab: Fungsi pembangkit untuk masalah diatas adalah G ( x) = ( x3 + x4 + . . .)( x2 + x3 + x4 )(1 + x + x2 + x3 + x4 + x5 ). (b) Dengan menggunakan hasil bagian (a), tentukan a7 . Jawab: a7 adalah koefisien x7 di G. Karena x7 = xn1 xn2 xn3 , dimana xni diambil dari faktor ke-i di G, maka nilai yang mungkin untuk (n1 , n2 , n3 ) adalah (3, 2, 2); (3, 3, 1); (3, 4, 0); (4, 2, 1); (4, 3, 0); (5, 2, 0). Jadi a7 = 6. 4. Tentukan koefisien x10 dari fungsi pembangkit x2 . (1 − 2x)2 Jawab: Menurut Teorema Binomial Diperluas, ∞ 1 −2 −2 = (1 − 2x) = ∑ (−2)k xk , k (1 − 2x)2 k=0 dimana
Jadi
−2 k
=
(−2) · (−3) · · · (−(k + 1)) = (k + 1)(−1)k . k!
∞ 1 −2 = (1 − 2x) = ∑ (k + 1)2k xk . 2 (1 − 2x) k=0
Akibatnya, ∞ ∞ x2 2 k k = x ( k + 1 ) 2 x = ( k + 1 ) 2k xk+2 . ∑ ∑ (1 − 2x)2 k=0 k=0
Dengan demikian koefisien x10 adalah 9 · 28 = 576.
− − − ≪≫ − − −
2
Solusi Tes IV MA2151 Matematika diskrit Semester 1, 2008-2009 Kamis, 11 Desember 2008 Waktu: 100 menit Pengajar: Hilda Assiyatun, Djoko Suprijanto
1. Tentukan banyaknya permutasi dari 0, 1, 2, . . . , 9 yang diawali dengan digit 987, atau memuat digit 45 pada posisi ke-5 dan ke-6, atau diakhiri oleh digit 123. Jawab: Misalkan A adalah himpunan permutasi dari 0, 1, 2, . . . , 9 yang diawali dengan digit 987, B adalah himpunan permutasi dari 0, 1, 2, . . . , 9 yang memuat digit 45 pada posisi ke-5 dan ke-6, C adalah himpunan permutasi dari 0, 1, 2, . . . , 9 yang diakhiri oleh digit 123. Berdasarkan PIE,
| A ∪ B ∪ C | = | A| + | B| + |C | − | A ∩ B| − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C | = 7! + 8! + 7! − 5! − 4! − 5! + 2! = 50138 Jadi banyaknya permutasi dari 0, 1, 2, . . . , 9 yang diawali dengan digit 987, atau memuat digit 45 pada posisi ke-5 dan ke-6, atau diakhiri oleh digit 123 adalah 50138. 2. Misalkan R adalah relasi pada A = {1, 2, 3, 4} dengan R = {(1, 1), (1, 2), (2, 4)}. Tentukan suatu relasi ekivalen R0 pada A yang memuat R. Jawab: Agar R0 refleksif maka R0 ⊇ {(i, i )|i ∈ A}. Karena (1, 2), (2, 4) ∈ R0 , maka haruslah (1, 4) ∈ R0 agar R0 transitif. Agar R0 simetris maka R0 ⊇ {(2, 1), (4, 2), (4, 1)}. Jadi R0 = {(1,1), (2, 2), (3, 3), (4, 4), (1,2), (2,4), (1, 4), (2, 1), (4, 2), (4, 1)}. 3. Misalkan relasi R pada himpunan A direpresentasikan oleh matriks 1 0 1 0 0 1 1 0 1 0 1 1 . 1 1 0 1 Periksa apakah R suatu urutan parsial. Jika bukan urutan parsial tunjukkan sifatsifat apa saja yang gagal dipenuhi oleh R.
Jawab: Misalkan A = {1, 2, 3, 4}, dan namakan matriks representasi di atas sebagai MR = [mi j ]. Karena mii = 1, untuk semua i, ini berarti ( x, x) ∈ R, untuk setiap x ∈ R. Jadi R refleksif. Perhatikan bahwa m13 = m31 = 1. Ini berarti (1, 3), (3, 1) ∈ R, tetapi jelas 1 6= 3. Jadi R tidak antisimetris. Perhatikan bahwa m13 = m34 = 1, sedangkan m14 = 0. Ini berarti (1, 3), (3, 4) ∈ R, tetapi (1, 4) ∈ / R. Jadi R tidak transitif. Dengan demikian R bukan urutan parsial. 4. Diberikan diagram Hasse berikut.
(a) Tentukan elemen minimal dan elemen maksimal. Jawab: Misalkan S = { a, b, c, d, e, f , g, h, i, }, dan poset ( S, ¹) direpresentasikan oleh Diagram Hasse di atas. Karena tidak terdapat x ∈ S, sehingga x ¹ a maka a adalah elemen minimal. Dengan alasan serupa b adalah juga elemen minimal. Karena tidak terdapat x ∈ S, sehingga i ¹ x maka i adalah elemen maksimal. Jadi elemen minimal adalah a dan b, sedangkan elemen maksimal adalah i. (b) Tentukan semua batas atas untuk {c, d, f }. Jawab: Misalkan A = { x ∈ S|c ¹ x ∧ d ¹ x ∧ f ¹ x}. Maka A = { g, h, i }. Jadi batas atas untuk {c, d, f } adalah g, h, dan i. (c) Tentukan batas atas terkecil untuk {c, d, f }, jika ada. Jawab: Karena tidak terdapat y ∈ A sehingga y ¹ x, untuk setiap x ∈ A, maka {c, d, f } tidak mempunyai batas atas terkecil. (d) Tentukan batas bawah terbesar untuk {c, d, f }, jika ada. Jawab: Misalkan B = { x ∈ S| x ¹ c ∧ x ¹ d ∧ x ¹ f }. Maka B = {b}. Karena b adalah satu-satunya batas bawah untuk {c, d, f } maka b adalah sekaligus batas bawah terbesar untuk {c, d, f }. (e) Tentukan sebuah rantai terpanjang yang diawali oleh a. Jawab: Perhatikan bahwa a ¹ e ¹ f ¹ g ¹ i, dan a ¹ e ¹ f ¹ h ¹ i. Jadi rantai terpanjang yang diawali oleh a adalah a, e, f , g, i atau a, e, f , h, i.
