100 Napi dan 100 Kotak

Di suatu penjara, Sang kepala Sipir menawarkan kesempatan kepada 100 narapidananya untuk bebas, jika mampu memenangkan permainan yang dirancang olehnya. Kepala sipir telah menyiapkan suatu ruangan yang berisikan 100 kotak identik yang tersusun rapih di atas meja. Kotak-kotak tersebut diberi nomer urut dari 1 sampai 100. Di setiap kotak berisikan satu nama dari 100 narapidana tersebut. Peletakan nama didalam kotak, dialkukan secara acak.

Nah…aturan mainnya sebagai berikut:

  • Satu persatu napi memasuk ruangan untuk menemukan kotak berisikan namanya.
  • Hanya memboleh membuka kotak, maksimal 50 kotak
  • Jika telah membuka lebih dari 50kotak dan belum juga menemukan kotak berisi namanya maka napi tersebut kalah.
  • Napi yang telah mengikuti permainan ditempatkan di raung tersendiri sehingga mereka tidak bisa berkomunikasi dengan napi yang belum mengikuti permainan.
  • Sebelum permainan dimulai, para napi boleh berdiskusi menentukan strategi

Supaya bisa bebas mereka semua harus memenangkan permainan (Ingat semua!). Tentukan strategi sehinga kemungkinan 100 napi tersebut bebas adalah 30% !

***

Teka-teki diatas pertamakali diajukan oleh Peter Bro Miltersen, seorang Ilmuwan komputer asal Belanda pada tahun 2003. Jika setiap napi membuka secara acak 50 kotak maka kemungkian seorang Napi mendapatkan kotak yang berisi namanya adalah 1/2. So.. kemungkinan 100 napi medapatkan kotak yang sesuai dengan kata lain bebas adalah

1/2^{100}\approx0,0000000000000000000000000000008

Mmmm…. benar-benar kemungkinan yang teramat kecil-kecil sekali. Benarkah ada strategi sehingga kemungkinan sukses menjadi 30%. Tentu saja ada.

Bagaimana Strateginya?

100napi 100kotak

Pertama-tama para napi harus menetukan urutan, siapa yang maju pertama, kedua dan setrusnya kemudian strategi mebuka kotaknya sebagai berikut:

Napi ke-i yang memasuki ruangan pertama-tama akan membuka kotak i. Jika kotak i berisi nama napi ke-j maka dia akan membuka kotak j. Jika kotak j berisi nama napi ke-k maka dia membuka kotak k. Begitu setrusnya sampai dia menemukan kotak berisi namanya.

Mengapa strategi tersebut mempunyai peluang sukses 30%?

Akan saya jelaskan dengan contoh yang lebih sederhana yang hanya terdiri dari 10 napi, 10 kotak dan maksimal membuka 5 kotak. Misalkan isi 10 kotak tersebut sebagai berikut:

10kotak

Dari tabel diatas maka kotak-kotak yang dibuka para Napi sebagai berikut:

  1. Napi ke-1 membuka kotak 1 dan 10
  2. Napi ke-2 membuka kotak 2, 4,  8, dan 5
  3. Napi ke-3 membuka kotak 3, 7, 6 dan 9
  4. Napi ke-4 membuka kotak 4, 8, 5, dan 2
  5. Napi ke-5 membuka kotak 5, 2, 4, dan 8
  6. Napi ke-6 membuk kotak 6, 9, 3, dan 7
  7. Napi ke-7 membuka kotak 7, 6, 9, dan 3
  8. Napi ke- 8 membuka kotak 8, 5, 2 dan 4
  9. Napi ke-9 membuka kotak 9, 3, 7 dan 6
  10. Napi ke-10 membuka kotak 10 dan 1.

Bisa kalian lihat SEMUA Napi suskses menemukan namanya denga membuka kutang dari 5 kotak. Padahal kolom kanan saya isi secara acak. Nah… sekarang penjelasan matematisnya.

Meletakkan nama napi ke-i didalam kotak j, sebenarnya merupakan permutasi. Jika tabel diatas direpresentasikan kedalam permutasi maka merupakan hasil permutasi siklik

(1 10)(2 4 8 5)(3 7 6 9)

Bisa kalian lihat panjang siklik yang terbentuk kurang dari 5. Inilah alasan utama 10 napi tersebut menang. Jika terbentuk siklik yang panjangnya lebih dari 5 itu artinya kegagalan. Nah selanjutnya akan kita hitung kemungkinan terbentuknya siklik dengan panjang lebih dari 5.

Pertama-tama kita akan hitung kemungkinan munculnya siklik dengan panjang 6 dari permutasi 10 elemen

Untuk membuat 6-siklik, kita harus memilih 6 eleman dari 10 elemen yan tersedia. Ada \binom{10}{6} carauntuk melakukannya. Ada 5! cara mengurutkan eleman-elema didalam 6-siklik dan 4! mengurukan eleman-eleman yang tersisa. So banyaknya cara membentuk 6-siklik dari 10 elemen adalah.

\binom{10}{6}5!4!=\frac{10!}{6!4!}5!4!=\frac{10!}{6}

Ada 10! cara membentuk permutasi dari 10 eleman maka kemungkinasuatu permutasi dengan 10 elemen mempunya 6-siklik adalah:

\frac{1}{10!}\cdot\frac{10!}{6}=1/6.

Dengan cara yang sama, kemungkinan munculnya 7-siklik adalah 1/7, begitu seterunya.

Diperoleh kemunkinan muculnya 6-siklik, 7-siklik, …, atau 10-siklik adalah

\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{10}\approx0,64

Itu berarti kemunkinan muculnya siklik dengan panjang kurang dari 5 adalah 1- 0,64 = 0,36. Inilah kemungkian sukses dengan mengunakan strategi di atas, jika permaianan hanya terdidiri dari 10 napi dan 10 kotak.

Dengan mengunakan argumentasi yang sama maka kemungkinan gagal, jika terdapat 100 napi dan 100 kotak adalah

\frac{1}{51}+\frac{1}{52}+\ldots+\frac{1}{98}+\frac{1}{99}+\frac{1}{100}\approx0,693

Itu berarti kemungkinan suksesnya adalah 0,307.

Referensi: Jamie Mulholland, Puzzle: Prisoners Names in Boxes, 2011

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, teka-teki, Uncategorized and tagged , , , . Bookmark the permalink.

2 Responses to 100 Napi dan 100 Kotak

  1. Restu Palayoga says:

    saya masih belum mengerti di awal. Apabila napi pertama tidak menemukan manya di 5 kota kan langsung kalah ? Apabila napi ke-i sudah membuka kotak sampai ke k (anggap yang ke 50) dan belum menemukan namanya, bagaimana ?

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