The Two Generals

  • Medium
  • Game strategy puzzles
  • Tests: Showing that no finite exchange can create certainty

The puzzle

Two generals on opposite hills must attack at the same hour or both be defeated. They can only communicate by messengers crossing the valley, and any messenger may be captured.

Devise a protocol that guarantees they attack together — or show that none exists.

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Suppose a shortest guaranteed protocol exists. Look at its final message.

Hint 2

Could the sender of that last message have known it arrived?

Show the answer Hide the answer

No protocol exists. Suppose one did, with the fewest messages; its last message cannot have been necessary, which contradicts the assumption.

How to get there

Assume some protocol guarantees a coordinated attack, and take one using the fewest messages. Consider its final message. The sender cannot know whether it arrived, since no acknowledgement follows it.

So the sender must be willing to attack whether or not it arrived - and the receiver, if the protocol works, must act the same way with or without it. That makes the last message unnecessary, giving a shorter protocol that also works. This contradicts the choice of the shortest one.

Therefore no guaranteed protocol exists at all. This is not a puzzle about cleverness but a proof of impossibility, and it is foundational in distributed computing: certainty is unattainable over an unreliable channel, so real systems settle for making failure arbitrarily unlikely - repeated acknowledgements, timeouts, and accepting a small risk rather than eliminating it.

The technique worth keeping

To prove no procedure exists, assume a shortest one and show its last step is removable. The contradiction rules out every procedure at once, which no amount of searching for a clever protocol could do.