Sunday, December 27, 2009

Inclusion Exclusion Principle: Matching Problem

Jangan ngeri dulu ngeliat judulnya yang ribet. Sebetulnya ini prinsip inklusi eksklusi ini mudah. Langsung aja kita lihat contoh kasus "Matching Problem".
Ada 10 bola dan 10 kotak. Setiap bola diberi label 1, 2, 3, ..., 10. Begitu pula dengan kotaknya, diberi label 1, 2, 3, ..., 10. Budi menaruh masing-masing bola ke masing-masing kotak secara acak, sehingga sekarang setiap kotak berisi masing-masing satu bola.

Pertanyaannya: Berapakah peluang tidak ada satu pun label bola dan kotaknya yang cocok? (misalnya seperti ilustrasi di atas).
Soal di atas identik dengan soal berikut:
Seorang guru ingin mengembalikan sejumlah N PR (pekerjaan rumah) ke N siswa secara acak. Berapakah peluang bahwa tak ada satupun siswa yang mendapatkan PR-nya sendiri? Jika N adalah 30? Apa yang terjadi jika N lebih besar atau lebih kecil?
=======================================================================
PENYELESAIAN
Jawabannya adalah .
Yang mengejutkan adalah peluangnya cenderung mendekati atau sekitar , berapapun nilai N yang ingin kita ambil, asalkan . Silakan dicek sendiri dengan memasukkan nilai N ke fungsi di atas.. Lebih jauh, silakan kalian bereksperimen sendiri dengan memisalkan N, misalnya 3, 4, 5, dan seterusnya.. Lalu, bagaimana hasil tersebut didapat? Bagaimana tiba-tiba muncul nilai ini? Lihat lanjutannya di bawah. :)


Prinsip Inklusi-Ekslusi
Cara untuk menyelesaikan kasus ini adalah dengan prinsip inklusi-eksklusi (atau dikenal dengan sieve prinsiple).
Inclusion-Exclusion Prinsiple

________

________

________
________
Kalau kalian melihat di rumus di atas (wikipedia), rumus itu terlihat sangat menakutkan, tapi sesungguhnya mudah sekali dijelaskan dengan *bahasa manusia*.. Nah, di post ini, saya ingin menjelaskannya dengan bahasa yang mudah dimengerti.

Ambil contoh:
Misalkan kita punya 2 himpunan, yaitu himpunan dan .
_______.
_______.
Untuk menentukan jumlah anggota , kita gunakan formula berikut:
_______
_______
_______
_______
Jika digambarkan di diagram Venn adalah sbb:


Ambil contoh lagi:
Misalkan kita punya tiga himpunan, yaitu , , dan .
_______.
_______.
_______
Untuk menentukan jumlah anggota , kita gunakan formula berikut:




Jika digambarkan di diagram Venn adalah sbb:



Pahami terlebih dahulu bagian yang di atas, karena sesungguhnya prinsipnya sangat mudah.
Untuk seterusnya, misalkan n = 4, berarti ada 4 himpunan, maka formulanya adalah sbb:

________________
________________
________________

Perhatikan bahwa tandanya berselang-seling, dari + ke -, lalu ke + dan ke - lagi. Ini dapat dibuktikan secara prinsip logika. Untuk selanjutnya, kita gunakan singkatan untuk penulisan formula di atas dengan notasi sigma dan pi sbb:



_______


Penyelesaian dengan Prinsip Inklusi-Eksklusi

Kita gunakan kasus bola dan kotak. Misalkan ada N bola dan N kotak.
Kita definisikan set-set himpunan sebagai berikut:
= himp semua urutan dimana urutan pertama pasti benar (bola 1 berpasangan dg kotak 1).
= himp semua urutan dimana urutan kedua pasti benar (bola 2 berpasangan dg kotak 2).
= himp semua urutan dimana urutan ketiga pasti benar (bola 3 berpasangan dg kotak 3).
....
dan seterusnya.

= himpunan semua urutan dimana setidaknya ada 1 urutan (bola dan kotak) yang pasti cocok.

Kita gunakan prinsip inklusi-eksklusi untuk menentukan nilai .
=
___________
___________

___________
___________

Keterangan:
berarti himpunan semua urutan dimana urutan ke i , j , ... hingga p benar.

Sebagai contoh:
berarti himpunan semua urutan dimana urutan ke 2 dan urutan ke 6 pasti benar (bola 2 berpasangan dg kotak 2; bola 6 berpasangan dg kotak 6).

Perhatikan bahwa banyaknya himpunan itu tidak bergantung pada letak urutan, tapi hanya bergantung pada banyak urutan yang cocok (k). Sebagai contoh: banyaknya himpunan dimana urutan ke 3,6, dan 10 cocok sama dengan banyaknya himpunan dimana urutan ke 2, 8, 9 cocok, dan juga sama dengan banyaknya himpunan dimana urutan ke 1, 3, 4 cocok. Oleh karenanya, secara logika, kita tahu bahwa setiap notasi sigma dapat direpresentasikan sebagai di mana k adalah jumlah urutan yang pasti benar.

Jadi, formulanya sekarang adl sbb:

___
___
___
___
___

Untuk menghitung , kita tahu bahwa dari n urutan kartu, urutan pertama pasti benar. Oleh karenanya kita tinggal menghitung permutasi sisa urutannya, yaitu .

Untuk menghitung , kita tahu bahwa dari n urutan kartu, ada 2 urutan yang pasti benar (yaitu di urutan pertama dan kedua). Oleh karenanya, banyaknya himpunan ini adalah permutasi sisa urutannya, yaitu .

Untuk selanjutnya, memakai konsep yang sama.

Dengan demikian:

___
___
___
___
___

Kita gunakan notasi sigma untuk :

Kita tahu bahwa . Oleh karenanya, dapat disederhanakan menjadi:


Kita tahu banyaknya himpunan yang setidaknya memuat 1 pasang yang cocok. Oleh karenanya, kita dapat menentukan peluangnya.





Dengan demikian,





Berdasarkan deret Taylor, , maka untuk nilai n mendekati tak hingga: . Artinya, peluangnya mendekati atau sekitar .
Namun, untuk , nilai ini sudah didekati dengan baik, dan dapat kita anggap bahwa nilai n tidak memberikan pengaruh yang signifikan.

=======================================================================
PENUTUP

Penerapan prinsip eksklusi-inklusi yang lainnya masih banyak. Mungkin akan dijelaskan lain waktu di post yang berikutnya. :)

So, kasus "Matching Problem" sudah kita pecahkan. Karena kemungkinan berhasilnya kecil, jangan coba-coba untuk menjawab ngasal ketika kita menjawab soal bertipe menjodohkan, karena peluang mendapatkan nilai nol adalah 40%. Wakakak.

Ada yang kurang ngerti dengan pembahasan di atas? Sialakn ditanyakan di comment di bawah. :D

21 comments:

  1. penjelasannya mungkin udah detail, namun saya masih belum "dong"

    ReplyDelete
  2. 38+38=76
    xx+yy=24 atau 124

    hasil 24 atau 124 didapat dari
    100-76=24
    atau
    200-76=124

    bagaimana cara mencari jawaban xx dan yy
    dalam bentuk 2 digit angka,saya akan sangat
    berterima kasih bila jawaban tersebut dijabarkan
    bersama contoh.
    salam

    ReplyDelete
  3. yang menjadi masalah
    karena
    xx= memiliki jawaban 0 s/d 100
    begitu juga dgn
    yy= memiliki jawaban 0 s/d 100
    apakah mungkin hasilnya bisa diminimalkan
    dari 100 menjadi 10 saja untuk
    masing2 jawaban xx dan yy atau bisa lebih kecil lagi.
    sekali lagi terima kasih bila mau membantu

    ReplyDelete
  4. oh.........begitu yah? cukup asyik juga.....

    ReplyDelete
  5. halo,slm kenal pak.sy riani.
    mw nanya,bpk ad tulisan/artikel/jurnal y ngebahas komunikasi matematika gak? klo iya tlong dikirim ke email sy. atw rekomendasi sumber pn blh.
    thanks :)

    ReplyDelete
  6. kk mau nanya, kalau misalnya kk pinter kk boleh donk jawab pertanyaan saya, boleh ya???
    plisss.......

    ini soalnya:
    ada satu cowok pergi ke gunung, lalu tiba tiba ia tersesat. lalu dia melihat ada dua satpam, kedua satpam itu KEMBAR.tapi mereka berbeda sifat, ada 1 penunjuk arah yg benar. ada 1 satpam yg penunjuk arah yg salah, tapi kita tidak tau mana yg satpam penunjuk arah yg benar dan baik, jika kita menanyakan jalan menuju gunung, ada satpam yg menunjuk arah yg benar dan ada satpam yg menunjuk arah yg salah. bantulah cowok tersebut untuk menanyakan dimana gunung tersebut, dng hanya 1 pertanyaan.

    PERTANYAAN: APA PERTANYAAN YG HARUS DITANYAKAN KEPADA KEDUA SATPAM TERSEBUT??????? ( KITA CUMAN BSA BERTANYA 1X LAGI SAJA

    ReplyDelete
    Replies
    1. Tanya ke 1satpam : Menurut kamu, jika aku bertanya ke satpam yang lain dia bakalan jawab ke arah mana?
      IKUTI LAWAN DARI JAWABANNYA.

      Delete
  7. gue suka banget sama ini blog....
    thanks kang hndry, banyak pengetahuan yang aku dapt

    ReplyDelete
  8. detail sekali juga menarik
    salam sukses selalu sob

    ReplyDelete
    Replies
    1. ada yang tau gak contoh persamaan diophantin non linier?

      Delete
  9. ada yang tau contoh triple phytagoras pada persamaan diophantin non linier gak?
    yang dalil 7.1 dan 7.2

    ReplyDelete
  10. Hal yang tidak pernah terbayankan kini menjadi kenyataan dengan keluargaku,,,untuk MBAH SARTO kami ucapkan banyak terimakasih karna berkat bantuannya ALHAMDULILLAH keluarga kami bisa lepas dari hutang dan masalah,karna nomor “GHOIB”untuk pasangf togel,hasil ritual MBAH SARTO meman benar2 merubah nasib kami hanya sekejap,dan disitulah aku berkesempatan kumpulkan uang untuk buka usaha kembali,karna baik rumah sudah disita,,warung makan jg sudah bangkrut,,tapi itu semua aku masih tetap bertahan hidup dengan anak istriku,,walau cuma kontrak tapi aku tetap bersabar dan akhirnya MBAH SARTO lah yang bisa merubah nasib kami..MBAH SARTO orang paling bersejarah kepada keluarga saya…!!! Kepada teman2 yang di lilit hutang dan ingin merubah nasib baik dari pada sekaran HBG: 082=378=607=111 MBAH SARTO,dengan penuh harapan INSYAH ALLAH pasti tercapai.

    ReplyDelete
  11. Blogging is the new poetry. I find it wonderful and amazing in many ways.

    ReplyDelete
  12. Very informative post for me as I am always looking for new content that can help me and my knowledge grow better.

    ReplyDelete
  13. Amazing blog and very interesting stuff you got here! I definitely learned a lot from reading through some of your earlier posts as well and decided to drop a comment on this one!

    ReplyDelete
    Replies
    1. Amazing blog and very interesting stuff you got here! I definitely learned a lot from reading through some of your earlier posts as well and decided to drop a comment on this one!

      Delete
  14. I really appreciate your professional approach. These are pieces of very useful information that will be of great use for me in future.

    ReplyDelete
  15. Hey keep posting such good and meaningful articles.

    ReplyDelete
  16. What you're saying is completely true. I know that everybody must say the same thing, but I just think that you put it in a way that everyone can understand. I'm sure you'll reach so many people with what you've got to say.

    ReplyDelete