El problema de los dos ejércitos y colorear un mapa

1.-Este problema quizá no tiene tanta relación con la matemática y está más vinculado a las ciencias de la telecomunicación, no obstante es un problema para pensar.
Imagínese dos ejércitos que se encuentran en un valle de tal forma: el ejército A se divide en dos, es decir, uno está en una montaña(1A) y el otro en otra montaña (2A), quedando entre ambos un ejército B. Existe el siguiente problema: 1A y 2A sólamente pueden comunicarse entre sí mediante un mensajero, del que no se tiene la certeza de que pudiese comunicarse con la otra parte, es decir, si 1A desease comunicarse con 2A, no podría tener la certeza de que el mensaje les llegase ya que el ejército B podría matarlo. Lo que ocurre es que el ejército 1A desearía atacar al amanecer y se precisa de un protocolo que permita que esta información le llegue a 2A. ¿Existe dicho protocolo?

NOTA: 1A no podría atacar sólo contra B pues perdería la batalla.

2.-¿Cuántos colores serían necesarios para colorear el mapa de Andalucía de la fotografía para que cada provincia tenga a su lado provincias de distinto color es decir, que ninguna provincia tenga otra a su lado del mismo color?