Mencari Istri

Buat kamu yang cowok yang masih melajang, belum menikah. Bagaimana seandainya kamu diberi kesempatan untuk memilih salah satu dari n cewek untuk di nikahi, untuk dijadikan istri.

Dengan ketentuan-ketentuan sebagai berikut.

  • Kamu tidak mengenal kesemua calon istrimu tersebut.
  • Pemilihan dilakukan dengan cara kencan, makan malam romantis berdua.
  • Kamu memilih secara acak siapa calon yang terlebih dahulu mau kamu ajak kencan.
  • Selesai kencan dengan seorang calon, kamu langsung melakukan penilaian dan memutuskan apakah kamu mau menikahi calon tersebut atau tidak.
  • Keputusanmu bersifat mutlak. Kamu tidak bisa meralat keputsan yang sudah kamu ambil.

Pertanyaannya:

Bagaimana strategi optimalmu untuk memilih cewek terbaik sebagai istrimu?

Tentunya kamu tidak akan langsung menerima calon yang pertama-tama di ajak kencan. Misalkan ada 100 calon, apakah kamu akan lansung menerima calon yang pertama kali kamu ajak kencan? Kecil kemungkinan kamu melakukan hal tersebut, ya kan..

Dari ketentuan-ketentuan diatas, untuk mendapatkan calon terbaik yang bisa kamu lakukan adalah memilih calon yang lebih baik dari calon-calon yang sudah kamu tolak dan berharap calon yang lebih baik tersebut adalah calon terbaik dari semua calon yang ada.

Misalkan k-1 adalah banyaknya  calon-calon pertama yang kamu tolak dan k adalah calon pertama yang kamu pertimbangkan, tidak langsung kamu tolak. Diberikan M adalah calon terbaik diantara k-1 kemudian pilih calon berikutnya yang lebih baik dari M

Jika ada n calon, berapa k yang kamu pilih supaya mendapatkan kemungkinan terbesar mendapatkan calon terbaik. Berapa kemungkinannya? Apa yang akan terjadi jika n menuju tak hingga?

Diberikan P_{n}\left(k\right) kemungkinan memilih calon terbaik dari n calon dengan menggunakan strategi k

Kasus n=3

Ada 6 permutasi dari \left\{ 1,2,3\right\} dengan 1 yang terbaik dan 3 yang terburuk. yaitu

  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1

Nilai k yang mungkin kita pilih antara 1 sampai 3. Jika k=1, kita akan selalu memilih calon pertama. jika k=3, kita akan selalu memilih calon terakhir. Jika k=2, kita akan selalu menolak calon yang pertama dan memilih calon  berikutnya yang lebih baik dari calon pertama. Jika calon pertama adalah 2, maka kita akan memilih 1. Jika calon pertama adalah 3, kita akan memilih 1 atau 2, tergantung siapa yang pertama kali kita lihat. Jika calon pertama adalah 1 maka kita tidak akan mendapatkan calon terbaik dan akan memilih calon terakhir.

Sekarang, kita daftar P_{n}\left(k\right) untuk setiap nilai k.

k P_{n}\left(k\right)
1 2/6
2 3/6
3 1/6

Jadi k=2 adalah optimal.

Kasus n=4

Terdapat 24 permutasi dari \left\{ 1,2,3,4,\right\}  dengan 1 yang terbaik dan 4 yang terburuk.

k P_{n}\left(k\right)
1 6/24
2 11/24
3 10/24
4 6/24

Jadi k=2 adalah optimal.

Kasus n=5

Terdapat 120 permutasi dari \left\{ 1,2,3,4,5\right\}  dengan 1 yang terbaik dan 5 yang terburuk.

k P_{n}\left(k\right)
1 24/120
2 50/120
3 52/120
4 42/120
5 24/120

Jadi k=3 adalah optimal.

Kasus Umum

Sekarang kita ambil sebarang n dan akan mengkontruksikan rumus umumnya. Dinotasikan X_n banyaknya cara mengurutkan calon terbaik dan  S_n menotasikan kejadian sukses yaitu terpilihnya calon terbaik.

Ada n calon dan hanya satu calon terbaik, itu artinya kemungkinan seorang calon adalah yang terbaik adalah 1/n.

Ada 2 kondisi yang akan menyebabkan kita akan selalu gagal mendapatkan calon terbaik.

  1. Calon terbaik berada diantara k-1 urutan pertama (Calon-calon  pertama yang telah ditolak)
  2. Calon terbaik tidak berada diantara k-1 urutan tetapi  didahului oleh calon yang lebih baik dari semua caloan pada k-1 urutan pertama.

Sebaliknya untuk sukses mendapatkan calon terbaik ada 2 syarat yang harus dipenuhi

  1. Calon terbaik harus diurutan ke-j dengan k\leq j\leq n
  2. Calon terbaik dari urutan 1 sampai j-1 haruslah terletak didalam k-1 urutan pertama.

Sekarang kita hitung kemungkinan kita sukses memilih calon diposisi k Kemungkinan dia calon terbaik adlah 1/n .Sedangkan kemungkinan calon terbaik sebelum posisi k berada diantara k-1 pertama adalah 1. Jadi kemungkinan kita suskes dengan calon di posisi k adalah 1/n\cdot1=1/n.

Selanjutnya kita hitung kemungkinan kita sukses memilih calon diposisi k+1 Kemungkinan dia calon terbaik adalah 1/n .Sedangkna kemungkian calon terbaik sebelum posisi k+1 berada diantara k-1 pertama adalah \left(k-1\right)/k. Jadi kemungkinan kita suskes dengan calon di posisi k+1 adalah \frac{1}{n}\cdot\frac{k-1}{k}=\left(k-1\right)/nk.

kita hitung kemungkinan kita sukses memilih calon diposisi k+2 Kemungkinan dia calon terbaik adalah 1/n .Sedangka kemungkinan calon terbaik sebelum posisi k+2 berada diantara k-1 pertama adalah \left(k-1\right)/k+1. Jadi kemungkinan kita suskes dengan calon di posisi k+2 adalah \frac{1}{n}\cdot\frac{k-1}{k+1}=\left(k-1\right)/n(k+1).

Begitu seterusnya sehingga untuk posisi terakhir, diperoleh kemungkian sukses untuk calon diposisi terakhir \frac{k-1}{n\left(n-1\right)}.

Jumlahkan semuanya, kita peroleh:

{\displaystyle P_{n}\left(k\right)=\mathbb{P}}\left(S_{n,k}\right)=\frac{1}{n}+\frac{k-1}{nk}+\frac{k-1}{n\left(k+1\right)}+\ldots+\frac{k-1}{n\left(n-1\right)}

{\displaystyle =\frac{k-1}{n}\sum_{j=k}^{n}\frac{1}{j-i}}

Asumsi n menuju tak hingga, dinotasikan x adalah limit dari k/n. subtitusi t untuk j/n dan dt untuk 1/n,Penjumlahan diatas bisa didekati dengan integral:

P\left(x\right)=x\int_{x}^{1}\frac{1}{t}dt=-x\ln x

Supaya P\left(x\right)=1 maka haruslah x=1/e \approx0,0.367, karena x adalah limit dari k/n maka diperoleh k=n/e.

Jadi nilai k optimal supaya menghasilkan kemungkinan terbesar mendapatkan calon terbaik  adalah n/e. Jika ada 100 calon maka kamu harus menolak 36 calon pertama.

Aturan n/e tetep berlaku meskipun n amat besar menuju tak hingga. Tidak peduli kamu punya sejuta calon istri, tetap gunakan Aturan n/e.

Masalah yang saya bahas diatas dikenal dengan nama the marriage problem, the sultan’s dowry problem, the fussy suitor problem, the googol game, dan the best choice problem.

Foto: jkt48

Advertisements

About Aria Turns

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in probabilitas and tagged , , , , . Bookmark the permalink.

3 Responses to Mencari Istri

  1. embun says:

    Hehe.. Pusing deh kalau dah harus makek rumus matematika buat cari istri..
    Tapi yang jadi masalah bagaimana jika ternyata yang terbaik adalah yang pertama kali kita ajak kencan dan keburu kita tolak..?

  2. pring says:

    kalau kemungkinan saya untuk mendapatkan ce yang pake celana pendek,, rambut cokelat, di tengah2 itu ada nggak?

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s