Di bulan Mei 2000, Irwan Hadi memberikan tebakan ini di milis pau-mikro@:
Begini.
Ada 12 coin, terus di antara 12 coin itu ada 1 coin palsu. Nah koin palsu itu pas banget bentuknya dengan 11 coin lainnya, dan dilihat dengan mata telanjang tidak ketahuan deh. Tapi … berat koin palsu itu beda dengan 11 coin lainnya, bisa lebih berat ATAU lebih ringan. Nah gimana caranya nemukan coin palsu itu, dengan menggunakan neraca 2 lengan (seperti neracanya tukang emas gitu lho) dengan HANYA 3 kali menimbang. Nah lho ;)
Trus waktu itu aku coba jawab kayak gini:
Saya membuat simulasi dengan bilangan triner (yakni 0, 1, 2). Dengan demikian nomor coin adalah sebagai berikut:
000 002 010 022
110 121 122 111
202 201 210 221
Perhatikan bahwa tidak ada koin dengan nomor kembar. Juga tidak ada koin dengan nomor 1 berkomplemen dengan nomor 2. Jadi, kalau ada 022 tidak akan ada 011. Kalau ada 121, tidak boleh ada 212.
Penimbangan dilakukan tiga kali :
Penimbangan I :
xx1 melawan xx2 (4 vs 4)
Kalau sama, koin palsu pada xx0
Kalau tidak sama, catat yang lebih berat pada 1 atau 2
dalam kasus ini beri nilai p jika 1 lebih berat, q jika 2 lebih berat
Penimbangan II :
x1x melawan x2x (4 vs 4)
Kalau sama, koin palsu pada x0x
Kalau tidak sama, catat yang lebih berat pada 1 atau 2 —> angka q
dalam kasus ini beri nilai p jika 1 lebih berat, q jika 2 lebih berat
Penimbangan III :
1xx melawan 2xx (4 vs 4)
Kalau sama, koin palsu pada 0xx
Kalau tidak sama, catat yang lebih berat pada 1 atau 2 —> angka r
dalam kasus ini beri nilai p jika 1 lebih berat, q jika 2 lebih berat
Penimbangan selesai. Sekarang kalkulasi. Dasarnya, koin palsu selalu lebih berat atau selalu lebih ringan dari koin lain. Tidak mungkin koin palsu sekarang lebih berat dan nanti lebih ringan. Itu gunanya angka p dan q.
Seluruh angka dijumlahkan dengan OR. Bilangan x OR bilangan apa pun menghasilkan bilangan itu. Hasilnya barangkali 000. Inilah yang palsu.
Enak kalau memang dapat koin nomor 000. Probabilitasnya 1/12. Kemungkinan besar sih sih kita dapat koin dengan nomor p dan q.
Kita ingat, koin palsu akan selalu lebih berat atau lebih ringan. Jadi jika nilai p=1, p akan selalu 1 dan q akan selalu 2. Sebaliknya jika nilai p=2, p akan selalu 2 dan q akan selalu 1. Kalau yang palsu koin nomor ppp atau qqq, berarti yang palsu nomor 111 atau 222. Tapi koin nomor 222 nggak ada. Jadi pasti koin nomor 111. Kalau yang palsu koin nomor pq0 atau qp0, berarti yang palsu nomor 120 atau 210. Tapi koin nomor 120 nggak ada. Jadi pasti koin nomor 210.
Dengan demikian, penimbangan 3 kali cukup untuk menentukan manakah koin yang palsu dari 12 koin. Juga, dengan probabilitas 11/12 kita bisa menentukan apakah koin palsu ini lebih berat atau lebih ringan.
Tolong diperiksakan yah.
