OLIMPIADE SAINS NASIONAL 2009

Untuk soal 2 sampai 6:
Sebuah perusahaan ingin membagi karyawan‐karyawannya menjadi beberapa tim, dan ingin agar tim‐tim
tersebut dapat bekerja seefektif mungkin. Agar dapat bekerja seefektif mungkin, setiap anggota dalam
sebuah tim harus menyukai anggota lainnya di dalam tim tersebut. Dari antara 8 karyawan yang sudah ada,
A, B, C, D, E, F, G, H, sang manager telah memperhatikan bahwa secara umum setiap karyawan saling
menyukai satu sama lain, kecuali pasangan‐pasangan berikut ini: A dan H, F dan G, C dan E, B dan E, F dan
D, B dan H, F dan B, C dan G, A dan F. Sebuah tim didefinisikan sebagai kumpulan dua atau lebih karyawan.
2. Sang manager harus membagi kedelapan karyawan tersebut minimal ke dalam berapa tim agar
tidak ada dua orang anggota dalam sebuah tim yang tidak menyukai satu sama lain, dan setiap
karyawan menjadi anggota tepat sebuah tim? Tuliskan jawabannya dalam bentuk angka.
3. Dari antara karyawan‐karyawan tersebut, misalkan sang manager ingin memecat satu orang
karyawan, agar banyaknya tim yang dibuatnya berkurang. Sebutkan siapa sajakah yang jika
menjadi seorang karyawan yang dipecat tersebut, tidak dapat mengurangi jumlah tim yang harus
dibuat? Tuliskan jawabannya terurut secara alfabetis, dengan huruf kapital, dipisahkan oleh sebuah
spasi.
4. Sang manager tidak jadi memecat satu orang, tetapi dia ingin memecat dua orang sekaligus agar
tidak ada yang merasa dikucilkan. Namun, kedua orang itu haruslah tidak menyukai satu sama
lain, untuk mengurangi resiko pemberontakan. Pasangan mana sajakah yang, meskipun sudah
dipecat, tetap tidak bisa mengurangi banyaknya tim yang harus dibuat sang manager? Tuliskan
jawabannya terurut secara alfabetis, dengan huruf kapital, dipisahkan oleh sebuah spasi.
5. Jika tiba‐tiba setiap pasang karyawan yang saling menyukai satu sama lain tiba‐tiba membenci satu
sama lain, dan setiap pasang karyawan yang saling tidak menyukai satu sama lain tiba‐tiba
menyukai satu sama lain, sang manager harus mengubah konfigurasi tim. Ada berapa tim paling
sedikit yang harus dibentuk? Tuliskan jawabannya dalam bentuk angka.
6. Dalam tim‐tim baru yang dibentuk ini, siapa sajakah karyawan‐karyawan yang berada di tim yang
sama dengan B? Tuliskan jawabannya terurut secara alfabetis, dengan huruf kapital, dipisahkan
oleh sebuah spasi.

Soal selanjutnya bisa diperoleh di sini!