In my rephrasing of Otto's solution, I should have mentioned that this method of having everyone meet everyone else is commonly used in English Country line dances, those described by the original source (John Playford, from 1651 on) as "longways for as many as will". ... I don't know of a 17th c. source for the observation that the result is each couple dancing with each other one, but I have no doubt that the observation was made. I'll ask a friend who might know.
In another context, it's more or less equivalent to a famous algorithm for testing whether a linked list is "proper" or whether it has a loop; or, equivalently, for testing whether an iteration is eventually periodic: you have a "tortoise" moving forward on alternate steps and a "hare" moving forward every step. (Or: a "tortoise" moving one step at a time and a "hare" moving two steps at a time.) Its soundness depends on the fact that if there's a cycle then every pair of elements will eventually get checked against one another, which is exactly the property required here. -- g