[Pembahasan OSK Informatika Tahun 2006] Jika orang yang pertama saya kirimi SMS adalah G maka siapakah yang akan menerima SMS tersebut paling banyak akhirnya?

Soal     :

           Suatu pesan akan saya distribusikan ke orang-orang bernama A, B, C, D, E, F, G, H, dan I melalui pesan singkat (SMS) secara berantai. Mereka mengetahui bebeapa nomor telp yang lain sbb.

A hanya mengetahui nomor-nomor telp F,G;

B hanya mengetahui nomor-nomor telp C, E, H;

C hanya mengetahui nomor telp A;

D hanya mengetahui nomor-nomor telp E, I;

E hanya mengetahui nomor telp H;

F hanya mengetahui nomor-nomor telp B, E;

H hanya mengetahui nomor-nomor telp I, C;

G hanya mengetahui nomor telp F;

I hanya mengetahui nomor-nomor telp A, B.

Karena teknologi komunikasi masih terbatas maka saat menerima SMS mereka tidak mengetahui siapa dan apa nomor telepon pengirimnya. Diasumsikan bahwa begitu mereka menerima SMS, maka dalam jeda tepat 5 menit SMS akan diteruskan secara serentak ke orang-orang yang mereka ketahui nomor teleponnya dan SMS yang dikirim tersebut langsung diterima tanpa ada jeda. Dipastikan bahwa mereka tidak akan mengirimi SMS yang sama ke orang yang sama lebih dari satu kali.

Jika orang yang pertama saya kirimi SMS adalah G. maka siapakah yang akan menerima SMS tersebut paling banyak akhirnya?

Jawab :

            Ketika saya mengirim SMS ke G

            G akan meneruskan SMS ke F

            F akan meneruskan SMS ke B dan E

            B akan meneruskan SMS ke C,E, dan H

            E akan meneruskan SMS ke H

            C akan meneruskan SMS ke A

            E tidak akan meneruskan SMS ke H (sudah pernah)

            H akan meneruskan SMS ke I dan C

            A akan meneruskan SMS ke F dan G

            I akan meneruskan SMS ke A dan B

            C tidak akan meneruskan SMS ke A (sudah pernah)

            Jadi, dapat disimpulkan bahwa yang menerima SMS terbanyak adalah A,E,F dan G