Olimpiade Sains Provinsi (OSP) 2013 - Komputer, Nomor 10
Besok, Raja Dengklek akan mengadakan pesta yang sangat besar. Raja Dengklek telah memesan 2013 botol anggur untuk pestanya tersebut. Namun berdasarkan laporan, salah satu dari botol anggur tersebut telah diberi racun. Racun ini diketahui tidak akan menunjukkan tanda-tanda keracunan sampai orang yang meminumnya mati. Kematian terjadi antara 13-20 jam setelah racun terminum, walaupun hanya terminum setetes. Raja Dengklek memiliki 2013 orang tahanan yang rencananya akan dieksekusi. Raja Dengklek harus berhasil menemukan botol anggur yang mengandung racun tersebut dalam waktu 24 jam. Berapa minimal banyaknya tahanan yang harus minum dari botol-botol anggur yang ada untuk memastikan botol mana yang mengandung racun?
7 jawaban
Reinhart Hermanus11 tahun lalu
TOKI 2011
14
Poin-poin penting tentang soal ini adalah:
-
Satu orang tahanan bisa minum beberapa tetes dari beberapa anggur sekaligus dalam satu waktu.
- Semua orang tahanan yang disuruh minum harus minum secara serentak karena tidak akan sempat menunggu tahanan mati terlebih dahulu.
Jadi inti dari soal ini adalah kita ingin mencari konfigurasi sedemikian sehingga dari beberapa orang yang mati dan beberapa orang yang hidup, dapat dianalisa anggur mana yang mengandung racun.
Solusi yang optimal adalah sebagai berikut:
1 orang minum anggur sepanjang interval 210 secara bergantian (minum anggur nomor 1 sampai 210, jangan minum anggur nomor 210 + 1 sampai 2013). Jika dia mati, berarti anggur beracun ada di interval dia. Jika tidak, ada di interval lainnya..
1 orang lain minum anggur sepanjang interval 29 secara bergantian (minum anggur nomor 1 sampai 29, minum lagi anggur nomor 210 + 1 sampai 210 + 29 dan seterusnya). Jika tidak, ada di interval lainnya.
1 orang lain minum anggur sepanjang interval 28 secara bergantian.
dan seterusnya sampai interval 20 secara bergantian. Jika diperhatikan, konfigurasi cara meminum membentuk biner. Total diperlukan 11 orang.
Ilustrasi 1 (warna yang sama melambangkan orang yang sama):
Ilustrasi 2 (anggap hanya ada 8 botol):
Untuk 8 botol kita hanya memerlukan 3 orang. Mari kita coba semua kemungkinan, dengan 0 berarti mati, 1 berarti hidup. Contoh: 101 berarti orang pertama dan ketiga hidup, orang kedua mati.
000: botol 1 beracun
001: botol 2 beracun
010: botol 3 beracun
011: botol 4 beracun
100: botol 5 beracun
101: botol 6 beracun
110: botol 7 beracun
111: botol 8 beracun
TBD TBD11 tahun lalu
mohon balasannya y kak.. thankz.. :)
Reinhart Hermanus11 tahun lalu
TOKI 2011
Sudah saya tambahkan ilustrasi untuk memperjelas. Semoga membantu :)
TBD TBD11 tahun lalu
ok kak.. makasih kak.. penjelasan binernya membantu x.. >.<
Abdul Haris7 tahun lalu
Bantu penjelasan yg untuk 3 orang dengan 8 botol, kira2 seperti ini. Anggap ada 3 orang (A, B, C) dan nomor adalah nomor botol minum :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| A | A | A | A | ||||
| B | B | B | B | ||||
| C | C | C | C |
si A minum sebanyak interval 22 , si B minum sebanyak 21 dan si C minum sebanyak interval 20
MAN 2 Kudus7 tahun lalu
itu dapat interval 2^10 darimana? #jawab
Masuk untuk menulis jawaban
kak,saya msh bingung kak.. bgmn kalau yg beracun it ad diinterval orng pertama?bgmn kita bs tahu dr interval it mana yg beracun??klo dikurangi interval2 lainnya kan jg blom tentu dapet tepat botol yg beracun kak?