[Pembahasan OSK Informatika Tahun 2006] Jika orang pertama yang saya kirimi SMS adalah A maka berapa menit lagi A akan menerima SMS dari I?

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 pertama yang saya kirimi SMS adalah A maka berapa menit lagi A akan menerima SMS dari I?

Jawab :

            A akan meneruskan SMS ke F dan G             (5 Menit)

            F akan meneruskan SMS ke B dan E              (10 Menit)

            G akan meneruskan SMS ke F                        (10 Menit)

            B akan meneruskan SMS ke C,E dan H         (15 Menit)

            E akan meneruskan SMS ke H                       (15 Menit)

            C akan meneruskan SMS ke A                       (20 Menit)

            H akan meneruskan SMS ke I dan C              (20 Menit)

            I akan meneruskan SMS ke A dan B              (25 Menit)

            Jadi A akan menerima SMS dari I setelah 25 menit lagi