El relevo de mensajes

**Qué entrena:** difusión óptima de información en red.

Cuatro espías A, B, C y D tienen cada uno un secreto distinto.

En cada llamada telefónica, los dos participantes se cuentan **todo** lo que saben hasta ese momento.

Pregunta 1: ¿cuál es el número mínimo de llamadas para que los cuatro conozcan los cuatro secretos?

Pregunta 2: para $n$ espías (con $n\ge4$), ¿cuál es el mínimo general?

1. Estrategia óptima: A llama a B Rightarrow A y B saben \ a,b\.
2. Con 3 llamadas no se logra que los cuatro acumulen información completa.
3. Respuesta (4 espías): mínimo 4 llamadas.

[Volver al problema](#prob-relevo-mensajes-gossip)

**Respuesta (4 espías):** mínimo **4** llamadas.

Estrategia óptima:

1. A llama a B $\Rightarrow$ A y B saben $\{a,b\}$.
2. C llama a D $\Rightarrow$ C y D saben $\{c,d\}$.
3. A llama a C $\Rightarrow$ A y C saben $\{a,b,c,d\}$.
4. B llama a D $\Rightarrow$ B y D también saben todo.

Con 3 llamadas no se logra que los cuatro acumulen información completa.

**Generalización:** para $n\ge4$, el mínimo es:
$$
2n-4.
$$

---