Задача 32062
|
|
 |
Условие
В компании из k человек (k > 3) у каждого появилась новость, известная ему одному. За один телефонный разговор двое сообщают друг другу все известные им новости. Докажите, что за 2k – 4 разговора все они могут узнать все новости.Решение
Передача информации может быть осуществлена следующим образом. Рассмотрим некоторых четверых людей в компании — назовем их A, B, C, D. Пусть сначала все члены компании, кроме B, C и D звонят A и сообщают ему свои новости. Это потребует k – 4 звонка. Затем между собой говорят A и B, а также C и D. После этого A говорит с C, а B с D, в результате чего все четверо будут знать все новости. За оставшиеся 2n – 4 звонка A сообщает их всем остальным.
