Friendly Robot Overlord

There are two armies on either side of an enemy city. They can't see each other. They can only communicate by sending messengers to each other. When they send a messenger, they might get captured. If both armies attack at the same time, then they will win. If only one army attacks, then they will both lose. All of the information in this question is known to both sides. What should the General commanding each army do?

This is the Two Generals' Problem which I've rephrased slightly to make it quicker to explain, and also to introduce a loophole so you can actually get a solution. I'm not being particularly formal about this, mainly because it makes it easier for me to handwave over the details that I'm trying to handwave over, but also because it is slightly more pleasant to read.

Why it is impossible

Suppose that there is a strategy which lets them agree on the plan. Then, there must also be some sequence of events that happen which mean that they can agree by sending the fewest number of messengers. What if, the very last messenger that was sent was captured? According to our assumption, there is still an agreement so that is fine. But in that case, the strategy could be simplified by not bothering to send that last messenger. Once you do that, you have a contradiction, because we were going for the fewest number of messengers - but we just found a strategy that sends one less messenger.

Why it is possible

The correct strategy is to just attack immediately and not send any messengers. Each General should realise that sending messages will result the problem mentioned above and they will never be able to attack. But, if no messengers are sent, then the proof breaks, as there is no 'last messenger' to capture. Each General should know that the other General is infinitely smart and perfectly rational, so they can know that the other General will realise that the only way they can win is to not send any messengers.

Sneaky Tricks

So in my rephrasing, I gave the Generals a bit more knowledge - they both knew that they were making their decision at the same time. The fact that they are both making the same decision at the same time was difficult to put into the wording without making it obvious that this was the trick I was doing - I tried to do it by not mentioning time at all, and presenting all the facts in the same tense, so there is some concept of a base reference of time.

So there you have it. If you word the problem poorly enough, you can solve it.