Olimpiade Sains Provinsi (OSP) 2012 - Komputer, Nomor 13
Anda memiliki sebuah neraca yang dapat digunakan untuk membandingkan bobot dua obyek dan mengetahui mana yang lebih berat. Jika Anda memiliki 128 benda, berapa kali minimal Anda harus menggunakan neraca tersebut untuk menentukan mana benda terberat DAN benda terberat kedua dari 128 benda tadi?
3 jawaban
Reinhart Hermanus11 tahun lalu
TOKI 2011
8
Untuk mencari yang terberat, kita bisa menggunakan kompetisi dengan sistem gugur (final, semi final, 8 besar, 16 besar, dst). Banyaknya penggunaan neraca untuk mengetahui yang terberat adalah 64 + 32 + 16 + 8 + 4 + 2 + 1 = 127 kali.
Setelah mengetahu mana yang terberat dengan sistem kompetisi tadi, kita dapat memastikan bahwa yang terberat kedua pasti "dikalahkan" oleh benda yang terberat (karena tidak ada benda lain yang bisa "mengalahkan" dia selain benda terberat). Jadi kita tidak perlu melakukan kompetisi ulang dengan melibatkan semua benda lain, kita cukup melakukan kompetisi ulang dengan melibatkan hanya benda yang "dikalahkan" oleh benda terberat (7 benda).
Banyaknya penggunaan neraca untuk mengetahu benda terberat dari 7 benda adalah 6 kali. Berarti total penggunaan neraca adalah 127 + 6 = 133 kali.
Reinhart Hermanus11 tahun lalu
TOKI 2011
Kalau dia secara kebetulan ditimbang sama yang terberat pertama di pertandingan pertama, jadi langsung gugur kan? Padahal dia terberat kedua. Kenapa 7 benda, karena di sistem turnamen nya ada 7 level (2 besar, 4 besar, dst sampai 128 besar). Jadi total si terberat pertama mengalahkan 7 benda, maka 7 benda itu lah yang harus ditandingkan kembali.
P satvikka11 tahun lalu
ini bener banget caranya :D
Masuk untuk menulis jawaban
Bukankah kalau kita gunakan sistem gugur tersebut maka benda terberat yang kedua pastilah yang kalah pada pertimbangan terakhir? Sehingga tidak perlu lagi menimbang ulang 7 benda tersebut, juga kenapa 7 benda?