Pengantar Matematika Diskrit 2016 1
Pengantar Matematika Diskrit 2016 1
Pengantar Matematika Diskrit 2016 1
MATEMATIKA DISKRIT
DIKTAT
Oleh:
Rippi Maya
Eliva Sukma Cipta
Diktat ini disusun sebagai bahan ajar kuliah Matematika Diskrit (2 SKS) di
program studi Pendidikan Matematika UIN-SGD Bandung. Ada 3 Bab dalam
diktat ini. Bab I berisi tentang Induksi Matematik. Pada bab ini akan dibahas
beberapa prinsip induksi matematik (PIM), yaitu sederhana, yang dirampatkan
dan kuat. Bab II tentang Rekurensi. Pada bab ini, akan dibahas tentang barisan
yang terdefinisi secara rekursif dan relasi rekurensi. Bab III tentang Prinsip
Penghitungan, yang hanya akan membahas kaidah penjumlahan dan perkalian,
prinsip inklusi eksklusi, dan prinsip sarang merpati.
Diktat ini masih jauh dari sempurna. Oleh sebab itu, agar mahasiswa dapat
memahami secara keseluruhan materi Matematika Diskrit, maka hendaknya
mahasiswa membaca buku Matematika Diskrit dari sumber lain yang lebih
lengkap. Namun, dengan segala keterbatasannya, diktat ini diharapkan dapat
bermanfaat bagi mahasiswa khususnya dan pembaca pada umumnya.
Penulis
Rippi Maya
rippimaya@gmail.com
i
DAFTAR ISI
ii
BAB I
INDUKSI MATEMATIK
Tahap (i) dalam pembuktian disebut basis induksi, sementara tahap (ii) disebut
langkah induksi. Asumsi yang dikemukakan dalam tahap (ii) disebut sebagai
hipotesis induksi.
Contoh 1.1:
Dengan induksi matematik, buktikan bahwa:
n(n 1)(n 2)
1 2 2 3 n n 1 , untuk semua n 1.
3
Bukti :
n(n 1)(n 2)
Misalkan P(n) :1 2 2 3 n n 1 , untuk semua n 1.
3
Basis Induksi:
Untuk n 1:
1(2)(3)
Ruas kiri: 1(2) 2 , dan Ruas kanan: 2
3
Karena kedua ruas bernilai sama, maka P(1) benar.
Langkah Induksi:
Hipotesis induksi: Andaikan P(n) benar, yaitu
n(n 1)(n 2)
1 2 2 3 n n 1
3
Akan dibuktikan P(n 1) benar, yaitu:
(n 1)(n 2)(n 3)
1 2 2 3 n n 1 (n 1)(n 2) .
3
Langkah-langkah pembuktiannya sebagai berikut:
n(n 1)(n 2)
1(2) 2(3) ... n(n 1) (n 1)(n 2) (n 1)(n 2)
3
n(n 1)(n 2) 3(n 1)(n 2)
3
(n 1){n(n 2) 3(n 2)}
3
(n 1)(n 5n 6) (n 1)(n 2)(n 3)
2
3 3
Jadi P(n 1) benar untuk setiap n 1.
Kesimpulan:
Karena P(1) dan P(n+1) benar untuk setiap n 1, maka P(n) juga benar untuk
semua bilangan bulat positif n .
Contoh 1.2:
Dengan menggunakan induksi matematik buktikan bahwa:
n(2n 1)(2n 1)
12 32 52 ... (2n 1)2 , untuk semua n 1.
3
Bukti:
n(2n 1)(2n 1)
Misalkan P(n) : 12 32 52 ... (2n 1)2 , untuk semua n 1 .
3
Basis induksi:
Untuk n 1:
1 2(1) 1 2(1) 1 11 3
Ruas kiri: 2(1) 1 1 dan ruas kanan:
2
1.
3 3
Karena kedua ruas bernilai sama, maka � benar.
Langkah induksi
Hipotesis induksi: Andaikan � benar yaitu
n(2n 1)(2n 1)
12 32 52 ... (2n 1)2 .
3
Akan dibuktikan � + juga benar, yaitu
12 32 52 ... 2n 1 2n 1
2 2 n 1 2n 1 2n 3
3
Langkah-langkah pembuktiannya sebagai berikut:
n 2n 1 2n 1
12 32 52 ... 2n 1 2n 1 2n 1
2 2 2
3
n 2n 1 2n 1 3 2n 1
2
3
2n 1n 2n 1 3 2n 1
3
2n 1 2n 5n 3
2
3
2n 1 n 1 2n 3
3
n 1 2n 1 2n 3
3
Contoh 1.3:
Dengan induksi matematik, buktikan bahwa 22n 1 habis dibagi 3, untuk semua
n 1.
Bukti:
Misalkan P(n) : 22n 1 habis dibagi 3, untuk semua n 1.
Basis Induksi:
Untuk n 1 : 22(1) 1 4 1 3 adalah kelipatan 3 yang habis dibagi 3. Jadi P(1)
benar.
Langkah Induksi:
Hipotesis Induksi: andaikan P(n) benar, yaitu 22n 1 habis dibagi 3, untuk semua
n 1 , maka terdapat k , sehingga 22n 1 3k.
Akan dibuktikan P(n 1) benar, yaitu 22( n1) 1 habis dibagi 3, untuk semua
n 1.
Langkah-langkah pembuktiannya sebagai berikut:
22( n 1) 1 22 n 2 1
4.22 n 1
(3 1)22 n 1
3. 22 n 22 n 1
Berdasarkan hipotesis induksi, 2 2n
adalah
1 habis dibagi 3 dan 3. 22 n
Kesimpulan:
Karena P(1) dan P(n 1) terbukti benar untuk setiap n 1 , maka P(n) benar
untuk semua bilangan bulat positif n 1 .
22( n 1) 1 22 n 2 1
4.22 n 1
4 3k 1 1.
12k 3
3 4k 1
untuk setiap n 1 .
Kesimpulan:
Karena P(1) dan P(n 1) terbukti benar untuk setiap n 1 , maka P(n) benar
Contoh 1.4:
Dengan induksi matematik, buktikan bahwa 32n 1 habis dibagi 8, untuk semua
n 1.
Bukti:
Andaikan P(n) benar, yaitu 32n 1 habis dibagi 8, untuk semua n 1 (hipotesis
induksi). Maka terdapat bilangan bulat k , sehingga 32n 1 8k .
8.
Langkah-langkah pembuktiannya sebagai berikut:
32( n1) 1 32 n 2 1
9.32 n 1
(8 1)32 n 1
3. 32 n 32 n 1
Berdasarkan hipotesis induksi, 32n
adalah
1 habis dibagi 8 dan 3. 32 n
Kesimpulan:
Karena P(1) dan P(n 1) terbukti benar untuk setiap bilangan bulat positif n 1 ,
maka P(n) benar untuk semua bilangan bulat positif n 1.
32( n 1) 1 32 n 2 1
9.32 n 1
9 8k 1 1.
72k 8
8 9k 1
Kesimpulan:
Karena P(1) dan P(n 1) terbukti benar untuk setiap bilangan bulat positif n 1 ,
maka P(n) benar untuk semua bilangan bulat positif n 1.
Soal-soal Latihan
n 3n 1
4. 1 4 7 ... (3n 2) , n 1.
2
2n n 1 2n 1
2
2 4 ... 2n
2
5. 2 2
, n 1.
3
n(n 1)
6. (a) 1 2 3 ... n , untuk setiap bilangan asli n.
2
n2 (n 1)2
(b) 13 23 33 ... n3 , untuk setiap bilangan asli n.
4
(c) Gunakan hasil pada soal (a) dan (b) untuk menyatakan bahwa
(ii) Jika P(n) benar, maka P(n 1) juga benar untuk setiap n n0 ,
Contoh 1.5:
Bukti:
Misal P(n): n ! 2n , untuk semua bilangan bulat positif n 4.
Basis induksi:
Untuk n = 4: 4! 24 dan 24 16 , sehingga 4! 24. Jadi P(4) benar.
Langkah induksi:
Andaikan P(n) benar, yaitu n ! 2n untuk semua bilangan bulat positif n 4.
Kesimpulan:
Karena P(4) dan P(n 1) terbukti benar untuk setiap n 4 , maka P(n) benar
untuk semua bilangan bulat positif n 4.
Contoh 1.6:
Bukti:
Misalkan P(n): 2n n2 , untuk n 5.
Basis induksi:
25 32
2 5 . Jadi P(5) benar.
5 2
Untuk n = 5:
5 25
2
Langkah induksi:
Andaikan P(n): 2n n2 , untuk n 5 benar (hipotesis induksi)
Kesimpulan:
Karena P(5) dan P(n 1) terbukti benar untuk setiap n 5 , maka P(n) benar
untuk semua bilangan bulat positif n 5.
Contoh 1.7:
Sebuah toko buku menjual amplop dalam paket yang berisi 5 amplop dan 7
amplop. Fatimah akan membeli n amplop. Buktikan dengan induksi matematik
bahwa untuk setiap n 24 , toko buku ini dapat memenuhi pesanan tepat n
amplop. Asumsikan bahwa persediaan untuk setiap paket amplop tidak terbatas.
Bukti:
Basis induksi:
Untuk n 24 2(5) 2(7) 24.
Artinya untuk membeli amplop sebanyak 24, diperlukan 2 paket amplop berisi 5
amplop dan 2 paket amplop berisi 7 amplop. Jadi P(24) benar.
Langkah Induksi:
Hipotesis Induksi : Misalkan P(n) benar.
Akan dibuktikan � + benar.
Ada dua kemungkinan solusi:
1) Misalkan Fatimah akan memesan amplop sebanyak n amplop, maka ia
sedikitnya akan menerima 1 paket amplop berisi 7 amplop. Dengan
mengganti 2 paket berisi 7 amplop dengan 3 paket berisi 5 amplop akan
diperoleh amplop sebanyak n 1 amplop.
2) Misalkan untuk memesan amplop sebanyak n amplop ( n 24 ), tidak ada
paket amplop berisi 5 amplop, hanya paket amplop berisi 7 amplop yang
tersedia. Maka dengan mengganti 4 paket amplop berisi 5 amplop dengan 3
paket amplop berisi 7 amplop, akan diperoleh amplop sebanyak n 1
amplop.
Jadi P(n 1) benar untuk setiap n 24 .
Kesimpulan:
Karena P(24) dan P(n 1) terbukti benar untuk setiap n 24 , maka P(n) benar
untuk semua bilangan bulat positif n 24. Jadi untuk memesan amplop sebanyak
n amplop, cukup dilakukan dengan memesan paket yang berisi 5 amplop dan
amplop saja.
Contoh 1.8:
Untuk membayar biaya pos sebesar n sen selalu dapat digunakan
perangko 3 sen dan perangko 5 sen saja. Buktikan pernyataan tersebut dengan
induksi matematik.
Bukti:
Misal: � : untuk membayar biaya pos sebesar n sen selalu dapat
digunakan perangko 3 sen dan perangko 5 sen.
Basis Induksi:
Untuk n 8: 8 1(3) 1(5) . Artinya untuk membayar perangko senilai 8 sen
dapat digunakan 1 perangko 3 sen dan 1 perangko 5 sen. Jadi P(8) benar.
Langkah Induksi:
Hipotesis Induksi : Andaikan � benar.
Akan dibuktikan � + benar.
Ada dua kemungkinan solusi:
1) Misalkan kita bayar biaya pos senilai n sen dengan sedikitnya 1 perangko 5
sen. Dengan mengganti 1 perangko 5 sen dengan 2 perangko 3 sen akan
diperoleh biaya pos senilai + .
2) Misalkan untuk biaya pos senilai n sen ( n ) dengan sedikitnya 3 perangko
3 sen. Dengan mengganti 3 perangko 3 sen dengan 2 perangko 5 sen akan
diperoleh biaya pos sebesar + sen.
Jadi P(n 1) benar untuk setiap n .
Kesimpulan:
Karena P(8) dan P(n 1) terbukti benar untuk setiap n , maka P(n) benar
untuk semua bilangan bulat positif n 8. Jadi untuk semua selalu dapat
digunakan perangko 3 sen dan 5 sen untuk membayar biaya pos.
Soal-soal Latihan
Catatan:
Contoh 1.9:
Gunakan induksi kuat untuk membuktikan bahwa setiap bilangan asli 2
adalah bilangan prima atau merupakan hasil kali bilangan prima.
Bukti:
Misalkan P(n) adalah proposisi bahwa setiap bilangan asli n 2 adalah bilangan
prima atau merupakan hasil kali bilangan prima.
Basis Induksi:
Untuk = 2, maka pernyataan di atas benar karena 2 adalah bilangan prima.
Langkah Induksi:
Hipotesis induksi:
Andaikan P(2), P(3),..., P(n) benar. Artinya bahwa setiap bilangan asli tersebut
(2, 3, …, n) merupakan bilangan prima atau merupakan hasil kali bilangan prima.
Akan ditunjukkan: + juga merupakan bilangan prima atau hasil kali bilangan
prima.
Ada dua kasus yang perlu dibuktikan, yaitu jika + prima atau + bukan
prima:
Jika + prima, maka jelas pernyataan benar;
Jika n 1 bukan prima, maka n 1 dapat difaktorkan, yaitu n 1 ab
dengan a, b yang memenuhi 2 a, b n 1.
Berdasarkan hipotesis induksi, a dan b merupakan bilangan prima atau merupakan
hasil kali bilangan prima, sehingga + juga merupakan hasil kali prima. Jadi,
setiap bilangan asli 2 adalah bilangan prima atau merupakan hasil kali prima.
Maya & Cipta: Pengantar Matematika Diskrit
14
Contoh 1.10:
Gunakan prinsip induksi kuat untuk membuktikan bahwa untuk menyelesaikan
suatu puzzle dengan potongan, diperlukan − langkah.
Bukti:
Misalkan P(n) adalah proposisi yang menyatakan bahwa untuk menyelesaikan
suatu puzzle dengan potongan, diperlukan − langkah.
Basis Induksi:
Untuk puzzle dengan 1 potongan tidak diperlukan cara menyelesaikannya. Jadi
P(1) benar.
Langkah Induksi:
Hipotesis Induksi: andaikan P(1), P(2), P(3),..., P(n) benar. Artinya untuk
menyelesaikan puzzle dengan = , , ,..., potongan diperlukan −
langkah.
Akan ditunjukkan bahwa puzzle dengan + potongan memerlukan langkah
untuk menyelesaikannya.
Bagi + potongan menjadi dua bagian yaitu dan bagian, sehingga
+ = + .
Menurut hipotesis induksi:
- untuk menyelesaikan puzzle dengan potongan diperlukan − langkah,
- untuk menyelesaikan puzzle dengan potongan diperlukan − langkah.
Apabila kedua langkah tersebut digabungkan dengan satu langkah terakhir untuk
menyatukannya, maka diperoleh:
(n1 1) (n2 1) 1 n1 n2 2 1 n 1 1 n.
Contoh 1.11:
Buktikan dengan induksi kuat bahwa untuk membayar biaya pos sebesar n sen
selalu dapat digunakan perangko 4 sen dan atau perangko 5 sen saja.
Bukti:
Misal: : untuk membayar biaya pos sebesar n sen selalu dapat
digunakan perangko 4 sen dan atau perangko 5 sen.
Basis Induksi:
Untuk = → = . Artinya untuk membayar perangko senilai 12 sen
dapat digunakan 3 perangko 4 sen. Jadi P(12) benar.
Langkah Induksi:
Hipotesis Induksi: Andaikan � ,� ,� ,...,� benar
� → = = + +
� → = + = + +
� → = + = + +
� → = = + +
� → = = + + +
� → = + = + + +
……
P(n) n k (4) l (5) dengan k , l .
Akan dibuktikan bahwa P(n 1) benar.
Berdasarkan hipotesis induksi, diperoleh pola penggantian perangko, yaitu 1
perangko 4 sen dapat diganti dengan 1 perangko 5 sen atau 3 perangko 5 sen
diganti dengan 4 perangko 4 sen, sehingga diperoleh biaya pos senilai + sen.
Jadi � + benar untuk setiap .
Kesimpulan:
Dari definisi terurut dengan baik tersebut, didefinisikan induksi secara umum.
Contoh 1.12:
Perhatikan barisan bilangan bulat yang didefinisikan sebagai berikut:
jika = dan =
, ={ − , + jika =
, − + jika ≠
Contoh barisan bilangan
, =
, = , + = + = , = , + = + =
, = , + = + = , = , + = + =
, = , + = + = , = , + = + =
, = , + = + = , = , + = + =
Buktikan dengan induksi matematik, bahwa untuk pasangan tak negatif m dan n,
berlaku , = + .
Bukti:
Misalkan P( x) adalah pernyataan yang berkaitan dengan Sm,n yang didefinisikan
Basis Induksi:
x0 0,0 adalah elemen terkecil di dalam X, sehingga P( x0 ) S0,0 .
Jadi P( x0 ) benar.
Langkah Induksi:
Misalkan P( y) Sm ',n ' dan P( x) Sm,n .
′ ′ ′ ′
Andaikan ′, ′ = + benar untuk semua , < , (Hipotesis
Induksi).
Akan dibuktikan bahwa , = + juga benar untuk semua (m, n) (0,0) di
X. Dengan kata lain, berdasarkan definisi di atas akan ditunjukkan bahwa
, = + , baik untuk = atau ≠ .
Kasus I:
Jika = , maka dari definisi , = − , + .
Kasus II:
Jika ≠ , maka dari definisi , = , − + .
Kesimpulan:
Karena P( x0 ) S0,0 dan P( x) Sm,n benar maka terbukti bahwa , = +
Latihan 1.14:
Perhatikan barisan bilangan yang didefinisikan sebagai berikut:
, =
, ={ − , + jika =
, − + jika ≠
Buktikan dengan induksi matematika bahwa untuk semua pasangan bilangan bulat
positif , berlaku Sm,n 2(m n) 1 .
BAB 2
REKURSI
Pernyataan (i) tersebut merupakan salah satu contoh dari definisi rekursif.
Pernyataan tersebut dengan jelas menyatakan definisi 2n , jika n 1 . Kemudian
dengan mengasumsikan 2n terdefinisi untuk n k , maka akan didefinisikan
untuk n k 1 . Berdasarkan Prinsip Induksi Matematik (PIM), 2n telah
terdefinisi untuk semua bilangan bulat n 1. …..
awal.
Atau
Setelah menyebutkan beberapa suku barisan, dapat diduga rumus umum untuk
an . . Untuk contoh di atas, rumus umumnya adalah an 2n , dan ini disebut
sebagai solusi relasi rekurensi.
Contoh:
a1 1, ak 1 3ak 1, untuk k 1.
Perkirakan rumus untuk an dan buktikan dengan PIM bahwa rumusmu benar.
Jawab:
a1 1,
a2 3a1 1 3(1) 1 4,
a3 3a2 1 3 4 1 13,
a4 3a3 1 3(13) 1 40,
a5 3a4 1 3(40) 1 121,
a6 3a5 1 3(121) 1 364.
Untuk n 1,
2
3 1 1 a1 (benar).
1 1
Untuk k 1, ak
2
3 1 diasumsikan benar.
1 k
Akan dibuktikan ak 1
2
3 1 benar.
1 k 1
1 3
ak 1 3ak 1 3 3k 1 1 3k 1 3k 1 1 ….. terbukti.
3 1
2 2 2 2
Tuliskan enam suku pertama dari barisannya. Perkirakan rumus untuk an dan
periksa keabsahan dugaanmu.
Jawab:
a0 1, a1 4,
a2 4a1 4a0 4 4 4 1 12,
a3 4a2 4a1 4 12 4 4 32,
a4 4a3 4a2 4 32 4 12 80,
a5 4a4 4a3 4 80 4 32 192.
Perhatikan bahwa
a3 32 24 8 3(8) 8 4(8)
a4 80 64 16 4(16) 16 5(16)
a5 192 160 32 5(32) 32 6(32)
Bukti:
Asumsikan bahwa untuk k > 1, dan an (n 1)2n , untuk semua n dalam selang
0 n k . Akan dibuktikan rumus benar untuk n = k, yaitu ak (k 1) 2k . Karena
ak 4 k.2k 1 4 k 1 2k 2
2k.2k k.2k 2k k.2k 2k k 1 2k terbukti .
Jadi berdasarkan PIM, rumusnya berlaku untuk semua n 0 .
diperoleh rumus an n 1 2n .
diperoleh rumus
1. Barisan Aritmetika
Definisi:
Barisan aritmetika dengan suku pertama a dan selisih d, adalah barisan yang
didefinisikan oleh
a1 a, dan untuk k 1, ak 1 ak d
a, a d , a 2d , a 3d ,...
Sehingga untuk n 1, suku ke-n barisan adalah
an a (n 1) d
Jumlah n suku barisan aritmetika dengan suku pertama a dan selisih d adalah
S
n
2
2a n 1 d
Contoh:
100 suku pertama dari barisan -17, -12, -7, -2, 3, … mempunyai jumlah
100
S 2 17 99 5 50 34 495 23.050
2
Dan suku ke-100 adalah a100 17 99(5) 478 .
Jika diketahui bilangan 2038 termasuk salah satu suku barisan tersebut, maka
dapat ditentukan suku ke berapa bilangan 2038 tersebut:
2. Barisan Geometri
Definisi:
Barisan geometri dengan suku pertama a dan rasio r adalah barisan yang
didefinisikan oleh
a(1 r n )
S
1 r
Contoh:
1
1. Jumlah 29 suku barisan geometri dengan a 812 dan r adalah
2
1 29 1 29
1 1
2 2 2
36 7
S 812 2
2 36 237 28 .
1
1 3 3 3
1 2
2 2
2
3. Barisan Fibonacci
Suku ke-n dari barisan Fibonacci adalah bilangan bulat yang terdekat dengan
n
1 1 5
bilangan .
5 2
Contoh:
1 ak /2 , jika k genap
a1 1, dan untuk k 1, ak .
1 a3k 1 , jika k ganjil
Bila diuraikan relasi rekurensinya, maka diperoleh suku-suku barisan sebagai
berikut:
a1 1, a2 1 a1 1 1 2.
a3 1 a8 1 (1 a4 ) 2 a4 2 (1 a2 ) 3 a2 5.
a4 1 a2 3.
a5 1 a14 1 (1 a7 ) 2 a7 2 (1 a20 )
3 a20 3 (1 a10 ) 4 a10
4 (1 a5 )
5 a5 (tidak mungkin 0 5)
Jadi tidak ada barisan yang telah didefinisikan.
Latihan:
1 ak /2 , jika k genap
a1 1 dan untuk k 1, ak .
1 a3k 1 , jika k ganjil
Dalam sub bab ini akan dibahas prosedur untuk penyelesaian relasi rekurensi yang
berbentuk:
Dengan r dan s konstanta, f (n) adalah fungsi dari n. Relasi rekurensi tersebut
dikenal sebagai relasi rekurensi linier orde ke-dua dengan koefisien
konstanta. Jika f (n) 0 , maka relasinya disebut homogen. Orde ke-dua
merujuk pada definisi relasi rekurensi yang menyatakan bahwa an sebagai fungsi
dari dua suku yang mendahuluinya.
Contoh 1:
Berikut ini adalah beberapa contoh relasi rekurensi linier orde ke-dua dengan
koefisien konstanta.
1. an an1 an2 , yaitu relasi rekurensi yang muncul dalam definisi barisan
Contoh 2:
Contoh:
Teorema:
Misalkan x1 dan x2 adalah akar-akar polinom x2 rx s . Maka solusi dari relasi
an c1 x1n c2 x2 n , jika x1 x2
rekurensi an r.an1 s.an2 , n 2 adalah .
an c1 x1 c2 n x2 , jika x1 x2 x
n n
Latihan 1:
Latihan 2:
a0 1, a1 4 .
Latihan 3:
Tentukan rumus suku ke-n dari barisan Fibonacci, bila diketahui kondisi awalnya
a0 a1 1 bukan a1 a2 1 .
Misalkan diperoleh satu solusi khusus pn dari relasi rekurensi di atas, maka
Misalkan tn adalah solusi lain dari relasi rekurensi (i) di atas, maka
Teorema:
Misalkan pn adalah solusi khusus untuk relasi rekurensi an ran1 san2 f (n) ,
dengan kondisi awalnya diabaikan. Misalkan qn adalah solusi untuk relasi
rekurensi homogen an ran1 san2 , dengan kondisi awal diabaikan. Maka
pn qn adalah solusi untuk relasi rekurensi an ran1 san2 f (n) . Kondisi
awal menentukan konstanta-konstanta di qn .
Contoh:
Jawab:
4a 3b 0 4a 3b
1 3 3
1 4a 3 a .
4b 1 b 4 4 16
4
3 1
Jadi pn n adalah solusi khusus untuk relasi rekurensi tersebut, dengan
16 4
mengabaikan kondisi awal.
Relasi rekurensi homogen yang berkaitan dengan kasus ini adalah an 3an1 ,
yang polinom karakteristiknya adalah x 2 3x , dengan akar-akar karakteristiknya
adalah -3 dan 0.
qn c1 3 c2 0 c1 3
n n n
3 1
solusi relasi nonhomogennya, yaitu an pn qn n c1 3 .
n
16 4
Karena a0 1 , maka
3 1 3 13
a0 0 c1 3 1 c1 1 c1 .
0
16 4 16 16
3 1 13
Jadi solusinya adalah an n 3 .
n
16 4 16
Latihan:
Jawab:
p n 2 pn 1 3 pn 2 5n
a 5n 2a 5n 1 3a 5n 2 5n
2 a 5n 3a 5n
5n
5 25
10a 3a 25
5n
25
Karena 5n 0 , maka
25a 10a 3a 25
pn 5n .
25 25
12a 25 a
12 12
Dari relasi rekurensi homogen an 2an1 3an2 , maka dapat ditentukan polinom
an qn pn
12
25 n
5 c1 1 c2 3 .
n n
a0 2
12
25 0
5 c1 1 c2 3
0 0
25 25 49
c1 c2 2 c1 c2 2
12 12 12
a1 1
12
25 1
5 c1 1 c2 31
1
25 125 113
5 c1 3c2 1 c1 3c2 1
12 12 12
17 27
Dengan menggunakan metode eliminasi, diperoleh hasil c1 dan c2 ,
24 8
sehingga solusi relasi rekurensi linier orde ke-dua adalah
an
12
5 1 3 .
25 n 17
24
n 27 n
8
Latihan:
2. an 4an1 8n , n 1 , diketahui a0 1 .
179 21
4. an 6an1 9an2 n2 3n, n 2 , diketahui a0 , a1
128 128
5. an 5an1 2an2 3n2 , n 2 , diketahui a0 0, a1 3
f ( x) a0 a1 x a2 x 2 a3 x3 ... an x n ...
Tidak seperti polinom pada umumnya, di mana koefisien ai semuanya nol setelah
titik tertentu, fungsi pembangkit biasanya mempunya tak hingga banyaknya suku
tak nol. Ada kaitan yang jelas antara fungsi pembangkit dengan barisan
a1 , a2 , a3 ,... , sebut saja
a0 a1 x a2 x 2 a3 x3 ... a0 , a1 , a2 , a3 ,...
Definisi:
Fungsi pembangkit dari suatu barisan a1 , a2 , a3 ,... adalah ekspresi
f ( x) a0 a1 x a2 x 2 ...
Contoh:
Fungsi pembangkit dari barisan 1,2,3,… bilangan asli adalah
f ( x) 1 2 x 3x 2 ... , sementara fungsi pembangkit dari barisan aritmetik
f ( x) g ( x) a0 b0 a1 b1 x a2 b2 x 2 ...
Catatan:
Meski fungsi pembangkit mempunyai takberhingga banyaknya suku, namun
definisi penjumlahan dan perkalian tidak melibatkan jumlah takberhingga; sebagai
contoh, koefisien x n dalam perkalian f ( x) g ( x) adalah jumlah berhingga
a0bn a1bn 1 a2bn2 ... anb0 .
Latihan:
tentukan
f ( x) g ( x) dan f ( x) g ( x) .
Jawab:
f ( x) g ( x) 1 x x 2 ... x n ... 1 x x 2 x 3 ... 1 x n ...
n
1 1 1 1 x 1 1 x 2 ... 1 1 x n
n
2 2 x 2 2 x 4 ...
f ( x) g ( x) 1 x x 2 ... x n ... . 1 x x 2 x 3 ... 1 x n ...
n
1 1 11 x 11 1 1 11 x 2 ...
1 x 2 x 4 x 6 ...
Bagi mahasiswa yang pernah belajar kalkulus lebih dari satu tahun, dapat melihat
kemiripan yang jelas di antara fungsi pembangkit dan deret kuasa dan akan
merasa nyaman dengan kenyataan bahwa fungsi pembangkit sering dinyatakan
sebagai kuosien dari polinom. Sebuah contoh yang penting adalah
1
1 x x 2 x3 ... ,
1 x
yang menunjukkan bahwa 1/(1-x) adalah fungsi pembangkit dari barisan 1,1,1,…
1 x 1 x x 2 ... x n ...
1 11 11 x 11 11 x 2 ... 11 11 x n ...
1 0 x 0 x 2 ... 0 x n ...
1.
1
yang menunjukkan bahwa adalah fungsi pembangkit dari barisan
1 x
2
bilangan asli.
Misalkan f ( x) adalah fungsi pembangkit dari barisan 0,1,2,3,…, yaitu
x
1 x
2
Latihan:
Selesaikan relasi rekurensi an 3an1 , n 1 diketahui a0 1.
Jawab:
Perhatikan fungsi pembangkit f ( x) a0 a1 x a2 x 2 a3 x3 ... an x n ... dari
barisan a0 , a1 , a2 , a3 ,..., an ,... Kalikan dengan 3x dan tuliskan hasil kali 3xf ( x) di
f ( x) a0 a1 x a2 x 2 a3 x3 ... an x n ...
3xf ( x) 3a0 x 3a1 x 2 3a2 x3 ... 3an1 x n ...
Hasil pengurangannya adalah
1
bahwa 1 3x f x 1. Jadi f x dan dengan menggunakan rumus
1 3x
sebelumnya diperoleh
1
1 3x 3x 3x ... 3x ...
2 3 n
1 3x
1 3x 9 x 2 27 x3 ... 3n x n ...
Dapat disimpulkan bahwa an yang merupakan koefisien x n di f ( x) , harus sama
1 2x x f x 3 8x 1 x f x 3 8x .
2 2
1
f x 3 8x
1 x
2
1 2 x 3x 2 4 x 3 ... n 1 x n ... 3 8 x
3 2 x 7 x 2 12 x3 ... 3 n 1 8n x n ...
3 2 x 7 x 2 12 x3 ... 5n 3 x n ...
Latihan:
Dengan menggunakan fungsi pembangkit, carilah solusi relasi rekurensi berikut
ini. Gunakan metode polinom karakteristik untuk memeriksa kebenaran
jawabanmu.
1. an 3an1 10an2 , n 2 , bila diketahui a0 1, a1 4 .
BAB 3
PRINSIP PENGHITUNGAN
Contoh:
1. Ada 5 karakter yang terdiri dari dua huruf yang diikuti dengan 3 angka, yang
muncul di belakang satu series mikrokomputer buatan salah satu pabrik
elektronik. Banyaknya kemungkinan pengaturan karakter dalam series
tersebut adalah:
a) 26x26x10x10x10=676.000, jika karakternya dapat diulang;
b) 26x25x10x10x10=650.000, jika hurufnya tidak dapat diulang;
c) 26x25x10x9x8=468.000, jika tidak ada karakter yang dapat diulang.
a. Kaidah Perkalian
Misalkan ada barisan dari r kejadian E1, E2, …, Er sedemikian sehingga:
i. Ada ni cara di mana Ei muncul (i = 1,2,…,r), dan
ii. Banyaknya cara suatu kejadian dalam barisan dapat terjadi tidak
bergantung pada bagaimana kejadian dalam barisan sebelumnya terjadi.
Dengan kata lain, dua kejadian itu bebas satu sama lain.
Maka ada (n1).(n2)…(nr) cara di mana semua kejadian dalam barisan tersebut
terjadi.
b. Kaidah Penjumlahan
Misalkan ada r kejadian E1, E2, …, Er sedemikian sehingga:
i. Ada ni hasil untuk Ei (i = 1,2,…,r), dan
ii. Dua kejadian tidak dapat terjadi secara bersamaan. Maka ada (n1) + (n2)
+…+ (nr) cara di mana salah satu kejadian dapat muncul (terjadi).
Latihan 2.1:
Tentukan banyaknya bilangan bulat ganjil dari 0 sampai 99.
Jawab:
Banyaknya bilangan ganjil dari 0 sampai 99 adalah 50. Dengan menggunakan
kaidah perkalian, dapat diperoleh hasil sebagai berikut:
i. Bilangan bulat di antara 0 dan 99 mempunyai digit satuan dan digit puluhan,
jika angka 0 sampai 9 ditulis sebagai 00, 01, …, 09.
ii. Misalkan E adalah kejadian memilih digit dari digit satuan. Hal ini dapat
dilakukan dengan 5 cara (karena bilangan ganjil, maka digit yang dipilih
adalah 1,3,5,7,9).
iii. Misalkan F adalah kejadian memilih digit dari digit puluhan, maka hal ini
dapat dilakukan dengan 10 cara (yaitu angka 0,1,…,9).
Perhatikan bahwa banyaknya cara dalam E dapat terjadi tanpa tergantung pada
bagaimana F dapat terjadi, demikian pula sebaliknya. Maka barisan F, E dapat
muncul dalam 50 cara.
Latihan 2.2:
Misalkan soalnya sama seperti pada Latihan 2.1, namun dengan digit yang
berbeda.
Jawab:
Kasus I:
i. E dapat dipilih dengan 5 cara.
ii. F dapat dipilih dengan 9 cara. Perhatikan bahwa banyaknya cara F terjadi
tidak bergantung pada bagaimana E terjadi.
Maka dengan aturan perkalian, barisan E, F dapat terjadi dalam 45 cara. Jadi ada
45 bilangan bulat ganjil yang berbeda.
Kasus II:
i. Jika F adalah kejadian pertama, maka F dapat dipilih dengan 10 cara.
ii. E sebagai kejadian ke dua dapat dipilih dengan 5 cara, jika F nya genap dan
4 cara jika F nya ganjil. Dengan kata lain banyaknya cara di mana E terjadi
bergantung kepada kejadian F muncul, sehingga aturan perkalian tidak dapat
diberlakukan untuk barisan F, E.
Maya & Cipta: Pengantar Matematika Diskrit
40
Latihan 2.3:
Tentukan banyaknya bilangan genap dari 100-999 yang tidak mempunyai
pengulangan digit.
Jawab:
Kasus I: bilangannya berakhir dengan angka 0
Karena bilangannya terdiri dari tiga digit dan digit ke-tiga sudah diambil oleh
angka 0, maka tinggal dua digit yang harus ditentukan banyaknya pilihan. Untuk
digit pertama, ada 9 pilihan (yaitu 1-9) dan untuk digit ke-dua, ada 8 pilihan
(angka 0 dan digit pertama tidak termasuk), sehingga secara keseluruhan ada
9 8 72 bilangan genap yang berakhir dengan angka 0.
Jawab:
Kasus I: jawabannya sama dengan soal Latihan 2.3 kasus pertama, ada 72
bilangan genap yang berakhir dengan angka 0.
Kasus II: bilangannya tidak berakhir dengan angka 0
a. Jika digit pertengahan adalah 0, maka digit terakhir ada 4 pilihan (2,4,6,8)
dan digit pertama ada 8 pilihan (digit terakhir dan 0 tidak termasuk),
sehingga ada 4 8 32 bilangan genap dengan tipe ini.
b. Jika digit pertengahan bukan angka 0, maka digit terakhir ada 4 pilihan
(2,4,6,8), digit pertengahan ada 8 pilihan (0 dan digit terakhir tidak
termasuk) dan digit pertama ada 7 pilihan, sehingga ada 487 224
bilangan dengan tipe ini.
Untuk kasus II ada 32 + 224 = 256 bilangan genap dengan tipe ini.
Jadi secara keseluruhan, ada 72 + 256 = 328 bilangan genap dari 100-999 yang
tidak mempunyai pengulangan digit.
Latihan 2.5:
Soalnya sama dengan Latihan 2.3, tetapi penyelesaiannya dibagi dalam 4 kasus,
yaitu:
i) Dua digit pertama genap,
ii) Dua digit pertama ganjil,
iii) Digit pertama genap, digit ke-dua ganjil,
iv) Digit pertama ganjil, digit ke-dua genap.
Jawab:
Pemilihan digit pertama dan ke-dua dibagi dalam empat kasus:
Kasus 1: Jika dua digit pertama genap, maka untuk digit pertama ada 4 pilihan
(2,4,6,8), digit ke-dua ada 4 pilihan (digit pertama tidak termasuk) dan digit
terakhir ada 3 pilihan (angka 0, digit pertama dan digit ke-dua tidak termasuk),
sehingga ada 4 4 3 48 bilangan dengan tipe ini.
Kasus 2: Jika dua digit pertama adalah ganjil, maka untuk digit pertama ada 5
pilihan (1,3,5,7,9), digit ke-dua ada 4 pilihan (digit pertama tidak termasuk) dan
digit terakhir ada 5 pilihan (0,2,4,6,8), sehingga ada 5 4 5 100 bilangan
dengan tipe ini.
Kasus 3: Jika digit pertama genap dan digit ke-dua ganjil, maka untuk digit
pertama ada 4 pilihan (2,4,6,8), digit ke-dua ada 5 pilihan (1,3,5,7,9) dan digit
Maya & Cipta: Pengantar Matematika Diskrit
42
Kasus 4: Jika digit pertama ganjil dan digit ke-dua genap, maka untuk digit
pertama ada 5 pilihan (1,3,5,7,9), digit ke-dua ada 5 pilihan (0,2,4,6,8) dan digit
terakhir ada 4 pilihan (digit ke-dua tidak termasuk), sehingga ada 5 5 4 100
bilangan dengan tipe ini.
Jadi secara keseluruhan, banyaknya bilangan genap yang tidak mempunyai digit
yang berulang ada 48 100 80 100 328 .
Proposisi:
Misalkan himpunan A dan B adalah subset dari himpunan berhingga U. Maka
(a) A B A B A B
(c) A \ B A A B A B
(d) Ac U A , dengan U adalah himpunan semesta
(e) A B A B A B A B 2 A B A \ B B \ A
(f ) A B A B
Prinsip Inklusi-Eksklusi:
Diketahui sejumlah berhingga himpunan berhingga A1, A2 ,..., An . Banyaknya
elemen dalam gabungan himpunan berhingga tersebut adalah
A1 A2 ... An Ai Ai A j Ai A j Ak
i i j i j k
n 1
... 1 A1 A2 ... An
Latihan 2.6:
Tentukan banyaknya bilangan bulat dari 1 sampai 300 yang:
a) Habis dibagi paling sedikit salah satu dari 3, 5, atau 7.
b) Habis dibagi 3 dan 5, tetapi tidak habis dibagi 7.
c) Habis dibagi 5, tetapi tidak habis dibagi 3 maupun 7.
Jawab:
Misalkan himpunan A, B dan C adalah himpunan-himpunan bilangan bulat dari 1
sampai 300 yang habis dibagi 3, 5 dan 7:
A n 1 n 300,3 n ,
B n 1 n 300,5 n , dan
C n 1 n 300,7 n .
a). Banyaknya bilangan bulat dari 1 sampai 300 yang habis dibagi paling sedikit
salah satu dari 3,5 atau 7, berarti mencari:
A B C A B C A B AC B C A B C .
Dengan demikian, banyaknya bilangan bulat dari 1 sampai 100 yang habis dibagi
paling sedikit salah satu dari 3, 5, 7 adalah 162 bilangan.
Catatan:
terbesar yang kurang dari atau sama dengan x, yaitu bilangan bulat tunggal x
yang memenuhi x 1 x x .
b). Banyaknya bilangan bulat yang habis dibagi 3 dan 5 tetapi tidak habis dibagi 7
adalah banyaknya bilangan bulat dalam himpunan A B \ C , sehingga
A B \ C A B A B C 20 2 18.
c). Banyaknya bilangan bulat yang habis dibagi 5, tetapi tidak habis dibagi 3 atau
7 adalah bilangan bulat dalam himpunan B \ ( A C ) sehingga penyelesaiannya
sebagai berikut:
B \ A C B B AC B B A B C
B A B C B A B C B A B C
B A B C B AC
20 8 2 26,
Sehingga
B \ A C B B A C 60 26 34.
Jadi banyaknya bilangan bulat yang habis dibagi 5 tetapi tidak habis dibagi 3 dan
7 adalah sebanyak 34 bilangan.
Latihan 2.7:
Tentukan banyaknya bilangan bulat dari 1 sampai 500 yang
a). habis dibagi 3 atau 5.
b). habis dibagi 3 tetapi tidak oleh 5 atau 6.
Jawab:
Misalkan A, B dan C adalah himpunan-himpunan bilangan bulat yang habis dibagi
3, 5 dan 6:
A n 1 n 500,3 n , B n 1 n 500,5 n , C n 1 n 500,6 n .
a). Banyaknya bilangan bulat dari 1 sampai 500 yang habis dibagi 3 atau 5 adalah
Keterangan:
b). Banyaknya bilangan bulat yang habis dibagi 3, tetapi tidak habis dibagi oleh 5
atau 6 adalah banyaknya bilangan dalam himpunan A \ B C :
A \ B C A A B C A A B A C ……. (1)
A B A C A B A C A B A C
…… (2)
A B A C A B C
Jadi banyaknya bilangan bulat yang habis dibagi 3, tetapi tidak habis dibagi 5 atau
6 ada 66 bilangan.
Latihan 2.8:
Tentukan banyaknya bilangan bulat dari 1 sampai 250 yang habis dibagi oleh
salah satu dari tiga bilangan bulat berikut: 4, 6 dan 15?
Jawab:
Misalkan P, Q dan R adalah himpuan-himpunan bilangan bulat dari 1 sampai 250
yang habis dibagi 4, 6 dan 15.
P n 1 n 250, 4 n , Q n 1 n 250,6 n , R n 1 n 250,15 n .
Maka banyaknya bilangan bulat yang habis dibagi salah satu tiga bilangan bulat 4,
6 atau 15 adalah:
P Q R P Q R P Q P R Q R P Q R. …. (3)
250 250
QR 8,
lcm 6,15 30
250 250
P Q R 4 , sehingga hasil perhitungan dari
lcm 4, 6,15 60
persamaan (3) adalah
P Q R 62 41 16 20 4 8 4 91.
Jadi banyaknya bilangan bulat dari 1 sampai 250 yang habis dibagi oleh salah satu
dari tiga bilangan 4, 6, atau 15 ada 91 bilangan.
Latihan 2.9:
a). Tentukan banyaknya bilangan bulat dari 1 sampai 1000 yang tidak habis dibagi
2, 3, 5 atau 7.
b). Tentukan banyaknya bilangan bulat di antara 1 dan 1000 yang tidak habis
dibagi 2, 3, 5 atau 7.
Jawab:
a). Misalkan K, L, M dan N adalah himpunan-himpunan bilangan bulat dari 1
sampai 1000 yang habis dibagi 2, 3, 5 dan 7.
K n 1 n 1000, 2 n ,
L n 1 n 1000,3 n ,
M n 1 n 1000,5 n , N n 1 n 1000,7 n .
Maka banyaknya bilangan bulat dari 1 sampai 1000 yang tidak habis dibagi 2, 3, 5
atau 7 adalah
K LM N 1000 K L M N
C
K LM N K L M N K L K M K N LM
LN M N K LM K LN LM N
K LM N
500 333 200 142 166 100 71 66 47 28
33 23 9 4
1175 478 65 4 758.
Jadi banyaknya bilangan bulat dari 1 sampai 1000 yang tidak habis dibagi 2, 3, 5
atau 7 adalah
Keterangan:
b). Dengan cara yang sama seperti pada penyelesaian soal a), diperoleh hasil
jawaban sebagai berikut:
R n 1 n 1000, 2 n , S n 1 n 1000,3 n , T n 1 n 1000,5 n ,
U n 1 n 1000,7 n .
Maka banyaknya bilangan bulat di antara 1 dan 1000 yang tidak habis dibagi 2, 3,
5 atau 7 adalah
R S T U 998 R S T U
C
R S T U R S T U R S R T R U S T
S U T U R S T R S U S T U
R S T U
499 332 199 142 166 99 71 66 47 28
33 23 9 4
1172 477 65 4 756.
Jadi banyaknya bilangan bulat di antara 1 dan 1000 yang tidak habis dibagi 2, 3, 5
atau 7 adalah
Keterangan:
998 998
R L T 33, R S U 23,
2 3 5 2 3 7
998 998
S T U 9, R S T U 4.
3 5 7 2 3 5 7
Latihan 2.10:
Tentukan banyaknya bilangan prima yang tidak lebih dari 100. Jelaskan
jawabanmu.
Jawab:
Banyaknya bilangan bulat positif n yang tidak lebih dari 100 adalah 100 bilangan.
Berdasarkan “The Sieve of Eratosthenes” (saringan Eratosthenes), bilangan prima
yang tidak lebih dari 100 dapat dicari dengan acuan bahwa bilangan prima p tidak
boleh lebih dari akar 100 ( p 100 ). Karena p 10 maka bilangan prima p
adalah 2, 3, 5, dan 7. Tuliskan bilangan bulat positif secara terurut dari 2 sampai
100, lalu eliminasi bilangan-bilangan yang merupakan kelipatan 2p, 3p, 4p, 5p, ...
Perhatikan bahwa bilangan-bilangan yang tidak tereliminasi adalah bilangan-
bilangan bulat yang tidak habis dibagi 2, 3, 5, atau 7. Untuk menghitung
banyaknya bilangan prima adalah dengan jalan menghitung banyaknya bilangan
bulat positif yang tidak habis dibagi 2, 3, 5 atau 7, dikurangi 1 (bilangan 1 bukan
prima), ditambah dengan 4 bilangan prima pertama, yaitu 2, 3, 5 dan 7.
A n 1 n 100, 2 n , B n 1 n 100,3 n , C n 1 n 100,5 n ,
D n 1 n 100,7 n .
Maka dengan menggunakan prinsip inklusi-eksklusi, diperoleh rumus untuk
menghitung banyaknya bilangan bulat yang habis dibagi 2, 3, 5 atau 7.
A B C D A B C D A B AC A D B C B D
C D A B C A B D AC D B C D
A B C D
dengan:
100 100 100 100
A 50, B 33, C 20, D 14,
2 3 5 7
100 100 100
A B 16, A C 10, A D 7,
2 3 25 2 7
100 100 100
B C 6, B D 4, C D 2,
3 5 3 7 5 7
100 100
A B C 3, A B D 2,
2 3 5 2 3 7
100 100
AC D 1, B C D 0,
2 5 7 3 5 7
100
A B C D 0.
2 3 5 7
Maka bilangan bulat dari 1 sampai 100 yang habis dibagi 2, 3, 5 atau 7 adalah:
Banyaknya bilangan bulat yang tidak habis dibagi 2, 3, 5 atau 7 adalah 100 – 78 =
22 (termasuk bilangan 1). Jadi banyaknya bilangan prima yang kurang dari 100
adalah banyaknya bilangan bulat yang tidak habis dibagi 2, 3, 5 atau 7 dikurang 1
(bilangan 1) ditambah 4 bilangan prima pertama (2, 3, 5 dan 7), yaitu 22 -1 + 4 =
25 bilangan prima.
Latihan 2.11:
Hitunglah banyaknya bilangan prima yang kurang dari 200. Jelaskan jawabanmu
dengan menggunakan prinsip inklusi-eksklusi.
Latihan 2.12:
Tentukan banyaknya bilangan dari 2 sampai 100 yang merupakan kuadrat
sempurna, pangkat tiga sempurna atau pangkat lebih tinggi.
Jawab:
Perhatikan himpunan obyek-obyek {2,3,…,100}. Misalkan elemen dari himpunan
ini mempunyai sifat i jika elemen tersebut sama dengan pangkat ke i dari suatu
bilangan bulat. Karena 27>100, maka tidak ada pangkat 7 dalam himpunan dan
sifat-sifat yang ada hanya sifat 2,3,4,5,dan 6. Maka banyaknya elemen yang
mempunyai sifat 2,3,4,5 dan 6 adalah
A2 A3 A4 A5 A6 A2 A3 A4 A5 A6
A2,3 A2, 4 A2,5 A2, 6 A3, 4 A3,5 A3, 6 A4,5 A4, 6 A5, 6
A2,3, 4 A2,3,5 A2,3, 6 A2, 4,5 A2, 4, 6 A2,5, 6 A3, 4,5 A3, 4, 6
A4,5, 6 A2,3, 4,5 A2,3, 4, 6 A3, 4,5, 6 A2,3, 4,5, 6 12.
Keterangan:
Misalkan:
Obyek-obyeknya adalah
22 4,32 9, 42 16,52 25,62 36,72 49,82 64,92 81,102 100.
A3, 4,6 A12 0, A4,5,6 A60 0, A2,3, 4,5 A60 0, A2,3, 4,6 A12 0,
A2,3,5,6 A30 0, A3, 4,5,6 A60 0, A2,3, 4,5,6 A60 0.
Kesimpulan:
Jadi banyaknya bilangan dari 2 sampai 100 yang merupakan kuadrat sempurna,
pangkat tiga sempurna, atau pangkat yang lebih tinggi ada 12 bilangan.
Latihan 2.13:
Andaikan himpunan A dan B adalah himpunan berhingga. Buktikan bahwa
A B A B .
Jawab:
A B n n n ... n n m A B .
m
Teorema 3.1:
Jika n + 1 atau lebih burung merpati menempati n sarang burung, maka paling
sedikit ada lebih dari 1 burung merpati di dalam sarang burung tersebut.
Contoh:
1. Dari 13 mahasiswa dalam 1 kelas, paling sedikit ada mahasiswa yang
berulang tahun pada bulan yang sama.
Jawab:
misalkan 13 mahasiswa sebagai merpati dan 12 bulan sebagai sarangnya,
maka paling sedikit dalam satu sarang ada dua merpati atau lebih. Dengan
kata lain, paling sedikit ada dua mahasiswa yang mempunyai bulan kelahiran
yang sama.
Jawab:
misalkan 32 mahasiswa sebagai merpati dan 31 hari sebagai sarangnya,
maka paling sedikit dalam satu sarang ada dua merpati atau lebih. Dengan
kata lain, paling sedikit ada dua mahasiswa yang mempunyai tanggal
kelahiran yang sama.
4. Diketahui sepuluh bilangan bulat positif yang kurang dari 107. Dari sepuluh
bilangan tersebut dibuat subset-subset, baik yang saling lepas maupun tidak.
Tunjukkan bahwa ada dua subset yang saling lepas dari subset-subset
tersebut yang jumlah elemen di dalam subsetnya sama.
Jawab:
Dari 10 bilangan tersebut dapat dibentuk subset sebanyak 210 = 1024. Jumlah
terendah dari subset tersebut adalah 0, yang dipunyai oleh {}=.
10 bilangan tertinggi yang kurang dari 107 tersebut adalah 97, 98, 99, 100,
101, 102, 103, 104, 105, 106, yang jumlah tertingginya adalah 1015. Dengan
memisalkan sarang burung dengan jumlah elemen subset, maka akan ada
sarang burung bernomor 0 sampai 1015. Misalkan setiap jumlah elemen
dalam subset dituliskan di atas secarik kertas dan kertas-kertas tersebut
ditempatkan ke sarang burung, maka akan ada 1024 carik kertas yang
ditempatkan dalam 1015 sarang burung. Berdasarkan Teorema Sarang
Merpati, akan ada dua atau lebih carik kertas yang menempati sarang burung
yang sama. Artinya, ada 2 subset atau lebih yang mempunyai jumlah elemen
yang sama.
5. Buktikan bahwa dari 5 titik yang dipilih dari sebuah persegi yang panjang
sisi-sisinya 2, ada 2 titik yang jaraknya satu sama lain paling banyak 2.
Bukti:
Bagilah persegi tersebut ke dalam persegi kecil dengan panjang sisi-sisi 1.
Berdasarkan prinsip sarang merpati, paling sedikit dua dari 5 titik yang
dipilih pasti terletak pada sudut-sudut persegi kecil atau pada batas persegi
kecil tersebut. Jarak dua titik pada persegi kecil tersebut paling banyak
adalah 2.
Teorema 3.2: Prinsip Sarang burung secara Umum
Jika kn + 1 atau lebih burung merpati menempati n sarang burung, maka akan ada
lebih dari k burung merpati dalam paling sedikit satu sarang burung, dengan k
bilangan bulat positif.
Catatan:
terkecil yang lebih besar dari atau sama dengan x, yaitu bilangan bulat tunggal
x yang memenuhi x x x 1 .
Contoh:
Di antara 40 mahasiswa yang ada di kelas, terdapat paling sedikit 40 /12 4
mahasiswa yang lahir pada bulan yang sama, 40 / 31 2 mahasiswa yang lahir
pada tanggal yang sama, 40 / 7 6 mahasiswa yang lahir pada hari yang sama,
Contoh:
Sekantung kelereng terdiri dari 5 merah, 8 biru, 10 putih, 12 hijau, dan 7 kuning.
Tentukan minimal kelereng yang dipilih yang menjamin paling sedikit ada:
a. 4 kelereng dengan warna sama
b. 6 kelereng dengan warna sama
c. 7 kelereng dengan warna sama
d. 9 kelereng dengan warna sama.
Petunjuk: setiap warna menyatakan sarang burung. Banyaknya sarang burung ada
5.
Jawab:
a. Jika paling sedikit ada 4 kelereng dengan warna sama, maka ada sarang
burung yang isinya lebih dari 3 burung. Dengan menggunakan Teorema 3.2
dengan k = 3, maka banyaknya kelereng yang diambil paling sedikit ada
(3).(5) + 1 =16.
d. Dengan cara yang sama dengan no. c, maka untuk n = 5 dan k = 8, dan batas
atas untuk kelereng merah adalah 5 dan kuning adalah 7, maka banyaknya
kelereng yang diambil adalah [(8.5+1)]-(8-5)-(8-7)=37.
Teorema:
a) Jika m merpati ditempatkan ke dalam n sarang burung, maka paling sedikit
satu sarang ditempati oleh lebih dari k merpati, dengan k adalah batas bawah
dari (m 1) / n .
b) Jika m p1 p2 ... pn n 1 merpati (masing-masing pi merupakan
bilangan bulat positif) ditempatkan ke dalam n sarang burung, maka sarang
pertama mempunyai paling sedikit p1 merpati, atau sarang ke-dua
mempunyai paling sedikit p2 merpati, …, atau sarang ke-n mempunyai
paling sedikit pn merpati.
Contoh:
Sekantung kelereng berisi tepat 6 kelereng merah, 5 kelereng putih, dan 7
kelereng biru. Tentukan jumlah terkecil kelereng yang bisa diambil yang akan
menjamin paling sedikit 3 kelereng merah atau paling sedikit 4 kelereng putih
atau paling sedikit 5 kelereng biru yang terambil.
Jawab:
Contoh:
1. Dari 100 orang mahasiswa, beberapa di antaranya berulang tahun pada bulan
yang sama. Paling sedikit ada berapa mahasiswa yang berulang tahun pada
bulang yang sama?
Jawab:
100 /12 9.
2. Dari suatu kelompok mahasiswa yang terdiri dari 6 orang, paling sedikit tiga
di antaranya adalah teman atau paling sedikit 3 di antaranya bukan teman.
Jawab:
Misalkan anda adalah satu di antara 6 mahasiswa tersebut dan mahasiswa
menyatakan merpati. Buatlah 2 kotak yang berlabel “temanku” dan “bukan
temanku”. Masukkan ke lima merpati yang dinyatakan dalam secarik kertas
yang bernomor 1 sampai 5 ke dalam dua kotak berlabel. Berdasarkan prinsip
sarang merpati bentuk kuat, paling sedikit ada 5 / 2 3 merpati dalam satu
kotak. Misalkan 3 teman ini adalah teman anda. Jika dua dari 3 teman ini
adalah teman anda, maka bersama-sama dengan anda, akan ada paling
sedikit 3 teman akrab. Jika dua dari 3 teman ini bukan teman anda, maka 3
teman tersebut bukan teman satu sama lain.
3. Dari 26 titik yang terletak pada persegi panjang berukuran 20 cm dan 15 cm,
tunjukkan bahwa paling sedikit ada dua titik yang jaraknya 5 cm.
Latihan:
1. Buatlah contoh soal dan jawab yang berkaitan dengan prinsip sarang
burung, yang berbeda dengan yang ada di contoh pada catatan kuliah.
2. Buatlah soal dan jawab seperti pada soal kelereng pada catatan kuliah.
DAFTAR PUSTAKA
Cupillari, Antonella (2005). The Nuts and Bolts of Proofs (Third Edition).
Burlington, MA.: Elsevier Academic Press.