El relevo de mensajes

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. Con la condicion fijada, verifica mensaj por descarte hasta cerrar una unica solucion coherente.

Volver al problema

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. $$