Qm
BrainteasersJane Street

The two generals who cannot agree

Two generals command armies on opposite sides of a city. They win only if both attack at the same time; an attack by one alone is a disaster. They can communicate only by messengers who must pass through the city and may be captured, in which case the message never arrives, and the sender does not know whether it arrived.

General A sends "attack at dawn". If the messenger gets through, B knows the plan, but A does not know that B knows, so B sends a confirmation; but B does not know whether the confirmation arrived, so A sends an acknowledgement; and so on.

Prove that no finite sequence of messages can guarantee that both generals attack.

Show a hint

Suppose some protocol works and always ends with both attacking. Look at the very last message that is sent. Could it have been captured without changing what the generals do?

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Related questions

Two opposite points with the same temperatureChameleons changing colorsFour pieces of a clock face with equal sums?A closed knight's tour on a five-by-five boardFifty-three bricks in a six-by-six-by-six box
All questions →