Bei diesem Problem wird von einer Situation ausgegangen, bei der im Mittelalter zwei feindliche Armeen A und B aufeinander treffen. Dabei soll bei einem Kampf die Regel gelten, dass eine zahlenmäßige Überlegenheit immer zum Sieg führt. Die Armee A soll der Armee B zahlenmäßig überlegen sein. Allerdings hat sie sich in die beiden Teilarmeen A1 und A2 aufgespalten, von denen jede der Armee B zahlenmäßig unterlegen ist.
Die beiden Teilarmeen A1 und A2 haben die Armee B in einer tiefen, von unüberwindbar hohen Bergen umgebenen Schlucht eingeschlossen. Um die Armee B besiegen zu können, müssen die Teilarmeen A1 und A2 gemeinsam angreifen. Aber genau dieses Vorhaben führt zu einem Problem, denn sie können sich nur über einen Nachrichtentransport miteinander verständigen, und die geografische Lage lässt ein Umgehen des Lagers der Armee B nicht zu. Jeder mögliche Weg zwischen dem Lager von A1 und dem von A2 führt durch das von B. Ein Nachrichtenaustausch zwischen den Teilarmeen A1 und A2 ist ein unsicherer Datentransport.
Angenommen, von A1 wird ein Bote mit der Nachricht "Angriff morgen früh 7:00 Uhr" zu A2 geschickt. Dann kann es sein, dass dieser Bote im Lager von B abgefangen wird und A2 gar keine Nachricht erhält. (Der Fall, dass die Armee B den Boten austauscht und der Teilarmee A2 eine falsche Nachricht zukommen lässt, soll nicht behandelt werden.) A2 wird deshalb nicht angreifen. Da A1, nachdem eine bestimmte Zeit lang vergeblich auf eine Bestätigung gewartet wurde, nicht wissen kann, ob die Nachricht angekommen ist, wird auch A1 nicht angreifen.
Angenommen, der Bote kann die Nachricht unbeschadet der Teilarmee A2 überbringen. Und weiter angenommen, A2 schickt einen Boten mit einer Bestätigung des Erhalts der Nachricht zurück, dann kann es geschehen, dass dieser Bestätigungsbote im Lager von B abgefangen wird. Das hat zur Folge, dass A1 keine Bestätigung erhält und deshalb nicht angreifen wird. Da A2 nicht wissen kann, ob die Bestätigung angekommen ist, wird auch A2 nicht angreifen.
Der anscheinend günstigste Fall liegt vor, wenn sowohl die Nachricht mit dem Angriffszeitpunkt als auch die Bestätigung ihre Empfänger erreichen. Aber auch in diesem Fall wird es keinen Angriff geben, denn A2 kann nicht wissen, ob die Bestätigung A1 erreicht hat, und wird deshalb nicht angreifen. Und A1 weiß, dass A2 nicht wissen kann, dass die Bestätigung ihr Ziel erreicht hat, weshalb auch A1 nicht angreifen wird. Das Zwei-Armeen-Problem ist (algorithmisch) unlösbar.