Olimpiade Sains Provinsi (OSP) 2010 - Komputer , Nomor 3 - 7
Deskripsi untuk soal nomor 3 - 7
Terdapat N buah lampu b1, b2, …bn dan tombolnya masing-masing di bawah setiap lampu itu. Tombol itu berperilaku aneh, jika tombol suatu lampu bi ditekan sekali, lampu bi berubah dari mati menjadi terang atau dari terang menjadi mati. Selain itu, ada beberapa lampu yang ikut berubah, mati menjadi terang atau terang menjadi mati. Hubungan lampu-lampu lain yang ikut berubah dinyatakan dengan relasi (i, j). Jika relasi (i, j) itu ada, maka penekanan tombol di bi akan berdampak juga pada lampu di bj selain bi itu sendiri, dan sebaliknya, penekanan tombol di bj berdampak juga pada lampu di bi.
Ada 5 buah lampu: b1, b2, b3, b4 ,dan b5, dan terdapat relasi (1, 2), (1, 5), (2, 3), (2, 4), (3, 5), (4, 5). Jika mula-mula seluruh lampu mati, apa yang terjadi dengan b1 dan b2 jika dilakukan penekanan berturut-turut pada tombol-tombol b1, b2, dan b3, dan b5, masing-masing sekali? Jawab dengan memilih:
(A) keduanya mati,
(B) keduanya terang,
(C) b1 terang dan b2 mati, atau
(D) mati dan b2 terang
Jika mula-mula seluruh lampu mati, tuliskan berapa banyak penekanan sesedikit-sedikitnya untuk membuat semua lampu menjadi terang dilakukan?
Jika ditambahkan relasi (2, 4) dengan pertanyaan yang sama dengan no 4, bagaimana jawaban anda sekarang?
Seperti pada pertanyaan no. 5 yaitu adanya relasi tambahan (2, 4), kecuali hanya satu yang terang yaitu b2, tuliskan jumlah penekanan minimal (sesedikit mungkin) untuk membuat semua terang?
Untuk 8 lampu dengan relasi-relasi: (5, 8), (1, 5), (8, 6), (1, 2), (7, 3), ( 8, 3), (6, 7), (2, 6), (7, 5),(5, 4),(4, 2),(3, 4). Semula semua mati, berapa penekanan yang dilakukan sesedikitsedikitnya agar semua lampu menjadi terang?
