Question

Каждый из 5 человек знает ровно одну новость, причём все новости различ- ны. Они сообщают по телефону эти новости друг другу, причём когда Х звонит Y, он рассказывает Y все новости, которые он к этому времени знает, но Y при этом звонке ничего не рассказывает Х. Какое наименьшее количество звонков необхо- димо, чтобы все услышали все эти 5 новостей?

Answer 1

1)5×5=25 - (это мы умножили 5 людей и 5 новостей.)

2) 25-5=20 - ( Вычислили 5 новостей)

Ответ: 20 звонков.

Answer 2

Чтобы каждый человек услышал все 5 новостей, им необходимо пройти через все комбинации звонков. Если мы представим каждого человека в виде вершины графа, а звонки между ними в виде ребер, то нам нужно найти наименьшее количество ребер (звонков), чтобы граф стал связным.

Для 5 человек граф будет выглядеть следующим образом:

cssCopy code
 A
/ \

B - C \ / D | E

Для того чтобы граф стал связным, нам необходимо добавить ещё два ребра. Один из способов сделать это - добавить ребро между A и D, и ребро между C и E. Таким образом, наименьшее количество звонков, необходимых, чтобы все услышали все новости, равно 7.

Если представить звонки в виде пар (отправитель, получатель), то последовательность звонков может быть следующей:

1. A -> B
2. B -> C
3. C -> A
4. A -> D
5. D -> B
6. B -> E
7. C -> E

Таким образом, после этих 7 звонков каждый человек услышит все 5 новостей.