Olimpiade Sains Provinsi (OSP) 2012 - Komputer, Nomor 16
Pak Dengklek memiliki 80 buah koin emas, semuanya dengan bentuk dan rupa yang sama. Sayangnya, di antara 80 koin tadi, diketahui ada satu koin yang palsu. Pak Dengklek tidak tahu yang mana yang palsu, akan tetapi ia mengetahui bahwa koin yang palsu pasti lebih ringan dari yang asli. Pak Dengklek memiliki sebuah neraca yang bisa ia gunakan untuk membandingkan berat dua buah benda. Pak Dengklek kemudian memilih sebuah strategi yang memastikan banyak penimbangan pada kasus terburuk adalah sesedikit mungkin. Berapakah banyak penimbangan yang Pak Dengklek perlukan pada kasus terburuk apabila ia menggunakan strategi tersebut?
3 jawaban
Reinhart Hermanus11 tahun lalu
TOKI 2011
4
Strategi nya adalah dengan selalu membagi menjadi 3 bagian dan menimbang dua bagian. Apabila tidak seimbang, maka ambil bagian yang lebih ringan. Apabila seimbang, maka ambil bagian yang tidak ditimbang. Lalu ulangi terus sampai tersisa satu batu.
Kasus terburuknya adalah bagian yang kita ambil adalah bagian yang berisi batu paling banyak:
80 -> 27 27 26
27 -> 9 9 9
9 -> 3 3 3
3 -> 1 1 1
Maka kasus terburuknya adalah menimbang sebanyak 4 kali.
Harso Adjie Broto S11 tahun lalu
Siswa SMA Negeri 68 Jakarta
2
tapi ada yang lebih singkat lagi ._. mungkin bisa dipertimbangkan..
80 --> 27 27 26
27 --> 9 9 9
9 --> 3 3 3
3 --> 1 1 1
jawabannya 4 kali
Ardhi Kamal Haq11 tahun lalu
-5
akan menghasilkan minimal 5 kali penimbangan
Masuk untuk menulis jawaban
TOKI 2011
oh iya bener, yang sendiri jangan lebih banyak dari yang berdua berarti. jawaban saya udah diupdate. thanks ya ;)