[Solution] War General and Prisoners (exploding island version)

Problem statement here.

This is one of those puzzles which looks impossible at first, but we can actually guarantee everyone can be freed!

Assume the prisoners are numbered $1, \dots, n$. The assigned numbers (which are distinct) results in a permutation of $1, \dots, n$ when they are sorted by the assigned numbers. Call this permutation $A$ ( $A$ for actual).

Now each prisoner $i$, assumes that they were assigned the least number, resulting in a permutation guess $G_i$ ($G$ for guess).

Now if prisoner $i$ was in the $k^{th}$ position in the actual sorted order, then we can get from $A$ to $G_i$ by doing exactly $k-1$ transpositions/swaps (bubble sort them to the smallest position) and thus we have that

$$\text{parity } G_i = \text{parity } A + (k-1 \mod 2)$$

Parity of a permutation is the parity of the number of transpositions required to convert it to the identity permutation and can be shown to be always even or odd (hence called parity).

Then the strategy is as follows:

If $\text{parity } G_i$ is $1$, then the prisoner $i$ chooses island $A$. They choose $B$ otherwise.

Since they get sorted into islands according to the parity of their position in the sorted order, they can guarantee everyone escapes.