XXV - I - Zadanie 9

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

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.