Tugas Soal Matif

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 4³ 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 simbol faktorial.

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 :

11.    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

22.    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

33.    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

44.   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

55.    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.

16  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

17. 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).

18.  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

19. 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

110.  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