Olimpiade Sains Kota (OSK) 2011 - Komputer, Nomor 17
Pada sebuah kantong terdapat 2 buah kelereng kuning, 5 buah kelereng biru, dan 8 buah kelereng hitam. Berapa minimal banyaknya kelereng yang perlu diambil agar kita pasti mendapatkan setidaknya 5 kelereng bewarna sama?
a. 10
b. 11
c. 9
d. 13
e. 12
3 jawaban
Noya Aldiputera8 tahun lalu
Jika ingin mendownvote, jangan lupa juga untuk komen tentang kesalahannya. That'll be helpful for everyone, don't let that be a habit.
2
Pada permasalahan ini, akan diterapkan Pigeonhole Principle. Terlebih dahulu untuk meninjau kasus-kasus pengambilan kelereng.
Saat di kasus kita mengambil 5 kelereng, akan ada probabilitas pengambilan kelereng terburuk menjadi A A B B C dengan A, B dan C adalah warna kelereng yang berbeda dan belum diketahui. Perhatikan jika kita mengambil 7 kelereng (dari penjumlahan kelereng kuning dan biru), akan terdapat probabilitas dimana semua kelereng kuning dan biru terambil tetapi jika kurang dari 5 kelereng hitam terambil maka tidak akan ditentukan bahwa kita akan mendapatkan 5 warna yang sama.
Misalkan A adalah kelereng kuning, B adalah kelereng biru, dan C adalah kelereng hitam. Pada kasus terburuk pengambilan 10 kelereng, terdapat A A B C B C B C B C sebagai probabilitas terburuk (kelereng A tidak akan pernah mencapai 5 sehingga dimasukkan sebagai kasus terburuk). Dengan menerapkan Pigeonhole Principle, jika kita mengambil 1 kelereng lagi dari kasus terburuk 10 kelereng maka 1 kelereng tersebut pasti akan berkorespondesi terhadap salah satu dari warna B atau C, yang dimana salah satu dari warna kelereng mempunyai 5 kelereng dengan warna yang sama.
Kita peroleh bahwa 11 adalah angka yang minimum untuk dapat memastikan akan mengambil 5 kelereng dengan warna yang sama.
Masuk untuk menulis jawaban