Обложка статьи «Помогите сплетникам как можно эффективнее распространить слухи»

Помогите сплетникам как можно эффективнее распространить слухи

Перевод задачи из книги «Algorithmic Puzzles», Anany Levitin, Maria Levitin

n сплетников знают слухи, каждый знает о чём-то своём. Они хотят поделиться друг с другом слухами через сообщения. Тот, кто отправляет сообщение, включает в него все слухи, которые слышал, но сообщение может иметь только одного адресата.

Какое минимальное количество сообщений им понадобится, чтобы каждый узнал все слухи?

Минимальное количество сообщений — 2n — 2.

Почему?

Есть несколько способов решить эту задачу. Например, можно определить одного человека — назовём его Сплетник 1 — которому все остальные отправят свои слухи. После того, как Сплетник 1 узнает все слухи, он запишет их в сообщение, добавит свой слух и разошлёт это сообщение каждому из n — 1 участников.

2n — 2 — минимальное количество сообщений, потому что если увеличить количество участников на 1, потребуется как минимум 2 дополнительных сообщения — к этом сплетнику и от него, что и демонстрирует алгоритм.