Maximus is one of 3 or more prisoners of war who have been lined up before the Roman Emperor. The prisoners are numbered from first in the line to last as 1, 2, 3, 4, ..., N. The Emperor orders the execution of the prisoners in the following manner:

1) The first and last are immediately executed.
2) If there are still 2 or more prisoners remaining, the half of the remaining prisoners with the lowest numbers (rounded up) are executed.
3) If there are still 3 or more prisoners remaining, start again from Step 1.

For example, if there were 5 prisoners to start then prisoners 1 and 5 would be executed in Step 2, and prisoners 2 and 3 would be executed in Step 3, leaving prisoner 4 alive.

Is there a strategy by which Maximus can save himself? What if Maximus also wants to save his friend Romulus?

(In reply to Solution by Larry)

Larry's strategy says that if there are 8 prisoners initially, prisoners 5, 6 and 7 are saved, but in the first go-round , first 1 and 8 are killed, then 2, 3 and 4. This leaves 5, 6 and 7 and this is at least three, so we go back to step 1, where 5 and 7 are eliminated, leaving prisoner 6 alone.

Posted by Charlie on 2024-04-20 11:59:02