Feladat: B.3362 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Birkner Tamás 
Füzet: 2000/október, 422 - 423. oldal  PDF  |  MathML 
Témakör(ök): Gráfelmélet, Szöveges feladatok, Feladat
Hivatkozás(ok):Feladatok: 2000/április: B.3362

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Nem megy az általánosság rovására, ha feltesszük, hogy minden időegység (azaz egy e-mail elküldéséhez szükséges időtartam) alatt a 18 gyerek között legfeljebb 1 levél elküldésére kerül sor. A folyamat elején mindenki pontosan 1 megoldást ismer, a végén pedig mindenki 18-at; tekintsük azt a legkorábbi időpontot, amikor van valaki (G), aki mind a 18 megoldást ismeri már. Ehhez G-nek legalább 17 e-mailt kellett kapnia. A többiek legfeljebb 17 feladat megoldását ismerik a vizsgált időpontban, ezért a későbbiek folyamán mindegyikük kap még legalább 1 levelet. Tehát az elküldött üzenetek száma legalább 217=34. Ennyi levél segítségével a teljes információcsere le is bonyolítható: először mindenki elküldi a megoldását G-nek, aki ezután a megoldások teljes listáját elküldi a többieknek.

 Birkner Tamás (Budapest, Fazekas M. Főv. Gyak. Gimn., 7. o.t.)