The Pigeonhole Principle (Prinsip Sarang Merpati)
Pigeonhole Principle atau Prinsip Rumah Merpati
pertama kali dinyatakan oleh ahli matematika dari Jerman yang
bernama Johann Peter Gustav Lejeune Dirichlet pada tahun 1834, sehingga prinsip ini juga
dikenal dengan istilah Prinsip Laci Dirichlet (Dirichlet drawer principle).
Jika (k + 1) atau lebih obyek ditempatkan ke
dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat dua atau
lebih obyek tersebut.
Missal Jika
n merpati ditempatkan pada m rumah merpati, dimana n > m, maka terdapat
rumah merpati yang memuat paling sedikit dua merpati. Untuk membuktikan
pernyataan Prinsip Pigeonhole ini,
kita gunakan kontradiksi. Misalkan kesimpulan dari pernyataan tersebut salah,
sehingga setiap rumah merpati memuat paling banyak satu merpati. Karena ada m
rumah merpati, maka paling banyak m merpati yang bisa dimuat. Padahal ada n
merpati yang tersedia dan n > m, sehingga kita dapatkan sebuah kontradiksi.
Contoh 1: Jika terdapat 11 pemain dalam sebuah
tim sepakbola yang menang dengan angka 12-0, maka haruslah terdapat paling
sedikit satu pemain dalam tim yang membuat gol paling sedikit dua kali.
Contoh 2: Jika anda menghadiri 6 kuliah dalam
selang waktu Senin sampai Jumat, maka haruslah terdapat paling sedikit satu
hari ketika anda menghadiri paling sedikit dua kelas.
Contoh 3:
Kasus A:
Misalkan di rumahmu ada sebuah
laci dan di dalam laci tersebut ada kaos kaki: 12 hitam dan 10 putih yang
tersebar secara acak. Suatu hari, lampu di rumahmu mati, maka berapa kaos kaki MINIMAL yang harus kamu ambil agar dapat memperoleh sepasang
kaos kaki dengan warna yang sama??
Jawab:cukup 3 kaos kaki.
Kasus B:
Selidikilah kebenaran kasus di bawah ini:
1. Di antara tiga orang, maka pasti
ada dua orang yang berjenis kelamin sama.
2. Dari 32 orang, pasti ada 2 orang yang
memiliki tanggal lahir yang sama.
3. Jika kn + 1 kelereng didistribusikan ke dalam
n kotak, maka satu kotak akan berisi paling tidak k + 1 kelereng.
4. Sebuah garis l di dalam bidang melalui
sisi-sisi segitiga ABC dengan tidak melewati titik sudutnya. Maka, garis itu
tidak akan melewati ketiga sisi segitiga.
Jawab:
Semua BENAR.
Perhatikan bahwa nomor 3 merupakan bentuk prm
yang lebih umum. (prm yang ditulis disini diperoleh untuk k = 1).
Kasus C:
Dapatkah kamu membuktikan bahwa ada paling tidak
dua orang penduduk di Bandung yang banyaknya rambut di kepala sama?
Jawab:
Sekilas, mungkin kamu akan berusaha memanggil
satu demi satu penduduk di Bandung.. Kemudian, menyuruh mereka mencabuti setiap
rambut mereka untuk dihitung.. Wahahaha.. Benar-benar lucu. Namun, untuk
membuktikannya, kamu tidak perlu melakukan hal bodoh seperti itu. Gunakan
prinsip rumah merpati di atas.
Perkirakan kemungkinan terburuk bahwa jumlah
rambut terlebat adalah 1000 helai rambut per inchi persegi. Kemudian asumsikan
kemungkinan terburuk bahwa rambut itu menutupi luas 1000 inchi persegi, maka
jumlah helai rambut terlebat manusia ada sekitar 1000.000 helai.. (Ini sudah
terburuk sekali)..
Membandingkannya dengan jumlah penduduk Bandung,
yaitu sekitar 2.500.000 juta jiwa (tahun 2005, dan pasti akan terus bertambah),
maka jumlah 1000.000 sekitar 2.5 kali lebih kceil dibandingkan jumlah
penduduknya. Di kasus ini, kita dapat menganalogikan 2.500.000 sebagai jumlah
merpati, dan 1000.000 sebagai jumlah rumah yang ada. Maka, akan ada paling
tidak 2 orang yang memiliki jumlah rambut yang sama.
Kasus D:
Seperti kasus nomor A. Sekarang, di laci ada 12
kaos kaki hitam, 13 kaos kaki putih, 20 kaos kaki biru, 5 kaos kaki merah, 1
kaos kaki hijau, dan 1 kaos kaki kuning. Berapa banyak kaos kaki minimal yang
harus diambil agar setidaknya:
a) terdapat 2 kaos kaki yang memiliki warna yang
sama
b) terdapat 2 kaos kaki yang memiliki warna yang
berbeda.
Jawaban Kasus D:
a)Kemungkinan terburuk yaitu saat mengambil 6
kaos kaki yang semuanya berbeda warna (hitam, putih, biru, merah, hijau, dan
kuning). Oleh karena itu, kaos kaki minimal yang harus diambil agar setidaknya
terdapat 2 kaos kaki dengan warna sama adalah 7 buah.
b) Kemungkinan terburuk yaitu saat mengambil 20
kaos kaki yang semuanya berwarna biru. Oleh karena itu, kaos kaki minimal yang
harus diambil agar setidaknya terdapat 2 kaos kaki dengan warna berbeda adalah
21 buah.
Prinsip Pigeonhole Bentuk Kedua
Jika f merupakan sebuah fungsi dari suatu
himpunan terhingga X ke suatu himpunan terhingga Y dan |X| > |Y |, maka
f(x1) = f(x2) untuk beberapa x1, x2 anggota X, dimana x1 ≠ x2.
Untuk membuktikan Prinsip Pigeonhole Bentuk Kedua
ini kita bisa mengasumsikan X sebagai himpunan merpati dan Y
sebagai himpunan rumah merpati. Selanjutkan kita memasangkan merpati x ke rumah
merpati f(x). Karena jumlah merpati lebih banyak dari rumahnya, maka terdapat
paling sedikit dua merpati, x1, x2 anggota X yang dipasangkan ke rumah merpati
yang sama, yaitu f(x1) = f(x2) untuk beberapa x1, x2 anggota X, dimana x1 ≠ x2.
contoh 1 :
Kasus A:
Jika dari barisan bilangan 1,2,3,4,5,...,400
diambil 201 bilangan, maka buktikanlah bahwa dari 201 bilangan tersebut paling
tidak ada dua bilangan yang koprima (faktor pembagi terbesarnya 1).
Jawab:
Konon, Erdos pernah mengundang makan siang
seorang anak ajaib, Lajos Posa. Di tengah makan siang Erdos bertanya ”Bagaimana
kamu membuktikan bahwa jika kita mengambil n+1 bilangan dari himpunan bilangan
1, 2, 3, ..., 2n, maka ada dua bilangan yang koprima?”
Sesaat pertanyaan tersebut tidak cukup jelas.
Namun, argumentasi Lajos yang dikemukakan sesaat setelah pertanyaan selesai
membuat pertanyaan Erdos lebih jelas: dalam n + 1 bilangan yang terpilih pasti
ada dua bilangan yang berbeda satu alias saling berurutan dan dua bilangan
tersebut koprima.
Kasus B:
Jika dari barisan bilangan 1,2,3,4,5,...,400
diambil 201 bilangan, maka buktikanlah bahwa dari 201 bilangan tersebut paling
tidak ada dua bilangan dimana bilangan yang satu yang membagi bilangan yang
lain.
Jawab:
Masalah di bawah ini mirip dengan masalah
sebelumnya:
Dari himpunan bilangan bulat 1, 2, 3, ..., 2n,
ambil n + 1 bilangan, sebutlah himpunan ini A. Maka selalu ada dua bilangan di
A sehingga bilangan yang satu membagi bilangan yang lain. Masalah ini berhasil
dibuktikan pula oleh Lajos.
Kita dapat menulis kembali setiap anggota dalam
himpunan A dalam bentuk: . Tentunya, karena yang diminta di soal adalah bilangan
yang membagi bilangan lain, maka asumsikan bahwa anggota-anggota dalam himpunan
A tidak boleh mengandung nilai m yang membagi satu sama lain. Dalam hal ini, m
adalah bilangan ganjil yang mungkin dari 1,2,3,..., 2n. Artinya, m maksimal ada
sebanyak n buah.
Perhatikan bahwa karena kita mengambil n+1
bilangan, maka artinya pernyataan di atas adalah kontradiksi. Akibatnya, pasti
akan ada 2 bilangan dengan nilai m yang sama. Artinya, kedua bilangan itu dapat
membagi bilangan yang lain.
contoh 2 :
Dalam membuat kode matakuliah untuk
matakuliah-matakuliah bidang studi informatika adalah dengan cara menambahkan
tiga angka pada huruf TIK. Terdapat 51 matakuliah yang harus diberi kode dan
tiga angka yang harus ditambahkan pada huruf TIK harus berkisar antara 101
sampai dengan 200. Tunjukkan bahwa terdapat paling sedikit dua matakuliah yang
diberi kode dengan angka berurutan.
Misalkan angka-angka yang dipilih adalah
a1, a2, …, a51.
Jika angka-angka diatas digunakan bersama-sama
dengan
a1 + 1, a2 + 1, …, a51 + 1
maka terdapat 102 nomor yang merentang antara
101 sampai dengan 201. Karena ada 100 nomor yang disediakan (yaitu 101 sampai
dengan 200) dan ada 102 nomor yang akan digunakan, maka menurut Prinsip
Pigeonhole Bentuk Kedua terdapat paling sedikit dua nomor yang sama. Nomor a1,
a2, …, a51 dan a1 + 1, a2 + 1, …, a51 + 1 semuanya berbeda. Sehingga kita
mempunyai ai = aj + 1 Dengan demikian kode ai berurutan dengan kode aj .
The Generalized Pigeonhole Principle Theorem
(Generalisasi Prinsip Sarang Merpati)
Jumlah dari objek melebihi dari jumlah kotak
yang tersedia.
Jika N obyek ditempatkan ke dalam k kotak, maka
terdapat paling sedikit satu kotak yang memuat sedikitnya [N/k] obyek.
Bukti?
Contoh 1: Di dalam kelas dengan 60 mahasiswa,
terdapat paling sedikit 12 mahasiswa akan mendapat nilai yang sama (A, B, C, D,
atau E).
Contoh 2: Di dalam kelas dengan 61 mahasiswa,
paling sedikit 13 mahasiswa akan memperoleh nilai yang sama.
Contoh 3 :
Dalam matakuliah Matematika Diskrit diberikan
tugas kelompok yang akan dibagi menjadi enam kelompok. Jika terdapat 62
mahasiswa yang menempuh mata kuliah tersebut, tunjukkan bahwa terdapat paling
sedikit ada 11 mahasiswa yang menjadi anggota suatu kelompok yang sama!
Kita asumsikan mahasiswa tersebut sebagai
anggota dari himpunan daerah asal X dan kelompoknya sebagai anggota daerah
kawan Y . Karena |X| = 62, |Y | = 6 dan [62/6] = 11. Maka dengan menggunakan
Prinsip Generalized Pigeonhole, terdapat paling sedikit 11 anggota X yang
dipasangkan dengan suatu anggota Y yang sama. Dengan demikian terdapat paling
sedikit ada 11 mahasiswa yang menjadi anggota suatu kelompok yang sama
Kombinasi adalah menggabungkan beberapa objek dari suatu grup tanpa
memperhatikan urutan. Di dalam kombinasi, urutan tidak diperhatikan.
{1,2,3} adalah sama dengan {2,3,1} dan {3,1,2}.
Contoh: Seorang anak hanya diperbolehkan mengambil dua buah amplop dari
tiga buah amplop yang disediakan yaitu amplop A, amplop B dan amplop C.
Tentukan ada berapa banyak kombinasi untuk mengambil dua buah amplop dari tiga
buah amplop yang disediakan?
Solusi: Ada 3 kombinasi yaitu; A-B, A-C dan B-C.
Sedangkan permutasi adalah menggabungkan beberapa
objek dari suatu grup dengan memperhatikan urutan. Di dalam permutasi, urutan
diperhatikan.
{1,2,3} tidak sama dengan {2,3,1} dan {3,1,2}
Contoh: Ada sebuah kotak berisi 3 bola masing-masing berwarna merah, hijau
dan biru. Jika seorang anak ditugaskan untuk mengambil 2 bola secara acak dan
urutan pengambilan diperhatikan, ada berapa permutasi yang terjadi?
Solusi: Ada 6 permutasi yaitu; M-H, M-B, H-M, H-B, B-M, B-H.
Salah satu aplikasi kombinasi dan permutasi adalah digunakan untuk mencari probabilitas suatu
kejadian.
Permutasi pengulangan
Jika urutan diperhatikan dan suatu objek dapat dipilih lebih dari sekali
maka jumlah permutasinya adalah:
di mana n adalah banyaknya objek yang dapat dipilih dan r adalah
jumlah yang harus dipilih.
Sebagai contoh, jika kamu memiliki huruf A, B, C, dan D dan kamu ingin
mencari tahu ada berapa cara untuk menyusunnya dalam suatu grup yang berisi
tiga angka maka kamu akan menemukan bahwa ada 43 atau 64 cara
untuk menyusunnya. Beberapa cara untuk menyusunnya adalah: AAA, BBB, CCC, DDD,
ABB, CBB, DBB, dst.
Permutasi tanpa pengulangan
Jika urutan diperhatikan dan setiap objek yang tersedia hanya bisa dipilih
atau dipakai sekali maka jumlah permutasi yang ada adalah:
di mana n adalah jumlah objek yang dapat kamu pilih, r adalah
jumlah yang harus dipilih dan ! adalah simbolfaktorial.
Sebagai contoh, ada sebuah pemungutan suara dalam suatu organisasi.
Kandidat yang bisa dipilih ada lima orang. Yang mendapat suara terbanyak akan
diangkat menjadi ketua organisasi tersebut. Yang mendapat suara kedua terbanyak
akan diangkat menjadi wakil ketua. Dan yang mendapat suara ketiga terbanyak
akan menjadi sekretaris. Ada berapa banyak hasil pemungutan suara yang mungkin
terjadi? Dengan menggunakan rumus di atas maka ada 5!/(5-3)! = 60 permutasi.
Umpamakan jika n = r (yang menandakan
bahwa jumlah objek yang bisa dipilih sama dengan jumlah yang harus dipilih)
maka rumusnya menjadi:
karena 0! = 1! = 1
Sebagai contoh, ada lima kotak kosong yang tersedia. Kelima kotak kosong
itu harus diisi (tidak boleh ada yang kosong). Kelima kotak kosong itu hanya
boleh diisi dengan angka 1,2,3,4,5. Ada berapa banyak cara untuk mengisi kotak
kosong? Dengan menggunakan rumus n! maka ada 5! = 120 permutasi.
Kombinasi tanpa pengulangan
Ketika urutan tidak diperhatikan akan tetapi setiap objek yang ada hanya
bisa dipilih sekali maka jumlah kombinasi yang ada adalah:
Di
mana n adalah
jumlah objek yang bisa dipilih dan r adalah jumlah yang harus dipilih.
Sebagai contoh, kamu mempunyai 5 pensil warna dengan warna yang berbeda
yaitu; merah, kuning, hijau, biru dan ungu. Kamu ingin membawanya ke sekolah.
Tapi kamu hanya boleh membawa dua pensil warna. Ada berapa banyak cara untuk
mengkombinasikan pensil warna yang ada? Dengan menggunakan rumus di atas maka
ada 5!/(5-2)!(2)! = 10 kombinasi.
Kombinasi pengulangan
Jika
urutan tidak diperhatikan dan objek bisa dipilih lebih dari sekali, maka jumlah
kombinasi yang ada adalah:
Di
mana n adalah
jumlah objek yang bisa dipilih dan r adalah jumlah yang harus dipilih. Sebagai contoh jika
kamu pergi ke sebuah toko donat. Toko donut itu menyediakan 10 jenis donat
berbeda. Kamu ingin membeli tiga donat. Maka kombinasi yang dihasilkan adalah
(10+3-1)!/3!(10-1)! = 220 kombinasi.
contoh
soal :
1. Ada berapa cara bila 4 orang remaja (w,x, y, z) menempati tempat duduk yang
akan disusun dalam suatu susunan yang teratua.
a. 1 cara
b. 30 cara
c. 42 cara
d. 24 cara
Jawaban:
4P4 = 4!
= 4 x 3 × 2 × 1
= 24 cara
2. Menjelang Pergantian kepengurusan BEM STMIK Tasikmalaya akan dibentuk
panitia inti sebanyak 2 orang (terdiri dari ketua dan wakil ketua), calon
panitia tersebut ada 6 orang yaitu: a, b, c, d, e, dan f. Ada berapa pasang
calon yang dapat duduk sebagai panitia inti tersebut?
a. 1 cara
b. 30 cara
c. 42 cara
d. 24 cara
Jawaban:
6P2 = 6!/(6-2)!
= (6.5.4.3.2.1)/(4.3.2.1)
= 720/24
= 30 cara
3. Sekelompok mahasiswa yang terdiri dari 10 orang akan mengadakan rapat dan
duduk mengelilingi sebuah meja, ada berapa carakah kelima mahasiswa tersebut
dapat diatur pada sekeliling meja tersebut?
a. 15246456
cara
b. 362880 cara
c. 763547 cara
d. 512 cara
Jawaban:
P5 = (10-1)!
= 9.8.7.6.5.4.3.2.1
= 362880 cara
4. Berapa banyak “kata” yang terbentuk dari kata “STMIK”?
a. 120 kata
b. 300 kata
c. 420 kata
d. 240 Kata
Jawab :
5! = 5 x 4 x 3 x 2 x 1 = 120 buah kata
5. Peluang lulusan PNJ dapat bekerja pada suatu perusahaan adalah 0,75. Jika
seorang lulusan PNJ mendaftarkan pada 24 perusahaan, maka berapakah dia dapat
diterima oleh perusahaan?
a. 16 perusahaan
b. 30 perushaaan
c. 418
Perusahaan
d. 31 Perushaan
Jawaban:
Frekuensi harapan kejadian A adalah
Fh(A) = n × P(A)
Diketahui P(A) = 0,75 dan n = 24. Maka:
Fh(A) = 24 × 0,75 = 18 perusahaan.
6 Dalam mengadakan suatu pemilihan dengan menggunakan obyek 4 orang pedagang
kaki lima untuk diwawancarai, maka untuk memilih 3 orang untuk satu kelompok.
Ada berapa cara kita dapat menyusunnya?
a. 1 cara
b. 2 cara
c. 3 cara
d. 4 cara
Jawaban:
4C3 =4! / 3! (4-3)!
= (4.3.2.1) / 3.2.1.1
= 24 / 6
= 4 cara
7. Suatu warna tertentu dibentuk dari campuran 3 warna yang berbeda. Jika
terdapat 4 warna, yaitu Merah, Kuning, Biru dan Hijau, maka berapa kombinasi
tiga jenis warna yang dihasilkan.
a. 1
b. 3
c. 4
d. 2
Jawaban:
nCx = (n!)/(x!(n-x)!)
4C3 = (4!)/(3!(4-3)!)
= 24/6 = 4 macam kombinasi (MKB, MKH,
KBH, MBH).
8. Dalam suatu pertemuan terdapat 10 orang yang belum saling kenal. Agar
mereka saling kenal maka mereka saling berjabat tangan. Berapa banyaknya jabat tangan yang terjadi.
a. 45 jabat tangan
b. 30 jabat
tangan
c. 42 jabat
tangan
d. 23 jabat
tangan
Jawaban:
10C2 = (10!)/(2!(10-2)!) = 45 jabat
tangan
9. Suatu kelompok yang terdiri dari 3 orang pria dan 2 orang wanita akan
memilih 3 orang pengurus. Berapa cara yang dapat dibentuk dari pemilihan jika
pengurus terdiri dari 2 orang pria dan 1 orang wanita.
a. 5 cara
b. 6 cara
c. 7 cara
d. 8 cara
Jawaban:
3C2 . 2C1 = (3!)/(2!(3-2)!) .
(2!)/(1!(2-1)!) = 6 cara, yaitu : L1 L2 W1 ; L1 L3 W1 ; L2 L3 W1 ; L1 L2 W2 ;
L1 L3 W2 ; L2 L3 W2
10. Dalam sebuah ujian, seorang mahasiswa diwajibkan mengerjakan 5 soal dari 8
soal yg tersedia. Tentukan:
a. banyaknya jenis pilihan soal yg mungkin untuk dikerjakan
b. banyaknya jenis pilihan soal yg mungkin dikerjakan jika no.6 dan 7 wajib
dikerjakan.
a. Ketentuan 1 = 56 cara, ketentuan 2 = 20 cara
b. Ketentuan 1 = 57 cara, ketentuan 2 = 21 cara
c. Ketentuan 1 = 59 cara, ketentuan 2 = 23 cara
d. Ketentuan 1 = 60 cara, ketentuan 2 = 24 cara
Jawaban:
c. 8 C5 = 8!/5!(8-5)! = (8×7×6×5!)/5!3! = 56 cara
d. 6C3 = 6!/3!(6-2)! = (6×5×4×3!)/3!3! = 20 cara
