XXV - I - Zadanie 9

Zbiór dokumentów rozdzielono na $ n $ części dając je do przechowania $ n $ osobom, z których każda posiada telefon. Dowieść, że dla $ n \geq 4 $ wystarczy $ 2n - 4 $ rozmów telefonicznych, aby po ich przeprowadzeniu każda z $ n $ osób znała treść wszystkich dokumentów.

Rozwiązanie

Dla czterech osób $ A $, $ B $, $ C $, $ D $ wystarczą cztery rozmowy. Mianowicie, najpierw $ A $ i $ B $ oraz $ C $ i $ D $ informują się nawzajem o posiadanych przez siebie dokumentach. Następnie $ A $ i $ C $ oraz $ B $ i $ D $ wymieniają między sobą posiadane informacje.

Jeżeli liczba osób $ n $ przekracza $ 4 $, to ustalamy pewne $ 4 $ osoby $ A $, $ B $, $ C $, $ D $. Najpierw każda z pozostałych $ n - 4 $ osób informuje $ A $ o treści posiadanych przez siebie dokumentów. Potem osoby $ A $, $ B $, $ C $, $ D $ przeprowadzają między sobą $ 4 $ rozmowy (jak wyżej) i wymieniają posiadane przez siebie informacje. Wreszcie każda z pozostałych $ n - 4 $ osób dzwoni do $ A $ i dowiaduje się od niej o treści wszystkich dokumentów.

Zostały przeprowadzone $ (n - 4) + 4 + (n - 4) = 2n - 4 $ rozmowy i każda z osób zna treść wszystkich dokumentów.

Komentarze

Dodaj nową odpowiedź