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

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

Bagaimana Strateginya?

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:

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

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

.

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

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

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

Itu berarti kemungkinan suksesnya adalah 0,307.

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