MATEMATIKA INFORMATIKA 3

INKLUSI DAN EKSKLUSI

Soal 1

Dalam sebuah bisokop terdapat 25 orang yang menyukai film horor, 13 orang menyukai film romantis dan 8 orang diantaranya menyukai film horor dan romantis. Berapa orang terdapat didalam bioskop tersebut?

a.       20

b.      30

c.       40

d.      50

Penyelesaian:

Misalkan A himpunan orang yang menyukai film horor dan B himpunan orang yang menyukai film romantis. Himpunan mahasiswa yang menyukai kedua film tersebut dapat dinyatakan sebagai himpunan (A∩B). Banyaknya orang yang menyukai salah satu film tersebut atau keduanya dinyatakan dengan (A∪B). Dengan demikian

n(A∪B) = n(A) + n(B) – n(A∩B)

              = 25 + 13 - 8

              = 30

Jadi, terdapat 30 orang didalam bioskop tersebut.

Soal 2

Dalam sebuah kelas terdapat 25 mahasiswa yang mengikuti mata kuliah matematika informatika dan 35 mahasiswa yang mengikuti mata kuliah algoritma dan pemrogramanan, dan 10 mahasiswa yang mengikuti mata kuliah matematika informatika dan algoritma dan pemrograman. Ada berapa mahasiswa didalam kelas itu jika setiap mahasiswa mengikuti mata kuliah matematika informatika, algoritma dan pemrograman, atau kedua-duanya?

a.       20

b.      30

c.       40

d.      50

Penyelesaian:

Misalkan A adalah banyaknya mahasiswa yang mengikuti mata kuliah matematika informatika dan B menyatakan mahasiswa yang mengikuti mata kuliah algoritma dan pemrograman. Maka AB merupakan himpunan mahasiswa yang mengambil kedua mata kuliah tersebut. Banyaknya mahasiswa didalam kelas itu yang mengambil mata kuliah matematika informatika, algoritma dan pemrograman, atau kedua-duanya adalah

n(A∪B) = n(A) + n(B) - n(A∩B)

  = 25 + 35 - 10

  = 50

Ini berarti, terdapat 50 mahasiswa didalam kelas yang mengambil mata kuliah matematika informatika, algoritma dan pemrograman, atau kedua-duanya.

Soal 3

Di sebuah jurusan terdapat 334 mahasiswa tingkat 2. Dari sekian banyak mahasiswa tersebut, 187 di antaranya mengambil mata kuliah statistika, 173 mengambil mata kuliah struktur data, dan 79 mengambil mata kuliah statistika dan struktur data. Berapa banyak mahasiswa yang tidak mengambil mata kuliah baik dalam statistika maupun struktur data?

a.       51

b.      52

c.       53

d.      54

Penyelesaian:

Untuk menentukan banyaknya mahasiswa tingkat 2 yang tidak mengambil mata kuliah statistika ataupun struktur data, kurangilah banyaknya mahasiswa tingkat 2 dengan banyaknya mahasiswa yang mengambil mata kuliah statistika, struktur data dan keduanya. Misalkan A merupakan himpunan semua mahasiwa tingkat 2 yang mengambil mata kuliah statistika, dan B adalah himpunan mahasiswa yang mengambil mata kuliah struktur data. Maka n(A)=187, n(B)=173, dan n(A∩B)=79. Banyaknya mahasiswa tingkat 2 yang mengambil mata kuliah statistika, struktur data, atau keduanya adalah

n(A∪B) = n(A) + n(B) – n(A∩B)

  = 187 + 173 - 79

  = 281

Ini artinya terdapat sebanyak 334–281 = 53 mahasiswa tingkat 2 yang tidak mengambil mata kuliah statistika ataupun struktur data.

Soal 4

Di sebuah kantin terdapat 24 mahasiswa yang memilih menu A, 17 memilih menu B, 11 memilih menu C, 6 memilih menu A dan B, 8 memilih menu A dan C, 9 memilih menu B dan C, dan 4 memilih menu A, B dan C. Berapa banyak mahasiswa yang terdapat didalam kantin tersebut?

a.       33

b.      34

c.       35

d.      36

Penyelesaian:

Misalkan A adalah banyaknya mahasiswa yang memilih menu A, B menyatakan mahasiswa yang memilih menu B dan C menyatakan mahasiswa yang memilih menu C. Maka A∩B∩C merupakan himpunan mahasiswa yang memilih ketiga menu tersebut. Dengan demikian

n(A∪B∪C) = n(A) + n(B) + n(C) - n(A∩B) - n(A∩C) - n(B∩C) + n(A∩B∩C)

        = 24 + 17 + 11 - 6 – 8 – 9 + 4

        = 33

Jadi, terdapat 33 orang di kantin tersebut.

Soal 5

Berapa banyak bilangan bulat positif yang tidak melampaui 1000 yang habis dibagi oleh 7 atau 11?

a.       200

b.      210

c.       220

d.      230

Penyelesaian:

Misalkan P himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 11. Dengan demikian P∪Q adalah himpunan bilangan bulat positif tidak meiampaui 1000 yang habis dibagi 7 atau habis dibagi 11, dan P∩Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan habis dibagi 11.

Jadi, terdapat 220 bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11.

Soal 6
Berapa banyak bilangan bulat positif yang tidak melampaui 1000 yang habis dibagi oleh 5, 7 atau 11?

a.    375
b.    376
c.    377
d.    378

Penyelesaian:
Misalkan P himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5, Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7, dan R himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 11. Dengan demikian P∪Q∪R adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5 atau 7 atau 11, dan himpunan P∩Q∩R adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5, 7 dan 11. Himpunan P∩Q adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5 dan 7, P∩R adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5 dan 11, dan Q∩R adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan 11.

Jadi, terdapat 376 bilangan bulat positif tidak melampaui 1000 yang habis dibagi 5, 7 atau habis dibagi 11.

 

PIGEONHOLE

Soal 1

Sebut dan jelaskan aplikasi dari pigeonhole?

Jawab:

Aplikasi Pada Permasalahan Relasi

Prinsip pigeonhole dapat diaplikasikan dalam berbagai permasalahan relasi. Misalkan ada pertemuan yang dihadiri oleh 50 orang. Dari 50 orang tersebut, ada beberapa yang kenal satu sama lain. Kita dapat membuktikan bahwa dalam ruangan tersebut pasti ada dua orang dengan jumlah kenalan yang sama menggunakan prinsip pigeonhole. Dengan mengasumsikan satu orang tidak mempunyai kenalan sama sekali, jumlah maksimum kenalan satu orang adalah 48. Maka, anggap jumlah kenalan dari 0 sampai 48 sebagai sarang burung merpati, dan anggap 50 orang yang hadir pada pertemuan tersebut sebagai merpatinya. Berdasarkan prinsip pigeonhole, setidak-tidaknya akan ada  dua  orang yang  mempunyai jumlah kenalan yang sama. Begitu pula jika kita asumsikan masing-masing orang yang hadir pada pertemuan tersebut mempunyai setidaknya satu kenalan, sehingga maksimum jumlah kenalan dari seseorang adalah 49. Jika dianggap jumlah kenalan dari 1 sampai 49 sebagai sarang burung merpati dan 50 orang yang hadir pada pertemuan tersebut sebagai merpatinya, tetap setidak-tidaknya ada dua orang yang mempunyai jumlah kenalan yang sama.

Aplikasi prinsip pigeonhole dalam relasi cukup berguna dalam mengaproksimasi kebutuhan minimal yang harus disiapkan dalam hal tertentu. Misalkan suatu perusahaan kereta  api  mempunyai  statistik  jumlah  pengguna  500 setiap harinya. Jika ada 20 lintasan kereta api yang berbeda, maka berdasarkan prinsip pigeonhole minimal ada 25 pengguna dengan lintasan kereta api yang sama. Maka dari itu, minimalnya perusahaan kereta api tersebut menyediakan kereta api yang mempunyai daya tampung 25 pengguna untuk setiap jurusan untuk memenuhi kebutuhan minimal tiap lintasan. Namun demikian, dalam prakteknya, prinsip pigeonhole memang tidak dapat diterapkan semudah itu.

Aplikasi Pada Sains Komputer

Salah satu aplikasi prinsip pigeonhole pada sains komputer adalah pada hash collision. Sebagai informasi, algoritma hash mengubah suatu data apapun ke dalam bentuk data lain. Hal ini dilakukan dengan memproses data tersebut dalam suatu formula matematika kompleks untuk menghasilkan hash unik bagi setiap potongan data. Umumnya, hash yang dihasilkan memiliki bit yang sama untuk setiap algoritma hash yang sama. Jika data yang diproses lebih kecil dari bit minimal hash yang akan dihasilkan, maka algoritma hash yang bersangkutan akan menambahkan junk data  untuk mengisi bit  yang  tidak terpakai. Hash collision terjadi apabila dua data atau lebih menghasilkan hash yang sama. Menggunakan prinsip pigeonhole, hash collision merupakan hal yang tidak terhindarkan, terlebih jika data yang di hash berukuran besar. Hal ini dikarenakan hash yang tersedia lebih sedikit daripada potongan data yang diproses. Anggap hash sebagai sarang burung merpati dan potongan data yang diproses sebagai burung merpati. Maka, pasti ada hash yang merepresentasikan lebih dari satu potongan data.

Aplikasi yang kedua adalah pada kompresi data. Kompresi data adalah proses memampatkan suatu data apapun ke dalam bentuk dengan ukuran yang lebih kecil. Dengan prinsip pigeonhole, dapat dibuktikan tidak mungkin ada algoritma kompresi yang dapat selalu berhasil memampatkan data menjadi lebih kecil. Hal ini dikarenakan ukuran yang lebih kecil berarti bit yang lebih sedikit, sehingga jika hasil kompresi dianalogikan dengan sarang burung merpati, jumlah sarang burung merpati selalu lebih sedikit daripada merpatinya (yaitu data yang akan diproses dengan algoritma kompresi).

Aplikasi Pada Permasalahan Numerikal

Prinsip pigeonhole mampu menyelesaikan beberapa permasalahan numerikal. Contohnya adalah permasalahan  divisibilitas.  Dengan  prinsip  pigeonhole, kita  mampu  membuktikan bahwa  pasti  ada  dua  angka dalam n angka yang selisihnya habis dibagi angka n-1 dengan n bilangan bulat positif ≥ 2. Kita ambil contoh n = sepuluh, sehingga dalam sepuluh angka yang diberikan ada minimal dua angka dengan selisih habis dibagi sembilan. Sisa dari pembagian suatu angka dengan sembilan juga berjumlah sembilan, yaitu 0, 1, 2, 3, 4, 5, 6, 7, dan 8. Jika sisa dari pembagian suatu angka dengan sembilan tersebut kita analogikan sebagai sarang burung merpati dan sepuluh angka  yang diberikan kita analogikan sebagai  merpati, maka dalam sepuluh angka tersebut minimal ada dua angka yang mempunyai sisa yang sama dari pembagian terhadap sembilan. Dua angka inilah yang bila diselisihkan selisihnya akan habis dibagi sembilan.

Aplikasi Pada Teori Ramsey

Secara umum, teori Ramsey membahas distribusi subset elemen dalam suatu set elemen. Teori Ramsey merupakan extremal combinatorics yang memberikan jumlah objek jika  kumpulan objek  tersebut harus  memenuhi kondisi tertentu. Berikut adalah permasalahan yang dapat memberikan gambaran  mengenai  teori  Ramsey:  dalam suatu grup yang terdiri dari enam orang, hubungan antara sepasang orang dapat berupa pertemanan ataupun permusuhan; buktikan bahwa ada setidaknya tiga orang yang saling berteman atau tiga orang yang saling bermusuhan. Misalkan A merupakan salah satu dari keenam orang tersebut, maka setidaknya tiga orang dari lima orang selain A bermusuhan atau berteman dengan A (sesuai prinsip pigeonhole). Anggap B, C, D berteman dengan A. Maka, jika dua dari B, C, D berteman, akan terbentuk tiga orang yang saling berteman. Sebaliknya, jika tidak, maka akan terbentuk tiga orang yang saling bermusuhan. Bila dikaitkan dengan permasalahan tersebut, bilangan Ramsey dengan notasi R(m,n) merupakan jumlah minimum orang yang diperlukan untuk menghasilkan m orang yang saling berteman atau n orang yang saling bermusuhan. Berdasarkan solusi dari permasalahan tersebut, R(3,3) = 6.

Soal 2

Adakah keterkaitan antara permutasi, kombinasi dan pigeonhole.? Jelaskan!

Jawab:

Keterkaitan antara permutasi, kombinasi dan pigeonhole tentu saja ada. Kenapa dikatakan demikian karena metode ini dapat menujukkan banyaknya suatu susunan yang dapat dibentuk dari suatu kumpulan objek yang berbeda dalam suatu tempat, baik yang dipilih seluruhnya atau sebagian. Dengan demikian, metode ini dapat mencari objek dalam suatu tempat dan dapat menentukan banyaknnya objek yang berhubungan dengan prinsip Pigeonhole.