Problem of the Week 949

Jumping Cards

Start with eight cards in a row, numbered 1 2 3 4 5 6 7 8. Transform the sequence into 8 7 6 5 4 3 2 1 using moves of the following form: you may take any two cards and exchange them provided that, after the exchange, two neighboring cards are within 1, 2, or 3 of each other. Thus at the start switching 1 and 3 is legal, but you could not exchange 1 and 4, because then 1 and 5 would be neighbors.

Source: Jaime Pontachik, in the wonderful new puzzle book, "Puzzlers' Tribute, A Feast for the Mind (David Wolfe and Tom Rodgers, eds., publ. by AK Peters, 2002), a collection of articles from a conference in honor of Martin Gardner.