IMO 1987 LL AUS2

Origin: AUS

Problem

Suppose we have a pack of 2n cards, in the order 1, 2, . . . , 2n. A perfect shuffle of these cards changes the order to n+1, 1, n+2, 2, . . ., n− 1, 2n, n; i.e., the cards originally in the first n positions have been moved to the places 2, 4, . . . , 2n, while the remaining n cards, in their original order, fill the odd positions 1, 3, . . . , 2n −1. Suppose we start with the cards in the above order 1, 2, . . . , 2n and then successively apply perfect shuffles. What conditions on the number n are necessary for the cards eventually to return to their original order? Justify your answer. Remark. This problem is trivial. Alternatively, it may be required to find the least number of shuffles after which the cards will return to the original order.