You enter a laboratory and see 5 insects arranged from left to right in alphabetical order, according to name:

Ant, Bee, Cricket, Dragonfly, Earwig.

By moving two adjacent insects at a time and inserting them elsewhere in the set (still adjacent, no rotations), can you find the fewest number of steps needed to place the insects in reverse alphabetical order? Each time you move an insect, the gap it leaves behind will be closed up.

Examples of legal and illegal moves:

Legal:
ABCDE -> CDABE
ABCDE -> ACDBE

Illegal:
ABCDE -> CBADE (as though the bugs got rotated, which is not allowed)
ABCDE -> CADBE (the bugs you are moving must stay adjacent)
ABCDE -> BDACE (the bugs you are moving must start adjacent)
ABCDE -> BADEC (you get the idea)

Credit for this problem goes to Cliff Pickover

(In reply to 3 another way by eric)

Robert      eric

ABCDE    ABCDE
CDABE    ADEBC
CBEDA    EBADC
EDCBA     EDCBA

notice when placed back to back the solutions have 180 degree rotation symmetry

notice I can't figure out how to get the bold text to turn off after cutting and pasting their solutions

Posted by Jer on 2005-05-06 17:04:22